Изменения

Рассмотрим задачу нахождения кратчайшего пути от точки <tex> S </tex> до <tex> T </tex> с препятствиями. Для начала рассмотрим движение материальной точки, случай произвольного полигона будет [[Visibility graph и motion planning#Motion planning|позднее]]. Для нахождения можно построить [[Трапецоидная карта | трапецоидную карту]], соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе любым алгоритмом поиска кратчайших путей (например, алгоритмом [[Алгоритм Дейкстры|Дейкстры]] или [[Алгоритм A*|A*]]) найти путь от <tex> S </tex> до <tex> T </tex>. Но этот путь, очевидно, не будет кратчайшим.

Для нахождения пути можно построить [[Трапецоидная карта | трапецоидную карту]], соединить ребрами середины вертикальных сторон трапецоидов с их центрами и в этом графе любым алгоритмом поиска кратчайших путей (например, алгоритмом [[Алгоритм Дейкстры|Дейкстры]] или [[Алгоритм A*|A*]]) найти путь от <tex> S </tex> до <tex> T </tex>. Однако , этот путь не будет абсолютно кратчайшим.  Этот алгоритм поиска пути через трапецоидную карту обширно используется, так как трапецоидная карта дает хорошее приближение, строится работает за <tex> O(n \log n) </tex> и занимает <tex> O(n) </tex> линейное количество памяти, в то время как точные решения в лучшем случае работают за <tex> O(n^2) </tex> времени и требуют <tex> O(n^2) </tex> памяти (здесь и далее <tex> n </tex> {{---}} количество всех вершин). Теперь рассмотрим точное решение с помощью построения графа видимости. Для этого нам потребуется лемма:

Пусть кратчайший путь {{---}} не ломаная. Тогда рассмотрим участок В таком случае, на путисуществует такая точка <tex> p </tex>, которая не принадлежит ни одному прямому отрезку. Это означает, где он что существует <tex>\epsilon</tex>-окрестность точки <tex> p </tex>, в которую не является прямымпопадает ни одно препятствие. По В таком случае, подпуть, который находится внутри <tex>\epsilon</tex>-окрестности, по неравенству треугольника в может быть сокращён по хорде, соединяющий точки пересечения границы <tex>\epsilon</tex>-окрестности этого участка мы сможем немного срезатьс путем. Значит этот Раз часть пути может быть уменьшена, значит и весь путь не кратчайшийможет быть уменьшен, а значит исходное предположение некорректно.}}{{Определение|definition ='''visibility graph''' {{---}} граф, вершины которого {{---}} вершины полигонов, а также <tex> S </tex> и <tex> T </tex>. ПротиворечиеМежду вершинами <tex> u </tex> и <tex> v </tex> существует ребро, значит лемма доказанаесли из <tex> u </tex> <i> видна </i>(mutually visible) <tex> v </tex>.

Если существуют вершины <tex> A, B, C </tex> одного препятствия и вершина <tex> D </tex> такая, что поворот <tex> DBA </tex> не совпадает с поворотом <tex> DBC </tex>, то ребро <tex> DB </tex> не принадлежит кратчайшему пути и его можно удалитьиз графа. (См. поясняющую картинку справа)