5

I have two polygons and I want to get the minimal distance and the points between this distance is measured. Of course such a point could very well lie on the edge between two nodes.

Here is an example:

Example

I am looking for an algorithm that gives me the green distance and the two points.

Moe
  • 1,356
  • 10
  • 13
  • 1
    From the picture it seems that the plygons may be concave. Otherwise GJK algorithm is a great solution to the problem – Ivaylo Strandjev Sep 24 '13 at 06:23
  • see http://stackoverflow.com/questions/3700983/what-is-the-fastest-algorithm-to-calculate-the-minimum-distance-between-two-sets – Ari Sep 24 '13 at 20:29

1 Answers1

2

If the polygons do not intersect, you could do this:

If you have polygon A and polygon B and A[i] and B[j] are the vertexes of A and B respectively. Then you could compute the closest distance from A[i] to each segment of B (you could use something like this, but take into account that you'd be working with segments, so you have to work with the starting and ending point of the segment).

Then you have to do the same but from all B[j] to all segments of A.

And finally take the smallest one.

Just remember my previous comment: consider the starting and ending point of the segment while computing the shortest distance to the line this segment is in, because the intersection point could be out of the segment. Look here to check this last thing. If the point is out keep the closest edge of the segment)

Regards

luiso1979
  • 868
  • 1
  • 6
  • 18