78
правок
Изменения
Нет описания правки
{{notreadyready}}
== Описание ==
{|align="center" |-valign="top" |Сумма Минковского позволяет решать задачу 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>}}
|[[Файл:minkowski_sum.png | 230px]]
|}
{{Определение
|definition=
Пусть заданы две выпуклые фигуры <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 | 290px]]
Для начала заметим, что любая крайняя точка в направлении вектора <tex>\vec{d}</tex> есть сумма крайних точек фигур в этом направлении. Убедиться в этом можно спроецировав обе фигуры на вектор <tex>\vec{d}</tex>.
В случае, когда обе фигуры невыпуклы, обе эти фигуры надо затриангулировать, получив <tex>n-2</tex> и <tex>m-2</tex> треугольников соответственно. Построив суммы Минковского множеств этих треугольников получим <tex>(n-2)(m-2)</tex> выпуклых фигур, объединение которых состоит из <tex>O(n^2m^2)</tex> вершин.
{|align="center"
|-valign="top"
|[[Файл:minkowski_medium_example.png | thumb | 550px | Пример суммы Минковского с O(nm) вершинами]]
|[[Файл:minkowski_hard_example.png | thumb | 550px | Пример суммы Минковского с O(n<sup>2</sup>m<sup>2</sup>) вершинами]]
|}
