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