3622
правки
Изменения
м
→Выпуклый полигон
=== Выпуклый полигон ===
В случае выпуклого многоугольника возникают только <tex> edge\ event'</tex>ы по определению. Объяснить алгоритм можно простым образом: найдём точки пересечения биссектрис многоугольника для каждой вершины со всеми соседними вершинами, возьмём такую точку, в которой произойдёт самый первый <tex> edge\ event</tex>, добавим полученную вершину в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>, соеденим соединим её с вершинами ребра, которое исчезло в процессе текущего <tex> edge\ event'</tex>а, а потом перестроим полигон, создав новую вершину и подвинув все остальные вдоль биссектрис на одинаковое расстояние. Будем продолжать этот процесс до тех пор, пока многоугольник не превратится в треугольник.
Теперь реализуем этот алгоритм более эффективно. Для этого мы будем использовать специальную структуру данных {{---}} <tex> \mathrm{SLAV}</tex> (set of circular lists of active vertices). Эта структура хранит цикл всех вершин для внешней грани, а так же цикл для каждой дырки многоугольника и для всех многоугольников, возникающих в процессе построения <tex> S(P) </tex>. В данном случае у нас будет просто <tex> \mathrm{LAV}</tex> {{---}} [[Список#Циклический список | циклический список]] всех вершин многоугольника.
Также может случиться, что какие-то рёбра не стянулись в итоге в одну вершину, а слились. Такое возможно, если какие-то стороны полигона были изначально параллельны (этот случай легко увидеть на прямоугольнике, не являющемся квадратом). С этим частным случаем можно разобраться в шаге <tex> 2c </tex>, проверив, не совпала ли одна из трёх вершин с другой. В выпуклом многоугольнике слияние двух рёбер может произойти только один раз (что неправда для невыпуклого многоугольника), поэтому здесь несложно разобраться с таким случаем.
=== Невыпуклый полигон ===
Основной принцип для невыпуклых полигонов такой же. Только с вершиной ещё хранится дополнительный атрибут, обозначающий событие, которое в ней произошло: <tex> edge\ event</tex> или <tex> split\ event</tex>.
