3622
правки
Изменения
→Эффективный алгоритм
:<tex>(a)</tex> Поместим все вершины многоугольника <tex> V_1, V_2 \dots V_n </tex> в двусвязный циклический список в порядке обхода вдоль контура. Все вершины в <tex> \mathrm{LAV}</tex> считаются активными сейчас.
:<tex>(b)</tex> Для каждой вершины <tex> V_i </tex> в <tex> \mathrm{LAV}</tex> добавим указатели на инцидентные рёбра <tex> e_{i-1} = V_{i-1}V_i</tex> и <tex> e_i = V_i V_{i+1}</tex>, а также найдём луч биссектрисы <tex> b_i </tex>.
:<tex>(c)</tex> Для каждой вершины <tex> V_i </tex> найдём ближайшее пересечение биссектрисы <tex> b_i </tex> с лучами <tex> b_{i-1} </tex> и <tex> b_{i+1} </tex>. Если это пересечение существует, то положим его в [[Двоичная куча | приоритетную очередь]] согласно <tex> L(e_i) </tex> {{---}} расстоянию от точки пересечения до одного из рёбер, инцидентных вершине <tex> V_i </tex>. Для каждой точки пересечения <tex> I_i </tex> будем так же хранить два указателя на вершины <tex> V_a </tex> и <tex> V_b </tex> {{---}} начала лучей биссектрис, которые пересекаются в точке <tex> I_i </tex>. Эти указатели понадобятся в будущем, когда нужно будет определять соответствующие вершинам рёбра <tex> e_a, e_b </tex> (см. рисунок ниже).
'''Шаг 2.''' Следующие действия выполняются в цикле, пока приоритетная очередь не пустая:
:<tex>(a)</tex> Извлечём точку пересечения <tex> I </tex> из приоритетной очереди.
[[Файл:skeleton_convex_example.png|600px]]
Заметим, что нам не нужно пересчитывать все расстояния в очереди приоритетов. Если мы стянем полигон до первого события исчезания ребра, то относительный порядок остальных событий не изменится. Нам необходимо только вставить новые точки пересечения в правильные места. Это можно эффективно сделать, если использовать структуру данных типа [[Список с пропусками | skip list]].
=== Невыпуклый полигон ===
