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