222
правки
Изменения
м
Нет описания правки
== Visibility graph ==
[[Файл:trap.png|200px|thumb|right|Путь с препятствиями через трапецоидную карту]]
В общем, когда мы ищем путь от точки <tex> S </tex> до <tex> T </tex> с препятствиями, можно построить [[Трапецоидная карта | трапецоидную карту]], соединить ребрами середины вертикальных сторон с центрами трапецоидов и в этом графе [[Алгоритм Дейкстры | Дейкстрой]] найти путь от <tex> S </tex> до <tex> T </tex>. Но этот путь не будет кратчайшим(кэп).
