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.
Best Answer
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.