Visibility graph и motion planning

Эта статья находится в разработке!

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]

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