Участник:Kabanov — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Ушной метод)
м (Сумма)
Строка 1: Строка 1:
'''Триангуляция полигона '''  —  декомпозиция многоугольника <tex>P</tex> на множество треугольников, внутренние области которых попарно не пересекаются и объединение которых в совокупности составляет <tex>P</tex>. В строгом смысле слова, вершины этих треугольников должны совпадать с вершинами исходного многоугольника. Триангуляция любого многоугольника не единственна. В этом можно убедиться из примера на рисунке.
+
== Описание ==
 
+
Сумма Минковского позволяет решать задачу Motion Planning, в случае, когда робота нельзя поворачивать. Таким образом, каждой точке <tex>(x, y)</tex> ставится в соответствие фигура робота <tex>R(x, y)</tex>, с точкой привязки помещенной в точку <tex>(x, y)</tex>.
На плоскости задан произвольный многоугольник. Стороны многоугольника не пересекаются. Требуется найти его триангуляцию.
+
{{Определение
 
+
|definition=Для заданного робота <tex>R</tex> и препятствия <tex>P</tex>, '''К-препятствием''' называется множество точек, будучи помещенным в которые, робот заденет препятствие:  
== Теорема о существовании триангуляции ==
+
<tex>CP := \{(x, y) : R(x, y) \cap P \neq \varnothing\}</tex>
 
 
'''Простым многоугольником''' является фигура, ограниченная одной замкнутой ломаной, стороны которой не пересекаются. Таким образом, случаи многоугольников с дырками в теореме исключаются.
 
{{Теорема
 
|about = О существовании триангуляции многоугольника
 
|statement =
 
У любого простого <tex>n</tex>-вершинного многоугольника <tex>P</tex> всегда существует триангуляция, причём количество треугольников в ней <tex>n - 2</tex> независимо от самой триангуляции.
 
|proof=
 
[[Файл:Proof theorem.jpg|100px|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>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>n - 2</tex> треугольников. Рассмотрим произвольную диагональ <tex>d</tex> в триангуляции <tex>T_P</tex>. <tex>d</tex> делит <tex>P</tex> на два многоугольника <tex>P_1</tex> и <tex>P_2</tex>, количество вершин в которых  <tex>m_1</tex> и <tex>m_2</tex> соответственно. Каждая вершина <tex>P</tex> встречается только в одном из двух многоугольников <tex>P_1</tex> и <tex>P_2</tex>, за исключением тех, которые являются концами <tex>d</tex>, поэтому справедливо следующее: <tex>m_1 + m_2 = n + 2</tex>. По индукции, любая триангуляция <tex>P_i</tex> состоит из <tex>m_i - 2</tex> треугольников, откуда следует, что <tex>T_P</tex>. состоит из <tex>(m_1 - 2) + (m_2 - 2) = n - 2</tex> треугольников.
 
 
}}
 
}}
 
== Ушной метод ==
 
 
{{Определение
 
{{Определение
 +
|definition='''Суммой Минковского''' двух множеств <tex>S_1 \subset R^2, S_2 \subset R^2</tex> называется множество <tex>S_1 \oplus S_2 := \{p + q : p \in S_1, q \in S_2\}</tex>, где <tex>p + q</tex> обозначает векторную сумму.
 +
}}{{Определение
 
|definition=
 
|definition=
Вершина <tex>v_i</tex> называется '''ухом''', если диагональ <tex>v_{i-1}v_{i+1}</tex> лежит строго во внутренней области многоугольника <tex>P</tex>
+
'''Отрицанием''' множества <tex>S \subset R^2</tex> называется множество <tex>-S := \{-p : p \in S\}</tex>, где <tex>-p</tex> обозначает векторное отрицание.
 
}}
 
}}
 
 
{{Теорема
 
{{Теорема
|about = О существовании двух ушей многоугольника
+
|statement=Для заданного робота <tex>R</tex> и препятствия <tex>P</tex>, К-препятствием является множество <tex>P \oplus (-R(0, 0))</tex>.
|statement =
 
У любого простого <tex>n</tex>-вершинного многоугольника <tex>P</tex> всегда существует два не пересекающихся между собой уха.
 
 
|proof=
 
|proof=
[[Файл:Ear case1.jpg‎|200px|thumb|left]]
+
[[Файл:minkowski_sum.png | right | 100px]]
[[Файл:Ear_case2.jpg|200px|thumb|right]]
+
Необходимо доказать, что робот <tex>R(x, y)</tex> пересекает препятствие <tex>P</tex> в том и только в том случае, если <tex>(x, y) \in P \oplus (-R(0, 0))</tex>.
Доказательство будем вести по индукции. Базовый случай: <tex>n = 4</tex>. Предположим для всех многоугольников, количество вершин в которых не больше <tex>n</tex>, теорема верна. Рассмотрим многоугольник <tex>P</tex>, в котором <tex>n+1</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>q = (q_x , q_y)</tex> является точкой пересечения. Тогда, так как <tex>q \in R(x, y)</tex>, то <tex>(q_x - x, q_y - y) \in R(0,0)</tex>, или <tex>(x - q_x , y - q_y) \in -R(0,0)</tex>. А заметив, что <tex>q \in P</tex>, получаем <tex>(x, y) \in P \oplus (-R(0,0))</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>(x, y) \in P \oplus (-R(0,0))</tex>, тогда существуют точки <tex>(r_x , r_y) \in R(0, 0)</tex> и <tex>(p_x , p_y) \in P</tex> такие, что <tex>(x, y) = (p_x - r_x , p_y - r_y)</tex> или <tex>(p_x , p_y) = (x + r_x , y + r_y)</tex>, а это означает, что <tex>R(x, y)</tex> пересекает <tex>P</tex>.
 
}}
 
}}
  
==== Идея ====
+
Допустим, для простоты, что робот и все препятствия выпуклые, а позже обобщим для невыпуклых фигур.
Рассмотрим все вершины многоугольника <tex>P</tex>, и где возможно, будем отрезать уши до тех пор, пока <tex>P</tex> не станет треугольником.
+
{{Теорема
 +
|statement=
 +
Пусть заданы две выпуклые фигуры <tex>P</tex> и <tex>R</tex>, с числом вершин <tex>n</tex> и <tex>m</tex> соответственно. Тогда суммой Минковского <tex>P \oplus R</tex> является выпуклая фигура с не более чем <tex>m + n</tex> вершинами.
 +
|proof=
 +
[[Файл:minkowski_extreme.png | right | 200px]]
 +
Для начала заметим, что любая крайняя точка в направлении вектора <tex>\vec{d}</tex> есть сумма крайних точек фигур в этом направлении. Убедиться в этом можно спроецировав обе фигуры на вектор <tex>\vec{d}</tex>.
  
Будем рассматривать вершины многоугольника в порядке обхода. Индексирование вершин для удобства будем вести по модулю <tex>n</tex>, т.е. <tex>v_{-1} = v_{n-1}</tex> и <tex>v_0 = v_n</tex>. Если вершина <tex>v_i</tex> является ухом, построим диагональ <tex>v_{i+1}v_{i-1}</tex> и отрежем треугольник <tex>\Delta v_{i-1}v_{i}v_{i+1}</tex> от <tex>P</tex>. В противном случае переходим к следующей вершине <tex>v_{i+1}</tex> в порядке обхода.
+
Теперь рассмотрим произвольное ребро <tex>e</tex> из <tex>P \oplus R</tex>. Оно является крайним в направлении к своей нормали, а значит оно образовано крайними точками фигур, и хотя бы у одной из фигур должно быть ребро, которое является крайним в этом направлении. Сопоставим <tex>e</tex> с этим ребром. Тогда сопоставив таким образом всем ребрам <tex>P \oplus R</tex> ребра исходных фигур, получаем что всего ребер в <tex>P \oplus R</tex> не более чем <tex>m + n</tex>, так как каждое ребро исходных фигур использовалось не более раза.
 
+
}}
==== Алгоритм ====
 
При проверке каждой вершину следует для начала проверить, является ли она выпуклой, в противном случае её просто нет надобности рассматривать в качестве уха. Это несложно сделать, воспользовавшись [[Предикат_"левый_поворот"|левым поворотом]]. "Ушную" проверку вершины будем осуществлять алгоритмом принадлежности точки <tex>n</tex>-угольнику (в нашем случае треугольнику). В качестве поддерживаемых структур удобно хранить DCEL, в котором будем строить новые диагонали, и список вершин с двойными связями, аналогичный DCEL по построению.
 
  
==== Псевдокод ====
+
== Псевдокод ==
DCVL D1 //список вершин doubly connected vertex list по аналогии с DCEL
+
  i = j = 0
DCEL D2
+
  V[n] = V[0], V[n+1] = V[1], W[n] = W[0], W[n+1] = W[1]
Construct(D1);
+
  while i < n or j < m do
Construct(D2);
+
    add V[i]+W[j] to answer
vertex v = random_vertex_of(D1);
+
    if angle(V[i], V[i+1]) < angle(W[j], W[j+1])
while size_of(D1) <tex> \neq </tex> 3
+
      ++i
    if IsConvex(v) //проверка на выпуклость
+
    else if angle(V[i], V[i+1]) > angle(W[j], W[j+1])
      for each Vertex v_i in D1
+
      ++j
          if v_i <tex> \neq </tex> v, v.prev(), v.next()                //проверка всех вершин на
+
    else
                and v_i <tex>\in </tex> Triangle(v, v.prev(), v.next())//принадлежность треугольнику,  
+
      ++i, ++j
                                                        //одной из вершин которого
+
Здесь множества точек <tex>V</tex> и <tex>W</tex> отсортированы в порядке обхода против часовой стрелки, причем первым элементом в обоих массивах является самая левая нижняя точка множества. Функция angle возвращает значение полярного угла вектора, заданного ее аргументами.
                                                        //является потенциальное ухо v.
 
            edge e = new edge(v.prev, v.next)
 
            Insert e in D2;
 
            v = v.next
 
            Delete v.prev from D1
 
  
==== Корректность ====
+
Корректность алгоритма следует из доказательства предыдущей теоремы, а время работы равно <tex>O(n + m)</tex>, так как на каждой итерации хотя бы один из индексов <tex>i</tex> и <tex>j</tex> увеличивается.
При нахождении каждого уха от многоугольника <tex>P</tex> отрезается треугольник, состоящий из самого уха и его двух смежных вершин. Существование ушей в свою очередь следует из теоремы, доказанной выше. В конце алгоритма, когда все уши от <tex>P</tex> отрезаны, остается только один треугольник. Как несложно видеть, триангуляция выстраивается корректно.
+
== Случай невыпуклых фигур ==
 +
Для начала заметим следующий факт:
 +
<tex>S_1 \oplus (S_2 \cup S_3) = (S_1 \oplus S_2) \cup (S_1 \oplus S_3)</tex>
  
==== Оценка работы ====
+
В случае, когда одна из фигур невыпукла, её сначала надо затриангулировать, получив <tex>n-2</tex> треугольников. После этого, уже известным алгоритмом, надо построить <tex>n-2</tex> выпуклых фигур с не более чем <tex>m+3</tex> вершинами, которые будут суммами Минковского соответствующих треугольников. Объединение этих выпуклых фигур будет состоять из <tex>O(nm)</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}(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>n-2</tex> и <tex>m-2</tex> треугольников соответственно. Построив суммы Минковского множеств этих треугольников получим <tex>(n-2)(m-2)</tex> выпуклых фигур, объединение которых состоит из <tex>O(n^2m^2)</tex> вершин.

Версия 21:44, 20 января 2015

Описание

Сумма Минковского позволяет решать задачу Motion Planning, в случае, когда робота нельзя поворачивать. Таким образом, каждой точке [math](x, y)[/math] ставится в соответствие фигура робота [math]R(x, y)[/math], с точкой привязки помещенной в точку [math](x, y)[/math].

Определение:
Для заданного робота [math]R[/math] и препятствия [math]P[/math], К-препятствием называется множество точек, будучи помещенным в которые, робот заденет препятствие: [math]CP := \{(x, y) : R(x, y) \cap P \neq \varnothing\}[/math]


Определение:
Суммой Минковского двух множеств [math]S_1 \subset R^2, S_2 \subset R^2[/math] называется множество [math]S_1 \oplus S_2 := \{p + q : p \in S_1, q \in S_2\}[/math], где [math]p + q[/math] обозначает векторную сумму.
Определение:
Отрицанием множества [math]S \subset R^2[/math] называется множество [math]-S := \{-p : p \in S\}[/math], где [math]-p[/math] обозначает векторное отрицание.
Теорема:
Для заданного робота [math]R[/math] и препятствия [math]P[/math], К-препятствием является множество [math]P \oplus (-R(0, 0))[/math].
Доказательство:
[math]\triangleright[/math]
Minkowski sum.png

Необходимо доказать, что робот [math]R(x, y)[/math] пересекает препятствие [math]P[/math] в том и только в том случае, если [math](x, y) \in P \oplus (-R(0, 0))[/math].

Пусть робот задевает препятствие, и точка [math]q = (q_x , q_y)[/math] является точкой пересечения. Тогда, так как [math]q \in R(x, y)[/math], то [math](q_x - x, q_y - y) \in R(0,0)[/math], или [math](x - q_x , y - q_y) \in -R(0,0)[/math]. А заметив, что [math]q \in P[/math], получаем [math](x, y) \in P \oplus (-R(0,0))[/math].

В обратную сторону, пусть [math](x, y) \in P \oplus (-R(0,0))[/math], тогда существуют точки [math](r_x , r_y) \in R(0, 0)[/math] и [math](p_x , p_y) \in P[/math] такие, что [math](x, y) = (p_x - r_x , p_y - r_y)[/math] или [math](p_x , p_y) = (x + r_x , y + r_y)[/math], а это означает, что [math]R(x, y)[/math] пересекает [math]P[/math].
[math]\triangleleft[/math]

Допустим, для простоты, что робот и все препятствия выпуклые, а позже обобщим для невыпуклых фигур.

Теорема:
Пусть заданы две выпуклые фигуры [math]P[/math] и [math]R[/math], с числом вершин [math]n[/math] и [math]m[/math] соответственно. Тогда суммой Минковского [math]P \oplus R[/math] является выпуклая фигура с не более чем [math]m + n[/math] вершинами.
Доказательство:
[math]\triangleright[/math]
Minkowski extreme.png

Для начала заметим, что любая крайняя точка в направлении вектора [math]\vec{d}[/math] есть сумма крайних точек фигур в этом направлении. Убедиться в этом можно спроецировав обе фигуры на вектор [math]\vec{d}[/math].

Теперь рассмотрим произвольное ребро [math]e[/math] из [math]P \oplus R[/math]. Оно является крайним в направлении к своей нормали, а значит оно образовано крайними точками фигур, и хотя бы у одной из фигур должно быть ребро, которое является крайним в этом направлении. Сопоставим [math]e[/math] с этим ребром. Тогда сопоставив таким образом всем ребрам [math]P \oplus R[/math] ребра исходных фигур, получаем что всего ребер в [math]P \oplus R[/math] не более чем [math]m + n[/math], так как каждое ребро исходных фигур использовалось не более раза.
[math]\triangleleft[/math]

Псевдокод

 i = j = 0
 V[n] = V[0], V[n+1] = V[1], W[n] = W[0], W[n+1] = W[1]
 while i < n or j < m do
   add V[i]+W[j] to answer
   if angle(V[i], V[i+1]) < angle(W[j], W[j+1])
     ++i
   else if angle(V[i], V[i+1]) > angle(W[j], W[j+1])
     ++j
   else
     ++i, ++j

Здесь множества точек [math]V[/math] и [math]W[/math] отсортированы в порядке обхода против часовой стрелки, причем первым элементом в обоих массивах является самая левая нижняя точка множества. Функция angle возвращает значение полярного угла вектора, заданного ее аргументами.

Корректность алгоритма следует из доказательства предыдущей теоремы, а время работы равно [math]O(n + m)[/math], так как на каждой итерации хотя бы один из индексов [math]i[/math] и [math]j[/math] увеличивается.

Случай невыпуклых фигур

Для начала заметим следующий факт: [math]S_1 \oplus (S_2 \cup S_3) = (S_1 \oplus S_2) \cup (S_1 \oplus S_3)[/math]

В случае, когда одна из фигур невыпукла, её сначала надо затриангулировать, получив [math]n-2[/math] треугольников. После этого, уже известным алгоритмом, надо построить [math]n-2[/math] выпуклых фигур с не более чем [math]m+3[/math] вершинами, которые будут суммами Минковского соответствующих треугольников. Объединение этих выпуклых фигур будет состоять из [math]O(nm)[/math] вершин.

В случае, когда обе фигуры невыпуклы, обе эти фигуры надо затриангулировать, получив [math]n-2[/math] и [math]m-2[/math] треугольников соответственно. Построив суммы Минковского множеств этих треугольников получим [math](n-2)(m-2)[/math] выпуклых фигур, объединение которых состоит из [math]O(n^2m^2)[/math] вершин.