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

Триангуляция полигона — декомпозиция многоугольника [math]P[/math] на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет [math]P[/math]. В строгом смысле слова, вершины этих треугольников должны совпадать с вершинами исходного многоугольника. Триангуляция любого многоугольника не единственна. В этом можно убедиться из примера на рисунке.

Два способа триангуляции одной и той же фигуры

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

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

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

Простым многоугольником является фигура, ограниченная одной замкнутой ломаной, стороны которой не пересекаются. Таким образом, случаи многоугольников с дырками в теореме исключаются.

Теорема (О существовании триангуляции многоугольника):

У любого простого [math]n[/math]-вершинного многоугольника [math]P[/math] всегда существует триангуляция, причём количество треугольников в ней [math]n - 2[/math] независимо от самой триангуляции.

Доказательство:

[math]\triangleright[/math]

Два случая в доказательстве теоремы Доказательство ведётся индуктивно по [math]n[/math]. При [math]n = 3[/math] теорема тривиальна. Рассмотрим случай при [math]n \gt 3[/math] и предположим, что теорема выполняется при всех [math]m \lt n[/math]. Докажем существование диагонали в многоугольнике [math]P[/math]. Возьмём самую левую по оси [math]x[/math] вершину [math]v[/math] многоугольника [math]P[/math] и две смежных с ней вершины [math]u[/math] и [math]w[/math]. Если отрезок [math]uw[/math] принадлежит внутренней области [math]P[/math] — мы нашли диагональ. В противном случае, во внутренней области треугольника [math]\Delta uwv[/math] или на самом отрезке [math]uw[/math] содержится одна или несколько вершин [math]P[/math]. Выберем из них наиболее удалённую от [math]uw[/math] вершину [math]v'[/math]. Отрезок, соединяющий [math]v[/math] и [math]v'[/math] не может пересекать ребро [math]P[/math], поскольку в противном случае одна из вершин этого ребра будет располагаться дальше от [math]uw[/math], чем [math]v'[/math]. Это противоречит условию выбора [math]v'[/math]. В итоге получаем, что [math]v'v[/math] — диагональ. Любая диагональ делит [math]P[/math] на два многоугольника [math]P_1[/math] и [math]P_2[/math]. За [math]m_1[/math] и [math]m_2[/math] обозначим количество вершин в [math]P_1[/math] и [math]P_2[/math] соответственно. [math]m_1 \lt n[/math] и [math]m_2 \lt n[/math], поэтому по предположению индукции у [math]P_1[/math] и [math]P_2[/math] существует триангуляция, следовательно и у [math]P[/math] она существует. Докажем, что триангуляция [math]P[/math] состоит из [math]n - 2[/math] треугольников. Рассмотрим произвольную диагональ [math]d[/math] в триангуляции [math]T_P[/math]. [math]d[/math] делит [math]P[/math] на два многоугольника [math]P_1[/math] и [math]P_2[/math], количество вершин в которых [math]m_1[/math] и [math]m_2[/math] соответственно. Каждая вершина [math]P[/math] встречается только в одном из двух многоугольников [math]P_1[/math] и [math]P_2[/math], за исключением тех, которые являются концами [math]d[/math], поэтому справедливо следующее: [math]m_1 + m_2 = n + 2[/math]. По индукции, любая триангуляция [math]P_i[/math] состоит из [math]m_i - 2[/math] треугольников, откуда следует, что [math]T_P[/math]. состоит из [math](m_1 - 2) + (m_2 - 2) = n - 2[/math] треугольников.

[math]\triangleleft[/math]

Способы нахождения триангуляции

Примитивный алгоритм

В общем случае в произвольном [math]n[/math]-угольнике всего [math]n^2[/math] возможных вариантов построения диагоналей. За [math]\mathcal{O}(n)[/math] проверим каждый из них. Для этого выясним:

• пересекает ли данная диагональ многоугольник — находится за линейное время проверкой по всем рёбрам
• принадлежит ли диагональ внутренней области многоугольника.

Чтобы построить триангуляцию нужно найти [math]n - 3[/math] диагоналей. В результате получается оценка [math]\mathcal{O}(n^4)[/math].

Для некоторых классов многоугольников предыдущую оценку можно улучшить. Например, если многоугольник выпуклый, то достаточно лишь выбирать одну его вершину и соединять со всеми остальными, кроме его соседей. В итоге оценка [math]\mathcal{O}(n)[/math].

Монотонный метод

Определение:

Простой многоугольник [math]P[/math] называется монотонным относительно прямой [math]l[/math], если любая [math]l'[/math], такая что [math]l' \perp l[/math], пересекает стороны [math]P[/math] не более двух раз (результатом пересечения [math]l'[/math] и [math]P[/math] может быть только один отрезок или точка).

Определение:

Многоугольник, монотонный относительно [math]y[/math]-оси называется [math]y[/math]-монотонным.

Суть данного метода заключается в том, чтобы разбить многоугольник на монотонные части, а затем триангулировать каждую из них.

Разбиение многоугольника на монотонные части

Основные понятия

Пять типов вершин

Рассмотрим самую верхнюю — максимальную по координате [math]y[/math] вершину. Будем идти вниз по рёбрам до самой нижней — соотвественно минимальной по [math]y[/math] вершине, то есть таким образом, что для некоторой вершины [math]j[/math]: [math]y_j \gt y_{j+1}[/math]. Поворотной назовём вершину [math]i[/math], на которой направление обхода будет меняется: [math]y_{i-1} \gt y_i[/math] и [math]y_i \lt y_{i+1}[/math]. Опишем более подробно этот тип вершин. Уточним понятния выше и ниже: точка [math]p[/math] лежит ниже точки [math]q[/math], если [math]p_y \lt q_y[/math] или если [math]p_y = q_y[/math] и [math]p_x \gt q_x[/math], соответственно точка [math]p[/math] лежит выше точки [math]q[/math], если [math]p_y \gt q_y[/math] или если [math]p_y = q_y[/math] и [math]p_x \lt q_x[/math]. Это было сделано для того, чтобы избежать неопределённых ситуаций с вершинами, у которых [math]y[/math]-координаты равны.

Обозначим за [math]\phi[/math] внутренний угол при некоторой вершине и определим далее пять типов вершин, четыре из которых являются поворотными:

• start вершина — два её соседа лежат ниже её самой и [math] \phi \lt \pi [/math]
• split вершина — два её соседа лежат ниже её самой и [math] \phi \gt \pi [/math]
• end вершина — два её соседа лежат выше её самой и [math] \phi \lt \pi [/math]
• merge вершина — два её соседа лежат выше её самой и [math] \phi \gt \pi [/math]
• regular вершина — не является поворотной, в отличие от остальных, другими словами один её сосед находится выше, а другой ниже её самой.

Лемма:

Многоугольник [math]P[/math] является [math]y[/math]-монотонным, если в нём отсутствуют split и merge вершины.

Доказательство:

[math]\triangleright[/math]

Предположим, что [math]P[/math] не [math]y[/math]-монотонный. Тогда докажем, что [math]P[/math] содержит split и merge вершины. Поскольку [math]P[/math] не [math]y[/math]-монотонный, существует горизонтальная прямая [math]l[/math], которая пересекает его стороны более двух раз. Выберем [math]l[/math] таким образом, чтобы самой левой компонентой пересечения [math]l[/math] и [math]P[/math] был бы отрезок [math]pq[/math]. Далее будем двигаться наверх по сторонам [math]P[/math], начиная от точки [math]q[/math]. В результате в некоторой точке [math]r[/math], где [math]r \neq p[/math] (случай (a) на рисунке), прямая [math]l[/math] снова пересечёт одну из сторон [math]P[/math]. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам [math]P[/math], будет split вершиной. Если же [math]r = p[/math] (случай (b) на рисунке), начём опять двигаться по сторонам [math]P[/math] теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка [math]r'[/math], которая будет результатом пересечения [math]l[/math] и [math]P[/math]. При этом [math]r' \neq p[/math], в противном случае [math]l[/math] будет пересекать [math]P[/math] только два раза, что противоречит выбору [math]l[/math]. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.

[math]\triangleleft[/math]

Алгоритм

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

Рассмотрим горизонтальную заметающую прямую [math]l[/math], будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник [math]P[/math]. Будем останавливать её в каждой вершине многоугольника. В тот момент, когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, у которой расстояние до [math]l[/math] минимально, при этом она должна лежать соответственно выше или ниже [math]l[/math].

Обработка split вершины [math]v_i[/math]

Рассмотрим каждый случай подробнее:

1. Split вершина. Пусть [math]e_j[/math] и [math]e_k[/math] — ближайшее левое и правое ребро относительно split вершины [math]v_i[/math], которые [math]l[/math] пересекает в данный момент. Нам нужно найти вершину, лежащую между [math]e_j[/math] и [math]e_k[/math], наиболее приближённую к [math]l[/math], либо если такой точки не существет выбрать минимальную из верхних вершин [math]e_j[/math] и [math]e_k[/math]. Для этого будем хранить указатель на искомую вершину у левого ребра [math]e_j[/math], который можно заранее вычислить. Тип вершины, хранящийся в [math]helper[/math] не имеет значения. Таким образом, чтобы построить диагональ для split вершины нужно обратиться к указателю [math]helper[/math] её левого ребра, которое [math]l[/math] пересекает в данный момент.
2. Merge вершина. В отличие от случая со split вершиной заранее вычислить указатель [math]helper[/math] нельзя, поскольку merge вершина [math]v_i[/math] должна быть соединена с вершиной, лежащей ниже заметающей прямой [math]l[/math]. Для этого в [math]helper[/math] левого относительно [math]v_i[/math] ребра запишем саму [math]v_i[/math]. Далее спускаем заметающую прямую вниз к следующей вершине [math]v_m[/math], обращаемся к [math]helper[/math]'у её левого ребра. Проверяем, если там хранится merge вершина, строим диагональ [math]v_{i}v_{m}[/math]. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.

Обработка merge вершины [math]v_i[/math]. На рисунке слева [math]v_i[/math] записывается в качестве [math]helper[/math]'а своего левого ребра. На правом рисунке ближайшая вершина [math]v_m[/math] при обращении к своему левому ребру [math]helper(e_j)[/math] находит [math]v_i[/math] и образует диагональ [math]v_{i}v_m[/math]

Структуры данных

В подходе, описанном выше, требуется находить пересечения заметающей прямой и левых ребёр многоугольника. Создадим двоичное дерево поиска [math]T[/math], в листьях которого будем хранить рёбра, пересекающие [math]l[/math], такие, что внутренняя область многоугольника будет лежать справа от них самих. С каждым таким ребром будем хранить его [math]helper[/math]. Порядок следования листьев в дереве соответствует порядку следования рёбер в многоугольнике: слева направо. Дерево изменяется в зависимости от текущего состояния заметающей прямой. Создадим приоритетную очередь [math]Q[/math] из вершин, в которой приоритетом будет [math]y[/math]-координата вершины. Если две вершины имеют одинаковые [math]y[/math]-координаты, больший приоритет у левой. Вершины будут добавляться на "остановках" заметающей прямой.

Многоугольник [math]P[/math] и добавленные в процессе диагонали удобно хранить в виде списка [math]D[/math] рёбер с двойными связями (DCEL — doubly-connected edge list), так как потом это обеспечит эффективный доступ к каждой из частей, которые нужно будет триангулировать.

Псевдокод

MakeMonotone(P)
   Construct(D);
   Construct(Q); // функция Construct создаёт объекты [math]D[/math] и [math]Q[/math] , описанные выше.
   bst T = new bst();
   while Q [math] \neq  \varnothing [/math]
      Remove [math]v_{max}[/math] from Q // удаление вершины с наивысшим приоритетом из [math]Q[/math]    
      switch (Type_of_vertex([math]v_{max}[/math])): // определение типа вершины
         case 'start':
            HandleStartVertex([math]v_{max}[/math]);
         case 'end':
            HandleEndVertex([math]v_{max}[/math]);
         case 'split':
            HandleSplitVertex([math]v_{max}[/math]);
         case 'merge':
            HandleMergeVertex([math]v_{max}[/math]);
         case 'regular':
            HandleRegularVertex([math]v_{max}[/math]);

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

HandleStartVertex([math]v_{i}[/math])
   Insert [math]e_{i}[/math] in T
   [math]helper(e_{i}) \leftarrow  v_i[/math]

HandleSplitVertex([math]v_{i}[/math])
   edge [math]e_j[/math] = [math]l \cap P[/math]
   Search [math]e_j[/math] in T
   Insert edge([math]v_{i}[/math], [math]helper(e_{j})[/math]) in D
   [math]helper(e_{j}) \leftarrow  v_i[/math] 
   Insert [math]e_{i}[/math] in T
   [math]helper(e_{i}) \leftarrow  v_i[/math]

В последующих трех функциях обработки вершины [math]v_i[/math] происходит обращение к смежному ребру [math]e_{i-1}[/math]. Это сделано для вершин, относительно которых внутренняя область [math]P[/math] лежит справа от них самих (вершина [math]v_6[/math]), либо для двух подряд идущих merge вершин, таких как [math]v_2[/math] и [math]v_8[/math].

HandleEndVertex([math]v_{i}[/math])
   if (Type_of_vertex([math]helper(e_{i-1})[/math] = 'merge')
      Insert edge([math]v_{i}[/math], [math]helper(e_{i-1})[/math]) in D
   Delete [math]e_{i-1}[/math] from T

HandleMergeVertex([math]v_{i}[/math])
   if (Type_of_vertex([math]helper(e_{i-1})[/math] = 'merge')
      Insert edge([math]v_{i}[/math], [math]helper(e_{i-1})[/math]) in D
   Delete [math]e_{i-1}[/math] from T
   edge [math]e_j[/math] = [math]l \cap P[/math]
   Search [math]e_j[/math] in T
   if (Type_of_vertex([math]helper(e_{j})[/math] = 'merge')
      Insert edge([math]v_{i}[/math], [math]helper(e_{j})[/math]) in D
   [math]helper(e_{j}) \leftarrow  v_i[/math]

HandleRegularVertex([math]v_{i}[/math])
   if (interior of [math]P[/math] lies to the right of [math]v_{i}[/math])
      then
         if (Type_of_vertex([math]helper(e_{i-1})[/math] = 'merge')
            Insert edge([math]v_{i}[/math], [math]helper(e_{i-1})[/math]) in D
         Delete [math]e_{i-1}[/math] from T
         Insert [math]e_{i}[/math] in T
         [math]helper(e_{i}) \leftarrow  v_i[/math]
      else
         edge [math]e_j[/math] = [math]l \cap P[/math]
         Search [math]e_j[/math] in T
         if (Type_of_vertex([math]helper(e_{j})[/math] = 'merge')
            Insert edge([math]v_{i}[/math], [math]helper(e_{j})[/math]) in D
         [math]helper(e_{j}) \leftarrow  v_i[/math]

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

Лемма:

Функция MakeMonotone(P) корректно выполняет разбиение многоугольника [math]P[/math]. Другими словами эта функция добавляет в [math]P[/math] множество непересекающихся диагоналей, которые разбивают [math]P[/math] на монотонные части.

Доказательство:

[math]\triangleright[/math]

Тот факт, что [math]P[/math] разбивается на монотонные части следует из предыдущей леммы. Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, попарно не пересекаются и не пересекают стороны [math]P[/math]. Рассмотрим случай выполнения функции HandleSplitVertex, поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершин, в отличие от остальных функций (в них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной). Допустим, что диагональ [math]v_{i}v_{m}[/math] была построена с помощью HandleSplitVertex по достижению split вершины [math]v_i[/math]. Рассмотрим четырёхугольник [math]H[/math], заключённый между [math]e_j[/math] и [math]e_k[/math] - левым и правым ребром относительно [math]v_i[/math] и горизонтальными прямыми, проведёнными через [math]v_i[/math] и [math]v_m[/math]. Внутри [math]H[/math], не может находиться ни одной из вершин [math]P[/math], в противном случае [math]helper(e_j)[/math] не равнялся бы [math]v_m[/math]. Предположим теперь, что [math]v_{i}v_{m}[/math] пересекает [math]e_s[/math] одну из сторон [math]P[/math]. Учитывая, что никаких вершин [math]P[/math] не лежит внутри [math]H[/math] и стороны [math]P[/math] не пересекаются, то [math]e_s[/math] должна пересечь либо отрезок, соединяющий [math]e_j[/math] и [math]v_m[/math], либо [math]e_j[/math] и [math]v_i[/math]. 1) Вершин внутри [math]H[/math] находиться не может; 2) [math]v_{i}v_m[/math] может пересекать только рёбра, помеченные зелёным Такое возможно только в случае, когда точками пересечения будут являться [math]v_i[/math] или [math]v_m[/math], что не противоречит условию. Отсюда [math]v_{i}v_{m}[/math] не пересекает ни одну из сторон [math]P[/math] в посторонних точках. Теперь рассмотрим случай с пересечением добавленной ранее диагональю. Поскольку внутри [math]H[/math] никаких вершин вершин находиться не может, и оба конца любой добавленной ранее диагонали должны лежать выше [math]v_i[/math], диагональ [math]v_{i}v_m[/math] не может пересекать никакую из ранее добавленных диагоналей.

[math]\triangleleft[/math]

Оценка работы

Построение описанной выше приоритетной очереди [math]Q[/math] происходит за линейное время. Когда заметающая прямая останавливается в вершине: операции с очередью занимают константу по времени, операции с деревом [math]T[/math] на запросы и обновления требуют [math]\mathcal{O}(\mathcal \log n)[/math]. Добавление диагонали в [math]D[/math] требует [math]\mathcal{O}(1)[/math]. В итоге обработка каждой вершины требует [math]\mathcal{O}(\log n)[/math], а весь алгоритм соответственно [math]\mathcal{O}(n \log n)[/math]. Что касается памяти, она очевидно составляет [math]\mathcal{O}(n) [/math]. Очередь [math]Q[/math] и дерево [math]T[/math] занимают линейную память.

Зелёным помечена так называемая воронка, которая образуется, когда мы достигнем красной вершины

Триангуляция монотонного многоугольника

Идея

Будем проходить сверху вниз по вершинам многоугольника проводя диагонали где это возможно.

Отсортируем все вершины многоугольника [math]P[/math] в порядке убывания их [math]y[/math]-координаты. Заведём стек вершин [math]S[/math]. В стеке будем хранить вершины в отсортированном порядке, которые были обработаны, но не были отрезаны от многоугольника, то есть находятся в той части многоугольника, которая ещё не была триангулирована. В момент обработки некоторой вершины, будем пытаться провести из неё как можно больше диагоналей к вершинам, содержащимся в стеке. Эти диагонали отрезают треугольники от [math]P[/math]. На вершине стека будет храниться вершина, которая будет обрабатываться последней.

Часть многоугольника [math]P[/math], лежащая выше последней обработанной вершины [math]v_i[/math] и которая ещё не была триангулирована имеет форму перевёрнутой воронки (см. рисунки). Одна сторона воронки состоит из одной из сторон [math]P[/math], а другая состоит из цепи вершин, которые лежат выше [math]v_i[/math] и внутренние углы которых не меньше [math]\pi[/math]. Несложно догадаться, что самая нижняя вершина стека является единственной выпуклой. Несложно также заметить, что при обработке следующей вершины свойство перевёрнутой воронки сохранится, то есть оно является инвариантом алгоритма.

Первый случай. Синим помечены стороны воронки, зелёным — диагонали, а жёлтым границы новой ещё не протриангулированной области

Алгоритм

Рассмотрим процесс обработки вершины более подробно. Возможны два случая:

• Текущая вершина [math]v_j[/math] является нижним концом стороны [math]e[/math], ограничивающего воронку. Вершины противоположной цепи уже были положены в стек. В этом случае можно просто построить диагонали, соединяющие [math]v_j[/math] со всеми вершинами, находящимися в стеке, кроме последней. Последняя вершина в стеке уже соединена с [math]v_j[/math] стороной [math]e[/math]. Часть многоугольника [math]P[/math], лежащая выше [math]v_j[/math], которая не была триангулирована, ограничена диагональю, которая соединяет [math]v_j[/math] с вершиной [math]v_{s1}[/math], которая была первой в стеке. Сторона многоугольника [math]P[/math], выходящая из [math]v_{s1}[/math] направлена вниз. Снова образуется фигура c одним выпуклым углом, похожая на воронку — инвариант сохраняется. Вершины [math]v_j[/math] и [math]v_{s1}[/math] кладутся в стек, поскольку они были были обработаны, но по прежнему являются вершинами непротриангулированной части [math]P[/math].

• Вершина [math]v_j[/math] принадлежит последовательной цепи вершин, добавленных в [math]S[/math]. Вынем из стека верхнюю вершину [math]v_{s1}[/math] — она уже соединена с [math]v_{j}[/math] одной из сторон [math]P[/math]. Затем будем пытаться выстраивать диагонали, соединяющие [math]v_{j}[/math] c вынимаемыми из стека вершинами пока это возможно. Проверку на возможность построения диагонали [math]v_{j}v_{k}[/math], где [math]v_{k}[/math] — текущая верхняя вершина стека, можно осуществлять посредством изучения взаимного расположения предыдущей вершины, вынутой из [math]S[/math], относительно [math]v_{j}v_{k}[/math]. Когда мы достигнем вершины [math]v_{k}[/math], до которой невозможно провести диагональ, положим предыдущую вершину [math]v_{k-1}[/math] обратно в стек. Вершина [math]v_{k-1}[/math] является либо последней, до которой было возможно провести диагональ, либо, если ни одной диагонали из [math]v_{j}[/math] провести не удалось, — соседом [math]v_{j}[/math]. Далее положим [math]v_{j}[/math] в стек. Опять же инвариант непротриангулированной части [math]P[/math] сохраняется: одна сторона воронки ограничена частью стороны многоугольника, а другая цепью невыпуклых вершин.

Второй случай. Синим помечена цепь из вершин, которая содержится в стеке [math]S[/math] на момент достижения вершины [math]v_j[/math], рыжей помечена первая вершина, до которой невозможно провести диагональ, жёлтой помечена новая нетриангулированная область [math]P[/math] в форме воронки

Псевдокод

Как ранее уже было отмечено, задаём [math]P[/math] в виде рёберного списка c двойными связями [math]D[/math].

TriangulateMonotonePolygon(P)
   vertex [n] V = new vertex(P); // массив вершин [math]P[/math], отсортированный по y-координате в порядке убывания.
   stack S = new stack();
   S.push(V[1]);
   S.push(V[2]);
   for j [math]\leftarrow[/math] 3 to n - 1
      if (V[j] = S.peek())
         while (S [math]\neq  \varnothing [/math])
            if (S.size() [math]\neq[/math] 1)
               Insert edge(V[j], S.peek()) in D
            S.pop()
         S.push(V[j-1])
         S.push(V[j]);
      else
         vertex last [math]\leftarrow[/math] S.peek();
         S.pop();
         while (IsValidDiagonal(edge(V[j], S.peek()), last)) //проверка возможности построения 
                                                             //диагонали — предикат "левый поворот"
            last [math]\leftarrow[/math] S.peek();
            S.pop();
            Insert edge(V[j], last) in D
         S.push(last);
         S.push(V[j]);
   S.pop()
   while (S [math]\neq  \varnothing [/math])
      if (S.size() [math]\neq[/math] 1)
         Insert edge(V[j], S.peek()) in D
      S.pop()

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

• Все построенные диагонали попарно не пересекаются. Это гарантируется тем, что при каждом просмотре определённой вершины рассматривается только та часть [math]P'[/math] многоугольника [math]P[/math], которая не была протриангулирована, следовательно внутри этой области по определению не может лежать ни одной из уже построенных диагоналей. Несложно заметить, что в стеке [math]S[/math] на каждой итерации главного цикла хранятся вершины, которые принадлежат именно [math]P'[/math] и лежат выше рассматриваемой вершины.
• Количество построенных диагоналей всегда будет [math]n-3[/math], поэтому непротриангулированных частей в многоугольнике не останется.

Оценка работы

Построение массива вершин требует линейное время и занимает линейную память. Главный цикл for выполняется [math]n-3[/math] раза. Каждая его итерация может потребовать линейное время. Однако заметим, что на каждой итерации главного цикла в стек кладутся максимум две вершины, следовательно общее число выполнения операции push, включая первые две вершины, положенные в начале алгоритма, ограничено [math]2n-4[/math]. Количество операций pop за время работы алгоритма не превысит количества операций push. Отсюда общее время работы цикла for [math]\mathcal{O}(n)[/math]. В итоге общее время работы [math]\mathcal{O}(n)[/math].

Общая оценка

Пример отверстия в форме монотонного многоугольника. У него обязательно будут существовать start и end вершина, если рассматривать его как обычный многоугольник. Однако, когда он станет полигональным отверстием, в силу определения start и end вершины обратятся в split и merge, которые соединятся с какими-то вершинами внешнего контура

Разбиение многоугольника на монотонные части занимает [math]\mathcal{O}(n \log n)[/math] времени и [math]\mathcal{O}(n)[/math] памяти. Триангуляция каждой из частей занимает линейную память и время. Учитывая то, что суммарное количество вершин во всех частях [math]\mathcal{O}(n)[/math], триангуляция всех частей займёт [math]\mathcal{O}(n)[/math] по времени и по памяти.

В итоге общая оценка составляет [math]\mathcal{O}(n \log n)[/math] по времени и [math]\mathcal{O}(n)[/math] по памяти.

Прочие случаи

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

Ушной метод

Определение:

Вершина [math]v_i[/math] называется ухом, если диагональ [math]v_{i-1}v_{i+1}[/math] лежит строго во внутренней области многоугольника [math]P[/math]

В первом случае выделенная вершина является ухом, в остальных нет

Теорема (О существовании двух ушей многоугольника):

У любого простого [math]n[/math]-вершинного многоугольника [math]P[/math] всегда существует два не пересекающихся между собой уха.

Доказательство:

[math]\triangleright[/math]

Тривиальный пример многоугольника с четырьмя вершинами. [math]E_1[/math] и [math]E_2[/math] — уши Доказательство будем вести по индукции. Базовый случай: [math]n = 4[/math]. Предположим для всех многоугольников, количество вершин в которых не больше [math]n[/math], теорема верна. Рассмотрим многоугольник [math]P[/math], в котором [math]n+1[/math] вершина. Далее возможны два случая: Случай, когда [math]v_i[/math] является ухом в [math]P[/math] Произвольная выпуклая вершина [math]v_i[/math] многоугольника [math]P[/math] является ухом. Отрезав это ухо, мы уменьшим число вершин [math]P[/math] на одну. В результате, получиv [math]n[/math]-вершинный многоугольник [math]P'[/math]. По предположению индукции у него существует два непересекающихся уха. Учитывая, что уши [math]P'[/math] являются ушами и [math]P[/math], несложно заметить, что для [math]P[/math] теорема верна. Произвольная выпуклая вершина [math]v_i[/math] многоугольника [math]P[/math] не является ухом. В таком случае в треугольнике [math]\Delta v_{i-1}v_{i}v_{i+1}[/math] лежат вершины, принадлежащие [math]P[/math]. Из этих вершин выберем вершину [math]q[/math], которая будет ближе всего к [math]v_i[/math]. Проведём отрезок [math]Q[/math], который разделит [math]P[/math] на два многоугольника: [math]P_1[/math] и [math]P_2[/math]. В каждом из них будет не более [math]n[/math] вершин, следовательно у каждого будет по два непересекающихся уха. Даже если предположить, что ухо из [math]P_1[/math] и ухо из [math]P_2[/math] будут пересекаться по стороне [math]v_{i}q[/math], в [math]P[/math] всё равно будет не менее двух непересекающихся ушей. Случай, когда [math]v_i[/math] не является ухом в [math]P[/math]. Желтым и зелёным отмечены уши, принадлежащие [math]P_2[/math] и [math]P_1[/math] соответственно.

[math]\triangleleft[/math]

Идея

Рассмотрим все вершины многоугольника [math]P[/math], и где возможно, будем отрезать уши до тех пор, пока [math]P[/math] не станет треугольником.

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

Алгоритм

При проверке каждой вершину следует для начала проверить, является ли она выпуклой, в противном случае её просто нет надобности рассматривать в качестве уха. Это несложно сделать, воспользовавшись левым поворотом. "Ушную" проверку вершины будем осуществлять алгоритмом принадлежности точки [math]n[/math]-угольнику (в нашем случае треугольнику). В качестве поддерживаемых структур удобно хранить 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) [math] \neq [/math] 3
   if IsConvex(v)  //проверка на выпуклость
      for each Vertex v_i in D1
         if v_i [math] \neq [/math] v, v.prev(), v.next()                 //проверка всех вершин на 
               and v_i [math]\in [/math] 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

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

При нахождении каждого уха от многоугольника [math]P[/math] отрезается треугольник, состоящий из самого уха и его двух смежных вершин. Существование ушей в свою очередь следует из теоремы, доказанной выше. В конце алгоритма, когда все уши от [math]P[/math] отрезаны, остается только один треугольник. Как несложно видеть, триангуляция выстраивается корректно.

Оценка работы

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

Источники

• 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.

• Ear Cutting for Simple Polygons

• Triangulation by ear-clipping