184
правки
Изменения
→Ушной метод
'''Триангуляция полигона ''' — декомпозиция многоугольника <tex>P</tex> на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет <tex>P</tex>. В строгом смысле слова, вершины этих треугольников должны совпадать с вершинами исходного многоугольника. Триангуляция любого многоугольника не единственна. В этом можно убедиться из примера на рисунке.[[Файл:2_examples_of_tringl.jpg|300px|thumb|right|Два способа триангуляции одной и той же фигуры]]
== Постановка задачи ==
В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска <tex>T</tex>, в листьях которого будем хранить рёбра, пересекающие <tex>l</tex>, такие, что внутренняя область многоугольника будет лежать справа от них самих. С каждым таким ребром будем хранить его <tex>helper</tex>. Порядок следования листьев в дереве соответствует порядку следования рёбер в многоугольнике: слева направо. Дерево изменяется в зависимости от текущего состояния заметающей прямой. Создадим приоритетную очередь <tex>Q</tex> из вершин, в которой приоритетом будет <tex>y</tex>-координата вершины. Если две вершины имеют одинаковые <tex>y</tex>-координаты, больший приоритет у левой. Вершины будут добавляться на "остановках" заметающей прямой.
Многоугольник <tex>P</tex> и добавленные в процессе диагонали удобно хранить в виде двусвязного спика <tex>D</tex> рёбер и добавленных в процессе диагоналейс двойными связями (''DCEL — doubly-connected edge list''), так как потом это обеспечит эффективный доступ к каждой из частей, которые нужно будет триангулировать.
===== Псевдокод =====
MakeMonotone(P)
Construct(<tex>D</tex>); Construct(<tex>Q</tex>); // функция Construct создаёт объекты <tex>D</tex> и <tex>Q</tex> , описанные выше. bst <tex>T</tex> = new bst(); while Q <tex> Q \neq \varnothing </tex> Remove <tex>v_{max}</tex> from <tex>Q</tex> // удаление вершины с наивысшим приоритетом из <tex>Q</tex>
switch (Type_of_vertex(<tex>v_{max}</tex>)): //определение типа вершины
case 'start':
HandleStartVertex(<tex>v_{i}</tex>)
Insert <tex>e_{i}</tex> in <tex>T</tex>
<tex>helper(e_{i}) \leftarrow v_i</tex>
HandleSplitVertex(<tex>v_{i}</tex>)
edge <tex>e_j</tex> = <tex>l \cap P</tex>
Search <tex>e_j</tex> in <tex>T</tex> Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i})</tex>) in <tex>D</tex>
<tex>helper(e_{j}) \leftarrow v_i</tex>
Insert <tex>e_{i}</tex> in <tex>T</tex> <tex>helper(e_{i}) \leftarrow v_i</tex>v
В последующих трех функциях обработки вершины <tex>v_i</tex> происходит обращение к смежному ребру <tex>e_{i-1}</tex>. Это сделано для вершин, относительно которых внутренняя область <tex>P</tex> лежит справа от них самих (вершина <tex>v_6</tex>), либо для двух подряд идущих merge вершин, таких как <tex>v_2</tex> и <tex>v_8</tex>.
HandleEndVertex(<tex>v_{i}</tex>)
if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in <tex>D</tex> Delete <tex>e_{i-1}</tex> from <tex>T</tex>
HandleMergeVertex(<tex>v_{i}</tex>)
if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in <tex>D</tex> Delete <tex>e_{i-1}</tex> from <tex>T</tex>
edge <tex>e_j</tex> = <tex>l \cap P</tex>
Search <tex>e_j</tex> in <tex>T</tex>
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in <tex>D</tex>
<tex>helper(e_{j}) \leftarrow v_i</tex>
then
if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in <tex>D</tex> Delete <tex>e_{i-1}</tex> from <tex>T</tex> Insert <tex>e_{i}</tex> in <tex>T</tex>
<tex>helper(e_{i}) \leftarrow v_i</tex>
else
edge <tex>e_j</tex> = <tex>l \cap P</tex>
Search <tex>e_j</tex> in <tex>T</tex>
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in <tex>D</tex>
<tex>helper(e_{j}) \leftarrow v_i</tex>
Построение описанной выше приоритетной очереди <tex>Q</tex> происходит за линейное время. Когда заметающая прямая останавливается в вершине: операции с очередью занимают константу по времени, операции с деревом <tex>T</tex> на запросы и обновления требуют <tex>\mathcal{O}(\mathcal \log(n))</tex>. Добавление диагонали в <tex>D</tex> требует <tex>\mathcal{O}(1)</tex>. В итоге обработка каждой вершины требует <tex>\mathcal{O}(\log(n))</tex>, а весь алгоритм соответственно <tex>\mathcal{O}(n \log(n))</tex>. Что касается памяти, она очевидно составляет <tex>\mathcal{O}(n) </tex>. Очередь <tex>Q</tex> и дерево <tex>T</tex> занимают линейную память.
[[Файл:Triangulationg intro.jpg|170px|thumb|right|Зелёным помечена так называемая воронка, которая образуется, когда мы достигнем красной вершины]]
==== Триангуляция монотонного многоугольника ====
===== Идея такова: будем =====Будем проходить сверху вниз по вершинам многоугольника проводя диагонали где это возможно.
Отсортируем все вершины многоугольника <tex>P</tex> в порядке убывания их <tex>y</tex>-координаты. Заведём стек вершин <tex>S</tex>. В стеке будем хранить вершины в отсортированном порядке, которые были обработаны, но не были отрезаны от многоугольника, то есть находятся в той части многоугольника, которая ещё не была триангулирована. В момент обработки некоторой вершины, будем пытаться провести из неё как можно больше диагоналей к вершинам, содержащимся в стеке. Эти диагонали отрезают треугольники от <tex>P</tex>. На вершине стека будет храниться вершина, которая будет обрабатываться последней.
Часть многоугольника <tex>P</tex>, лежащая выше последней обработанной вершины <tex>v_i</tex> и которая ещё не была триангулирована имеет форму перевёрнутой воронки (см. рисунки). Одна сторона воронки состоит из одной из сторон <tex>P</tex>, а другая состоит из цепи вершин, которые лежат выше <tex>v_i</tex> и внутренние углы которых не меньше <tex>\pi</tex>. Несложно догадаться, что самая нижняя вершина стека является единственной выпуклой. Несложно также заметить, что при обработке следующей вершины свойство перевёрнутой воронки сохранится, то есть оно является инвариантом алгоритма.
[[Файл:Triang_alg_case1.jpg|200px|thumb|right|Первый случай. Синим помечены стороны воронки, зелёным — диагонали, а жёлтым границы новой ещё не протриангулированной области]]===== Алгоритм =====Рассмотрим алгоритм процесс обработки вершины более подробно. Возможны два случая:
* Текущая вершина <tex>v_j</tex> является нижним концом стороны <tex>e</tex>, ограничивающего воронку. Вершины противоположной цепи уже были положены в стек. В этом случае можно просто построить диагонали, соединяющие <tex>v_j</tex> со всеми вершинами, находящимися в стеке, кроме последней. Последняя вершина в стеке уже соединена с <tex>v_j</tex> стороной <tex>e</tex>. Часть многоугольника <tex>P</tex>, лежащая выше <tex>v_j</tex>, которая не была триангулирована, ограничена диагональю, которая соединяет <tex>v_j</tex> с вершиной <tex>v_{s1}</tex>, которая была первой в стеке. Сторона многоугольника <tex>P</tex>, выходящая из <tex>v_{s1}</tex> направлена вниз. Снова образуется фигура c одним выпуклым углом, похожая на воронку — инвариант сохраняется. Вершины <tex>v_j</tex> и <tex>v_{s1}</tex> кладутся в стек, поскольку они были были обработаны, но по прежнему являются вершинами непротриангулированной части <tex>P</tex>.
* Вершина <tex>v_j</tex> принадлежит последовательной цепи вершин, добавленных в <tex>S</tex>. Вынем из стека верхнюю вершину <tex>v_{s1}</tex> — она уже соединена с <tex>v_{j}</tex> одной из сторон <tex>P</tex>. Затем будем пытаться выстраивать диагонали, соединяющие <tex>v_{j}</tex> c вынимаемыми из стека вершинами пока это возможно. Проверку на возможность построения диагонали <tex>v_{j}v_{k}</tex>, где <tex>v_{k}</tex> — текущая верхняя вершина стека, можно осуществлять посредством изучения взаимного расположения предыдущей вершины, вынутой из <tex>S</tex>, относительно <tex>v_{j}v_{k}</tex>. Когда мы достигнем вершины <tex>v_{k}</tex>, до которой невозможно провести диагональ, положим предыдущую вершину <tex>v_{k-1}</tex> обратно в стек. Вершина <tex>v_{k-1}</tex> является либо последней, до которой было возможно провести диагональ, либо, если ни одной диагонали из <tex>v_{j}</tex> провести не удалось, — соседом <tex>v_{j}</tex>. Далее положим <tex>v_{j}</tex> в стек. Опять же инвариант непротриангулированной части <tex>P</tex> сохраняется: одна сторона воронки ограничена частью стороны многоугольника, а другая цепью невыпуклых вершин.
[[Файл:Triang alg case2.jpg|500px|thumb|center|Второй случай. Синим помечена цепь из вершин, которая содержится в стеке <tex>S</tex> на момент достижения вершины <tex>v_j</tex>, рыжей помечена первая вершина, до которой невозможно провести диагональ, жёлтой помечена новая нетриангулированная область <tex>P</tex> в форме воронки]]
===== Псевдокод =====
Как ранее уже было отмечено, задаём <tex>P</tex> в виде рёберного списка c двойными связями <tex>D</tex>.
TriangulateMonotonePolygon(P)
vertex [n] V = new vertex(P); // массив вершин <tex>P</tex>, отсортированный по y-координате в порядке убывания.
stack S = new stack();
S.push(V[1]);
S.push(V[2]);
for j \leftarrow 3 to n - 1
if (V[j] = S.peek())
while (S <tex>\neq \varnothing </tex>)
if (S.size() <tex>\neq</tex> 1)
Insert edge(V[j], S.peek()) in D
S.pop()
S.push(V[j-1])
S.push(V[j]);
else
vertex last = S.peek();
S.pop();
while (IsValidDiagonal(edge(V[j], S.peek()), last)) //проверка возможности построения диагонали — предикат "левый поворот"
last = S.peek();
S.pop();
Insert edge(V[j], last) in D
S.push(last);
S.push(V[j]);
S.pop()
while (S <tex>\neq \varnothing </tex>)
if (S.size() <tex>\neq</tex> 1)
Insert edge(V[j], S.peek()) in D
S.pop()
===== Корректность =====
* Все построенные диагонали попарно не пересекаются. Это гарантируется тем, что при каждом просмотре определённой вершины рассматривается только та часть <tex>P'</tex> многоугольника <tex>P</tex>, которая не была протриангулирована, следовательно внутри этой области по определению не может лежать ни одной из уже построенных диагоналей. Несложно заметить, что в стеке <tex>S</tex> на каждой итерации главного цикла хранятся вершины, которые принадлежат именно <tex>P'</tex> и лежат выше рассматриваемой вершины.
* Количество построенных диагоналей всегда будет <tex>n-3</tex>, поэтому непротриангулированных частей в многоугольнике не останется.
===== Оценка работы =====
Построение массива вершин требует линейное время и занимает линейную память. Главный цикл ''for'' выполняется <tex>n-3</tex> раза. Каждая его итерация может потребовать линейное время. Однако заметим, что на каждой итерации главного цикла в стек кладутся максимум две вершины, следовательно общее число выполнения операции ''push'', включая первые две вершины, положенные в начале алгоритма, ограничено <tex>2n-4</tex>. Количество операций ''pop'' за время работы алгоритма не превысит количества операций ''push''. Отсюда общее время работы цикла ''for'' <tex>\mathcal{O}(n)</tex>. В итоге общее время работы <tex>\mathcal{O}(n)</tex>.
==== Общая оценка ====
Разбиение многоугольника на монотонные части занимает <tex>\mathcal{O}(n \log n)</tex> времени и <tex>\mathcal{O}(n)</tex> памяти. Триангуляция каждой из частей занимает линейную память и время. Учитывая то, что суммарное количество вершин во всех частях <tex>\mathcal{O}(n)</tex>, триангуляция всех частей займёт <tex>\mathcal{O}(n)</tex> по времени и по памяти.
В итоге общая оценка составляет <tex>\mathcal{O}(n \log n)</tex> по времени и <tex>\mathcal{O}(n)</tex> по памяти.
==== Прочие случаи ====
[[Файл:Monotone with holes.png|350px|thumb|right|Пример отверстия в форме монотонного многоугольника. У него обязательно будут существовать start и end вершина, если рассматривать его как обычный многоугольник. Однако, когда он станет полигональным отверстием, в силу определения start и end вершины обратятся в split и merge, которые соединятся с какими-то вершинами внешнего контура]]
Алгоритм так же работает и для частных случаев, например для многоугольника с полигональным отверстием. Такой многоугольник будет поделен на части без отверстий и будет успешно триангулирован. Это обуславливается тем, что хотя бы две вершины, принадлежащих отверстию будут split и merge (см. рисунок). Диагональ от таких вершин можно провести только до вершин внешнего контура, а поскольку у внутреннего отверстия хотя бы одна split и одна merge вершина весь многоугольник будет разделён как минимум на две части.
=== Ушной метод ===
