- Rotating calipers
Rotating calipers is a computational
algorithm developed byMichael Shamos in 1978 for determining all antipodal pairs of points and vertices on aconvex polygon orconvex hull . The term "rotating calipers" was later coined in 1983 by the computer scientistGodfried Toussaint cite_paper
author = Toussaint, G. T
title = Solving geometric problems with the rotating calipers
publisher=Proc. MELECON '83, Athens
url=http://citeseer.ist.psu.edu/toussaint83solving.html
date = 1983 ] .The name comes from the analogy of rotating a spring-loadedcaliper 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 algorithm runs in
O(n) time.Applicable problems [ [http://cgm.cs.mcgill.ca/~orm/rotcal.html Rotating Calipers ] ]
* Diameter (maximum width) of a convex polygon
* Width (minimum width) of a convex polygon
* Maximum distance between two convex polygons
*Minimum distance between two convex polygons
* Minimum areaoriented bounding box
* Minimum perimeteroriented bounding box
* Onion triangulations
* Spiral triangulations
*Quadrangulations
* Merging two convex polygons
* Common tangents to two convex polygons
* Intersection points of two convex polygons
*Critical support lines of two convex polygons
* Vector sums of two convex polygons
*Thinnest-strip transversals across multiple convex polygonsMinimum width of a convex polygon
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;
References
See also
*
Convex polygon
*Convex hull
*Smallest enclosing box
Wikimedia Foundation. 2010.