Участник:Kabanov

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

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

Простой многоугольник [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(e_j)[/math] её левого ребра, которое [math]l[/math] пересекает в данный момент.
2. Merge вершина. В отличие от случая со split вершиной заранее вычислить указатель [math]helper[/math] нельзя, поскольку merge вершина [math]v_i[/math] должна быть соединена с вершиной, лежащей ниже заметающей прямой [math]l[/math]. Для этого в [math]helper(e_j)[/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]S[/math] на момент достижения вершины [math]v_j[/math], рыжей помечена первая вершина, до которой невозможно провести диагональ, жёлтой помечена новая нетриангулированная область [math]P[/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]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].

Общая оценка

Разбиение многоугольника на монотонные части занимает [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] по памяти.