3622
правки
Изменения
→Алгоритм с изпользованием SLAV
Теперь реализуем этот алгоритм более эффективно. Для этого мы будем использовать специальную структуру данных {{---}} <tex> \mathrm{SLAV}</tex> (set of circular lists of active vertices). Эта структура хранит цикл всех вершин для внешней грани, а так же цикл для каждой дыры многоугольника и для всех многоугольников, возникающих в процессе построения <tex> S(P) </tex>. В данном случае у нас будет просто <tex> \mathrm{LAV}</tex> {{---}} [[Список#Циклический список | циклический список]] всех вершин многоугольника.
==== Эффективный алгоритм Алгоритм для выпуклых полигонов ====
Далее считаем, что полигон представлен рёбрами вдоль движения по контуру полигона против часовой стрелки.
Заметим, что нам не нужно пересчитывать все расстояния в очереди приоритетов. Если мы стянем полигон до первого события исчезания ребра, то относительный порядок остальных событий не изменится. Нам необходимо только вставить новые точки пересечения в правильные места. Это можно эффективно сделать, если использовать структуру данных типа [[Список с пропусками | skip list]].
В этом случае асимптотика алгоритма составляет <tex> \mathcal{O}(n \log n)</tex>, так как на каждой итерации цикла нам нужно положить константное число элементов в очередь, а итераций цикла не больше <tex> n </tex>.
==== Частные случаи ====
Частным случаем в алгоритме может быть совпадение нескольких <tex> edge\ event'</tex>ов в одной точке. Эти совпадения добавляются в шагах <tex> 1c </tex> и <tex> 2f </tex>, но могут быть относительно легко обработаны в шаге <tex> 2b </tex>. Также может случиться, что какие-то рёбра не стянулись в итоге в одну вершину, а слились. Такое возможно, если какие-то стороны полигона были изначально параллельны (этот случай легко увидеть на прямоугольнике, не являющемся квадратом). С этим частным случаем можно разобраться в шаге <tex> 2c </tex>, проверив, не совпала ли одна из трёх вершин с другой. В выпуклом многоугольнике слияние двух рёбер может произойти только один раз (что неправда для невыпуклого многоугольника), поэтому здесь несложно разобраться с таким случаем.
=== Невыпуклый полигон ===
Основной принцип для невыпуклых полигонов такой же. Только с вершиной ещё хранится дополнительный атрибут, обозначающий событие, которое в ней произошло: <tex> edge\ event</tex> или <tex> split\ event</tex>.
[[Файл:skeleton_split_event_example.png|400px]]
Наличие невыпуклой вершины может привести (а может и не привести) к разделению внутренней области. Невыпуклая вершина может так же участвовать в обычном <tex> edge\ event'</tex>е (точка <tex> A </tex> на рисунке выше). В таком случае <tex> edge\ event'</tex>ы обрабатываются так же, как и в алгоритме с выпуклым многоугольником.
Посмотрим теперь, что делать с точкой <tex> B </tex>, в которой возникает <tex> split\ event</tex>.
==== Нахождение координат точки B ====
[[Файл:skeleton_b_point_coord.png|500px]]
==== Работа с LAV в момент возникновения split event'a ====
==== Частный случай множественных split event'ов на одном ребре ====
[[Файл:skeleton_lav_managing.png|400px]]
==== Алгоритм для невыпуклых полигонов ====
=== Ещё примеры ===
[[Файл:Skeleton_example1.png|500px]]
[[Файл:skeleton_hole_example.png|500px]]
== Алгоритм построения с помощью Motorcycle graph ==
