Участник: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 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 [math]T[/math]
   [math]helper(e_{i}) \leftarrow  v_i[/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]

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]

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]. Такое возможно только в случае, когда точками пересечения будут являться [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]D[/math] и дерево [math]T[/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] занимают линейную память.

Ушной метод

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