The diameter of a convex polygon
The diameter of a polygon is defined as the maximum distance between any two points of the polygon. It is possible for more than one pair of points to determine the diameter. In fact, if the polygon has
n vertices, as many as
n "diameter pairs" may exist.
A simple example of a polygon's diameter is illustrated to the left. The diameter pair, shown as black dots admits parallel lines of support (shown in red). The diameter is highlighted in light blue.
Obviously, the pair of points determining the diameter of a convex polygon
P does not belong to the interior of
P. The search should concentrate on the boundary. In fact, only pairs of points should be checked, for the diameter is the greatest distance between parallel lines of support. Shamos (1978) provides a simple algorithm computing the anti-podal pairs of a convex n-gon in
O(n) time. The diameter can then obtained by going through the list, and outputting the pair with maximum distance. The following is the pseudo-code for Shamos' algorithm, as presented in the text by Preparata and Shamos (1985).
The input is a polygon
P={
p1,...,
pn}.
begin p0:=pn; q:=NEXT[p]; while (Area(p,NEXT[p],NEXT[q]) > Area(p,NEXT[p],q)) do q:=NEXT[q]; q0:=q; while (q != p0) do begin p:=NEXT[p]; Print(p,q); while (Area(p,NEXT[p],NEXT[q]) > Area(p,NEXT[p],q) do begin q:=NEXT[q]; if ((p,q) != (q0,p0)) then Print(p,q) else return end; if (Area(p,NEXT[p],NEXT[q]) = Area(p,NEXT[p],q)) then if ((p,q) != (q0,p0)) then Print(p,NEXT[q]) else Print(NEXT[p],q) end end.
Note that Print(p,q) signifies the output of (p,q) as an anti-podal pair and Area(p,q,r) signifies the signed-area of triangle pqr.
Although this procedure is not as intuitive as the usual Rotating Calipers algorithm, it is essentially the same, and avoids any angle computations.
A more intuitive algorithm would be:
//注：旋转卡壳算法(Rotating Calipers algorithm)的直观描述
- Compute the polygon's extreme points in the y direction. Call them ymin and ymax.
- Construct two horizontal lines of support through ymin and ymax. Since this is already an anti-podal pair, compute the distance, and keep as maximum.
- Rotate the lines until one is flush with an edge of the polygon.
- A new anti-podal pair is determined. Compute the new distance, compare to old maximum, and update if necessary.
- Repeat steps 3 and 4 until the anti-podal pair considered is (ymin,ymax) again.
- Output the pair(s) determining the maximum as the diameter pair(s).
Still, the above procedure (given in pseudocode) happens to be very useful, as other information can be obtained from the anti-podal pairs, like the of a convex polygon.
