Изменения

Перейти к: навигация, поиск

Пересечение многоугольников (PSLG overlaying)

468 байт добавлено, 16:54, 17 мая 2015
Нет описания правки
|proof=Копирование двух РСДС в один занимает <tex>O(n)</tex> времени, заметающая прямая работает <tex>O(n \log{n} + k \log{n})</tex> времени по лемме. Создание граней работает линейное время от сложности <tex>O(S_1, S_2)</tex>. Маркировка граней РСДС работает за <tex>O(n \log{n} + k \log{n})</tex>.
}}
 
== См.также ==
*[[ППЛГ и РСДС (PSLG и DCEL): определение, построение РСДС множества прямых]]
*[[Пересечение множества отрезков]]
 
== Источники ==
* de Berg, Cheong, van Kreveld, Overmars. Computational Geometry, Algorithms and Applicants, 2008. pp. 33-39
 
[[Категория: Вычислительная геометрия]]
[[Категория: ППЛГ и РСДС]]
113
правок

Навигация