Изменения

Рассмотрим задачу нахождения кратчайшего пути от точки <tex> S </tex> до <tex> T </tex> с препятствиями. Для начала рассмотрим движение материальной точки, случай произвольного полигона , когда размером и формой движимого объекта пренебречь нельзя, будет [[Visibility graph и motion planning#Motion planning|позднее]].

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

Этот Данный алгоритм поиска пути через трапецоидную карту обширно используется, так как дает хорошее приближение, работает за <tex> O(n \log n) </tex> и занимает за линейное количество памятии идеально подходит для нахождения какого-нибудь пути между конечными вершинами. Но иногда нужно найти кратчайший путь, в то время как точные решения в лучшем случае работают за <tex> O(n^2) </tex> времени и памяти (здесь этот алгоритм не подходит, хоть и далее <tex> n </tex> {{---}} количество всех вершин)дает хорошее приближение.

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

Любой кратчайший путь от <tex> S </tex> до <tex> T </tex> между двумя вершинами с полигональными препятствиями представляет собой ломаную, вершины которой {{---}} вершины полигонов.

'''visibility graph''' {{---}} граф, вершины которого {{---}} вершины полигонов, а также <tex> S </tex> и <tex> T </tex>. Между вершинами <tex> u </tex> и <tex> v </tex> существует ребро, если из <tex> u </tex> <i> видна </i>(mutually visible) <tex> v </tex>.