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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Visibility graph)
м
Строка 3: Строка 3:
  
 
== Visibility graph ==
 
== Visibility graph ==
 +
[[Файл:trap.png|200px|thumb|right|Путь с препятствиями через трапецоидную карту]]
  
 
В общем, когда мы ищем путь от точки <tex> S </tex> до <tex> T </tex> с препятствиями, можно построить [[Трапецоидная карта | трапецоидную карту]], соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе [[Алгоритм Дейкстры | Дейкстрой]] найти путь от <tex> S </tex> до <tex> T </tex>. Но этот путь не будет кратчайшим(кэп).
 
В общем, когда мы ищем путь от точки <tex> S </tex> до <tex> T </tex> с препятствиями, можно построить [[Трапецоидная карта | трапецоидную карту]], соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе [[Алгоритм Дейкстры | Дейкстрой]] найти путь от <tex> S </tex> до <tex> T </tex>. Но этот путь не будет кратчайшим(кэп).

Версия 18:55, 6 января 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]

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