Изменения

В случае выпуклого многоугольника возникают только <tex> edge\ event'</tex>ы по определению. Поэтому просто Объяснить алгоритм можно описать следующим простым образом: найдём точки пересечения биссектрис многоугольника для каждой вершины со всеми соседними вершинами, возьмём такую точку, в которой произойдёт самый первый <tex> edge\ event</tex>, добавим полученную вершину в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex>, соеденим её с вершинами ребра, которое исчезло в процессе текущего <tex> edge\ event'</tex>а, а потом перестроим полигон, создав новую вершину и подвинув все остальные вдоль биссектрис на одинаковое расстояние. Будем продолжать этот процесс до тех пор, пока многоугольник не превратится в треугольник.

В таком списке частично найденного <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> вершины имеют указатели на следующую и предыдущую вершину в порядке обхода контура, а так же указатели на инцидентные рёбра. Если представить процесс стягивания многоугольника, как будто у нас уже построена для него крыша, а мы двигаем вверх некоторую заметающую плоскость, где пересечение крыши и плоскости будет обозначать текущий слой, то можно заметить, что область полигона разбивается на несколько частей. Каждой части будет соответствовать свой <tex> \mathrm{LAV}</tex>, отсюда нам и нужен <tex> \mathrm{SLAV}</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> (см. рисунок ниже).

:<tex>(b)</tex> Если вершины <tex> V_a </tex> и <tex> V_b </tex>, соответствующие данной точке пересечения помечены как обработанные, то переходим к следующей итерации цикла шага 2. Это означает, что ребро между данными вершинами полностью стянулось (обработанные вершины и стянутые рёбра помечены крестом на рисунке ниже). Эту проверку необходимо делать из-за того, что мы могли поместить обработанные вершины в момент получения новых <tex>event'</tex>ов.

::* точки пересечения луча биссектрисы <tex>b </tex> с соседями биссектрисами вершин, соседними к <tex> V </tex> в <tex> \mathrm{LAV}</tex>, как в шаге <tex> 1c </tex>,::* сохраним ближайшие точки пересечения в приоритетной очереди. Точку пересечения кладём с расстоянием до стянутого ребра <tex> L(e_i) </tex>.

Частным случаем в алгоритме может быть совпадение нескольких <tex> edge\ event'</tex>ов в одной точке. Эти совпадения добавляются в шагах <tex> 1c </tex> и <tex> 2f </tex>, так как точки пересечения добавляются только в них, но могут быть относительно легко обработаны в шаге <tex> 2b </tex>. Или мы можем считать, что между <tex> edge\ event'</tex>ами в одной точке будут рёбра нулевого веса в полученном <tex> S(P) </tex>, а затем можно просто избавиться от лишних вершин в итоговом результате.

В простейшем случае точка <tex> B </tex> появляется, когда "волновой фронт" распространения движения рёбер от невыпуклой вершины натыкается на встречный фронт противолежащего ребра. В такой момент возникает <tex> split\ event</tex>. Поэтому точка <tex> B </tex> может быть изначально охарактеризована, как точка, находящаяся на одном расстоянии от противолежащего угла ребра и прямых, содержащих рёбра невыпуклой вершины. Задача состоит в том, чтобы найти это самое противолежащее ребро (случай <tex> a) </tex> на рисунке выше). Но как показывает случай <tex> b) </tex>, простой тест на пересечение ребра и биссектрисы невыпуклой вершины не может быть использован (в этом случае луч биссектрисы пересекает сразу два ребра, непонятно, с каким из них произойдёт <tex> split\ event</tex>). Поэтому необходимо ещё проверять, что точка <tex> B </tex> лежит между лучами <tex> b_i </tex> и <tex> b_{i+1} </tex>, идущих из вершин, инцидентных противолежащему ребру <tex> e_i </tex>.

Когда происходит работа с точкой <tex> B\ split\ event'</tex>а, то необходимо разбить соответствующий полигон на две части, что соответствует разделению <tex> \mathrm{LAV} </tex> данного полигона на два списка. И в каждый новый список нужно вставить новую вершину копию вершины <tex> X V </tex>, образующуюся образующейся в точке пересечения <tex> B </tex>. Обе вершины <tex> X V_1 </tex> и <tex> V_2 </tex> указывают на разделяющее ребро <tex> e_i </tex> (см. рисунок выше).

Уже должно было стать понятно, что алгоритм не строит промежуточного представления <tex> \mathrm{straight}\ \mathrm{skeleton}</tex>, а работает исключительно с рёбрами исходного полигона. Это приводит к ситуации (см. рисунок выше), когда одно ребро является общим для нескольких новых полигонов в промежуточном представлении (то есть одно ребро меняет свою топологию разбивается несколько раз), образовавшихся после разделения старого полигона. В случае, когда ребро уже разбито, и происходит следующий за ним <tex>event</tex>, необходимо правильно определить концы противолежащего ребра (то есть вершины/узлы, которые активный активны в текущем уровне конструирования крыши, как например вершины <tex> X </tex> и <tex> Y </tex> на рисунке ниже).

Например, в данном случае ребро <tex> SY </tex> является частью ребра <tex> e_i = ZY </tex>, которое стягивается и должно теперь указывать на вершину <tex> X </tex>. Когда произойдёт следующее событые в точке пересечения <tex> B </tex>, то нам необходимо правильно указать ребро новой вершине в этой точке в <tex> \mathrm{LAV} </tex>. Реальный конец ребра <tex> e_i </tex> {{---}} точка <tex> Z </tex>, но мы хотим указать на ребро <tex> XY </tex>. Это необходимо для поддержания корректности структуры <tex> \mathrm{SLAV} </tex>. Ниже будет представлено два способа решения этой проблемы.===== Первый способ =====Можно физически разделить исходное ребро на два, вставив новую точку <tex> S </tex>. Это решает проблему, так как никакое ребро не будет разделено дважды, а определение концов разделяемого ребра выполняется просто. Вставка вершины для точки <tex> B </tex> в <tex> \mathrm{LAV} </tex> тоже происходит относительно просто, потому что мы знаем точно, с каким ребром эта вершина связана. Но такой подход требует отдельно рассматривать вершины типа <tex> S </tex>, чтобы не добавить их случайно в <tex> \mathrm{straight}\ \mathrm{skeleton}</tex>.===== Второй способ (используемый в авторском решении) =====Идея заключается в том, чтобы хранить только вершины, которые реально будут в <tex> \mathrm{straight}\ \mathrm{skeleton}</tex>, а указатели на разделямое ребро хранятся во всех подполигонах, для которых это ребро является общим. Это приводит к множественным попаданиям <tex> split\ event'</tex>ов на одно ребро. Для примера, два полигона на рисунке выше разделяют общую ссылку на ребро <tex> e_i </tex>. Во время процесса обработки вершины <tex> B </tex> многоугольник <tex> XMVNY </tex> разбивается на две части <tex> XMB </tex> и <tex> BNY </tex>, а вершина <tex> V </tex> помечается как обработанная.

Всё это нужно для тогоЧтобы решить эту проблему, чтобы правильно связать следует хранить <tex> B split\ event</tex> с вершинами как <tex> X 3</tex> и <tex> Y </tex>, а не с <tex> Z </tex> и <tex> Y </tex>. Во время обхода <tex> \mathrmвершины {{SLAV---}} </tex> выбирается правильная часть невыпуклая вершина и две вершины противолежащего ребра <tex> e_i </tex> (. Дополнительно нужно хранить [[Хеш-таблица | ассоциативный массив]] из пары вершин в ребро для этих вершин. Тогда в данном случае она определяется вершинами момент разделения ребра <tex> X ZY</tex> необходимо удалить это ребро из ассоциативного массива и поместить туда два новых ребра <tex> Y ZX</tex>). Определяется следующим образом: вершина и <tex> B XY</tex> лежит справа от биссектрисы посещённой вершины , которые будут ссылаться на исходное ребро <tex> Y </tex> и слева от биссектрисы предка посещённой вершины <tex> X e_i </tex>.

:<tex>(a)</tex> Извлечём точку пересечения <tex> I </tex> из приоритетной очереди. Если она имеет тип <tex> edge\ event</tex>, то её надо обработать так же, как в шагах <tex> 2b-2f</tex> алгоритма для невыпуклых выпуклых полигонов. Иначе выполнять шаги ниже.

==== Случай полигонов с дырами дырками ====Данный алгоритм может работать и с многоугольниками, содержащими дырыдырки, если они ориентированы по часовой стрелке, чтобы внутренняя область многоугольника лежала слева от рёбер. И в самом начале алгоритма каждый замкнутый контур помещается в свой <tex> \mathrm{LAV} </tex> в множестве <tex> \mathrm{SLAV} </tex>.

Мы можем также упорядочить сами цепи вокруг точки события, объединив эти цепи в один циклический список. Таким образом событие получается как бы окружено списком рёбер, которые участвуют в этом событии, и никакие другие рёбра не участвуют. Можно заметить (рисунки <tex> c,\ d,\ e</tex> выше), что соседние рёбра в списке из изначально разных цепей становятся потом соседними в <tex>\mathrm{LAV}</tex>. И эти цепочки рёбер на самом деле не хранятся отдельными цепочками. Эти цепи и есть <tex>\mathrm{LAV}</tex>.