Distances between points and polygons

Question

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.

Answer 1

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.

Answer 2

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.