Search code examples
algorithmgeometrygraph-algorithm

Finding shortest distance between two points with segments blocking

I need to find the shortest Euclidean distance between endpoints A, B in the plane, subject to the constraint that there is a set of N segments S=[S1,S2,...] that my Euclidean path cannot intersect.

I can imagine a recursive approach that first "guesses" the straight line between A,B, and checks for any intersection with a segment s, changes the path to go around s, and then recursively calls the same algorithm on new endpoints. This would have runtime O(2^N) it seems like, since there are 2 ways to go around each segment.

This is a subproblem for a version of the Traveling Salesman Problem I am working on.

EDIT: If two segments share an endpoint, this point is passable.

Solution

  • Construct a graph G whose vertices are A, B and the 2N endpoints of the segments. Connect two points with an edge if and only if the straight line between them does not intersect any other edges.

    Now use an A* search to find the shortest path.