3622
правки
Изменения
м
→Алгоритм для невыпуклых полигонов
:<tex>(a)</tex> Положим все вершины в <tex> \mathrm{LAV}</tex>, как это делается в алгоритме для выпуклых многоугольников, а потом <tex> \mathrm{LAV}</tex> поместим в <tex> \mathrm{SLAV}</tex>.
:<tex>(b)</tex> Найдём биссектрисы как в случае с выпуклым многоугольником.
:<tex>(c)</tex> Для каждой биссектрисы выпуклой вершины найдём ближайшую точку пересечения с биссектрисой соседней вершины, а для невыпуклых вершин найдём также точки пересечения с противолежащими рёбрами (как это описывалось раньше), и положим в приоритетную очередь ближайшую точку пересечения <tex> I </tex>. Будем также с этой точкой хранить её тип {{---}} <tex> edge\ event</tex> или <tex> split\ event</tex>.
'''Шаг 2.''' Пока очередь не пуста:
:<tex>(a)</tex> Извлечём точку пересечения <tex> I </tex> из приоритетной очереди. Если она имеет тип <tex> edge\ event</tex>, то её надо обработать так же, как в шагах <tex> 2b-2f</tex> алгоритма для выпуклых полигонов. Иначе выполнять шаги ниже.
