3622
правки
Изменения
→Частный случай множественных split event'ов на одном ребре
==== Частный случай множественных split event'ов на одном ребре ====
Уже должно было стать понятно, что алгоритм не строит промежуточного представления <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> 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.''' Инициализация:
