Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have two polygons $P_1 \subseteq P_2$ in the plane, and I would like to determine to which polygon a given point $p\in P_1 \setminus P_2$ is "closest", by means of the following measure: $$r(p)=d(p,P_1)/d_p(P_1,P_2),$$ where $d(p,P_1)$ is the distance between $p$ and $P_1$ and $d_p(P_1,P_2)$ is the distance between $P_1$ and $P_2$. The $p$ subscript in that case indicates that this distance between both polygons will vary according to where $p$ is located, and the idea is that the smaller (resp. larger) $r(p)$ is, the closer it is to $P_1$ (resp. $P_2$).

I know about the formulas for computing the distance between a point and a line segment, but this does not seem to be enough here. I might be thinking a bit too much in algorithmic terms, but my idea was to construct a circle with center $p$ and let it grow until it "hits" either polygon (or both); the distance between $p$ and $P_1$ (or $P_2$) is then given by the radius of the smallest circle centered at $p$.

This answers the question of how to compute $d(p,P_1)$. However, I'm having trouble seeing how I should compute $d_p(P_1,P_2)$. Any ideas? Is this well-known? If that helps, one can assume that $P_1$ and $P_2$ are rectangles whose sides are pairwise parallel.

share|improve this question
add comment

2 Answers 2

If your two polygons $P_1$ and $P_2$ are (a) disjoint, and (b) convex, then there is a simple linear-time algorithm, known as the rotating calipers algorithm. Here is a description. If your polygons are not convex, then it is more complicated: they could spiral around one another and be quite entangled. There is an efficient algorithm for finding the closest pair of vertices that see one another: "Finding the minimum visible vertex distance between two non-intersecting simple polygons," Proceedings of the 2nd Symposium on Computational Geometry, 1986.

A key search term here is collision detection, as many applications require the minimum distance between two polygons to detect and avoid collisions.

share|improve this answer
    
Thanks, I had a look at the links. I'm not sure how well this corresponds to my purpose however, since I need my measure to depend on where $p$ is located (if you have two // rectangles, one inside the other, then their difference can be partitioned into 8 rectangles, and the $r(p)$ should depend on which sub-rectangle $p$ belongs to). –  Anthony Labarre Jan 28 '11 at 8:29
1  
I was only responding to the issue of how to compute the distance between two polygons, independent of your $p$. –  Joseph O'Rourke Jan 28 '11 at 10:53
add comment

Assuming the obvious definition of the distance between two polygons, there are three (not mutually exclusive) possible cases:

  1. The shortest distance between P1 and P2 is equal to the distance between a vertex v1 of P1 and a vertex v2 of P2.
  2. The shortest distance between P1 and P2 is equal to the distance between a vertex v of one of them and an edge e of the other.
  3. The shortest distance between P1 and P2 is equal to the distance between an edge e1 of P1 and an edge e2 of P2.

The brute force approach is to enumerate all of the distances between candidate pairs (v1, v2), (v, e), and (e1, e2), and then pick the smallest. If the polygons have many vertices then you will obviously want to look for more efficient approaches based around eliminating most of the vertices and edges as candidates.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.