2012-06-11T09:47:37Z

Muravyov:

'''Триангуляция полигона ''' — декомпозиция многоугольника <tex>P</tex> на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет <tex>P</tex>. В строгом смысле слова, вершины этих треугольников должны совпадать с вершинами исходного многоугольника. Триангуляция любого многоугольника не единственна. В этом можно убедиться из примера на рисунке. [[Файл:2_examples_of_tringl.jpg‎|300px|thumb|right|Два способа триангуляции одной и той же фигуры]]

== Постановка задачи ==

На плоскости задан произвольный многоугольник. Стороны многоугольника не пересекаются. Требуется найти его триангуляцию.

== Теорема о существовании трингуляции ==

'''Простым многоугольником''' является фигура, ограниченная одной замкнутой ломаной, стороны которой не пересекаются. Таким образом, случаи многоугольников с дырками в теореме исключаются.
{{Теорема
|about = О существовании триангуляции многоугольника
|statement =
У любого простого <tex>n</tex>-вершинного многоугольника <tex>P</tex> всегда существует триангуляция, причём количество треугольников в ней <tex>n - 2</tex> независимо от самой триангуляции.
|proof=
[[Файл:Proof theorem.jpg|200px|thumb|right|Два случая в доказательстве теоремы]]
Доказательство ведётся индуктивно по <tex>n</tex>. При <tex>n = 3</tex> теорема тривиальна. Рассмотрим случай при <tex>n > 3</tex> и предположим, что теорема выполняется при всех <tex>m < n</tex>. Докажем существование диагонали в многоугольнике <tex>P</tex>. Возьмём самую левую по оси <tex>x</tex> вершину <tex>v</tex> многоугольника <tex>P</tex> и две смежных с ней вершины <tex>u</tex> и <tex>w</tex>. Если отрезок <tex>uw</tex> принадлежит внутренней области <tex>P</tex> — мы нашли диагональ. В противном случае, во внутренней области треугольника <tex>\Delta uwv</tex> или на самом отрезке <tex>uw</tex> содержится одна или несколько вершин <tex>P</tex>. Выберем самую наиболее далеко отстоящую от <tex>uw</tex> вершину <tex>v'</tex>. Отрезок, соединяющий <tex>v</tex> и <tex>v'</tex> не может пересекать сторон <tex>P</tex>, поскольку в противном случае одна из вершин это отрезка будет располагаться дальше от <tex>uw</tex>, чем <tex>v'</tex>. Это противоречит условию выбора <tex>v'</tex>. В итоге получаем, что <tex>v'v</tex> — диагональ.
Любая диагональ делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>. За <tex>m_1</tex> и <tex>m_2</tex> обозначим количество вершин в <tex>P_1</tex> и <tex>P_2</tex> соответственно. <tex>m_1 < n</tex> и <tex>m_2 < n</tex>, поэтому по предположению индукции у <tex>P_1</tex> и <tex>P_2</tex> существует триангуляция, следовательно и у <tex>P</tex> она существует.

Докажем, что триангуляция <tex>P</tex> состоит из <tex>n - 2</tex> треугольников. Рассмотрим произвольную диагональ <tex>d</tex> в триангуляции <tex>T_P</tex>. <tex>d</tex> делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>, количество вершин в которых <tex>m_1</tex> и <tex>m_2</tex> соответственно. Каждая вершина <tex>P</tex> встречается только в одном из двух многоугольников <tex>P_1</tex> и <tex>P_2</tex>, за исключением тех, которые являются концами <tex>d</tex>, поэтому справедливо следующее: <tex>m_1 + m_2 = n + 2</tex>. По индукции, любая триангуляция <tex>P_i</tex> состоит из <tex>m_i - 2</tex> треугольников, откуда следует, что <tex>T_P</tex>. состоит из <tex>(m_1 - 2) + (m_2 - 2) = n - 2</tex> треугольников.
}}

== Способы нахождения триангуляции ==
=== Примитивный алгоритм ===
В общем случае в произвольном <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>P</tex> не <tex>y</tex>-монотонный. Тогда докажем, что <tex>P</tex> содержит split и merge вершины. Поскольку <tex>P</tex> не <tex>y</tex>-монотонный, горизонтальная прямая <tex>l</tex> пересекает его стороны более двух раз. Выберем <tex>l</tex> таким образом, чтобы самой левой компонентой пересечения <tex>l</tex> и <tex>P</tex> был бы отрезок <tex>pq</tex>. Далее будем двигаться наверх по сторонам <tex>P</tex>, начиная от точки <tex>q</tex>. В результате в некоторой точке <tex>r</tex>, где <tex>r \neq p</tex> (случай '''(a)''' на рисунке), прямая <tex>l</tex> снова пересечёт одну из сторон <tex>P</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам <tex>P</tex>, будет split вершиной.

[[Файл:Proof_lemma.jpg|450px]]

Если же <tex>r = p</tex> (случай '''(b)''' на рисунке), начём опять двигаться по сторонам <tex>P</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка <tex>r'</tex>, которая будет результатом пересечения <tex>l</tex> и <tex>P</tex>. При этом <tex>r' \neq p</tex>, в противном случае <tex>l</tex> будет пересекать <tex>P</tex> только два раза, то есть <tex>P</tex> будет <tex>y</tex>-монотонным, что противоречит нашему предположению. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.
}}

===== Алгоритм =====
Чтобы сделать многоугольник монотонным, нужно избавиться от split и merge вершин путём проведения непересекающихся дигоналей из таких вершин.

Рассмотрим заметающую прямую <tex>l</tex>, перпендукулярную <tex>y</tex>-оси, будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, у которой расстояние до <tex>l</tex> минимально, при этом она должна лежать соответственно выше или ниже <tex>l</tex>.
[[Файл:Split_case.jpg|200px|thumb|right|Обработка ''split'' вершины <tex>v_i</tex>]] Рассмотрим каждый случай подробнее:

1) '''''Split вершина'''''. Пусть <tex>e_j</tex> и <tex>e_k</tex> — ближайшее левое и правое ребро относительно split вершины <tex>v_i</tex>, которые <tex>l</tex> пересекает в данный момент. Нам нужно найти вершину, лежащую между <tex>e_j</tex> и <tex>e_k</tex>, наиболее приближённую к <tex>l</tex>, либо если такой точки не существет выбрать минимальную из верхних вершин <tex>e_j</tex> и <tex>e_k</tex>. Для этого будем хранить указатель на искомую вершину у левого ребра <tex>e_j</tex>, который можно заранее вычислить. Тип вершины, хранящийся в <tex>helper</tex> не имеет значения. Таким образом, чтобы построить диагональ для split вершины нужно обратиться к указателю <tex>helper</tex> её левого ребра, которое <tex>l</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>v_{i}v_{m}</tex>. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.
[[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''megre'' вершины <tex>v_i</tex>. На рисунке слева <tex>v_i</tex> записывается в качестве <tex>helper</tex>'а своего левого ребра. На правом рисунке ближайшая вершина <tex>v_m</tex> при обращении к своему левому ребру <tex>helper(e_j)</tex> находит <tex>v_i</tex> и образует диагональ <tex>v_{i}v_m</tex>]]

===== Структуры данных =====
В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска <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(D);
Construct(Q); // функция Construct создаёт объекты <tex>D</tex> и <tex>Q</tex> , описанные выше.
bst T = new bst();
while Q <tex> \neq \varnothing </tex>
Remove <tex>v_{max}</tex> from Q // удаление вершины с наивысшим приоритетом из <tex>Q</tex>
switch (Type_of_vertex(<tex>v_{max}</tex>)): //определение типа вершины
case 'start':
HandleStartVertex(<tex>v_{max}</tex>);
case 'end':
HandleEndVertex(<tex>v_{max}</tex>);
case 'split':
HandleSplitVertex(<tex>v_{max}</tex>);
case 'merge':
HandleMergeVertex(<tex>v_{max}</tex>);
case 'regular':
HandleRegularVertex(<tex>v_{max}</tex>);

[[Файл:Split-merge - result.png|470px]]

Опишем теперь каждый метод из последнего switch:

HandleStartVertex(<tex>v_{i}</tex>)
Insert <tex>e_{i}</tex> in T
<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 T
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>
Insert <tex>e_{i}</tex> in T
<tex>helper(e_{i}) \leftarrow v_i</tex>

В последующих трех функциях обработки вершины <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 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 \cap P</tex>
Search <tex>e_j</tex> in T
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>

HandleRegularVertex(<tex>v_{i}</tex>)
if (interior of <tex>P</tex> lies to the right of <tex>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 D
Delete <tex>e_{i-1}</tex> from T
Insert <tex>e_{i}</tex> in T
<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 T
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>

===== Корректность =====

{{Лемма
|statement=
Функция ''MakeMonotone(P)'' корректно выполняет разбиение многоугольника <tex>P</tex>. Другими словами эта функция добавляет в <tex>P</tex> множество непересекающихся диагоналей, которые разбивают <tex>P</tex> на монотонные части.
|proof=
Тот факт, что <tex>P</tex> разбивается на монотонные части следует из предыдущей леммы.
Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, не попарно не пересекаются и не пересекают стороны <tex>P</tex>.

Рассмотрим случай выполнения функции ''HandleSplitVertex'', поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершин, в отличие от остальных функций (в них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной).

Допустим, что диагональ <tex>v_{i}v_{m}</tex> была построена с помощью ''HandleSplitVertex'' по достижению split вершины <tex>v_i</tex>. Рассмотрим четырёхугольник <tex>H</tex>, заключённый между <tex>e_j</tex> и <tex>e_k</tex> - левым и правым ребром относительно <tex>v_i</tex> и горизонтальными прямыми, проведёнными через <tex>v_i</tex> и <tex>v_m</tex>. Внутри <tex>H</tex>, не может находиться ни одной из вершин <tex>P</tex>, в противном случае <tex>helper(e_j)</tex> не равнялся бы <tex>v_m</tex>. Предположим теперь, что <tex>v_{i}v_{m}</tex> пересекает <tex>e_s</tex> одну из сторон <tex>P</tex>. Учитывая, что никаких вершин <tex>P</tex> не лежит внутри <tex>H</tex> и стороны <tex>P</tex> не пересекаются, то <tex>e_s</tex> должна пересечь либо отрезок, соединяющий <tex>e_j</tex> и <tex>v_m</tex>, либо <tex>e_j</tex> и <tex>v_i</tex>.[[Файл:Pic_of_correctness.jpg‎|400px|thumb|right|1) Вершин внутри <tex>H</tex> находиться не может; 2) <tex>v_{i}v_m</tex> может пересекать только рёбра, помеченные зелёным]] Такое возможно только в случае, когда точками пересечения будут являться <tex>v_i</tex> или <tex>v_m</tex>, что не противоречит условию. Отсюда <tex>v_{i}v_{m}</tex> не пересекает ни одну из сторон <tex>P</tex> в посторонних точках.

Теперь рассмотрим случай с пересечением добавленной ранее диагональю. Поскольку внутри <tex>H</tex> никаких вершин вершин находиться не может, и оба конца любой добавленной ранее диагонали должны лежать выше <tex>v_i</tex>, диагональ <tex>v_{i}v_m</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 <tex>\leftarrow</tex> 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 <tex>\leftarrow</tex> S.peek();
S.pop();
while (IsValidDiagonal(edge(V[j], S.peek()), last)) //проверка возможности построения
//диагонали — предикат "левый поворот"
last <tex>\leftarrow</tex> 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>.

==== Общая оценка ====
[[Файл:Monotone with holes.png|350px|thumb|right|Пример отверстия в форме монотонного многоугольника. У него обязательно будут существовать start и end вершина, если рассматривать его как обычный многоугольник. Однако, когда он станет полигональным отверстием, в силу определения start и end вершины обратятся в split и merge, которые соединятся с какими-то вершинами внешнего контура]]
Разбиение многоугольника на монотонные части занимает <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> по памяти.

==== Прочие случаи ====
Алгоритм так же работает и для частных случаев, например для многоугольника с полигональным отверстием. Такой многоугольник будет поделен на части без отверстий и будет успешно триангулирован. Это обуславливается тем, что хотя бы две вершины, принадлежащих отверстию будут split и merge (см. рисунок). Диагонали от таких вершин можно провести только до вершин внешнего контура, а поскольку у внутреннего отверстия хотя бы одна split и одна merge вершина весь многоугольник будет разделён как минимум на две части.

=== Ушной метод ===
{{Определение
|definition=
Вершина <tex>v_i</tex> называется '''ухом''', если диагональ <tex>v_{i-1}v_{i+1}</tex> лежит строго во внутренней области многоугольника <tex>P</tex>
}}
[[Файл:Ear1.jpg‎|350px|thumb|left|В первом случае выделенная вершина является ухом, в остальных нет]]

{{Теорема
|about = О существовании двух ушей многоугольника
|statement =
У любого простого <tex>n</tex>-вершинного многоугольника <tex>P</tex> всегда существует два не пересекающихся между собой уха.
|proof=}}

==== Идея ====
Рассмотрим все вершины многоугольника <tex>P</tex>, и где возможно, будем отрезать уши до тех пор, пока <tex>P</tex> не станет треугольником.

Будем рассматривать вершины многоугольника в порядке обхода. Индексирование вершин для удобства будем вести по модулю <tex>n</tex>, т.е. <tex>v_{-1} = v_{n-1}</tex> и <tex>v_0 = v_n</tex>. Если вершина <tex>v_i</tex> является ухом, построим диагональ <tex>v_{i+1}v_{i-1}</tex> и отрежем треугольник <tex>\Delta v_{i-1}v_{i}v_{i+1}</tex> от <tex>P</tex>. В противном случае переходим к следующей вершине <tex>v_{i+1}</tex> в порядке обхода.

==== Алгоритм ====
При проверке каждой вершину следует для начала проверить, является ли она выпуклой, в противном случае её просто нет надобности рассматривать в качестве уха. Это несложно сделать, воспользовавшись [[Предикат_"левый_поворот"|левым поворотом]]. "Ушную" проверку вершины будем осуществлять алгоритмом принадлежности точки <tex>n</tex>-угольнику (в нашем случае треугольнику). В качестве поддерживаемых структур удобно хранить DCEL, в котором будем строить новые диагонали, и список вершин с двойными связями, аналогичный DCEL по построению.

==== Псевдокод ====
DCVL D1 //список вершин doubly connected vertex list по аналогии с DCEL
DCEL D2
Construct(D1);
Construct(D2);
vertex v = random_vertex_of(D1);
while size_of(D1) <tex> \neq </tex> 3
if IsConvex(v) //проверка на выпуклость
for each Vertex v_i in D1
if v_i <tex> \neq </tex> v, v.prev(), v.next() //проверка всех вершин на
and v_i <tex>\in </tex> Triangle(v, v.prev(), v.next())//принадлежность треугольнику,
//одной из вершин которого
//является потенциальное ухо v.
edge e = new edge(v.prev, v.next)
Insert e in D2;
v = v.next
Delete v.prev from D1

==== Корректность ====
При нахождении каждого уха от многоугольника <tex>P</tex> отрезается треугольник, состоящий из самого уха и его двух смежных вершин. В конце алгоритма, когда все уши от <tex>P</tex> отрезаны, остается только один треугольник. Как несложно видеть, триангуляция выстраивается корректно.

==== Оценка работы ====
Изначально в многоугольнике содержится <tex>\mathcal{O}(n)</tex> ушей. Нетрудно понять, что в процессе отрезания ушей, смежные точки могут тоже становиться ушами. В результате триангуляции образуется <tex>n - 3</tex> диагонали, соответственно максимальное количество вершин, которые в процессе могут становиться ушами <tex>2n - 6</tex>. Итого общее количество ушей будет <tex>\mathcal{O}(n)</tex>. Определить, является ли вершина ухом можно за <tex>\mathcal{O}(n)</tex>, поскольку используется алгоритм определения принадлежности точки треугольнику — это <tex>\mathcal{O}(3)</tex>. Таким образом общий процесс отрезания ушей займёт <tex>\mathcal{O}(n^2)</tex>. Невыпуклых вершин всего <tex>\mathcal{O}(n)</tex>, каждая из них обрабатывается за константу, поэтому общее время для их обработки <tex>\mathcal{O}(n)</tex>. Списки рёбер и вершин строятся за линейное время, добавление ребра и удаление вершины в каждом из них работает за константу. Общее время <tex>\mathcal{O}(n^2)</tex>. Поскольку храним только два списка — память линейная.

ДОПИЛЮ ЕЩЁ.

== Источники ==
* Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0 Chapter 3: Polygon Triangulation: pp.45–61.

* [http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/cutting_ears.html Ear Cutting for Simple Polygons]

* [http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf Triangulation by ear-clipping]

Файл:Ear1.jpg

2012-06-11T09:46:12Z

Muravyov: загружена новая версия «Файл:Ear1.jpg»

Файл:Ear1.jpg

2012-06-11T09:39:19Z

Muravyov:

Триангуляция полигонов (ушная + монотонная)

2012-05-12T16:39:40Z

Muravyov: /* Ушной метод */

'''Триангуляция полигона ''' — декомпозиция многоугольника <tex>P</tex> на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет <tex>P</tex>. В строгом смысле слова, вершины этих треугольников должны совпадать с вершинами исходного многоугольника. Триангуляция любого многоугольника не единственна. В этом можно убедиться из примера на рисунке. [[Файл:2_examples_of_tringl.jpg‎|300px|thumb|right|Два способа триангуляции одной и той же фигуры]]

== Постановка задачи ==

На плоскости задан произвольный многоугольник. Стороны многоугольника не пересекаются. Требуется найти его триангуляцию.

== Теорема о существовании трингуляции ==

'''Простым многоугольником''' является фигура, ограниченная одной замкнутой ломаной, стороны которой не пересекаются. Таким образом, случаи многоугольников с дырками в теореме исключаются.
{{Теорема
|about = О существовании триангуляции многоугольника
|statement =
У любого простого <tex>n</tex>-вершинного многоугольника <tex>P</tex> всегда существует триангуляция, причём количество треугольников в ней <tex>n - 2</tex> независимо от самой триангуляции.
|proof=
[[Файл:Proof theorem.jpg|200px|thumb|right|Два случая в доказательстве теоремы]]
Доказательство ведётся индуктивно по <tex>n</tex>. При <tex>n = 3</tex> теорема тривиальна. Рассмотрим случай при <tex>n > 3</tex> и предположим, что теорема выполняется при всех <tex>m < n</tex>. Докажем существование диагонали в многоугольнике <tex>P</tex>. Возьмём самую левую по оси <tex>x</tex> вершину <tex>v</tex> многоугольника <tex>P</tex> и две смежных с ней вершины <tex>u</tex> и <tex>w</tex>. Если отрезок <tex>uw</tex> принадлежит внутренней области <tex>P</tex> — мы нашли диагональ. В противном случае, во внутренней области треугольника <tex>\Delta uwv</tex> или на самом отрезке <tex>uw</tex> содержится одна или несколько вершин <tex>P</tex>. Выберем самую наиболее далеко отстоящую от <tex>uw</tex> вершину <tex>v'</tex>. Отрезок, соединяющий <tex>v</tex> и <tex>v'</tex> не может пересекать сторон <tex>P</tex>, поскольку в противном случае одна из вершин это отрезка будет располагаться дальше от <tex>uw</tex>, чем <tex>v'</tex>. Это противоречит условию выбора <tex>v'</tex>. В итоге получаем, что <tex>v'v</tex> — диагональ.
Любая диагональ делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>. За <tex>m_1</tex> и <tex>m_2</tex> обозначим количество вершин в <tex>P_1</tex> и <tex>P_2</tex> соответственно. <tex>m_1 < n</tex> и <tex>m_2 < n</tex>, поэтому по предположению индукции у <tex>P_1</tex> и <tex>P_2</tex> существует триангуляция, следовательно и у <tex>P</tex> она существует.

Докажем, что триангуляция <tex>P</tex> состоит из <tex>n - 2</tex> треугольников. Рассмотрим произвольную диагональ <tex>d</tex> в триангуляции <tex>T_P</tex>. <tex>d</tex> делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>, количество вершин в которых <tex>m_1</tex> и <tex>m_2</tex> соответственно. Каждая вершина <tex>P</tex> встречается только в одном из двух многоугольников <tex>P_1</tex> и <tex>P_2</tex>, за исключением тех, которые являются концами <tex>d</tex>, поэтому справедливо следующее: <tex>m_1 + m_2 = n + 2</tex>. По индукции, любая триангуляция <tex>P_i</tex> состоит из <tex>m_i - 2</tex> треугольников, откуда следует, что <tex>T_P</tex>. состоит из <tex>(m_1 - 2) + (m_2 - 2) = n - 2</tex> треугольников.
}}

== Способы нахождения триангуляции ==
=== Примитивный алгоритм ===
В общем случае в произвольном <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>P</tex> не <tex>y</tex>-монотонный. Тогда докажем, что <tex>P</tex> содержит split и merge вершины. Поскольку <tex>P</tex> не <tex>y</tex>-монотонный, горизонтальная прямая <tex>l</tex> пересекает его стороны более двух раз. Выберем <tex>l</tex> таким образом, чтобы самой левой компонентой пересечения <tex>l</tex> и <tex>P</tex> был бы отрезок <tex>pq</tex>. Далее будем двигаться наверх по сторонам <tex>P</tex>, начиная от точки <tex>q</tex>. В результате в некоторой точке <tex>r</tex>, где <tex>r \neq p</tex> (случай '''(a)''' на рисунке), прямая <tex>l</tex> снова пересечёт одну из сторон <tex>P</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам <tex>P</tex>, будет split вершиной.

[[Файл:Proof_lemma.jpg|450px]]

Если же <tex>r = p</tex> (случай '''(b)''' на рисунке), начём опять двигаться по сторонам <tex>P</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка <tex>r'</tex>, которая будет результатом пересечения <tex>l</tex> и <tex>P</tex>. При этом <tex>r' \neq p</tex>, в противном случае <tex>l</tex> будет пересекать <tex>P</tex> только два раза, то есть <tex>P</tex> будет <tex>y</tex>-монотонным, что противоречит нашему предположению. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.
}}

===== Алгоритм =====
Чтобы сделать многоугольник монотонным, нужно избавиться от split и merge вершин путём проведения непересекающихся дигоналей из таких вершин.

Рассмотрим заметающую прямую <tex>l</tex>, перпендукулярную <tex>y</tex>-оси, будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, у которой расстояние до <tex>l</tex> минимально, при этом она должна лежать соответственно выше или ниже <tex>l</tex>.
[[Файл:Split_case.jpg|200px|thumb|right|Обработка ''split'' вершины <tex>v_i</tex>]] Рассмотрим каждый случай подробнее:

1) '''''Split вершина'''''. Пусть <tex>e_j</tex> и <tex>e_k</tex> — ближайшее левое и правое ребро относительно split вершины <tex>v_i</tex>, которые <tex>l</tex> пересекает в данный момент. Нам нужно найти вершину, лежащую между <tex>e_j</tex> и <tex>e_k</tex>, наиболее приближённую к <tex>l</tex>, либо если такой точки не существет выбрать минимальную из верхних вершин <tex>e_j</tex> и <tex>e_k</tex>. Для этого будем хранить указатель на искомую вершину у левого ребра <tex>e_j</tex>, который можно заранее вычислить. Тип вершины, хранящийся в <tex>helper</tex> не имеет значения. Таким образом, чтобы построить диагональ для split вершины нужно обратиться к указателю <tex>helper</tex> её левого ребра, которое <tex>l</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>v_{i}v_{m}</tex>. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.
[[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''megre'' вершины <tex>v_i</tex>. На рисунке слева <tex>v_i</tex> записывается в качестве <tex>helper</tex>'а своего левого ребра. На правом рисунке ближайшая вершина <tex>v_m</tex> при обращении к своему левому ребру <tex>helper(e_j)</tex> находит <tex>v_i</tex> и образует диагональ <tex>v_{i}v_m</tex>]]

===== Структуры данных =====
В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска <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(D);
Construct(Q); // функция Construct создаёт объекты <tex>D</tex> и <tex>Q</tex> , описанные выше.
bst T = new bst();
while Q <tex> \neq \varnothing </tex>
Remove <tex>v_{max}</tex> from Q // удаление вершины с наивысшим приоритетом из <tex>Q</tex>
switch (Type_of_vertex(<tex>v_{max}</tex>)): //определение типа вершины
case 'start':
HandleStartVertex(<tex>v_{max}</tex>);
case 'end':
HandleEndVertex(<tex>v_{max}</tex>);
case 'split':
HandleSplitVertex(<tex>v_{max}</tex>);
case 'merge':
HandleMergeVertex(<tex>v_{max}</tex>);
case 'regular':
HandleRegularVertex(<tex>v_{max}</tex>);

[[Файл:Split-merge - result.png|470px]]

Опишем теперь каждый метод из последнего switch:

HandleStartVertex(<tex>v_{i}</tex>)
Insert <tex>e_{i}</tex> in T
<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 T
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>
Insert <tex>e_{i}</tex> in T
<tex>helper(e_{i}) \leftarrow v_i</tex>

В последующих трех функциях обработки вершины <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 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 \cap P</tex>
Search <tex>e_j</tex> in T
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>

HandleRegularVertex(<tex>v_{i}</tex>)
if (interior of <tex>P</tex> lies to the right of <tex>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 D
Delete <tex>e_{i-1}</tex> from T
Insert <tex>e_{i}</tex> in T
<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 T
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>

===== Корректность =====

{{Лемма
|statement=
Функция ''MakeMonotone(P)'' корректно выполняет разбиение многоугольника <tex>P</tex>. Другими словами эта функция добавляет в <tex>P</tex> множество непересекающихся диагоналей, которые разбивают <tex>P</tex> на монотонные части.
|proof=
Тот факт, что <tex>P</tex> разбивается на монотонные части следует из предыдущей леммы.
Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, не попарно не пересекаются и не пересекают стороны <tex>P</tex>.

Рассмотрим случай выполнения функции ''HandleSplitVertex'', поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершин, в отличие от остальных функций (в них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной).

Допустим, что диагональ <tex>v_{i}v_{m}</tex> была построена с помощью ''HandleSplitVertex'' по достижению split вершины <tex>v_i</tex>. Рассмотрим четырёхугольник <tex>H</tex>, заключённый между <tex>e_j</tex> и <tex>e_k</tex> - левым и правым ребром относительно <tex>v_i</tex> и горизонтальными прямыми, проведёнными через <tex>v_i</tex> и <tex>v_m</tex>. Внутри <tex>H</tex>, не может находиться ни одной из вершин <tex>P</tex>, в противном случае <tex>helper(e_j)</tex> не равнялся бы <tex>v_m</tex>. Предположим теперь, что <tex>v_{i}v_{m}</tex> пересекает <tex>e_s</tex> одну из сторон <tex>P</tex>. Учитывая, что никаких вершин <tex>P</tex> не лежит внутри <tex>H</tex> и стороны <tex>P</tex> не пересекаются, то <tex>e_s</tex> должна пересечь либо отрезок, соединяющий <tex>e_j</tex> и <tex>v_m</tex>, либо <tex>e_j</tex> и <tex>v_i</tex>.[[Файл:Pic_of_correctness.jpg‎|400px|thumb|right|1) Вершин внутри <tex>H</tex> находиться не может; 2) <tex>v_{i}v_m</tex> может пересекать только рёбра, помеченные зелёным]] Такое возможно только в случае, когда точками пересечения будут являться <tex>v_i</tex> или <tex>v_m</tex>, что не противоречит условию. Отсюда <tex>v_{i}v_{m}</tex> не пересекает ни одну из сторон <tex>P</tex> в посторонних точках.

Теперь рассмотрим случай с пересечением добавленной ранее диагональю. Поскольку внутри <tex>H</tex> никаких вершин вершин находиться не может, и оба конца любой добавленной ранее диагонали должны лежать выше <tex>v_i</tex>, диагональ <tex>v_{i}v_m</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>.

==== Общая оценка ====
[[Файл:Monotone with holes.png|350px|thumb|right|Пример отверстия в форме монотонного многоугольника. У него обязательно будут существовать start и end вершина, если рассматривать его как обычный многоугольник. Однако, когда он станет полигональным отверстием, в силу определения start и end вершины обратятся в split и merge, которые соединятся с какими-то вершинами внешнего контура]]
Разбиение многоугольника на монотонные части занимает <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> по памяти.

==== Прочие случаи ====
Алгоритм так же работает и для частных случаев, например для многоугольника с полигональным отверстием. Такой многоугольник будет поделен на части без отверстий и будет успешно триангулирован. Это обуславливается тем, что хотя бы две вершины, принадлежащих отверстию будут split и merge (см. рисунок). Диагональ от таких вершин можно провести только до вершин внешнего контура, а поскольку у внутреннего отверстия хотя бы одна split и одна merge вершина весь многоугольник будет разделён как минимум на две части.

=== Ушной метод ===
{{Определение
|definition=
Вершина <tex>v_i</tex> называется '''ухом''', если диагональ <tex>v_{i-1}v_{i+1}</tex> лежит строго во внутренней области многоугольника <tex>P</tex>
}}

==== Идея ====
Рассмотрим все вершины многоугольника, и где возможно, будем отрезать уши.

== Источники ==
* Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0 Chapter 3: Polygon Triangulation: pp.45–61.

Триангуляция полигонов (ушная + монотонная)

2012-05-09T15:07:29Z

Muravyov: /* Примитивный алгоритм */

'''Триангуляция полигона ''' — декомпозиция многоугольника <tex>P</tex> на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет <tex>P</tex>. В строгом смысле слова, вершины этих треугольников должны совпадать с вершинами исходного многоугольника. Триангуляция любого многоугольника не единственна. В этом можно убедиться из примера на рисунке. [[Файл:2_examples_of_tringl.jpg‎|300px|thumb|right|Два способа триангуляции одной и той же фигуры]]

== Постановка задачи ==

На плоскости задан произвольный многоугольник. Стороны многоугольника не пересекаются. Требуется найти его триангуляцию.

== Теорема о существовании трингуляции ==

'''Простым многоугольником''' является фигура, ограниченная одной замкнутой ломаной, стороны которой не пересекаются. Таким образом, случаи многоугольников с дырками в теореме исключаются.
{{Теорема
|about = О существовании триангуляции многоугольника
|statement =
У любого простого <tex>n</tex>-вершинного многоугольника <tex>P</tex> всегда существует триангуляция, причём количество треугольников в ней <tex>n - 2</tex> независимо от самой триангуляции.
|proof=
[[Файл:Proof theorem.jpg|200px|thumb|right|Два случая в доказательстве теоремы]]
Доказательство ведётся индуктивно по <tex>n</tex>. При <tex>n = 3</tex> теорема тривиальна. Рассмотрим случай при <tex>n > 3</tex> и предположим, что теорема выполняется при всех <tex>m < n</tex>. Докажем существование диагонали в многоугольнике <tex>P</tex>. Возьмём самую левую по оси <tex>x</tex> вершину <tex>v</tex> многоугольника <tex>P</tex> и две смежных с ней вершины <tex>u</tex> и <tex>w</tex>. Если отрезок <tex>uw</tex> принадлежит внутренней области <tex>P</tex> — мы нашли диагональ. В противном случае, во внутренней области треугольника <tex>\Delta uwv</tex> или на самом отрезке <tex>uw</tex> содержится одна или несколько вершин <tex>P</tex>. Выберем самую наиболее далеко отстоящую от <tex>uw</tex> вершину <tex>v'</tex>. Отрезок, соединяющий <tex>v</tex> и <tex>v'</tex> не может пересекать сторон <tex>P</tex>, поскольку в противном случае одна из вершин это отрезка будет располагаться дальше от <tex>uw</tex>, чем <tex>v'</tex>. Это противоречит условию выбора <tex>v'</tex>. В итоге получаем, что <tex>v'v</tex> — диагональ.
Любая диагональ делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>. За <tex>m_1</tex> и <tex>m_2</tex> обозначим количество вершин в <tex>P_1</tex> и <tex>P_2</tex> соответственно. <tex>m_1 < n</tex> и <tex>m_2 < n</tex>, поэтому по предположению индукции у <tex>P_1</tex> и <tex>P_2</tex> существует триангуляция, следовательно и у <tex>P</tex> она существует.

Докажем, что триангуляция <tex>P</tex> состоит из <tex>n - 2</tex> треугольников. Рассмотрим произвольную диагональ <tex>d</tex> в триангуляции <tex>T_P</tex>. <tex>d</tex> делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>, количество вершин в которых <tex>m_1</tex> и <tex>m_2</tex> соответственно. Каждая вершина <tex>P</tex> встречается только в одном из двух многоугольников <tex>P_1</tex> и <tex>P_2</tex>, за исключением тех, которые являются концами <tex>d</tex>, поэтому справедливо следующее: <tex>m_1 + m_2 = n + 2</tex>. По индукции, любая триангуляция <tex>P_i</tex> состоит из <tex>m_i - 2</tex> треугольников, откуда следует, что <tex>T_P</tex>. состоит из <tex>(m_1 - 2) + (m_2 - 2) = n - 2</tex> треугольников.
}}

== Способы нахождения триангуляции ==
=== Примитивный алгоритм ===
В общем случае в произвольном <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>P</tex> не <tex>y</tex>-монотонный. Тогда докажем, что <tex>P</tex> содержит split и merge вершины. Поскольку <tex>P</tex> не <tex>y</tex>-монотонный, горизонтальная прямая <tex>l</tex> пересекает его стороны более двух раз. Выберем <tex>l</tex> таким образом, чтобы самой левой компонентой пересечения <tex>l</tex> и <tex>P</tex> был бы отрезок <tex>pq</tex>. Далее будем двигаться наверх по сторонам <tex>P</tex>, начиная от точки <tex>q</tex>. В результате в некоторой точке <tex>r</tex>, где <tex>r \neq p</tex> (случай '''(a)''' на рисунке), прямая <tex>l</tex> снова пересечёт одну из сторон <tex>P</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам <tex>P</tex>, будет split вершиной.

[[Файл:Proof_lemma.jpg|450px]]

Если же <tex>r = p</tex> (случай '''(b)''' на рисунке), начём опять двигаться по сторонам <tex>P</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка <tex>r'</tex>, которая будет результатом пересечения <tex>l</tex> и <tex>P</tex>. При этом <tex>r' \neq p</tex>, в противном случае <tex>l</tex> будет пересекать <tex>P</tex> только два раза, то есть <tex>P</tex> будет <tex>y</tex>-монотонным, что противоречит нашему предположению. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.
}}

===== Алгоритм =====
Чтобы сделать многоугольник монотонным, нужно избавиться от split и merge вершин путём проведения непересекающихся дигоналей из таких вершин.

Рассмотрим заметающую прямую <tex>l</tex>, перпендукулярную <tex>y</tex>-оси, будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, у которой расстояние до <tex>l</tex> минимально, при этом она должна лежать соответственно выше или ниже <tex>l</tex>.
[[Файл:Split_case.jpg|200px|thumb|right|Обработка ''split'' вершины <tex>v_i</tex>]] Рассмотрим каждый случай подробнее:

1) '''''Split вершина'''''. Пусть <tex>e_j</tex> и <tex>e_k</tex> — ближайшее левое и правое ребро относительно split вершины <tex>v_i</tex>, которые <tex>l</tex> пересекает в данный момент. Нам нужно найти вершину, лежащую между <tex>e_j</tex> и <tex>e_k</tex>, наиболее приближённую к <tex>l</tex>, либо если такой точки не существет выбрать минимальную из верхних вершин <tex>e_j</tex> и <tex>e_k</tex>. Для этого будем хранить указатель на искомую вершину у левого ребра <tex>e_j</tex>, который можно заранее вычислить. Тип вершины, хранящийся в <tex>helper</tex> не имеет значения. Таким образом, чтобы построить диагональ для split вершины нужно обратиться к указателю <tex>helper</tex> её левого ребра, которое <tex>l</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>v_{i}v_{m}</tex>. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.
[[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''megre'' вершины <tex>v_i</tex>. На рисунке слева <tex>v_i</tex> записывается в качестве <tex>helper</tex>'а своего левого ребра. На правом рисунке ближайшая вершина <tex>v_m</tex> при обращении к своему левому ребру <tex>helper(e_j)</tex> находит <tex>v_i</tex> и образует диагональ <tex>v_{i}v_m</tex>]]

===== Структуры данных =====
В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска <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(D);
Construct(Q); // функция Construct создаёт объекты <tex>D</tex> и <tex>Q</tex> , описанные выше.
bst T = new bst();
while Q <tex> \neq \varnothing </tex>
Remove <tex>v_{max}</tex> from Q // удаление вершины с наивысшим приоритетом из <tex>Q</tex>
switch (Type_of_vertex(<tex>v_{max}</tex>)): //определение типа вершины
case 'start':
HandleStartVertex(<tex>v_{max}</tex>);
case 'end':
HandleEndVertex(<tex>v_{max}</tex>);
case 'split':
HandleSplitVertex(<tex>v_{max}</tex>);
case 'merge':
HandleMergeVertex(<tex>v_{max}</tex>);
case 'regular':
HandleRegularVertex(<tex>v_{max}</tex>);

[[Файл:Split-merge - result.png|470px]]

Опишем теперь каждый метод из последнего switch:

HandleStartVertex(<tex>v_{i}</tex>)
Insert <tex>e_{i}</tex> in T
<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 T
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>
Insert <tex>e_{i}</tex> in T
<tex>helper(e_{i}) \leftarrow v_i</tex>

В последующих трех функциях обработки вершины <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 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 \cap P</tex>
Search <tex>e_j</tex> in T
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>

HandleRegularVertex(<tex>v_{i}</tex>)
if (interior of <tex>P</tex> lies to the right of <tex>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 D
Delete <tex>e_{i-1}</tex> from T
Insert <tex>e_{i}</tex> in T
<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 T
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>

===== Корректность =====

{{Лемма
|statement=
Функция ''MakeMonotone(P)'' корректно выполняет разбиение многоугольника <tex>P</tex>. Другими словами эта функция добавляет в <tex>P</tex> множество непересекающихся диагоналей, которые разбивают <tex>P</tex> на монотонные части.
|proof=
Тот факт, что <tex>P</tex> разбивается на монотонные части следует из предыдущей леммы.
Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, не попарно не пересекаются и не пересекают стороны <tex>P</tex>.

Рассмотрим случай выполнения функции ''HandleSplitVertex'', поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершин, в отличие от остальных функций (в них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной).

Допустим, что диагональ <tex>v_{i}v_{m}</tex> была построена с помощью ''HandleSplitVertex'' по достижению split вершины <tex>v_i</tex>. Рассмотрим четырёхугольник <tex>H</tex>, заключённый между <tex>e_j</tex> и <tex>e_k</tex> - левым и правым ребром относительно <tex>v_i</tex> и горизонтальными прямыми, проведёнными через <tex>v_i</tex> и <tex>v_m</tex>. Внутри <tex>H</tex>, не может находиться ни одной из вершин <tex>P</tex>, в противном случае <tex>helper(e_j)</tex> не равнялся бы <tex>v_m</tex>. Предположим теперь, что <tex>v_{i}v_{m}</tex> пересекает <tex>e_s</tex> одну из сторон <tex>P</tex>. Учитывая, что никаких вершин <tex>P</tex> не лежит внутри <tex>H</tex> и стороны <tex>P</tex> не пересекаются, то <tex>e_s</tex> должна пересечь либо отрезок, соединяющий <tex>e_j</tex> и <tex>v_m</tex>, либо <tex>e_j</tex> и <tex>v_i</tex>.[[Файл:Pic_of_correctness.jpg‎|400px|thumb|right|1) Вершин внутри <tex>H</tex> находиться не может; 2) <tex>v_{i}v_m</tex> может пересекать только рёбра, помеченные зелёным]] Такое возможно только в случае, когда точками пересечения будут являться <tex>v_i</tex> или <tex>v_m</tex>, что не противоречит условию. Отсюда <tex>v_{i}v_{m}</tex> не пересекает ни одну из сторон <tex>P</tex> в посторонних точках.

Теперь рассмотрим случай с пересечением добавленной ранее диагональю. Поскольку внутри <tex>H</tex> никаких вершин вершин находиться не может, и оба конца любой добавленной ранее диагонали должны лежать выше <tex>v_i</tex>, диагональ <tex>v_{i}v_m</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 вершина весь многоугольник будет разделён как минимум на две части.

=== Ушной метод ===
// ещё допишу.

== Источники ==
* Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0 Chapter 3: Polygon Triangulation: pp.45–61.

Триангуляция полигонов (ушная + монотонная)

2012-05-09T07:17:34Z

Muravyov:

'''Триангуляция полигона ''' — декомпозиция многоугольника <tex>P</tex> на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет <tex>P</tex>. В строгом смысле слова, вершины этих треугольников должны совпадать с вершинами исходного многоугольника. Триангуляция любого многоугольника не единственна. В этом можно убедиться из примера на рисунке. [[Файл:2_examples_of_tringl.jpg‎|300px|thumb|right|Два способа триангуляции одной и той же фигуры]]

== Постановка задачи ==

На плоскости задан произвольный многоугольник. Стороны многоугольника не пересекаются. Требуется найти его триангуляцию.

== Теорема о существовании трингуляции ==

'''Простым многоугольником''' является фигура, ограниченная одной замкнутой ломаной, стороны которой не пересекаются. Таким образом, случаи многоугольников с дырками в теореме исключаются.
{{Теорема
|about = О существовании триангуляции многоугольника
|statement =
У любого простого <tex>n</tex>-вершинного многоугольника <tex>P</tex> всегда существует триангуляция, причём количество треугольников в ней <tex>n - 2</tex> независимо от самой триангуляции.
|proof=
[[Файл:Proof theorem.jpg|200px|thumb|right|Два случая в доказательстве теоремы]]
Доказательство ведётся индуктивно по <tex>n</tex>. При <tex>n = 3</tex> теорема тривиальна. Рассмотрим случай при <tex>n > 3</tex> и предположим, что теорема выполняется при всех <tex>m < n</tex>. Докажем существование диагонали в многоугольнике <tex>P</tex>. Возьмём самую левую по оси <tex>x</tex> вершину <tex>v</tex> многоугольника <tex>P</tex> и две смежных с ней вершины <tex>u</tex> и <tex>w</tex>. Если отрезок <tex>uw</tex> принадлежит внутренней области <tex>P</tex> — мы нашли диагональ. В противном случае, во внутренней области треугольника <tex>\Delta uwv</tex> или на самом отрезке <tex>uw</tex> содержится одна или несколько вершин <tex>P</tex>. Выберем самую наиболее далеко отстоящую от <tex>uw</tex> вершину <tex>v'</tex>. Отрезок, соединяющий <tex>v</tex> и <tex>v'</tex> не может пересекать сторон <tex>P</tex>, поскольку в противном случае одна из вершин это отрезка будет располагаться дальше от <tex>uw</tex>, чем <tex>v'</tex>. Это противоречит условию выбора <tex>v'</tex>. В итоге получаем, что <tex>v'v</tex> — диагональ.
Любая диагональ делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>. За <tex>m_1</tex> и <tex>m_2</tex> обозначим количество вершин в <tex>P_1</tex> и <tex>P_2</tex> соответственно. <tex>m_1 < n</tex> и <tex>m_2 < n</tex>, поэтому по предположению индукции у <tex>P_1</tex> и <tex>P_2</tex> существует триангуляция, следовательно и у <tex>P</tex> она существует.

Докажем, что триангуляция <tex>P</tex> состоит из <tex>n - 2</tex> треугольников. Рассмотрим произвольную диагональ <tex>d</tex> в триангуляции <tex>T_P</tex>. <tex>d</tex> делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>, количество вершин в которых <tex>m_1</tex> и <tex>m_2</tex> соответственно. Каждая вершина <tex>P</tex> встречается только в одном из двух многоугольников <tex>P_1</tex> и <tex>P_2</tex>, за исключением тех, которые являются концами <tex>d</tex>, поэтому справедливо следующее: <tex>m_1 + m_2 = n + 2</tex>. По индукции, любая триангуляция <tex>P_i</tex> состоит из <tex>m_i - 2</tex> треугольников, откуда следует, что <tex>T_P</tex>. состоит из <tex>(m_1 - 2) + (m_2 - 2) = n - 2</tex> треугольников.
}}

== Способы нахождения триангуляции ==
=== Примитивный алгоритм ===
В общем случае в произвольном <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>P</tex> не <tex>y</tex>-монотонный. Тогда докажем, что <tex>P</tex> содержит split и merge вершины. Поскольку <tex>P</tex> не <tex>y</tex>-монотонный, горизонтальная прямая <tex>l</tex> пересекает его стороны более двух раз. Выберем <tex>l</tex> таким образом, чтобы самой левой компонентой пересечения <tex>l</tex> и <tex>P</tex> был бы отрезок <tex>pq</tex>. Далее будем двигаться наверх по сторонам <tex>P</tex>, начиная от точки <tex>q</tex>. В результате в некоторой точке <tex>r</tex>, где <tex>r \neq p</tex> (случай '''(a)''' на рисунке), прямая <tex>l</tex> снова пересечёт одну из сторон <tex>P</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам <tex>P</tex>, будет split вершиной.

[[Файл:Proof_lemma.jpg|450px]]

Если же <tex>r = p</tex> (случай '''(b)''' на рисунке), начём опять двигаться по сторонам <tex>P</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка <tex>r'</tex>, которая будет результатом пересечения <tex>l</tex> и <tex>P</tex>. При этом <tex>r' \neq p</tex>, в противном случае <tex>l</tex> будет пересекать <tex>P</tex> только два раза, то есть <tex>P</tex> будет <tex>y</tex>-монотонным, что противоречит нашему предположению. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.
}}

===== Алгоритм =====
Чтобы сделать многоугольник монотонным, нужно избавиться от split и merge вершин путём проведения непересекающихся дигоналей из таких вершин.

Рассмотрим заметающую прямую <tex>l</tex>, перпендукулярную <tex>y</tex>-оси, будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, у которой расстояние до <tex>l</tex> минимально, при этом она должна лежать соответственно выше или ниже <tex>l</tex>.
[[Файл:Split_case.jpg|200px|thumb|right|Обработка ''split'' вершины <tex>v_i</tex>]] Рассмотрим каждый случай подробнее:

1) '''''Split вершина'''''. Пусть <tex>e_j</tex> и <tex>e_k</tex> — ближайшее левое и правое ребро относительно split вершины <tex>v_i</tex>, которые <tex>l</tex> пересекает в данный момент. Нам нужно найти вершину, лежащую между <tex>e_j</tex> и <tex>e_k</tex>, наиболее приближённую к <tex>l</tex>, либо если такой точки не существет выбрать минимальную из верхних вершин <tex>e_j</tex> и <tex>e_k</tex>. Для этого будем хранить указатель на искомую вершину у левого ребра <tex>e_j</tex>, который можно заранее вычислить. Тип вершины, хранящийся в <tex>helper</tex> не имеет значения. Таким образом, чтобы построить диагональ для split вершины нужно обратиться к указателю <tex>helper</tex> её левого ребра, которое <tex>l</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>v_{i}v_{m}</tex>. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.
[[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''megre'' вершины <tex>v_i</tex>. На рисунке слева <tex>v_i</tex> записывается в качестве <tex>helper</tex>'а своего левого ребра. На правом рисунке ближайшая вершина <tex>v_m</tex> при обращении к своему левому ребру <tex>helper(e_j)</tex> находит <tex>v_i</tex> и образует диагональ <tex>v_{i}v_m</tex>]]

===== Структуры данных =====
В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска <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(D);
Construct(Q); // функция Construct создаёт объекты <tex>D</tex> и <tex>Q</tex> , описанные выше.
bst T = new bst();
while Q <tex> \neq \varnothing </tex>
Remove <tex>v_{max}</tex> from Q // удаление вершины с наивысшим приоритетом из <tex>Q</tex>
switch (Type_of_vertex(<tex>v_{max}</tex>)): //определение типа вершины
case 'start':
HandleStartVertex(<tex>v_{max}</tex>);
case 'end':
HandleEndVertex(<tex>v_{max}</tex>);
case 'split':
HandleSplitVertex(<tex>v_{max}</tex>);
case 'merge':
HandleMergeVertex(<tex>v_{max}</tex>);
case 'regular':
HandleRegularVertex(<tex>v_{max}</tex>);

[[Файл:Split-merge - result.png|470px]]

Опишем теперь каждый метод из последнего switch:

HandleStartVertex(<tex>v_{i}</tex>)
Insert <tex>e_{i}</tex> in T
<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 T
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>
Insert <tex>e_{i}</tex> in T
<tex>helper(e_{i}) \leftarrow v_i</tex>

В последующих трех функциях обработки вершины <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 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 \cap P</tex>
Search <tex>e_j</tex> in T
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>

HandleRegularVertex(<tex>v_{i}</tex>)
if (interior of <tex>P</tex> lies to the right of <tex>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 D
Delete <tex>e_{i-1}</tex> from T
Insert <tex>e_{i}</tex> in T
<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 T
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>

===== Корректность =====

{{Лемма
|statement=
Функция ''MakeMonotone(P)'' корректно выполняет разбиение многоугольника <tex>P</tex>. Другими словами эта функция добавляет в <tex>P</tex> множество непересекающихся диагоналей, которые разбивают <tex>P</tex> на монотонные части.
|proof=
Тот факт, что <tex>P</tex> разбивается на монотонные части следует из предыдущей леммы.
Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, не попарно не пересекаются и не пересекают стороны <tex>P</tex>.

Рассмотрим случай выполнения функции ''HandleSplitVertex'', поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершин, в отличие от остальных функций (в них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной).

Допустим, что диагональ <tex>v_{i}v_{m}</tex> была построена с помощью ''HandleSplitVertex'' по достижению split вершины <tex>v_i</tex>. Рассмотрим четырёхугольник <tex>H</tex>, заключённый между <tex>e_j</tex> и <tex>e_k</tex> - левым и правым ребром относительно <tex>v_i</tex> и горизонтальными прямыми, проведёнными через <tex>v_i</tex> и <tex>v_m</tex>. Внутри <tex>H</tex>, не может находиться ни одной из вершин <tex>P</tex>, в противном случае <tex>helper(e_j)</tex> не равнялся бы <tex>v_m</tex>. Предположим теперь, что <tex>v_{i}v_{m}</tex> пересекает <tex>e_s</tex> одну из сторон <tex>P</tex>. Учитывая, что никаких вершин <tex>P</tex> не лежит внутри <tex>H</tex> и стороны <tex>P</tex> не пересекаются, то <tex>e_s</tex> должна пересечь либо отрезок, соединяющий <tex>e_j</tex> и <tex>v_m</tex>, либо <tex>e_j</tex> и <tex>v_i</tex>.[[Файл:Pic_of_correctness.jpg‎|400px|thumb|right|1) Вершин внутри <tex>H</tex> находиться не может; 2) <tex>v_{i}v_m</tex> может пересекать только рёбра, помеченные зелёным]] Такое возможно только в случае, когда точками пересечения будут являться <tex>v_i</tex> или <tex>v_m</tex>, что не противоречит условию. Отсюда <tex>v_{i}v_{m}</tex> не пересекает ни одну из сторон <tex>P</tex> в посторонних точках.

Теперь рассмотрим случай с пересечением добавленной ранее диагональю. Поскольку внутри <tex>H</tex> никаких вершин вершин находиться не может, и оба конца любой добавленной ранее диагонали должны лежать выше <tex>v_i</tex>, диагональ <tex>v_{i}v_m</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 вершина весь многоугольник будет разделён как минимум на две части.

=== Ушной метод ===
// ещё допишу.

== Источники ==
* Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000), Computational Geometry (2nd revised ed.), Springer-Verlag, ISBN 3-540-65620-0 Chapter 3: Polygon Triangulation: pp.45–61.

Триангуляция полигонов (ушная + монотонная)

2012-05-08T19:45:42Z

Muravyov: Новая страница: «'''Триангуляция полигона ''' — декомпозиция многоугольника <tex>P</tex> на множество треуголь...»

'''Триангуляция полигона ''' — декомпозиция многоугольника <tex>P</tex> на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет <tex>P</tex>. В строгом смысле слова, вершины этих треугольников должны совпадать с вершинами исходного многоугольника. Триангуляция любого многоугольника не единственна. В этом можно убедиться из примера на рисунке. [[Файл:2_examples_of_tringl.jpg‎|300px|thumb|right|Два способа триангуляции одной и той же фигуры]]

== Постановка задачи ==

На плоскости задан произвольный многоугольник. Стороны многоугольника не пересекаются. Требуется найти его триангуляцию.

== Теорема о существовании трингуляции ==

'''Простым многоугольником''' является фигура, ограниченная одной замкнутой ломаной, стороны которой не пересекаются. Таким образом, случаи многоугольников с дырками в теореме исключаются.
{{Теорема
|about = О существовании триангуляции многоугольника
|statement =
У любого простого <tex>n</tex>-вершинного многоугольника <tex>P</tex> всегда существует триангуляция, причём количество треугольников в ней <tex>n - 2</tex> независимо от самой триангуляции.
|proof=
[[Файл:Proof theorem.jpg|200px|thumb|right|Два случая в доказательстве теоремы]]
Доказательство ведётся индуктивно по <tex>n</tex>. При <tex>n = 3</tex> теорема тривиальна. Рассмотрим случай при <tex>n > 3</tex> и предположим, что теорема выполняется при всех <tex>m < n</tex>. Докажем существование диагонали в многоугольнике <tex>P</tex>. Возьмём самую левую по оси <tex>x</tex> вершину <tex>v</tex> многоугольника <tex>P</tex> и две смежных с ней вершины <tex>u</tex> и <tex>w</tex>. Если отрезок <tex>uw</tex> принадлежит внутренней области <tex>P</tex> — мы нашли диагональ. В противном случае, во внутренней области треугольника <tex>\Delta uwv</tex> или на самом отрезке <tex>uw</tex> содержится одна или несколько вершин <tex>P</tex>. Выберем самую наиболее далеко отстоящую от <tex>uw</tex> вершину <tex>v'</tex>. Отрезок, соединяющий <tex>v</tex> и <tex>v'</tex> не может пересекать сторон <tex>P</tex>, поскольку в противном случае одна из вершин это отрезка будет располагаться дальше от <tex>uw</tex>, чем <tex>v'</tex>. Это противоречит условию выбора <tex>v'</tex>. В итоге получаем, что <tex>v'v</tex> — диагональ.
Любая диагональ делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>. За <tex>m_1</tex> и <tex>m_2</tex> обозначим количество вершин в <tex>P_1</tex> и <tex>P_2</tex> соответственно. <tex>m_1 < n</tex> и <tex>m_2 < n</tex>, поэтому по предположению индукции у <tex>P_1</tex> и <tex>P_2</tex> существует триангуляция, следовательно и у <tex>P</tex> она существует.

Докажем, что триангуляция <tex>P</tex> состоит из <tex>n - 2</tex> треугольников. Рассмотрим произвольную диагональ <tex>d</tex> в триангуляции <tex>T_P</tex>. <tex>d</tex> делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>, количество вершин в которых <tex>m_1</tex> и <tex>m_2</tex> соответственно. Каждая вершина <tex>P</tex> встречается только в одном из двух многоугольников <tex>P_1</tex> и <tex>P_2</tex>, за исключением тех, которые являются концами <tex>d</tex>, поэтому справедливо следующее: <tex>m_1 + m_2 = n + 2</tex>. По индукции, любая триангуляция <tex>P_i</tex> состоит из <tex>m_i - 2</tex> треугольников, откуда следует, что <tex>T_P</tex>. состоит из <tex>(m_1 - 2) + (m_2 - 2) = n - 2</tex> треугольников.
}}

== Способы нахождения триангуляции ==
=== Примитивный алгоритм ===
В общем случае в произвольном <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>P</tex> не <tex>y</tex>-монотонный. Тогда докажем, что <tex>P</tex> содержит split и merge вершины. Поскольку <tex>P</tex> не <tex>y</tex>-монотонный, горизонтальная прямая <tex>l</tex> пересекает его стороны более двух раз. Выберем <tex>l</tex> таким образом, чтобы самой левой компонентой пересечения <tex>l</tex> и <tex>P</tex> был бы отрезок <tex>pq</tex>. Далее будем двигаться наверх по сторонам <tex>P</tex>, начиная от точки <tex>q</tex>. В результате в некоторой точке <tex>r</tex>, где <tex>r \neq p</tex> (случай '''(a)''' на рисунке), прямая <tex>l</tex> снова пересечёт одну из сторон <tex>P</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам <tex>P</tex>, будет split вершиной.

[[Файл:Proof_lemma.jpg|450px]]

Если же <tex>r = p</tex> (случай '''(b)''' на рисунке), начём опять двигаться по сторонам <tex>P</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка <tex>r'</tex>, которая будет результатом пересечения <tex>l</tex> и <tex>P</tex>. При этом <tex>r' \neq p</tex>, в противном случае <tex>l</tex> будет пересекать <tex>P</tex> только два раза, то есть <tex>P</tex> будет <tex>y</tex>-монотонным, что противоречит нашему предположению. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.
}}

===== Алгоритм =====
Чтобы сделать многоугольник монотонным, нужно избавиться от split и merge вершин путём проведения непересекающихся дигоналей из таких вершин.

Рассмотрим заметающую прямую <tex>l</tex>, перпендукулярную <tex>y</tex>-оси, будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, у которой расстояние до <tex>l</tex> минимально, при этом она должна лежать соответственно выше или ниже <tex>l</tex>.
[[Файл:Split_case.jpg|200px|thumb|right|Обработка ''split'' вершины <tex>v_i</tex>]] Рассмотрим каждый случай подробнее:

1) '''''Split вершина'''''. Пусть <tex>e_j</tex> и <tex>e_k</tex> — ближайшее левое и правое ребро относительно split вершины <tex>v_i</tex>, которые <tex>l</tex> пересекает в данный момент. Нам нужно найти вершину, лежащую между <tex>e_j</tex> и <tex>e_k</tex>, наиболее приближённую к <tex>l</tex>, либо если такой точки не существет выбрать минимальную из верхних вершин <tex>e_j</tex> и <tex>e_k</tex>. Для этого будем хранить указатель на искомую вершину у левого ребра <tex>e_j</tex>, который можно заранее вычислить. Тип вершины, хранящийся в <tex>helper</tex> не имеет значения. Таким образом, чтобы построить диагональ для split вершины нужно обратиться к указателю <tex>helper</tex> её левого ребра, которое <tex>l</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>v_{i}v_{m}</tex>. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.
[[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''megre'' вершины <tex>v_i</tex>. На рисунке слева <tex>v_i</tex> записывается в качестве <tex>helper</tex>'а своего левого ребра. На правом рисунке ближайшая вершина <tex>v_m</tex> при обращении к своему левому ребру <tex>helper(e_j)</tex> находит <tex>v_i</tex> и образует диагональ <tex>v_{i}v_m</tex>]]

===== Структуры данных =====
В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска <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(D);
Construct(Q); // функция Construct создаёт объекты <tex>D</tex> и <tex>Q</tex> , описанные выше.
bst T = new bst();
while Q <tex> \neq \varnothing </tex>
Remove <tex>v_{max}</tex> from Q // удаление вершины с наивысшим приоритетом из <tex>Q</tex>
switch (Type_of_vertex(<tex>v_{max}</tex>)): //определение типа вершины
case 'start':
HandleStartVertex(<tex>v_{max}</tex>);
case 'end':
HandleEndVertex(<tex>v_{max}</tex>);
case 'split':
HandleSplitVertex(<tex>v_{max}</tex>);
case 'merge':
HandleMergeVertex(<tex>v_{max}</tex>);
case 'regular':
HandleRegularVertex(<tex>v_{max}</tex>);

[[Файл:Split-merge - result.png|470px]]

Опишем теперь каждый метод из последнего switch:

HandleStartVertex(<tex>v_{i}</tex>)
Insert <tex>e_{i}</tex> in T
<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 T
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>
Insert <tex>e_{i}</tex> in T
<tex>helper(e_{i}) \leftarrow v_i</tex>

В последующих трех функциях обработки вершины <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 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 \cap P</tex>
Search <tex>e_j</tex> in T
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>

HandleRegularVertex(<tex>v_{i}</tex>)
if (interior of <tex>P</tex> lies to the right of <tex>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 D
Delete <tex>e_{i-1}</tex> from T
Insert <tex>e_{i}</tex> in T
<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 T
if (Type_of_vertex(<tex>helper(e_{j})</tex> = 'merge')
Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D
<tex>helper(e_{j}) \leftarrow v_i</tex>

===== Корректность =====

{{Лемма
|statement=
Функция ''MakeMonotone(P)'' корректно выполняет разбиение многоугольника <tex>P</tex>. Другими словами эта функция добавляет в <tex>P</tex> множество непересекающихся диагоналей, которые разбивают <tex>P</tex> на монотонные части.
|proof=
Тот факт, что <tex>P</tex> разбивается на монотонные части следует из предыдущей леммы.
Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, не попарно не пересекаются и не пересекают стороны <tex>P</tex>.

Рассмотрим случай выполнения функции ''HandleSplitVertex'', поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершин, в отличие от остальных функций (в них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной).

Допустим, что диагональ <tex>v_{i}v_{m}</tex> была построена с помощью ''HandleSplitVertex'' по достижению split вершины <tex>v_i</tex>. Рассмотрим четырёхугольник <tex>H</tex>, заключённый между <tex>e_j</tex> и <tex>e_k</tex> - левым и правым ребром относительно <tex>v_i</tex> и горизонтальными прямыми, проведёнными через <tex>v_i</tex> и <tex>v_m</tex>. Внутри <tex>H</tex>, не может находиться ни одной из вершин <tex>P</tex>, в противном случае <tex>helper(e_j)</tex> не равнялся бы <tex>v_m</tex>. Предположим теперь, что <tex>v_{i}v_{m}</tex> пересекает <tex>e_s</tex> одну из сторон <tex>P</tex>. Учитывая, что никаких вершин <tex>P</tex> не лежит внутри <tex>H</tex> и стороны <tex>P</tex> не пересекаются, то <tex>e_s</tex> должна пересечь либо отрезок, соединяющий <tex>e_j</tex> и <tex>v_m</tex>, либо <tex>e_j</tex> и <tex>v_i</tex>.[[Файл:Pic_of_correctness.jpg‎|400px|thumb|right|1) Вершин внутри <tex>H</tex> находиться не может; 2) <tex>v_{i}v_m</tex> может пересекать только рёбра, помеченные зелёным]] Такое возможно только в случае, когда точками пересечения будут являться <tex>v_i</tex> или <tex>v_m</tex>, что не противоречит условию. Отсюда <tex>v_{i}v_{m}</tex> не пересекает ни одну из сторон <tex>P</tex> в посторонних точках.

Теперь рассмотрим случай с пересечением добавленной ранее диагональю. Поскольку внутри <tex>H</tex> никаких вершин вершин находиться не может, и оба конца любой добавленной ранее диагонали должны лежать выше <tex>v_i</tex>, диагональ <tex>v_{i}v_m</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 вершина весь многоугольник будет разделён как минимум на две части.

=== Ушной метод ===
// ещё допишу.

Вычислительная геометрия

2012-05-08T14:06:42Z

Muravyov: /* Псевдокод */