Visibility graph и motion planning — различия между версиями
Igorjan94 (обсуждение | вклад) м |
Igorjan94 (обсуждение | вклад) м |
||
| Строка 3: | Строка 3: | ||
== Visibility graph == | == Visibility graph == | ||
| − | [[Файл:trap.png|200px|thumb| | + | [[Файл:trap.png|200px|thumb|left|Путь с препятствиями через трапецоидную карту]] |
| + | [[Файл:notShort.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>. Но этот путь не будет кратчайшим(кэп). |
{{Лемма | {{Лемма | ||
| Строка 11: | Строка 12: | ||
Любой кратчайший путь от <tex> S </tex> до <tex> T </tex> с полигональными препятствиями представляет собой ломаную, вершины которой {{---}} вершины полигонов. | Любой кратчайший путь от <tex> S </tex> до <tex> T </tex> с полигональными препятствиями представляет собой ломаную, вершины которой {{---}} вершины полигонов. | ||
|proof= | |proof= | ||
| + | [[Файл:short.png|150px|thumb|right|Ну в общем тут все очевидно]] | ||
Пусть путь проходит(в смысле вершины) через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко, да срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказано и все офигенно. | Пусть путь проходит(в смысле вершины) через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко, да срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказано и все офигенно. | ||
}} | }} | ||
Версия 21:48, 6 января 2014
Эта статья находится в разработке!
Visibility graph
В общем, когда мы ищем путь от точки до с препятствиями (надо уточнить, что двигаем мы точку, а не какой-то полигон), можно построить трапецоидную карту, соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе Дейкстрой найти путь от до . Но этот путь не будет кратчайшим(кэп).
| Лемма: |
Любой кратчайший путь от до с полигональными препятствиями представляет собой ломаную, вершины которой — вершины полигонов. |
| Доказательство: |
| Пусть путь проходит(в смысле вершины) через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко, да срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказано и все офигенно. |
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
