Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Closest points of two polygons

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.

like image 624
Moe Avatar asked Nov 01 '22 14:11

Moe


1 Answers

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

like image 116
luiso1979 Avatar answered Nov 13 '22 05:11

luiso1979