Поиск глобального кратчайшего пути в невырожденных трапециях

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

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

Запуск алгоритма кратчайшего пути на самой трапеции с последующим использованием алгоритма воронки не гарантирует нахождения кратчайшего в глобальном масштабе пути.

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

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

.