Visibility graph и motion planning — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 25: Строка 25:
 
В общем тут все очевидно. Тут мы просто двигаем не точку, а произвольный выпуклый полигон. Если мы его не можем вращать, просто "обводим"  препятствия нашим полигоном (запиливаем [[Сумма Минковского (определение, вычисление)|сумму Минковского]] препятствий и полигона) и получаем другие препятствия, но зато теперь мы двигаем точку. А это мы уже научились делать выше.
 
В общем тут все очевидно. Тут мы просто двигаем не точку, а произвольный выпуклый полигон. Если мы его не можем вращать, просто "обводим"  препятствия нашим полигоном (запиливаем [[Сумма Минковского (определение, вычисление)|сумму Минковского]] препятствий и полигона) и получаем другие препятствия, но зато теперь мы двигаем точку. А это мы уже научились делать выше.
  
Если же этот полигон можно вращать, то делаем примерно то же самое, только как-то по-хитрому. Нам про это, кажется не рассказывали(или так же :))
+
Если же этот полигон можно вращать, то делаем примерно то же самое, только как-то по-хитрому. Нам про это, кажется, не рассказывали(или рассказывали так же:))
  
 
== Источники ==
 
== Источники ==

Версия 00:50, 7 января 2014

Конспект написан не до конца, но основные вещи уже есть.
Эта статья находится в разработке!


Visibility graph

Путь с препятствиями через трапецоидную карту
Такой путь не самый короткий

В общем, когда мы ищем путь от точки [math] S [/math] до [math] T [/math] с препятствиями (надо уточнить, что двигаем мы точку, а не какой-то полигон), можно построить трапецоидную карту, соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе Дейкстрой найти путь от [math] S [/math] до [math] T [/math]. Но этот путь не будет кратчайшим(кэп).

Лемма:
Любой кратчайший путь от [math] S [/math] до [math] T [/math] с полигональными препятствиями представляет собой ломаную, вершины которой — вершины полигонов.
Доказательство:
[math]\triangleright[/math]
Ну в общем тут все очевидно
Пусть путь проходит(в смысле вершины) через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко, да срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказана и все офигенно.
[math]\triangleleft[/math]

По этой лемме запилим visibility graph. Его вершины — вершины полигонов. Между вершинами [math] u [/math] и [math] v [/math] существует ребро, если из [math] u [/math] видна (mutually visible) [math] v [/math] (ребра полигонов тоже входят в этот граф). Теперь, если мы добавим к множеству вершин [math] S [/math] и [math] T [/math] (и ребра в видимые вершины), у нас получится граф, в котором опять же Дейкстрой находим кратчайший путь. По лемме любое ребро кратчайшего пути — ребро visibility графа, так что мы нашли то, что нужно.

Построение visibility графа

Если делать в тупую наивно, т. е. для каждой пары вершин проверять можно ли добавить ли такое ребро(нет ли пересечений с полигонами), будет [math] O(n^3) [/math] (зато просто пилится).

Motion planning

В общем тут все очевидно. Тут мы просто двигаем не точку, а произвольный выпуклый полигон. Если мы его не можем вращать, просто "обводим" препятствия нашим полигоном (запиливаем сумму Минковского препятствий и полигона) и получаем другие препятствия, но зато теперь мы двигаем точку. А это мы уже научились делать выше.

Если же этот полигон можно вращать, то делаем примерно то же самое, только как-то по-хитрому. Нам про это, кажется, не рассказывали(или рассказывали так же:))

Источники

  • Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 15 page 324-331