In computational geometry, the method of rotating calipers is an algorithm design technique that can be used to solve optimization problems including finding the width or diameter of a set of points.
The method is so named because the idea is analogous to rotating a spring-loaded vernier caliper around the outside of a convex polygon. Every time one blade of the caliper lies flat against an edge of the polygon, it forms an antipodal pair with the point or edge touching the opposite blade. The complete "rotation" of the caliper around the polygon detects all antipodal pairs; the set of all pairs, viewed as a graph, forms a thrackle. The method of rotating calipers can be interpreted as the projective dual of a sweep line algorithm in which the sweep is across slopes of lines rather than across x- or y-coordinates of points.
The rotating calipers method was first used in the dissertation of Michael Shamos in 1978. Shamos uses this method to generate all antipodal pairs of points on a convex polygon and to compute the diameter of a convex polygon in O ( n ) time. Godfried Toussaint coined the phrase "rotating calipers" and also demonstrated that the method was applicable in solving many other computational geometry problems.
Shamos gave following algorithm in his dissertation (pp 77–82) for the rotating calipers method that generated all antipodal pairs of vertices on convex polygon:
Another version of this algorithm appeared in the text by Preparata and Shamos in 1985 that avoided calculation of angles:
This method has several advantages including that it avoids calculation of area or angles as well as sorting by polar angles. The method is based on finding convex hull using Monotone chain method devised by A.M. Andrew which returns upper and lower portions of hull separately that then can be used naturally for rotating callipers analogy.
Toussaint and Pirzadeh describes various applications of rotating calipers method.
Diameter (maximum width) of a convex polygonWidth (minimum width) of a convex polygonMaximum distance between two convex polygonsMinimum distance between two convex polygonsWIdest empty (or separating) strip between two convex polygons (a simplified low-dimensional variant of a problem arising in support vector machine based machine learning)Grenander distance between two convex polygonsOptimal strip separation (used in medical imaging and solid modeling)Minimum area oriented bounding boxMinimum perimeter oriented bounding boxOnion triangulationsSpiral triangulationsQuadrangulationNice triangulationArt gallery problemWedge placement optimization problemUnion of two convex polygonsCommon tangents to two convex polygonsIntersection of two convex polygonsCritical support lines of two convex polygonsVector sums (or Minkowski sum) of two convex polygonsConvex hull of two convex polygonsShortest transversalsThinnest-strip transversalsNon parametric decision rules for machine learned classificationAperture angle optimizations for visibility problems in computer visionFinding longest cells in millions of biological cellsComparing precision of two people at firing rangeClassify sections of brain from scan images ARRAY points := {P1, P2, ..., PN}; points.delete(middle vertices of any collinear sequence of three points); REAL p_a := index of vertex with minimum y-coordinate; REAL p_b := index of vertex with maximum y-coordinate; REAL rotated_angle := 0; REAL min_width := INFINITY; VECTOR caliper_a(1,0); // Caliper A points along the positive x-axis VECTOR caliper_b(-1,0); // Caliper B points along the negative x-axis WHILE rotated_angle < PI // Determine the angle between each caliper and the next adjacent edge in the polygon VECTOR edge_a(points[p_a + 1].x - points[p_a].x, points[p_a + 1].y - points[p_a].y); VECTOR edge_b(points[p_b + 1].x - points[p_b].x, points[p_b + 1].y - points[p_b].y); REAL angle_a := angle(edge_a, caliper_a); REAL angle_b := angle(edge_b, caliper_b); REAL width := 0; // Rotate the calipers by the smaller of these angles caliper_a.rotate(min(angle_a, angle_b)); caliper_b.rotate(min(angle_a, angle_b)); IF angle_a < angle_b p_a++; // This index should wrap around to the beginning of the array once it hits the end width = caliper_a.distance(points[p_b]); ELSE p_b++; // This index should wrap around to the beginning of the array once it hits the end width = caliper_b.distance(points[p_a]); END IF rotated_angle = rotated_angle + min(angle_a, angle_b); IF (width < min_width) min_width = width; END IF END WHILE RETURN min_width;
