Search for the shortest way around the world in non-degenerate trapezoid

Question

I am looking for an efficient algorithm that finds the globally shortest path between two points in a two-dimensional space with polygonal obstacles.

The initial data are presented in the form of a non-degenerate vertical trapezoid, consisting of up to 10 ^ 4 trapezoids (non-degenerate meaning: the lower and upper sides of each trapezoid have no more than two adjacent trapezoids).

Running the shortest path algorithm along the trapezoid itself, and then using the funnel algorithm does not guarantee the search for the shortest path around the world.

Computing the graph of visibility of corner vertices can potentially work, although I suspect that it may use too much memory, because the requirement for the algorithm is that it can be used often (about 100 times per second) on a server with several (up to 700) cards in my memory, but feel free to correct me if you think this is not a problem!

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

.

Answer 1

If you create a graph with

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

2) the edges between any 2 of these vertices, if they are a straight line of sight relative to each other and with an edge weight equal to the distance between two vertices.

Then this problem looks exactly like the shortest distance between two points in a graph problem that has many well-known solutions ( Dijkstra Algorithm , etc.)