Изменения

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

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

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

Очевидно, что путь Путь проходящий через ребро <tex> BD </tex> будет длинее, чем через соседей точки <tex> B </tex>. Так , так как по неравенству треугольника <tex> AB + BD < AD </tex>