Участник:Muravyov

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

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

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

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

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

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

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

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

$\triangleright$

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

$\triangleleft$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Лемма:

Многоугольник $P$ является $y$-монотонным, когда в нём отсутствуют split и merge вершины.

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

$\triangleright$

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

$\triangleleft$

Ушной метод

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