Нахождение кратчайшего в мире пути в невырожденных трапецеидациях

Question

Я ищу эффективный алгоритм, который находит кратчайший путь между двумя точками в двухмерном пространстве с полигональными препятствиями.

Исходные данные представлены в виде невырожденной вертикальной трапеции, состоящей из до 10 ^ 4 трапеций (невырожденная означает, что нижняя и верхняя сторона каждой трапеции имеют не более 2 соседних трапеций каждая).

Выполнение алгоритма кратчайшего пути на самой трапеции, а затем использование алгоритма воронки не гарантирует нахождение кратчайшего в мире пути.

Вычисление графика видимости угловых вершин может потенциально работать, хотя я подозреваю, что это может использовать слишком много памяти, потому что требование к алгоритму состоит в том, что его можно часто использовать (примерно 100 раз в секунду) на сервере с несколькими ( до 700) карт в памяти, но вы можете поправить меня, если считаете, что это не проблема!

Чтобы визуализировать, как выглядят данные, я загрузил триангуляцию маленькой карты, вы можете щелкнуть изображение, чтобы просмотреть его в формате SVG.

.

Answer 1

Если вы создаете граф с

1) вершинами во всех вершинах трапеций в дополнение к точкам отправления и назначения.

2) ребра между любыми 2 из этих вершинесли они находятся на линии прямой видимости относительно друг друга и вес ребра равен расстоянию между двумя вершинами.

Тогда эта проблема выглядит как кратчайшее расстояние между двумя точками в задаче о графе, которая имеет много известных решений ( Алгоритм Дейкстры и т. Д.)