3622
правки
Изменения
→Алгоритм с изпользованием SLAV
::* сохраним ближайшие точки пересечения в приоритетной очереди.
Заметим, что нам не нужно пересчитывать все расстояния в очереди приоритетов. Если мы стянем полигон до первого события исчезания ребра, то относительный порядок остальных событий не изменится. Нам необходимо только вставить новые точки пересечения в правильные места. Это можно эффективно сделать, если использовать структуру данных типа [[Список с пропусками | skip list]].
Частным случаем в алгоритме может быть совпадение нескольких <tex> edge\ event'</tex>ов в одной точке. Эти совпадения добавляются в шагах <tex> 1c </tex> и <tex> 2f </tex>, но могут быть относительно легко обработаны в шаге <tex> 2b </tex>. Также может случиться, что какие-то рёбра не стянулись в итоге в одну вершину, а слились. Такое возможно, если какие-то стороны полигона были изначально параллельны (этот случай легко увидеть на прямоугольнике, не являющемся квадратом). {{TODO | t = И что делать?(}}
=== Невыпуклый полигон ===
=== Невыпуклый полигон с дырами ===
