Изменения

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

|about = о сеченияхО существовании триангуляции многоугольника

Пусть У любого простого <tex> E \subset \mathbb R^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>\lambda_2 E 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 < + \infty 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> \forall x_1 \in \mathbb R : E(x_1) m_1 + m_2 = n + 2</tex> — измеримое множество.# По индукции, любая триангуляция <tex>P_i</tex> состоит из <tex> \lambda_1(E(x_1)) m_i - 2</tex> — измеримая на треугольников, откуда следует, что <tex> \mathbb R T_P</tex> функция.# состоит из <tex> \lambda_2(Em_1 - 2) = \int\limits_{\mathbb R} \lambda_1 + (E(x_1m_2 - 2)) d x_1 = n - 2</tex>треугольников.}}

Схема доказательства — такая жеПредположим, как что <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]]

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

<tex> E(x_1) = \begin{cases} [c, d] &, x_1 \in [a, b] \\ \varnothing &, x_1 \notin a==== Алгоритм =====Чтобы сделать многоугольник монотонным, b] \end{cases} </tex> — измеримонужно избавиться от split и merge вершин путём проведения непересекающихся дигоналей из таких вершин.

Рассмотрим заметающую прямую <tex> \lambda(E(x_1)) = \begin{cases} d l</tex>, перпендукулярную <tex>y</tex>- c &оси, x_1 \in [aбудем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, b] \\ 0 &когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, x_1 \notin [aу которой расстояние до <tex>l</tex> минимально, b] \end{cases} при этом она должна лежать соответственно выше или ниже <tex>l</tex> — кусочно-постоянная функция на оси, суммируема.[[Файл:Split_case.jpg|200px|thumb|right|Обработка ''split'' вершины <tex>v_i</tex>]] Рассмотрим каждый случай подробнее:

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

===== Структуры данных =====В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска <tex> G = \bigcup\limits_n \Delta_n (x_1) T</tex> , по 1) в листьях которого будем хранить рёбра, пересекающие <tex> \Delta_n (x_1) l</tex> — измеримо, а не болеетакие, чем счётное объединение измеримыхчто внутренняя область многоугольника будет лежать справа от них самих. С каждым таким ребром будем хранить его <tex>helper</tex>. Порядок следования листьев в дереве соответствует порядку следования рёбер в многоугольнике: слева направо. Дерево изменяется в зависимости от текущего состояния заметающей прямой. Создадим приоритетную очередь <tex>Q</tex> из вершин, в которой приоритетом будет <tex>y</tex>-координата вершины. Если две вершины имеют одинаковые <tex>y</tex>-координаты, измеримобольший приоритет у левой. Вершины будут добавляться на "остановках" заметающей прямой.

В силу сигма-аддитивности длиныМногоугольник <tex>P</меры Лебега, tex> и добавленные в процессе диагонали удобно хранить в виде спика <tex> \lambda_1(G(x_1)) = \sum\limits_n \lambda_1 (\Delta_n(x_1)) 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> \intneq \limits_varnothing </tex> Remove <tex>v_{\mathbb Rmax} \lambda_1</tex> from Q // удаление вершины с наивысшим приоритетом из <tex>Q</tex> switch (GType_of_vertex(x_1<tex>v_{max}</tex>)) dx = : //определение типа вершины case 'start': HandleStartVertex(<tex>v_{max}</tex> ); case 'end': HandleEndVertex(т. Леви <tex>v_{max}</tex>); case 'split': HandleSplitVertex(Но причем тут она? Надо пользоваться сигма-аддитивностью интеграла.)) <tex> \sum\limits_n \int\limits_v_{\mathbb Rmax} \lambda_1 (\Delta_n (x_1)</tex>) d x_1 = \sum\limits_n \lambda_2 ; case 'merge': HandleMergeVertex(\Delta_n<tex>v_{max}</tex>) = \lambda_2 ; case 'regular': HandleRegularVertex(G) <tex>v_{max}</tex>.);

3) <tex> E </tex> — множество типа <tex> G_\delta </tex> (не более, чем счётное пересечение открытых множеств)[[Файл:Split-merge - result.png|470px]]

По сигма-аддитивности, HandleStartVertex(<tex> \lambda_2 E = \lim\limits_v_{n \to \inftyi} \lambda_2 (G_n)</tex>. ) Insert <tex>E(x_1) = \bigcap\limits_n G_n(x_1) e_{i}</tex> — измеримо для любого in T <tex> x_1 helper(e_{i}) \leftarrow v_i</tex>.

HandleSplitVertex(<tex> v_{i}</tex>) edge <tex>e_j</tex> = <tex>l \lambda_1 cap P</tex> Search <tex>e_j</tex> in T Insert edge(E<tex>v_{i}</tex>, <tex>helper(x_1e_{i})</tex>)in D <tex>helper(e_{j}) = \lim\limits_leftarrow v_i</tex> Insert <tex>e_{n \to \inftyi} \lambda_1 </tex> in T <tex>helper(G_n(x_1)e_{i}) \leftarrow v_i</tex> — тоже измеримо(как предел измеримой функции).

HandleEndVertex(<tex> \int\limits_v_{\mathbb Ri} \lambda_1 </tex>) if (EType_of_vertex(x_1<tex>helper(e_{i-1})</tex> = 'merge') d x_1 = \lim\limits_ Insert edge(<tex>v_{n \to \inftyi} \int\limits_</tex>, <tex>helper(e_{\mathbb Ri-1} \lambda_1 (G_n(x_1)</tex>) d x_1 in D Delete <tex>e_{i-1}</tex>.from T

HandleMergeVertex(<tex>v_{i}</tex>) if (Type_of_vertex(<tex>helper(e_{i-1})</tex> = 'merge') Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i-1})</tex>) in D Delete <tex>e_{i-1}</tex> from T edge <tex>e_j</tex> = <tex>l \lambda_2 cap P</tex> Search <tex>e_j</tex> in T if (Type_of_vertex(<tex>helper(G_ne_{j}) \to \lambda_2</tex> = 'merge') Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D <tex>helper(Ee_{j}) \leftarrow v_i</tex>

4 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> E = 'merge') Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D <tex>helper(e_{j}) \leftarrow v_i</tex> — нульмерно.

Представим <tex> E </tex> как пересечение убывающих открытых множеств: <tex> E = \bigcap\limits_n G_n, G_{n + 1} \subset G_n </tex>. Для всех <tex> G_n </tex> теорема уже доказана.==== Корректность =====

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

Множество Лебега <tex> E(f \le a) </tex> Рассмотрим случай выполнения функции <tex> f = \lambda_1 (E(x_1)) </tex> тоже будет измеримо при любом <tex> a </tex> как пересечение измеримых множеств''HandleSplitVertex'', поскольку это наиболее общий случай: <tex> E(f \le a) = \bigcap\limits_n G_nsplit вершина может быть соединена со всеми типами вершин, в отличие от остальных функций (f \le aв них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной) </tex>.

По теореме Лебега о мажорируемой сходимости (так жеДопустим, что диагональ <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>, в 3противном случае <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> G_\delta 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> E(x_1) = K(x_1) \setminus (K \setminus E)(x_1) H</tex>никаких вершин вершин находиться не может, а почти все сечения множества и оба конца любой добавленной ранее диагонали должны лежать выше <tex> K \setminus E v_i</tex>, по пункту 4, имеют меру 0диагональ <tex>v_{i}v_m</tex> не может пересекать никакую из ранее добавленных диагоналей.

Из этого следует===== Оценкка работы =====Построение описанной выше приоритетной очереди <tex>Q</tex> происходит за линейное время. Когда заметающая прямая останавливается в вершине: операции с очередью занимают константу по времени, что операции с деревом <tex> T</tex> на запросы и обновления требуют <tex>\mathcal{O}(\mathcal \lambda_1 Elog(x_1n) )</tex>. Добавление диагонали в <tex>D</tex> требует <tex>\sim mathcal{O}(1)</tex>. В итоге обработка каждой вершины требует <tex>\lambda_1 Kmathcal{O}(x_1\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> \int\limits_{\mathbb R} \lambda_1 E (x_1) d x_1 когда мы достигнем красной вершины]]==== Триангуляция монотонного многоугольника == \int\limits_{\mathbb R} K(x_1) d x_1 = \lambda_2 K = \lambda_2 E </tex>.

===== Идея =====Будем проходить сверху вниз по вершинам многоугольника проводя диагонали где это возможно. Отсортируем все вершины многоугольника <tex>P</tex> в порядке убывания их <tex>y</tex>-координаты. Заведём стек вершин <tex>S</tex>. В стеке будем хранить вершины в отсортированном порядке, которые были обработаны, но не были отрезаны от многоугольника, то есть находятся в той части многоугольника, которая ещё не была триангулирована. В момент обработки некоторой вершины, будем пытаться провести из неё как можно больше диагоналей к вершинам, содержащимся в стеке. Эти диагонали отрезают треугольники от <tex>P</tex>. На вершине стека будет храниться вершина, которая будет обрабатываться последней. Часть многоугольника <tex>P</tex>, лежащая выше последней обработанной вершины <tex>v_i</tex> и которая ещё не была триангулирована имеет форму перевёрнутой воронки (см. рисунки). Одна сторона воронки состоит из одной из сторон <tex>P</tex>, а другая состоит из цепи вершин, которые лежат выше <tex>v_i</tex> и внутренние углы которых не меньше <tex>\pi</tex>. Несложно догадаться, что самая нижняя вершина стека является единственной выпуклой. Несложно также заметить, что при обработке следующей вершины свойство перевёрнутой воронки сохранится, то есть оно является инвариантом алгоритма. [[Файл:Triang_alg_case1.jpg|200px|thumb|right|Первый случай. Синим помечены стороны воронки, зелёным — диагонали, а жёлтым границы новой ещё не протриангулированной области]]===== Алгоритм =====Рассмотрим процесс обработки вершины более подробно. Возможны два случая:* Текущая вершина <tex>v_j</tex> является нижним концом стороны <tex>e</tex>, ограничивающего воронку. Вершины противоположной цепи уже были положены в стек. В этом случае можно просто построить диагонали, соединяющие <tex>v_j</tex> со всеми вершинами, находящимися в стеке, кроме последней. Последняя вершина в стеке уже соединена с <tex>v_j</tex> стороной <tex>e</tex>. Часть многоугольника <tex>P</tex>, лежащая выше <tex>v_j</tex>, которая не была триангулирована, ограничена диагональю, которая соединяет <tex>v_j</tex> с вершиной <tex>v_{s1}</tex>, которая была первой в стеке. Сторона многоугольника <tex>P</tex>, выходящая из <tex>v_{s1}</tex> направлена вниз. Снова образуется фигура c одним выпуклым углом, похожая на воронку — инвариант сохраняется. Вершины <tex>v_j</tex> и <tex>v_{s1}</tex> кладутся в стек, поскольку они были были обработаны, но по прежнему являются вершинами непротриангулированной части <tex>P</tex>. * Вершина <tex>v_j</tex> принадлежит последовательной цепи вершин, добавленных в <tex>S</tex>. Вынем из стека верхнюю вершину <tex>v_{s1}</tex> — она уже соединена с <tex>v_{j}</tex> одной из сторон <tex>P</tex>. Затем будем пытаться выстраивать диагонали, соединяющие <tex>v_{j}</tex> c вынимаемыми из стека вершинами пока это возможно. Проверку на возможность построения диагонали <tex>v_{j}v_{k}</tex>, где <tex>v_{k}</tex> — текущая верхняя вершина стека, можно осуществлять посредством изучения взаимного расположения предыдущей вершины, вынутой из <tex>S</tex>, относительно <tex>v_{j}v_{k}</tex>. Когда мы достигнем вершины <tex>v_{k}</tex>, до которой невозможно провести диагональ, положим предыдущую вершину <tex>v_{k-1}</tex> обратно в стек. Вершина <tex>v_{k-1}</tex> является либо последней, до которой было возможно провести диагональ, либо, если ни одной диагонали из <tex>v_{j}</tex> провести не удалось, — соседом <tex>v_{j}</tex>. Далее положим <tex>v_{j}</tex> в стек. Опять же инвариант непротриангулированной части <tex>P</tex> сохраняется: одна сторона воронки ограничена частью стороны многоугольника, а другая цепью невыпуклых вершин.[[Файл:Triang alg case2.jpg|500px|thumb|center|Второй случай. Синим помечена цепь из вершин, которая содержится в стеке <tex>S</tex> на момент достижения вершины <tex>v_j</tex>, рыжей помечена первая вершина, до которой невозможно провести диагональ, жёлтой помечена новая нетриангулированная область <tex>P</tex> в форме воронки]] ===== Псевдокод ===== Как ранее уже было отмечено, задаём <tex>P</tex> в виде рёберного списка c двойными связями <tex>D</tex>. TriangulateMonotonePolygon(P) vertex [n] V = new vertex(P); // массив вершин <tex>P</tex>, отсортированный по y-координате в порядке убывания. stack S = new stack(); S.push(V[1]); S.push(V[2]); for j \leftarrow 3 to n - 1 if (V[j] = S.peek()) while (S <tex>\neq \varnothing </tex>) if (S.size() <tex>\neq</tex> 1) Insert edge(V[j], S.peek()) in D S.pop() S.push(V[j-1]) S.push(V[j]); else vertex last = S.peek(); S.pop(); while (IsValidDiagonal(edge(V[j], S.peek()), last)) //проверка возможности построения диагонали — предикат "левый поворот" last = S.peek(); S.pop(); Insert edge(V[j], last) in D S.push(last); S.push(V[j]); S.pop() while (S <tex>\neq \varnothing </tex>) if (S.size() <tex>\neq</tex> 1) Insert edge(V[j], S.peek()) in D S.pop() ===== Корректность =====* Все построенные диагонали попарно не пересекаются. Это гарантируется тем, что при каждом просмотре определённой вершины рассматривается только та часть <tex>P'</tex> многоугольника <tex>P</tex>, которая не была протриангулирована, следовательно внутри этой области по определению не может лежать ни одной из уже построенных диагоналей. Несложно заметить, что в стеке <tex>S</tex> на каждой итерации главного цикла хранятся вершины, которые принадлежат именно <tex>P'</tex> и лежат выше рассматриваемой вершины.* Количество построенных диагоналей всегда будет <tex>n-3</tex>, поэтому непротриангулированных частей в многоугольнике не останется. ===== Оценка работы ===== Построение массива вершин требует линейное время и занимает линейную память. Главный цикл ''for'' выполняется <tex>n-3</tex> раза. Каждая его итерация может потребовать линейное время. Однако заметим, что на каждой итерации главного цикла в стек кладутся максимум две вершины, следовательно общее число выполнения операции ''push'', включая первые две вершины, положенные в начале алгоритма, ограничено <tex>2n-4</tex>. Количество операций ''pop'' за время работы алгоритма не превысит количества операций ''push''. Отсюда общее время работы цикла ''for'' <tex>\mathcal{O}(n)</tex>. В итоге общее время работы <tex>\mathcal{O}(n)</tex>. ==== Общая оценка ====Разбиение многоугольника на монотонные части занимает <tex>\mathcal{O}(n \log n)</tex> времени и <tex>\mathcal{O}(n)</tex> памяти. Триангуляция каждой из частей занимает линейную память и время. Учитывая то, что суммарное количество вершин во всех частях <tex>\mathcal{O}(n)</tex>, триангуляция всех частей займёт <tex>\mathcal{O}(n)</tex> по времени и по памяти. В итоге общая оценка составляет <tex>\mathcal{O}(n \log n)</tex> по времени и <tex>\mathcal{O}(n)</tex> по памяти. ==== Прочие случаи ====[[Файл:Monotone with holes.png|350px|thumb|right|Пример отверстия в форме монотонного многоугольника. У него обязательно будут существовать start и end вершина, если рассматривать его как обычный многоугольник. Однако, когда он станет полигональным отверстием, в силу определения start и end вершины обратятся в split и merge, которые соединятся с какими-то вершинами внешнего контура]]Алгоритм так же работает и для частных случаев, например для многоугольника с полигональным отверстием. Такой многоугольник будет поделен на части без отверстий и будет успешно триангулирован. Это обуславливается тем, что хотя бы две вершины, принадлежащих отверстию будут split и merge (см. рисунок). Диагональ от таких вершин можно провести только до вершин внешнего контура, а поскольку у внутреннего отверстия хотя бы одна split и одна merge вершина весь многоугольник будет разделён как минимум на две части. === Ушной метод ===// ещё допишу.