Distance To Move Two Polygons So They Touch Edges

4
votes

Best described in the image below.

Polygon

I need to know the minimum distance to move a reference polygon (shown in red) in one axis (just y) such that will just touch the other polygon. If it's inside the polygon, it will need to move outwards.

I tried to look at all the lines in one polygon and all the points in another, project the point onto the line, and get the difference between the point y and the projection point y, then find the minimum distance. However, this had the issue that if the polygons overlapped and farthest line in one polygon and farthest point in the other had the minimum distance, it would give a result that would make the polygons overlap.

Edit: by projecting the point on the line, I mean find the y value for a point on the line that has the same x value as the original point. Skip this step if the x value lies outside of the line.

2
geometrycomputational-geometrypolygons
I suggest adding tags geometry and computational-geometry to attract more readers (can't do it myself, edits need to be more than 10 chars, grrr!) – kebs
So ? You got two answers, and not a single comment or upvote from you ? Are you really interested ? Did you find another solution ? If so, please contribute, you can also give an answer to your own question. – kebs

2 Answers

2
votes

I'm not sure I have correctly understood your proposal (what's "projecting the point onto the line"?).

Anyway, I would try this (pseudo code), :

for pA: points of polygon A:
   for sB: segments of polygon B
      compute distance along y-axis d(pA,sB) and store in table
Find minimum distance in table: d1
Proceed as above by reversing A and B: d2
final d = min(d1,d2)

But unfortunatly, this probably isn't good if your polygons are concave, which seems to be the case.

2
votes

You need to draw a vertical line through every vertex of both polygons and determine its intersection with the polygons (a line/polygon intersection is made of disjoint intervals).

On a given vertical, compute the difference between the highest endpoint of a polygon and the lowest of the other. The answer is the smallest difference among all verticals (which can be a negative number).

To perform the computation efficiently, you can use the scanline principle: sort all vertices from left to right and maintain an "active list", which is the list of edges that intersect the current vertical. As you move from one vertex to the next, you will update this list.

For two polygons of size N and M, sorting will cost O(N+M)Log(N+M)); then the scan will cost approximately O((N+M)K), where K is the average number of intersections of a vertical with a polygon, usually a small number between 2 and 4.