3622
правки
Изменения
→Алгоритм для невыпуклых полигонов
'''Шаг 2.''' Пока очередь не пуста:
:<tex>(a)</tex> Извлечём точку пересечения <tex> I </tex> из приоритетной очереди. Если она имеет тип <tex> edge\ event</tex>, то её надо обработать так же, как в шагах <tex> 2b-2f</tex> алгоритма для выпуклых полигонов. Иначе выполнять шаги ниже.
:<tex>(b)</tex> Если точка пересечения указывает на уже обработанные вершины, то продолжить со следующей итерации цикла шага 2, как в случае с выпуклым полигоном. По этой причине мы не будем обрабатывать лишние <tex> split\ event'</tex>ы, хотя в очередь вполне могли их добавить.
:<tex>(c)</tex> Нужно сделать примерно то же самое, что и шаге <tex>2c</tex> алгоритма для выпуклых многоугольников. Только на этом цикл не завершается, а продолжается с новой итерации, так как многоугольник мог разделиться на несколько частей, и, возможно, мы обработали лишь один подпалигон и не последний.
:<tex>(d)</tex> Добавим в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> ребро <tex> IV </tex>, где точка <tex> I </tex> указывает на вершину <tex> V </tex>. Для <tex> split\ event'</tex>ов точки пересечения указывают ровно на одну вершину в <tex> \mathrm{SLAV}</tex>.
::* Добавим указатели вершинам <tex> V_1 </tex> и <tex> V_2 </tex> на соответствующие рёбра.
:<tex>(f)</tex> Для обеих вершин <tex> V_1 </tex> и <tex> V_2 </tex>:
::* найдём биссектрисы между рёбрами, на которые эти вершины слинковались указывают в шаге <tex>2e</tex>,::* найдём точки все события точек пересечения лучей с биссектрисами соседних вершин как в шаге <tex> 1c </tex> (тут могут получиться точки пересечения события обоих типов),::* сохраним ближайшие точки пересечения , отвечающие найденным событиям, в приоритетной очереди.
Обработка событий обоих типов <tex> edge\ event'</tex>ов выполняется с такой же асимптотикой, что и в алгоритме для выпуклых полигонов. Основной вклад Но из-за того, что в очередь кладутся всевозможные точки свершения <tex> split\ event'</tex>ов, в ней может оказаться <tex>\mathcal{O}(n^2)</tex> элементов. Хотя обработка <tex> split\ event'</tex>а может занять линейное время от числа вершин (если новая вершина в асимптотику вносит вычисление точке пересечения осталась невыпуклой), это произойдёт только для <tex> split\ event'</tex>ов, когда нам нужно пробежаться которые создают новые вершины <tex> S(P) </tex>, а их <tex>\mathcal{O}(n)</tex> по всем рёбрам и найти противолежащеедоказанной [[#lemma1 | лемме]]. Отсюда и получается Остальные <tex> split\ event'</tex>ы обработаются за <tex>\mathcal{O}(1)</tex> в шаге <tex> 2b </tex>, поэтому итоговая асимптотика составит <tex> \mathcal{O}(n^2\log n) </tex>.
==== Случай полигонов с дырками ====
