78
правок
Изменения
Новая страница: «{{notready}} == Описание == Сумма Минковского позволяет решать задачу Motion Planning, в случае, когда ...»
{{notready}}
== Описание ==
Сумма Минковского позволяет решать задачу 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>}}
{{Определение
|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=
'''Отрицанием''' множества <tex>S \subset R^2</tex> называется множество <tex>-S := \{-p : p \in S\}</tex>, где <tex>-p</tex> обозначает векторное отрицание.
}}
{{Теорема
|statement=
Для заданного робота <tex>R</tex> и препятствия <tex>P</tex>, К-препятствием является множество <tex>P \oplus (-R(0, 0))</tex>.
|proof=
Необходимо доказать, что робот <tex>R(x, y)</tex> пересекает препятствие <tex>P</tex> в том и только в том случае, если <tex>(x, y) \in P \oplus (-R(0, 0))</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>(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>.
}}
Допустим, для простоты, что робот и все препятствия выпуклые, а позже обобщим для невыпуклых фигур.
{{Теорема
|statement=
Пусть заданы две выпуклые фигуры <tex>P</tex> и <tex>R</tex>, с числом вершин <tex>n</tex> и <tex>m</tex> соответственно. Тогда суммой Минковского <tex>P \oplus R</tex> является выпуклая фигура с не более чем <tex>m + n</tex> вершинами.
|proof=
Для начала заметим, что любая крайняя точка в направлении вектора <tex>\vec{d}</tex> есть сумма крайних точек фигур в этом направлении. Убедиться в этом можно спроецировав обе фигуры на вектор <tex>\vec{d}</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>, так как каждое ребро исходных фигур использовалось не более раза.
}}
== Алгоритм ==
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
Здесь множества точек <tex>V</tex> и <tex>W</tex> отсортированы в порядке обхода против часовой стрелки, причем первым элементом в обоих массивах является самая левая нижняя точка множества. Функция angle возвращает значение полярного угла вектора, заданного ее аргументами.
Корректность алгоритма следует из доказательства предыдущей теоремы, а время работы равно <tex>O(n + m)</tex>, так как на каждой итерации хотя бы один из индексов <tex>i</tex> и <tex>j</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>n-2</tex> и <tex>m-2</tex> треугольников соответственно. Построив суммы Минковского множеств этих треугольников получим <tex>(n-2)(m-2)</tex> выпуклых фигур, объединение которых состоит из <tex>O(n^2m^2)</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>}}
{{Определение
|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=
'''Отрицанием''' множества <tex>S \subset R^2</tex> называется множество <tex>-S := \{-p : p \in S\}</tex>, где <tex>-p</tex> обозначает векторное отрицание.
}}
{{Теорема
|statement=
Для заданного робота <tex>R</tex> и препятствия <tex>P</tex>, К-препятствием является множество <tex>P \oplus (-R(0, 0))</tex>.
|proof=
Необходимо доказать, что робот <tex>R(x, y)</tex> пересекает препятствие <tex>P</tex> в том и только в том случае, если <tex>(x, y) \in P \oplus (-R(0, 0))</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>(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>.
}}
Допустим, для простоты, что робот и все препятствия выпуклые, а позже обобщим для невыпуклых фигур.
{{Теорема
|statement=
Пусть заданы две выпуклые фигуры <tex>P</tex> и <tex>R</tex>, с числом вершин <tex>n</tex> и <tex>m</tex> соответственно. Тогда суммой Минковского <tex>P \oplus R</tex> является выпуклая фигура с не более чем <tex>m + n</tex> вершинами.
|proof=
Для начала заметим, что любая крайняя точка в направлении вектора <tex>\vec{d}</tex> есть сумма крайних точек фигур в этом направлении. Убедиться в этом можно спроецировав обе фигуры на вектор <tex>\vec{d}</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>, так как каждое ребро исходных фигур использовалось не более раза.
}}
== Алгоритм ==
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
Здесь множества точек <tex>V</tex> и <tex>W</tex> отсортированы в порядке обхода против часовой стрелки, причем первым элементом в обоих массивах является самая левая нижняя точка множества. Функция angle возвращает значение полярного угла вектора, заданного ее аргументами.
Корректность алгоритма следует из доказательства предыдущей теоремы, а время работы равно <tex>O(n + m)</tex>, так как на каждой итерации хотя бы один из индексов <tex>i</tex> и <tex>j</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>n-2</tex> и <tex>m-2</tex> треугольников соответственно. Построив суммы Минковского множеств этих треугольников получим <tex>(n-2)(m-2)</tex> выпуклых фигур, объединение которых состоит из <tex>O(n^2m^2)</tex> вершин.
