Given two convex polygons P and Q, the goal is to find the pair(s) of points (p,q) (p belonging to P and q to Q) maximizing the distance between them.
Intuitively, these points will not belong to the interior of their respective polygons. The situation is in fact similar to the diameter problem:
The maximum distance between two convex polygons P and Q is determined by anti-podal pair between the polygons.
Although the terminology is the same, this definition is different from that of anti-podal pair for a given convex polygon.
The essential difference with an anti-podal pair between convex polygons is that the lines of support are directed and h***e opposite direction. An example is illustrated below:
Not only does the above result imply that only pairs of vertices should be checked, only specific pairs need to be considered. The fact that they admit parallel lines of support calls for an algorithm based on the Rotating Calipers paradigm.
Consider the following algorithm, where the input is assumed to be two convex polygons P and Q with m and n vertices respectively given in clockwise order.
- Compute the vertex with minimum y coordinate for P (call it yminP) and the vertex with maximum y coordinate for Q (call it ymaxQ).
- Construct two lines of support LP and LQ for the polygons at yminP and ymaxQ such that the polygons lie to the right of their respective lines of support. Then LP and LQ h***e opposite direction, and yminP and ymaxQ form an anti-podal pair between the polygons.
- Compute dist(yminP,ymaxQ) and keep it as the maximum.
- Rotate the lines clockwise until one of them coincides with an edge of its polygon.
- A new anti-podal pair is determined. The new distance is computed, compared to the current maximum, which is updated if necessary. If both lines of support coincide with edges, then a total of three anti-podal pairs (combinations of the previous vertices and the new vertices) need to be considered.
- Repeat steps 4 and 5, until the new pair considered is (yminP,ymaxQ).
- Output the maximum distance.
The Rotating Calipers paradigm ensures all possible anti-podal pairs are considered. Furthermore, the whole algorithm has linear time complexity, since (besides the initialization), there are only as many steps as there are vertices.
A similar algorithm can be used for the minimum distance between two convex polygons.
Trace: http://cgm.cs.mcgill.ca/~orm/rotcal.html
