184
правки
Изменения
→Ушной метод
'''Триангуляция полигона ''' — декомпозиция внутренней области многоугольника <tex>P</tex> на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет <tex>P</tex>. В строгом смысле слова, эти треугольники могут иметь вершины только в вершинах этих треугольников должны совпадать с вершинами исходного многоугольника. Кроме того, случаи Триангуляция любого многоугольника не единственна. В этом можно убедиться из примера на рисунке. [[Файл:2_examples_of_tringl.jpg|300px|thumb|right|Два способа триангуляции простого многоугольника одной и многоугольника с полигональными отверстиями рассматриваются отдельно.той же фигуры]]
== Постановка задачи ==
На плоскости задан произвольный многоугольник. Стороны многоугольника не пересекаются. Требуется найти его триангуляцию.
== Теорема о существовании трингуляции ==
'''Простым многоугольником''' является фигура, ограниченная одной замкнутой ломаной, стороны которой не пересекаются. Таким образом, случаи многоугольников с дырками в теореме исключаются.
{{Теорема
|about = о сеченияхО существовании триангуляции многоугольника
|statement =
== Способы нахождения триангуляции ==
=== Примитивный алгоритм ===
В общем случае в произвольном <tex>n</tex>-угольнике всего <tex>n^2</tex> возможных вариантов построения диагоналей. За <tex>\mathcal{O}(n)</tex> проверим каждый из них. Для этого выясним:
* пересекает ли данная диагональ многоугольник — находится за линейное время проверкой по всем рёбрам
* принадлежит ли диагональ внутренней область многоугольника.
Чтобы построить триангуляцию нужно найти <tex>n - 3</tex> диагоналей. В результате получается оценка <tex>\mathcal{O}(n^4)</tex>.
Для некоторых классов многоугольников предыдущую оценку можно улучшить. Например, если многоугольник выпуклый, то достаточно лишь выбирать одну его вершину и соединять со всеми остальными, кроме его соседей. В итоге оценка <tex>\mathcal{O}(n)</tex>.
=== Монотонный метод ===
{{Определение
|definition=
Простой многоугольник <tex>P</tex> называется '''монотонным''' относительно прямой <tex>l</tex>, если любая <tex>l'</tex>, такая что <tex>l' \perp l</tex>, пересекает стороны <tex>P</tex> не более двух раз (результатом пересечения <tex>l'</tex> и <tex>P</tex> может быть только один отрезок или точка).
}}
{{Определение
|definition=
Многоугольник, монотонный относительно <tex>y</tex>-оси называется '''<tex>y</tex>-монотонным'''.
}}
Суть данного метода заключается в том, чтобы разбить многоугольник на монотонные части, а затем триангулировать каждую из них.
==== Разбиение многоугольника на монотонные части ====
===== Основные понятия =====
[[Файл:Split-merge.png|500px|thumb||Пять типов вершин]]
Рассмотрим самую верхнюю — максимальную по оси <tex>y</tex> вершину. Будем идти вниз по рёбрам до самой нижней — соотвественно минимальной по <tex>y</tex> вершине, то есть таким образом, что для некоторой вершины <tex>j</tex>: <tex>y_j > y_{j+1}</tex>. '''Поворотной''' назовём вершину <tex>i</tex>, на которой направление обхода будет меняется: <tex>y_{i-1} > y_i</tex> и <tex>y_i < y_{i+1}</tex>. Опишем более подробно этот тип вершин.
Уточним понятния ''выше'' и ''ниже'': точка <tex>p</tex> лежит ''ниже'' точки <tex>q</tex>, если <tex>p_y < q_y</tex> или если <tex>p_y < q_y</tex> и <tex>p_x > q_x</tex>, соответственно точка <tex>p</tex> лежит ''выше'' точки <tex>q</tex>, если <tex>p_y > q_y</tex> или если <tex>p_y = q_y</tex> и <tex>p_x < q_x</tex>. Это было сделано для того, чтобы избежать неопределённых ситуаций с вершинами, у которых <tex>y</tex>-координаты равны.
Обозначим за <tex>\phi</tex> внутренний угол при некоторой вершине вершине и определим далее пять типов вершин, четыре из которых являются поворотными:
* '''''start вершина''''' — два её соседа лежат ниже её самой и <tex> \phi < \pi </tex>
* '''''split вершина''''' — два её соседа лежат ниже её самой и <tex> \phi > \pi </tex>
* '''''end вершина''''' — два её соседа лежат выше её самой и <tex> \phi < \pi </tex>
* '''''merge вершина''''' — два её соседа лежат выше её самой и <tex> \phi > \pi </tex>
* '''''regular вершина''''' — не является поворотной, в отличие от остальных, другими словами один её сосед находится выше, а другой ниже её самой.
{{Лемма
|statement=
Многоугольник <tex>P</tex> является <tex>y</tex>-монотонным, когда в нём отсутствуют split и merge вершины.
|proof=
Рассмотрим заметающую прямую <tex> \lambda(E(x_1)) = \begin{cases} d l</tex>, перпендукулярную <tex>y</tex>- c &оси, x_1 \in [aбудем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, b] \\ 0 &когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, x_1 \notin [aу которой расстояние до <tex>l</tex> минимально, b] \end{cases} при этом она должна лежать соответственно выше или ниже <tex>l</tex> — кусочно-постоянная функция на оси, суммируема.[[Файл:Split_case.jpg|200px|thumb|right|Обработка ''split'' вершины <tex>v_i</tex>]] Рассмотрим каждый случай подробнее:
2) '''''Merge вершина'''''. В отличие от случая со split вершиной заранее вычислить указатель <tex>helper</tex> нельзя, поскольку merge вершина <tex>v_i</tex> должна быть соединена с вершиной, лежащей ниже заметающей прямой <tex>l</tex>. Для этого в <tex>helper</tex> левого относительно <tex>v_i</tex> ребра запишем саму <tex>v_i</tex>. Далее спускаем заметающую прямую вниз к следующей вершине <tex>v_m</tex>, обращаемся к <tex>helper</tex>'у её левого ребра. Проверяем, если там хранится merge вершина, строим диагональ <tex> G v_{i}v_{m}</tex> — открытое множество. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.[[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''megre'' вершины <tex>v_i</tex>. На рисунке слева <tex> \lambda G v_i< + \infty /tex> записывается в качестве <tex>helper</tex>'а своего левого ребра. На правом рисунке ближайшая вершина <tex>v_m</tex> при обращении к своему левому ребру <tex>helper(e_j)</tex> находит <tex>v_i</tex> и образует диагональ <tex>v_{i}v_m</tex>]]
===== Структуры данных =====В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска <tex> G = \bigcup\limits_n \Delta_n (x_1) T</tex> , по 1) в листьях которого будем хранить рёбра, пересекающие <tex> \Delta_n (x_1) l</tex> — измеримо, а не болеетакие, чем счётное объединение измеримыхчто внутренняя область многоугольника будет лежать справа от них самих. С каждым таким ребром будем хранить его <tex>helper</tex>. Порядок следования листьев в дереве соответствует порядку следования рёбер в многоугольнике: слева направо. Дерево изменяется в зависимости от текущего состояния заметающей прямой. Создадим приоритетную очередь <tex>Q</tex> из вершин, в которой приоритетом будет <tex>y</tex>-координата вершины. Если две вершины имеют одинаковые <tex>y</tex>-координаты, измеримобольший приоритет у левой. Вершины будут добавляться на "остановках" заметающей прямой.
MakeMonotone(P) Construct(D); Construct(Q); // функция Construct создаёт объекты <tex>D</tex> и <tex>Q</tex> , описанные выше. bst T = new bst(); while Q <tex> \intneq \limits_varnothing </tex> Remove <tex>v_{\mathbb Rmax} \lambda_1</tex> from Q // удаление вершины с наивысшим приоритетом из <tex>Q</tex> switch (GType_of_vertex(x_1<tex>v_{max}</tex>)) dx = : //определение типа вершины case 'start': HandleStartVertex(<tex>v_{max}</tex> ); case 'end': HandleEndVertex(т. Леви <tex>v_{max}</tex>); case 'split': HandleSplitVertex(Но причем тут она? Надо пользоваться сигма-аддитивностью интеграла.)) <tex> \sum\limits_n \int\limits_v_{\mathbb Rmax} \lambda_1 (\Delta_n (x_1)</tex>) d x_1 = \sum\limits_n \lambda_2 ; case 'merge': HandleMergeVertex(\Delta_n<tex>v_{max}</tex>) = \lambda_2 ; case 'regular': HandleRegularVertex(G) <tex>v_{max}</tex>.);
HandleSplitVertex(<tex> v_{i}</tex>) edge <tex>e_j</tex> = <tex>l \lambda_1 cap P</tex> Search <tex>e_j</tex> in T Insert edge(E<tex>v_{i}</tex>, <tex>helper(x_1e_{i})</tex>)in D <tex>helper(e_{j}) = \lim\limits_leftarrow v_i</tex> Insert <tex>e_{n \to \inftyi} \lambda_1 </tex> in T <tex>helper(G_n(x_1)e_{i}) \leftarrow v_i</tex> — тоже измеримо(как предел измеримой функции).
HandleEndVertex(<tex> \int\limits_v_{\mathbb Ri} \lambda_1 </tex>) if (EType_of_vertex(x_1<tex>helper(e_{i-1})</tex> = 'merge') d x_1 = \lim\limits_ Insert edge(<tex>v_{n \to \inftyi} \int\limits_</tex>, <tex>helper(e_{\mathbb Ri-1} \lambda_1 (G_n(x_1)</tex>) d x_1 in D Delete <tex>e_{i-1}</tex>.from T
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 D Delete <tex>e_{i-1}</tex> from T edge <tex>e_j</tex> = <tex>l \lambda_2 cap P</tex> Search <tex>e_j</tex> in T if (Type_of_vertex(<tex>helper(G_ne_{j}) \to \lambda_2</tex> = 'merge') Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D <tex>helper(Ee_{j}) \leftarrow v_i</tex>
===== Идея =====Будем проходить сверху вниз по вершинам многоугольника проводя диагонали где это возможно. Отсортируем все вершины многоугольника <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 вершина весь многоугольник будет разделён как минимум на две части. === Ушной метод ===// ещё допишу.