Участник:Kabanov

Триангуляция полигона — декомпозиция многоугольника [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]v_i[/math] называется ухом, если диагональ [math]v_{i-1}v_{i+1}[/math] лежит строго во внутренней области многоугольника [math]P[/math]

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

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

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

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

[math]\triangleright[/math]

Доказательство будем вести по индукции. Базовый случай: [math]n = 4[/math]. Предположим для всех многоугольников, количество вершин в которых не больше [math]n[/math], теорема верна. Рассмотрим многоугольник [math]P[/math], в котором [math]n+1[/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]\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}(1)[/math]. Таким образом общий процесс отрезания ушей займёт [math]\mathcal{O}(n^2)[/math]. Невыпуклых вершин всего [math]\mathcal{O}(n)[/math], каждая из них обрабатывается за константу, поэтому общее время для их обработки [math]\mathcal{O}(n)[/math]. Списки рёбер и вершин строятся за линейное время, добавление ребра и удаление вершины в каждом из них работает за константу. Общее время [math]\mathcal{O}(n^2)[/math]. Поскольку храним только два списка — память линейная.