Участник:Muravyov

Триангуляция полигона — декомпозиция многоугольника [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 \lt 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]P[/math] будет [math]y[/math]-монотонным, что противоречит нашему предположению. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.

[math]\triangleleft[/math]

Алгоритм

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

Рассмотрим заметающую прямую [math]l[/math], перпендукулярную [math]y[/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.

Обработка megre вершины [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] рёбер и добавленных в процессе диагоналей, так как потом это обеспечит эффективный доступ к каждой из частей, которые нужно будет триангулировать.

Псевдокод

MakeMonotone(P)
   Construct([math]D[/math]);
   Construct([math]Q[/math]); // функция Construct создаёт объекты [math]D[/math] и [math]Q[/math] , описанные выше.
   bst [math]T[/math] = new bst();
   while [math] Q \neq  \varnothing [/math]
      Remove [math]v_{max}[/math] from [math]Q[/math] // удаление вершины с наивысшим приоритетом из [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 [math]T[/math]
   [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 [math]T[/math]
   Insert edge([math]v_{i}[/math], [math]helper(e_{i})[/math]) in [math]D[/math]
   [math]helper(e_{j}) \leftarrow  v_i[/math] 
   Insert [math]e_{i}[/math] in [math]T[/math]
   [math]helper(e_{i}) \leftarrow  v_i[/math]v

В последующих трех функциях обработки вершины [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 [math]D[/math]
   Delete [math]e_{i-1}[/math] from [math]T[/math]

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 [math]D[/math]
   Delete [math]e_{i-1}[/math] from [math]T[/math]
   edge [math]e_j[/math] = [math]l \cap P[/math]
   Search [math]e_j[/math] in [math]T[/math]
   if (Type_of_vertex([math]helper(e_{j})[/math] = 'merge')
      Insert edge([math]v_{i}[/math], [math]helper(e_{j})[/math]) in [math]D[/math]
   [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 [math]D[/math]
         Delete [math]e_{i-1}[/math] from [math]T[/math]
         Insert [math]e_{i}[/math] in [math]T[/math]
         [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 [math]T[/math]
         if (Type_of_vertex([math]helper(e_{j})[/math] = 'merge')
            Insert edge([math]v_{i}[/math], [math]helper(e_{j})[/math]) in [math]D[/math]
         [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/tex\gt является нижним концом стороны \lt tex\gt e[/math], ограничивающего воронку. Вершины противоположной цепи уже были положены в стек. В этом случае можно просто построить диагонали, соединяющие [math]v_j[/math] со всеми вершинами, находящимися в стеке, кроме последней. Последняя вершина в стеке уже соединена с [math]v_j[/math] стороной [math]e[/math]. Часть многоугольника [math]З[/math], лежащая выше [math]v_j[/math], которая не была триангулирована, ограничена диагональю, которая соединяет [math]v_j[/math] с вершиной [math]v_k1[/math], которая была первой в стеке. Сторона многоугольника [math]P[/math], выходящая из [math]v_k1[/math] направлена вниз. Снова образуется фигура, похожая на воронку -- инвариант сохраняется. Вершины [math]v_j[/math] и [math]v_k1[/math] кладутся в стек, поскольку они были были обработаны, но по прежнему являются вершинами непротриангулированной части [math]P[/math].
• Вершина [math]v_j[/math] принадлежит цепи вершин, добавленных в стек, до которых невозможно провести диагонали.

Ушной метод

Более эффективным я