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."Rotating Calipers" at Toussaint's home page 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 - or -coordinates of points.
History
The rotating calipers method was first used in the dissertation of Michael Shamos in 1978. Shamos used this method to generate all antipodal pairs of points on a convex polygon and to compute the diameter of a convex polygon in time. Godfried Toussaint coined the phrase "rotating calipers" and demonstrated that the method was applicable in solving many other computational geometry problems.
Shamos's algorithm Shamos gave the following algorithm in his dissertation (pp. 77–82) for the rotating calipers method, which generated all antipodal pairs of vertices on a convex polygon:
/* p[] is in standard form, ie, counter clockwise order, distinct vertices, no collinear vertices. ANGLE(m, n) is a procedure that returns the clockwise angle swept out by a ray as it rotates from a position parallel to the directed segment Pm,Pm+1 to a position parallel to Pn, Pn+1 We assume all indices are reduced to mod N (so that N+1 = 1). */ GetAllAntiPodalPairs(p[1..n]) // Find first anti-podal pair by locating vertex opposite P1 i = 1 j = 2 while angle(i, j) < pi j++ yield i, j
/* Now proceed around the polygon taking account of possibly parallel edges. Line L passes through Pi, Pi+1 and M passes through Pj, Pj+1 */
// Loop on j until all of P has been scanned current = i while j != n if angle(current, i + 1) <= angle(current, j + 1) j++ current = j else i++ current = i yield i, j
// Now take care of parallel edges if angle(current, i + 1) = angle(current, j + 1) yield i + 1, j yield i, j + 1 yield i + 1, j + 1 if current = i j++ else i++
Another version of this algorithm appeared in the text by Preparata and Shamos in 1985 that avoided calculation of angles:
GetAllAntiPodalPairs(p[1..n]) i = n j = i + 1 while (Area(i, i + 1, j + 1) > Area(i, i + 1, j)) j = j + 1 j0 = j while (i != j0) i = i + 1 yield i, j while (Area(i, i + 1, j + 1) > Area(i, i + 1, j)) j = j + 1 if ((i, j) != (j0, 1)) yield i, j if (Area(i, i + 1, j + 1) = Area(i, i + 1, j)) if ((i, j) != (j0, n)) yield i, j + 1
Applications
Pirzadeh describes various applications of rotating calipers method.
Distances Diameter (maximum width) of a convex polygonBinay K. Bhattacharya and Godfried T. Toussaint, "Fast algorithms for computing the diameter of a finite planar set," The Visual Computer, Vol. 3, No. 6, May 1988, pp.379–388.Binay K. Bhattacharya and Godfried T. Toussaint, "A counter example to a diameter algorithm for convex polygons," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-4, No. 3, May 1982, pp. 306–309. Width (minimum width) of a convex polygonMichael E. Houle and Godfried T. Toussaint, "Computing the width of a set," IEEE Transactions on Pattern Analysis & Machine Intelligence, Vol. 10, no. 5, September 1988, pp. 761–765. Maximum distance between two convex polygonsGodfried T. Toussaint and Jim A. McAlear, "A simple O(n log n) algorithm for finding the maximum distance between two finite planar sets," Pattern Recognition Letters, Vol. 1, 1982, pp. 21–24.Binay K. Bhattacharya and Godfried T. Toussaint, "Efficient algorithms for computing the maximum distance between two finite planar sets," Journal of Algorithms, vol. 14, 1983, pp. 121–136. Minimum distance between two convex polygonsGodfried T. Toussaint and Binay K. Bhattacharya, "Optimal algorithms for computing the minimum distance between two finite planar sets," Pattern Recognition Letters, vol. 2, December, 1983, pp. 79–82. Widest 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 polygons Optimal strip separation (used in medical imaging and solid modeling)
Bounding boxes Minimum area oriented bounding box Minimum perimeter oriented bounding box
Triangulations Onion triangulations Spiral triangulations Quadrangulation Nice triangulation Art gallery problem Wedge placement optimization problem
Multi-polygon operations Union of two convex polygons Common tangents to two convex polygons Intersection of two convex polygonsGodfried T. Toussaint, "A simple linear algorithm for intersecting convex polygons, The Visual Computer, Vol. 1, 1985, pp. 118–123. Critical support lines of two convex polygons Vector sums (or Minkowski sum) of two convex polygonsTomas Lozano-Perez, "Spatial planning: A configuration space approach," IEEE Transactions on Computers, Vol. 32, No. 2, 1983, pp. 108–120. Convex hull of two convex polygons
Traversals Shortest transversalsBinay K. Bhattacharya and Godfried T. Toussaint, "Computing shortest transversals," Computing, vol. 46, 1991, pp. 93–119.Binay K. Bhattacharya, Jurek Czyzowicz, Peter Egyed, Ivan Stojmenovic, Godfried T. Toussaint, and Jorje Urrutia, "Computing shortest transversals of sets," International Journal of Computational Geometry and Applications, Vol. 2, No. 4, December 1992, pp. 417–436. Thinnest-strip transversalsJean-Marc Robert and Godfried T. Toussaint, "Linear approximation of simple objects," Computational Geometry: Theory and Applications, Vol. 4, 1994, pp. 27–52.
Others Non parametric decision rules for machine learned classification Aperture angle optimizations for visibility problems in computer vision Finding longest cells in millions of biological cells Comparing precision of two people at firing range Classify sections of brain from scan images
See also Convex polygon Convex hull Smallest enclosing box
References