CODEWITHSUNDEEP
algorithmgeometrygraph-algorithm
wilbs
wilbs

Reputation: 23

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.

Upvotes: 0

Views: 490

Answers (1)

btilly
btilly

Reputation: 46389

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.

Upvotes: 1

Related Questions