Visibility graph и motion planning — различия между версиями
Igorjan94 (обсуждение | вклад) м |
Igorjan94 (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | {{ptready}} | ||
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div> | <div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div> | ||
<includeonly>[[Категория: В разработке]]</includeonly> | <includeonly>[[Категория: В разработке]]</includeonly> | ||
| Строка 13: | Строка 14: | ||
|proof= | |proof= | ||
[[Файл:short.png|150px|thumb|right|Ну в общем тут все очевидно]] | [[Файл:short.png|150px|thumb|right|Ну в общем тут все очевидно]] | ||
| − | Пусть путь проходит(в смысле вершины) через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко, да срезать. Значит этот путь не кратчайший. Противоречие, значит лемма | + | Пусть путь проходит(в смысле вершины) через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко, да срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказана и все офигенно. |
}} | }} | ||
| + | |||
| + | По этой лемме запилим visibility graph. Его вершины {{---}} вершины полигонов. Между вершинами <tex> u </tex> и <tex> v </tex> существует ребро, если из <tex> u </tex> <i> видна </i>(mutually visible) <tex> v </tex> (ребра полигонов тоже входят в этот граф). Теперь, если мы добавим к множеству вершин <tex> S </tex> и <tex> T </tex> (и ребра в видимые вершины), у нас получится граф, в котором опять же Дейкстрой находим кратчайший путь. По лемме любое ребро кратчайшего пути {{---}} ребро visibility графа, так что мы нашли то, что нужно. | ||
| + | |||
| + | === Построение visibility графа === | ||
| + | Если делать <s> в тупую</s> наивно, т. е. для каждой пары вершин проверять можно ли добавить ли такое ребро(нет ли пересечений с полигонами), будет <tex> O(n^3) </tex> (зато просто пилится). | ||
== Motion planning == | == Motion planning == | ||
| − | + | В общем тут все очевидно. Тут мы просто двигаем не точку, а произвольный выпуклый полигон. Если мы его не можем вращать, просто "обводим" препятствия нашим полигоном (запиливаем [[Сумма Минковского (определение, вычисление)|сумму Минковского]] препятствий и полигона) и получаем другие препятствия, но зато теперь мы двигаем точку. А это мы уже научились делать выше. | |
| − | |||
== Источники == | == Источники == | ||
Версия 00:36, 7 января 2014
| Конспект написан не до конца, но основные вещи уже есть. |
Visibility graph
В общем, когда мы ищем путь от точки до с препятствиями (надо уточнить, что двигаем мы точку, а не какой-то полигон), можно построить трапецоидную карту, соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе Дейкстрой найти путь от до . Но этот путь не будет кратчайшим(кэп).
| Лемма: |
Любой кратчайший путь от до с полигональными препятствиями представляет собой ломаную, вершины которой — вершины полигонов. |
| Доказательство: |
| Пусть путь проходит(в смысле вершины) через какую-то другую точку. Рассмотрим окрестность этой точки. По неравенству треугольника мы сможем немножко, да срезать. Значит этот путь не кратчайший. Противоречие, значит лемма доказана и все офигенно. |
По этой лемме запилим visibility graph. Его вершины — вершины полигонов. Между вершинами и существует ребро, если из видна (mutually visible) (ребра полигонов тоже входят в этот граф). Теперь, если мы добавим к множеству вершин и (и ребра в видимые вершины), у нас получится граф, в котором опять же Дейкстрой находим кратчайший путь. По лемме любое ребро кратчайшего пути — ребро visibility графа, так что мы нашли то, что нужно.
Построение visibility графа
Если делать в тупую наивно, т. е. для каждой пары вершин проверять можно ли добавить ли такое ребро(нет ли пересечений с полигонами), будет (зато просто пилится).
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
