3622
правки
Изменения
Нет описания правки
==== Частные случаи ====
Частным случаем в алгоритме может быть совпадение нескольких <tex> edge\ event'</tex>ов в одной точке. Эти совпадения добавляются в шагах <tex> 1c </tex> и <tex> 2f </tex>, но могут быть относительно легко обработаны в шаге <tex> 2b </tex>. Также может случиться, что какие-то рёбра не стянулись в итоге в одну вершину, а слились. Такое возможно, если какие-то стороны полигона были изначально параллельны (этот случай легко увидеть на прямоугольнике, не являющемся квадратом). С этим частным случаем можно разобраться в шаге <tex> 2c </tex>, проверив, не совпала ли одна из трёх вершин с другой. В выпуклом многоугольнике слияние двух рёбер может произойти только один раз (что неправда для невыпуклого многоугольника), поэтому здесь несложно разобраться с таким случаем.
=== Невыпуклый полигон ===
Основной принцип для невыпуклых полигонов такой же. Только с вершиной ещё хранится дополнительный атрибут, обозначающий событие, которое в ней произошло: <tex> edge\ event</tex> или <tex> split\ event</tex>.
Всё это нужно для того, чтобы правильно связать <tex> B </tex> с вершинами <tex> X </tex> и <tex> Y </tex>, а не с <tex> Z </tex> и <tex> Y </tex>. Во время обхода <tex> \mathrm{SLAV} </tex> выбирается правильная часть ребра <tex> e_i </tex> (в данном случае она определяется вершинами <tex> X </tex> и <tex> Y </tex>). Определяется следующим образом: вершина <tex> B </tex> лежит справа от биссектрисы посещённой вершины <tex> Y </tex> и слева от биссектрисы предка посещённой вершины <tex> X </tex>.
==== Алгоритм для невыпуклых полигонов ====
'''Шаг 1.''' Инициализация: :<tex>(a)</tex> Положим все вершины в <tex> \mathrm{LAV}</tex>, как это делается в алгоритме для выпуклых многоугольников, а потом <tex> \mathrm{LAV}</tex> поместим в <tex> \mathrm{SLAV}</tex>.:<tex>(b)</tex> Найдём биссектрисы как в случае с выпуклым многоугольником.:<tex>(c)</tex> Для каждой биссектрисы выпуклой вершины найдём ближайшую точку пересечения с биссектрисой соседней вершины, а для невыпуклых вершин найдём также точки пересечения с противолежащими рёбрами (как это описывалось раньше), и положим в приоритетную очередь ближайшую точку пересечения <tex> I </tex>. Будем также с этой точкой хранить её тип {{---}} <tex> edge\ event</tex> или <tex> split\ event</tex>.'''Шаг 2.''' Пока очередь не пуста::<tex>(a)</tex> Извлечём точку пересечения <tex> I </tex> из приоритетной очереди. Если она имеет тип <tex> edge\ event</tex>, то её надо обработать так же, как в шагах <tex> 2b-2f</tex> алгоритма для невыпуклых полигонов. Иначе выполнять шаги ниже.:<tex>(b)</tex> Если точка пересечения указывает на уже обработанные вершины, то продолжить со следующей итерации цикла шага 2, как в случае с выпуклым полигоном.:<tex>(c)</tex> Нужно сделать примерно то же самое, что и шаге <tex>2c</tex> алгоритма для выпуклых многоугольников. Только на этом цикл не завершается, а продолжается с новой итерации, так как многоугольник мог разделиться на несколько частей, и, возможно, мы обработали лишь один подпалигон и не последний.:<tex>(d)</tex> Добавим в <tex> \mathrm{straight}\ \mathrm{skeleton} </tex> ребро <tex> IV </tex>, где точка <tex> I </tex> указывает на вершину <tex> V </tex>. Для <tex> split\ event'</tex>ов точки пересечения указывают ровно на одну вершину в <tex> \mathrm{SLAV}</tex>.:<tex>(e)</tex> Модифицируем теперь <tex> \mathrm{SLAV}</tex>:::* пометим вершину <tex> V </tex> как обработанную,::* создадим две новые вершины <tex> V_1 </tex> и <tex> V_2 </tex> с одинаковыми координатами точки пересечения <tex> I </tex>,::* найдём для каждой вершины <tex> V_1 </tex> и <tex> V_2 </tex> противолежащее ребро в своём подпалигоне,::* разделим <tex> \mathrm{LAV}</tex> с вершиной <tex> V </tex> на две части (как показано на рисунке выше), вставим в части вершины <tex> V_1 </tex> и <tex> V_2 </tex>, а затем обе части добавим в <tex> \mathrm{SLAV}</tex>. Вершина <tex> V_1 </tex> будет следующей для предыдующего к <tex> V </tex> узлу в <tex> \mathrm{LAV}</tex> и предыдущей для конца противолежащего ребра. Аналогично для вершины <tex> V_2 </tex>. Этот шаг в действительно разбивает полигон на две части,::* Добавим указатели вершинам <tex> V_1 </tex> и <tex> V_2 </tex> на соответствующие рёбра.:<tex>(f)</tex> Для обеих вершин <tex> V_1 </tex> и <tex> V_2 </tex>:::* найдём биссектрисы между рёбрами, на которые эти вершины слинковались в шаге <tex>2e</tex>,::* найдём точки пересечения лучей с биссектрисами соседних вершин как в шаге <tex> 1c </tex> (тут могут получиться точки пересечения обоих типов),::* сохраним ближайшие точки пересечения в приоритетной очереди.
==== Случай полигонов с дырами ====
Данный алгоритм может работать и с многоугольниками, содержащими дыры, если они ориентированы по часовой стрелки, чтобы внутренняя область многоугольника лежала слева от рёбер. И в самом начале алгоритма каждый замкнутый контур помещается в свой <tex> \mathrm{LAV} </tex> в множестве <tex> \mathrm{SLAV} </tex>.
