Изменения

Пусть мы ищем какой-то путь от точки <tex> S </tex> до <tex> T </tex> с препятствиями (сначала будем двигать точку, а не полигон). Для нахождения можно построить [[Трапецоидная карта | трапецоидную карту]], соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе [[Алгоритм Дейкстры | Дейкстрой]] найти путь от <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> ребер.

Если у ребра на предыдущю предыдущую точку от данной левый поворот, а на следующую, от данной, правый - то ребро, идущее к текущей точке может быть удалено.