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> из приоритетной очереди.
