3622
правки
Изменения
→Алгоритм для невыпуклых полигонов
::* найдём точки пересечения лучей с биссектрисами соседних вершин как в шаге <tex> 1c </tex> (тут могут получиться точки пересечения обоих типов),
::* сохраним ближайшие точки пересечения в приоритетной очереди.
Обработка событий обоих типов выполняется с такой же асимптотикой, что и в алгоритме для выпуклых полигонов. Основной вклад в асимптотику вносит вычисление <tex> split\ event'</tex>ов, когда нам нужно пробежаться по всем рёбрам и найти противолежащее. Отсюда и получается итоговая асимптотика <tex> \mathcal{O}(n^2) </tex>.
==== Случай полигонов с дырами ====
Данный алгоритм может работать и с многоугольниками, содержащими дыры, если они ориентированы по часовой стрелки, чтобы внутренняя область многоугольника лежала слева от рёбер. И в самом начале алгоритма каждый замкнутый контур помещается в свой <tex> \mathrm{LAV} </tex> в множестве <tex> \mathrm{SLAV} </tex>.
