Finding the globally shortest path in non-degenerate trapezoidations

Question

I'm searching for an efficient algorithm that finds the globally shortest path between two points in a 2-dimensional space with polygonal obstacles.

The source data is in the form of a non-degenerate vertical trapezoidation consisting of up to 10^4 trapezoids (non-degenerate meaning the lower and upper side of each trapezoid have at most 2 neighboring trapezoids each).

Running a shortest-path algorithm on the trapezoidation itself and then using a funnel algorithm does not guarantee finding the globally shortest path.

Computing the visibility graph of the corner vertices could potentially work, though I suspect this might use too much memory because the requirement for the algorithm is that it can be used frequently (about 100 times a second) on a server with multiple (up to 700) maps in memory, but feel free to correct me if you think that is not an issue!

To visualize what the data looks like, I uploaded the triangulation of a small map, you can click the image to view it as a SVG.

.

Answer 1

If you create a graph with

1) vertices at all of the vertices of the trapezoids in addition to the source and destination points.

2) edges between any 2 of these vertices if they are line of sight with respect to each other and with edge weight equal to the distance between the 2 vertices.

Then this problem seems exactly like the shortest distance between 2 points in a graph problem, which has many well known solutions (Dijkstra's Algorithm etc.)