Редактирование: Триангуляция полигонов (ушная + монотонная)

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 5: Строка 5:
 
На плоскости задан произвольный многоугольник. Стороны многоугольника не пересекаются. Требуется найти его триангуляцию.
 
На плоскости задан произвольный многоугольник. Стороны многоугольника не пересекаются. Требуется найти его триангуляцию.
  
== Теорема о существовании триангуляции ==
+
== Теорема о существовании трингуляции ==
  
 
'''Простым многоугольником''' является фигура, ограниченная одной замкнутой ломаной, стороны которой не пересекаются. Таким образом, случаи многоугольников с дырками в теореме исключаются.
 
'''Простым многоугольником''' является фигура, ограниченная одной замкнутой ломаной, стороны которой не пересекаются. Таким образом, случаи многоугольников с дырками в теореме исключаются.
Строка 14: Строка 14:
 
|proof=
 
|proof=
 
[[Файл:Proof theorem.jpg|200px|thumb|right|Два случая в доказательстве теоремы]]
 
[[Файл:Proof theorem.jpg|200px|thumb|right|Два случая в доказательстве теоремы]]
Доказательство ведётся индуктивно по <tex>n</tex>. При <tex>n = 3</tex> теорема тривиальна. Рассмотрим случай при <tex>n > 3</tex> и предположим, что теорема выполняется при всех <tex>m < n</tex>. Докажем существование диагонали в многоугольнике <tex>P</tex>. Возьмём самую левую по оси <tex>x</tex> вершину <tex>v</tex> многоугольника <tex>P</tex> и две смежных с ней вершины <tex>u</tex> и <tex>w</tex>. Если отрезок  <tex>uw</tex> принадлежит внутренней области <tex>P</tex> — мы нашли диагональ. В противном случае, во внутренней области треугольника <tex>\Delta uwv</tex> или на самом отрезке <tex>uw</tex> содержится одна или несколько вершин <tex>P</tex>. Выберем из них наиболее удалённую от <tex>uw</tex> вершину <tex>v'</tex>. Отрезок, соединяющий <tex>v</tex> и <tex>v'</tex> не может пересекать ребро <tex>P</tex>, поскольку в противном случае одна из вершин этого ребра будет располагаться дальше от <tex>uw</tex>, чем <tex>v'</tex>. Это противоречит условию выбора <tex>v'</tex>. В итоге получаем, что <tex>v'v</tex> — диагональ.  
+
Доказательство ведётся индуктивно по <tex>n</tex>. При <tex>n = 3</tex> теорема тривиальна. Рассмотрим случай при <tex>n > 3</tex> и предположим, что теорема выполняется при всех <tex>m < n</tex>. Докажем существование диагонали в многоугольнике <tex>P</tex>. Возьмём самую левую по оси <tex>x</tex> вершину <tex>v</tex> многоугольника <tex>P</tex> и две смежных с ней вершины <tex>u</tex> и <tex>w</tex>. Если отрезок  <tex>uw</tex> принадлежит внутренней области <tex>P</tex> — мы нашли диагональ. В противном случае, во внутренней области треугольника <tex>\Delta uwv</tex> или на самом отрезке <tex>uw</tex> содержится одна или несколько вершин <tex>P</tex>. Выберем самую наиболее далеко отстоящую от <tex>uw</tex> вершину <tex>v'</tex>. Отрезок, соединяющий <tex>v</tex> и <tex>v'</tex> не может пересекать сторон <tex>P</tex>, поскольку в противном случае одна из вершин это отрезка будет располагаться дальше от <tex>uw</tex>, чем <tex>v'</tex>. Это противоречит условию выбора <tex>v'</tex>. В итоге получаем, что <tex>v'v</tex> — диагональ.  
 
Любая диагональ делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>. За <tex>m_1</tex> и <tex>m_2</tex> обозначим количество вершин в <tex>P_1</tex> и <tex>P_2</tex> соответственно. <tex>m_1 < n</tex> и <tex>m_2 < n</tex>, поэтому по предположению индукции у <tex>P_1</tex> и <tex>P_2</tex> существует триангуляция, следовательно и у <tex>P</tex> она существует.
 
Любая диагональ делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>. За <tex>m_1</tex> и <tex>m_2</tex> обозначим количество вершин в <tex>P_1</tex> и <tex>P_2</tex> соответственно. <tex>m_1 < n</tex> и <tex>m_2 < n</tex>, поэтому по предположению индукции у <tex>P_1</tex> и <tex>P_2</tex> существует триангуляция, следовательно и у <tex>P</tex> она существует.
  
Строка 32: Строка 32:
  
 
{{Определение
 
{{Определение
|id=def_monotone_polygon
 
 
|definition=
 
|definition=
 
Простой многоугольник <tex>P</tex> называется '''монотонным''' относительно прямой <tex>l</tex>, если любая <tex>l'</tex>, такая что <tex>l' \perp l</tex>, пересекает стороны <tex>P</tex> не более двух раз (результатом пересечения <tex>l'</tex> и <tex>P</tex> может быть только один отрезок или точка).
 
Простой многоугольник <tex>P</tex> называется '''монотонным''' относительно прямой <tex>l</tex>, если любая <tex>l'</tex>, такая что <tex>l' \perp l</tex>, пересекает стороны <tex>P</tex> не более двух раз (результатом пересечения <tex>l'</tex> и <tex>P</tex> может быть только один отрезок или точка).
Строка 49: Строка 48:
  
 
Рассмотрим самую верхнюю — максимальную по координате <tex>y</tex> вершину. Будем идти вниз по рёбрам до самой нижней — соотвественно минимальной по <tex>y</tex> вершине, то есть таким образом, что для некоторой вершины <tex>j</tex>: <tex>y_j > y_{j+1}</tex>. '''Поворотной''' назовём вершину <tex>i</tex>, на которой направление обхода будет меняется: <tex>y_{i-1} > y_i</tex> и <tex>y_i < y_{i+1}</tex>. Опишем более подробно этот тип вершин.  
 
Рассмотрим самую верхнюю — максимальную по координате <tex>y</tex> вершину. Будем идти вниз по рёбрам до самой нижней — соотвественно минимальной по <tex>y</tex> вершине, то есть таким образом, что для некоторой вершины <tex>j</tex>: <tex>y_j > y_{j+1}</tex>. '''Поворотной''' назовём вершину <tex>i</tex>, на которой направление обхода будет меняется: <tex>y_{i-1} > y_i</tex> и <tex>y_i < y_{i+1}</tex>. Опишем более подробно этот тип вершин.  
Уточним понятния ''выше'' и ''ниже'': точка <tex>p</tex> лежит ''ниже'' точки <tex>q</tex>, если <tex>p_y < q_y</tex> или если <tex>p_y = q_y</tex> и <tex>p_x > q_x</tex>, соответственно точка <tex>p</tex> лежит ''выше'' точки <tex>q</tex>, если <tex>p_y > q_y</tex> или если <tex>p_y = q_y</tex> и <tex>p_x < q_x</tex>. Это было сделано для того, чтобы избежать неопределённых ситуаций с вершинами, у которых <tex>y</tex>-координаты равны.
+
Уточним понятния ''выше'' и ''ниже'': точка <tex>p</tex> лежит ''ниже'' точки <tex>q</tex>, если <tex>p_y < q_y</tex> или если <tex>p_y < q_y</tex> и <tex>p_x > q_x</tex>, соответственно точка <tex>p</tex> лежит ''выше'' точки <tex>q</tex>, если <tex>p_y > q_y</tex> или если <tex>p_y = q_y</tex> и <tex>p_x < q_x</tex>. Это было сделано для того, чтобы избежать неопределённых ситуаций с вершинами, у которых <tex>y</tex>-координаты равны.
  
Обозначим за <tex>\phi</tex> внутренний угол при некоторой вершине и определим далее пять типов вершин, четыре из которых являются поворотными:
+
Обозначим за <tex>\phi</tex> внутренний угол при некоторой вершине вершине и определим далее пять типов вершин, четыре из которых являются поворотными:
 
* '''''start вершина''''' — два её соседа лежат ниже её самой и <tex> \phi < \pi </tex>
 
* '''''start вершина''''' — два её соседа лежат ниже её самой и <tex> \phi < \pi </tex>
 
* '''''split вершина''''' — два её соседа лежат ниже её самой и <tex> \phi > \pi </tex>
 
* '''''split вершина''''' — два её соседа лежат ниже её самой и <tex> \phi > \pi </tex>
Строка 60: Строка 59:
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Многоугольник <tex>P</tex> является <tex>y</tex>-монотонным, если в нём отсутствуют split и merge вершины.
+
Многоугольник <tex>P</tex> является <tex>y</tex>-монотонным, когда в нём отсутствуют split и merge вершины.
 
|proof=
 
|proof=
Предположим, что <tex>P</tex> не <tex>y</tex>-монотонный. Тогда докажем, что <tex>P</tex> содержит split и merge вершины. Поскольку <tex>P</tex> не <tex>y</tex>-монотонный, существует горизонтальная прямая <tex>l</tex>, которая пересекает его стороны более двух раз. Выберем <tex>l</tex> таким образом, чтобы самой левой компонентой пересечения <tex>l</tex> и <tex>P</tex> был бы отрезок <tex>pq</tex>. Далее будем двигаться наверх по сторонам <tex>P</tex>, начиная от точки <tex>q</tex>. В результате в некоторой точке <tex>r</tex>, где <tex>r \neq p</tex> (случай '''(a)''' на рисунке), прямая <tex>l</tex> снова пересечёт одну из сторон <tex>P</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам <tex>P</tex>, будет split вершиной.
+
Предположим, что <tex>P</tex> не <tex>y</tex>-монотонный. Тогда докажем, что <tex>P</tex> содержит split и merge вершины. Поскольку <tex>P</tex> не <tex>y</tex>-монотонный, горизонтальная прямая <tex>l</tex> пересекает его стороны более двух раз. Выберем <tex>l</tex> таким образом, чтобы самой левой компонентой пересечения <tex>l</tex> и <tex>P</tex> был бы отрезок <tex>pq</tex>. Далее будем двигаться наверх по сторонам <tex>P</tex>, начиная от точки <tex>q</tex>. В результате в некоторой точке <tex>r</tex>, где <tex>r \neq p</tex> (случай '''(a)''' на рисунке), прямая <tex>l</tex> снова пересечёт одну из сторон <tex>P</tex>. Отсюда самая высокая точка, которую мы достигли во время движения по сторонам <tex>P</tex>, будет split вершиной.
  
 
[[Файл:Proof_lemma.jpg|450px]]
 
[[Файл:Proof_lemma.jpg|450px]]
  
Если же <tex>r = p</tex> (случай '''(b)''' на рисунке), начём опять двигаться по сторонам <tex>P</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка <tex>r'</tex>, которая будет результатом пересечения <tex>l</tex> и <tex>P</tex>. При этом <tex>r' \neq p</tex>, в противном случае <tex>l</tex> будет пересекать <tex>P</tex> только два раза, что противоречит выбору <tex>l</tex>. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.
+
Если же <tex>r = p</tex> (случай '''(b)''' на рисунке), начём опять двигаться по сторонам <tex>P</tex> теперь уже вниз. Как и в предыдущем случае найдётся некоторая точка <tex>r'</tex>, которая будет результатом пересечения <tex>l</tex> и <tex>P</tex>. При этом <tex>r' \neq p</tex>, в противном случае <tex>l</tex> будет пересекать <tex>P</tex> только два раза, то есть <tex>P</tex> будет <tex>y</tex>-монотонным, что противоречит нашему предположению. Аналогично предыдущему случаю, выберем теперь самую низкую точку, которую мы достигли во время движения по сторонам P. Она будет merge вершиной.
 
}}
 
}}
  
Строка 72: Строка 71:
 
Чтобы сделать многоугольник монотонным, нужно избавиться от split и merge вершин путём проведения непересекающихся дигоналей из таких вершин.
 
Чтобы сделать многоугольник монотонным, нужно избавиться от split и merge вершин путём проведения непересекающихся дигоналей из таких вершин.
  
Рассмотрим горизонтальную заметающую прямую <tex>l</tex>, будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, у которой расстояние до <tex>l</tex> минимально, при этом она должна лежать соответственно выше или ниже <tex>l</tex>.
+
Рассмотрим заметающую прямую <tex>l</tex>, перпендукулярную <tex>y</tex>-оси, будем перемещать её сверху вниз вдоль плоскости на которой лежит исходный многоугольник <tex>P</tex>. Будем останавливать её в каждой вершине многоугольника. В тот момент, когда на пути заметающей прямой встречается split или merge вершина её нужно соединить с вершиной, у которой расстояние до <tex>l</tex> минимально, при этом она должна лежать соответственно выше или ниже <tex>l</tex>.
 
[[Файл:Split_case.jpg|200px|thumb|right|Обработка ''split'' вершины <tex>v_i</tex>]] Рассмотрим каждый случай подробнее:
 
[[Файл:Split_case.jpg|200px|thumb|right|Обработка ''split'' вершины <tex>v_i</tex>]] Рассмотрим каждый случай подробнее:
  
# '''''Split вершина'''''. Пусть <tex>e_j</tex> и <tex>e_k</tex> — ближайшее левое и правое ребро относительно split вершины <tex>v_i</tex>, которые <tex>l</tex> пересекает в данный момент. Нам нужно найти вершину, лежащую между <tex>e_j</tex> и <tex>e_k</tex>, наиболее приближённую к <tex>l</tex>, либо если такой точки не существет выбрать минимальную из верхних вершин <tex>e_j</tex> и <tex>e_k</tex>. Для этого будем хранить указатель на искомую вершину у левого ребра <tex>e_j</tex>, который можно заранее вычислить. Тип вершины, хранящийся в <tex>helper</tex> не имеет значения. Таким образом, чтобы построить диагональ для split вершины нужно обратиться к указателю <tex>helper(e_j)</tex> её левого ребра, которое <tex>l</tex> пересекает в данный момент.
+
 
# '''''Merge вершина'''''. В отличие от случая со split вершиной заранее вычислить указатель <tex>helper</tex> нельзя, поскольку merge вершина <tex>v_i</tex> должна быть соединена с вершиной, лежащей ниже заметающей прямой <tex>l</tex>. Для этого в <tex>helper(e_j)</tex> - левого относительно <tex>v_i</tex> ребра запишем саму <tex>v_i</tex>. Далее спускаем заметающую прямую вниз к следующей вершине <tex>v_m</tex>, обращаемся к <tex>helper</tex>'у её левого ребра. Проверяем, если там хранится merge вершина, строим диагональ <tex>v_{i}v_{m}</tex>. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.
+
1) '''''Split вершина'''''. Пусть <tex>e_j</tex> и <tex>e_k</tex> — ближайшее левое и правое ребро относительно split вершины <tex>v_i</tex>, которые <tex>l</tex> пересекает в данный момент. Нам нужно найти вершину, лежащую между <tex>e_j</tex> и <tex>e_k</tex>, наиболее приближённую к <tex>l</tex>, либо если такой точки не существет выбрать минимальную из верхних вершин <tex>e_j</tex> и <tex>e_k</tex>. Для этого будем хранить указатель на искомую вершину у левого ребра <tex>e_j</tex>, который можно заранее вычислить. Тип вершины, хранящийся в <tex>helper</tex> не имеет значения. Таким образом, чтобы построить диагональ для split вершины нужно обратиться к указателю <tex>helper</tex> её левого ребра, которое <tex>l</tex> пересекает в данный момент.
[[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''merge'' вершины <tex>v_i</tex>. На рисунке слева <tex>v_i</tex> записывается в качестве <tex>helper</tex>'а своего левого ребра. На правом рисунке ближайшая вершина <tex>v_m</tex> при обращении к своему левому ребру <tex>helper(e_j)</tex> находит <tex>v_i</tex> и образует диагональ <tex>v_{i}v_m</tex>]]
+
 
 +
2) '''''Merge вершина'''''. В отличие от случая со split вершиной заранее вычислить указатель <tex>helper</tex> нельзя, поскольку merge вершина <tex>v_i</tex> должна быть соединена с вершиной, лежащей ниже заметающей прямой <tex>l</tex>. Для этого в <tex>helper</tex> левого относительно <tex>v_i</tex> ребра запишем саму <tex>v_i</tex>. Далее спускаем заметающую прямую вниз к следующей вершине <tex>v_m</tex>, обращаемся к <tex>helper</tex>'у её левого ребра. Проверяем, если там хранится merge вершина, строим диагональ <tex>v_{i}v_{m}</tex>. Последняя проверка осуществляется для любого типа вершины, кроме split, согласно п.1.
 +
[[Файл:Merge_case_1_2.jpg|500px|thumb|center|Обработка ''megre'' вершины <tex>v_i</tex>. На рисунке слева <tex>v_i</tex> записывается в качестве <tex>helper</tex>'а своего левого ребра. На правом рисунке ближайшая вершина <tex>v_m</tex> при обращении к своему левому ребру <tex>helper(e_j)</tex> находит <tex>v_i</tex> и образует диагональ <tex>v_{i}v_m</tex>]]
  
 
===== Структуры данных =====
 
===== Структуры данных =====
Строка 90: Строка 91:
 
     Construct(Q); // функция Construct создаёт объекты <tex>D</tex> и <tex>Q</tex> , описанные выше.
 
     Construct(Q); // функция Construct создаёт объекты <tex>D</tex> и <tex>Q</tex> , описанные выше.
 
     bst T = new bst();
 
     bst T = new bst();
     while Q <tex> \neq  \varnothing </tex>
+
     while Q <tex> \neq  \varnothing </tex>
 
       Remove <tex>v_{max}</tex> from Q // удаление вершины с наивысшим приоритетом из <tex>Q</tex>     
 
       Remove <tex>v_{max}</tex> from Q // удаление вершины с наивысшим приоритетом из <tex>Q</tex>     
       switch (Type_of_vertex(<tex>v_{max}</tex>)): // определение типа вершины
+
       switch (Type_of_vertex(<tex>v_{max}</tex>)): //определение типа вершины
 
           case 'start':
 
           case 'start':
 
             HandleStartVertex(<tex>v_{max}</tex>);
 
             HandleStartVertex(<tex>v_{max}</tex>);
Строка 104: Строка 105:
 
             HandleRegularVertex(<tex>v_{max}</tex>);
 
             HandleRegularVertex(<tex>v_{max}</tex>);
  
[[Файл:Split-merge - result.png|470px|thumb|right]]
+
[[Файл:Split-merge - result.png|470px]]
  
 
Опишем теперь каждый метод из последнего switch:
 
Опишем теперь каждый метод из последнего switch:
Строка 115: Строка 116:
 
     edge <tex>e_j</tex> = <tex>l \cap P</tex>
 
     edge <tex>e_j</tex> = <tex>l \cap P</tex>
 
     Search <tex>e_j</tex> in T
 
     Search <tex>e_j</tex> in T
     Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{j})</tex>) in D
+
     Insert edge(<tex>v_{i}</tex>, <tex>helper(e_{i})</tex>) in D
 
     <tex>helper(e_{j}) \leftarrow  v_i</tex>  
 
     <tex>helper(e_{j}) \leftarrow  v_i</tex>  
 
     Insert <tex>e_{i}</tex> in T
 
     Insert <tex>e_{i}</tex> in T
Строка 159: Строка 160:
 
|proof=
 
|proof=
 
Тот факт, что <tex>P</tex> разбивается на монотонные части следует из предыдущей леммы.
 
Тот факт, что <tex>P</tex> разбивается на монотонные части следует из предыдущей леммы.
Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, попарно не пересекаются и не пересекают стороны <tex>P</tex>.  
+
Остаётся доказать, что диагонали, построенные в процессе выполнения алгоритма, не попарно не пересекаются и не пересекают стороны <tex>P</tex>.  
  
 
Рассмотрим случай выполнения функции ''HandleSplitVertex'', поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершин, в отличие от остальных функций (в них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной).  
 
Рассмотрим случай выполнения функции ''HandleSplitVertex'', поскольку это наиболее общий случай: split вершина может быть соединена со всеми типами вершин, в отличие от остальных функций (в них рассматриваемая в данный момент вершина может быть соединена только с merge вершиной).  
Строка 170: Строка 171:
 
}}
 
}}
  
===== Оценка работы =====
+
===== Оценкка работы =====
Построение описанной выше приоритетной очереди <tex>Q</tex> происходит за линейное время. Когда заметающая прямая останавливается в вершине: операции с очередью занимают константу по времени, операции с деревом <tex>T</tex> на запросы и обновления требуют <tex>\mathcal{O}(\mathcal \log n)</tex>. Добавление диагонали в <tex>D</tex> требует <tex>\mathcal{O}(1)</tex>. В итоге обработка каждой вершины требует <tex>\mathcal{O}(\log n)</tex>, а весь алгоритм соответственно <tex>\mathcal{O}(n \log n)</tex>. Что касается памяти, она очевидно составляет <tex>\mathcal{O}(n) </tex>. Очередь <tex>Q</tex> и дерево <tex>T</tex> занимают линейную память.
+
Построение описанной выше приоритетной очереди <tex>Q</tex> происходит за линейное время. Когда заметающая прямая останавливается в вершине: операции с очередью занимают константу по времени, операции с деревом <tex>T</tex> на запросы и обновления требуют <tex>\mathcal{O}(\mathcal \log(n))</tex>. Добавление диагонали в <tex>D</tex> требует <tex>\mathcal{O}(1)</tex>. В итоге обработка каждой вершины требует <tex>\mathcal{O}(\log(n))</tex>, а весь алгоритм соответственно <tex>\mathcal{O}(n \log(n))</tex>. Что касается памяти, она очевидно составляет <tex>\mathcal{O}(n) </tex>. Очередь <tex>Q</tex> и дерево <tex>T</tex> занимают линейную память.
  
 
[[Файл:Triangulationg intro.jpg|170px|thumb|right|Зелёным помечена так называемая воронка, которая образуется, когда мы достигнем красной вершины]]
 
[[Файл:Triangulationg intro.jpg|170px|thumb|right|Зелёным помечена так называемая воронка, которая образуется, когда мы достигнем красной вершины]]
 
 
==== Триангуляция монотонного многоугольника ====
 
==== Триангуляция монотонного многоугольника ====
  
Строка 257: Строка 257:
 
Доказательство будем вести по индукции. Базовый случай: <tex>n = 4</tex>. Предположим для всех многоугольников, количество вершин в которых не больше <tex>n</tex>, теорема верна. Рассмотрим многоугольник <tex>P</tex>, в котором <tex>n+1</tex> вершина. Далее возможны два случая:
 
Доказательство будем вести по индукции. Базовый случай: <tex>n = 4</tex>. Предположим для всех многоугольников, количество вершин в которых не больше <tex>n</tex>, теорема верна. Рассмотрим многоугольник <tex>P</tex>, в котором <tex>n+1</tex> вершина. Далее возможны два случая:
 
[[Файл:Ear case1.jpg‎|300px|thumb|left|Случай, когда <tex>v_i</tex> является ухом в <tex>P</tex>]]
 
[[Файл:Ear case1.jpg‎|300px|thumb|left|Случай, когда <tex>v_i</tex> является ухом в <tex>P</tex>]]
* Произвольная выпуклая вершина <tex>v_i</tex> многоугольника <tex>P</tex> является ухом. Отрезав это ухо, мы уменьшим число вершин <tex>P</tex> на одну. В результате, получиv <tex>n</tex>-вершинный многоугольник <tex>P'</tex>. По предположению индукции у него существует два непересекающихся уха. Учитывая, что уши <tex>P'</tex> являются ушами и <tex>P</tex>, несложно заметить, что для <tex>P</tex> теорема верна.
+
* Произвольная вершина <tex>v_i</tex> многоугольника <tex>P</tex> является ухом. Отрезав это ухо, мы уменьшим число вершин <tex>P</tex> на одну. В результате, получиv <tex>n</tex>-вершинный многоугольник <tex>P'</tex>. По предположению индукции у него существует два непересекающихся уха. Учитывая, что уши <tex>P'</tex> являются ушами и <tex>P</tex>, несложно заметить, что для <tex>P</tex> теорема верна.
  
* Произвольная выпуклая вершина <tex>v_i</tex> многоугольника <tex>P</tex> не является ухом. В таком случае в треугольнике <tex>\Delta v_{i-1}v_{i}v_{i+1}</tex> лежат вершины, принадлежащие <tex>P</tex>. Из этих вершин выберем вершину <tex>q</tex>, которая будет ближе всего к <tex>v_i</tex>. Проведём отрезок <tex>Q</tex>, который разделит <tex>P</tex> на два многоугольника: <tex>P_1</tex> и <tex>P_2</tex>. В каждом из них будет не более <tex>n</tex> вершин, следовательно у каждого будет по два непересекающихся уха. Даже если предположить, что ухо из <tex>P_1</tex> и ухо из <tex>P_2</tex> будут пересекаться по стороне <tex>v_{i}q</tex>, в <tex>P</tex> всё равно будет не менее двух непересекающихся ушей.
+
* Произвольная вершина <tex>v_i</tex> многоугольника <tex>P</tex> не является ухом. В таком случае в треугольнике <tex>\Delta v_{i-1}v_{i}v_{i+1}</tex> лежат вершины, принадлежащие <tex>P</tex>. Из этих вершин выберем вершину <tex>q</tex>, которая будет ближе всего к <tex>v_i</tex>. Проведём отрезок <tex>Q</tex>, который разделит <tex>P</tex> на два многоугольника: <tex>P_1</tex> и <tex>P_2</tex>. В каждом из них будет не более <tex>n</tex> вершин, следовательно у каждого будет по два непересекающихся уха. Даже если предположить, что ухо из <tex>P_1</tex> и ухо из <tex>P_2</tex> будут пересекаться по стороне <tex>v_{i}q</tex>, в <tex>P</tex> всё равно будет не менее двух непересекающихся ушей.
 
[[Файл:Ear_case2.jpg|400px|thumb|center|Случай, когда <tex>v_i</tex> не является ухом в <tex>P</tex>. Желтым и зелёным отмечены уши, принадлежащие <tex>P_2</tex> и <tex>P_1</tex> соответственно.]]
 
[[Файл:Ear_case2.jpg|400px|thumb|center|Случай, когда <tex>v_i</tex> не является ухом в <tex>P</tex>. Желтым и зелёным отмечены уши, принадлежащие <tex>P_2</tex> и <tex>P_1</tex> соответственно.]]
 
}}
 
}}
Строка 298: Строка 298:
  
 
==== Оценка работы ====
 
==== Оценка работы ====
Изначально в многоугольнике содержится <tex>\mathcal{O}(n)</tex> ушей. Нетрудно понять, что в процессе отрезания ушей, смежные точки могут тоже становиться ушами. В результате триангуляции образуется <tex>n - 3</tex> диагонали, соответственно максимальное количество вершин, которые в процессе могут становиться ушами <tex>2n - 6</tex>. Итого общее количество ушей будет <tex>\mathcal{O}(n)</tex>. Определить, является ли вершина ухом можно за <tex>\mathcal{O}(n)</tex>, поскольку используется алгоритм определения принадлежности точки треугольнику — это <tex>\mathcal{O}(1)</tex>. Таким образом общий процесс отрезания ушей займёт <tex>\mathcal{O}(n^2)</tex>. Невыпуклых вершин всего <tex>\mathcal{O}(n)</tex>, каждая из них обрабатывается за константу, поэтому общее время для их обработки <tex>\mathcal{O}(n)</tex>. Списки рёбер и вершин строятся за линейное время, добавление ребра и удаление вершины в каждом из них работает за константу. Общее время <tex>\mathcal{O}(n^2)</tex>. Поскольку храним только два списка — память линейная.
+
Изначально в многоугольнике содержится <tex>\mathcal{O}(n)</tex> ушей. Нетрудно понять, что в процессе отрезания ушей, смежные точки могут тоже становиться ушами. В результате триангуляции образуется <tex>n - 3</tex> диагонали, соответственно максимальное количество вершин, которые в процессе могут становиться ушами <tex>2n - 6</tex>. Итого общее количество ушей будет <tex>\mathcal{O}(n)</tex>. Определить, является ли вершина ухом можно за <tex>\mathcal{O}(n)</tex>, поскольку используется алгоритм определения принадлежности точки треугольнику — это <tex>\mathcal{O}(3)</tex>. Таким образом общий процесс отрезания ушей займёт <tex>\mathcal{O}(n^2)</tex>. Невыпуклых вершин всего <tex>\mathcal{O}(n)</tex>, каждая из них обрабатывается за константу, поэтому общее время для их обработки <tex>\mathcal{O}(n)</tex>. Списки рёбер и вершин строятся за линейное время, добавление ребра и удаление вершины в каждом из них работает за константу. Общее время <tex>\mathcal{O}(n^2)</tex>. Поскольку храним только два списка — память линейная.
 +
 
 +
ДОПИЛЮ ЕЩЁ.
  
 
== Источники ==
 
== Источники ==
Строка 306: Строка 308:
  
 
* [http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf  Triangulation by ear-clipping]
 
* [http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf  Triangulation by ear-clipping]
 
[[Категория: Вычислительная геометрия]]
 

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблоны, используемые на этой странице: