3622
правки
Изменения
→Невыпуклый полигон
[[Файл:skeleton_lav_managing.png|600px]]
Когда происходит работа с точкой <tex> B </tex> <tex> \ split\ event'</tex>а, то необходимо разбить соответствующий полигон на две части, что соответствует разделению <tex> \mathrm{LAV} </tex> данного полигона на два списка. И в каждый новый список нужно вставить новую вершину <tex> X </tex>, образующуюся в точке пересечения <tex> B </tex>. Обе вершины <tex> X </tex> указывают на разделяющее ребро <tex> e_i </tex> (см. рисунок выше).
==== Частный случай множественных split event'ов на одном ребре ====
Уже должно было стать понятно, что алгоритм не строит промежуточного представления <tex> \mathrm{straight}\ \mathrm{skeleton}</tex>, а работает исключительно с рёбрами исходного полигона. Это приводит к ситуации (см. рисунок выше), когда одно ребро является общим для нескольких новых полигонов в промежуточном представлении, образовавшихся после разделения старого полигона. В случае, когда ребро уже разбито, и происходит следующий за ним <tex> edge\ 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>
==== Алгоритм для невыпуклых полигонов ====
