CODEWITHSUNDEEP
computational-geometry
Paul94
Paul94

Reputation: 21

Shortest distance between two polygonal lines

I'm trying to calculate the shortest distance between two polygonal lines. I had thought of using a sweep algorithm but I don't know what events to take into account because the vertical ray can intersect between two vertices, a vertex and an edge or two edges. What will my events be? Is there any other way to calculate the distance?

Upvotes: 1

Views: 277

Answers (1)

Joseph O'Rourke
Joseph O'Rourke

Reputation: 4406

The minimum distance will always be achieved by a segment one end of which is a vertex of one of the polygonal chains P1 or P2. Even if the min distance is achieved by two parallel edges, an endpoint of those edges also realizes the min distance. So a naive algorithm is to iterate over all vertices v1 of P1, find the minimum distance from v1 to P2.

The problem of finding the minimum distance between v and P can iterate over each edge of P.

What I am describing is a quadratic algorithm. If you want to achieve the optimal O(n log n), you will need to compute a Voronoi diagram.

Upvotes: 1

Related Questions