Rotating calipers

In computational geometry, rotating calipers is a method used to construct efficient algorithms for a number of problems.

The method was first used by Michael Shamos in 1978 for determining all antipodal pairs of points and vertices on a convex polygon. The term "rotating calipers" was later coined in 1983 by the computer scientist Godfried Toussaint,[1] who applied this approach to a number of other geometric problems.[2] The name comes from the analogy of 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 and may be carried out in O(n) time.[3]

Rotating calipers, finding a bridge between two convex polygons

Applicable problems

Minimum 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

  1. ↑ "Rotating Calipers" at Toussaint's home page
  2. ↑ Toussaint, Godfried T. (1983). "Solving geometric problems with the rotating calipers". Proc. MELECON '83, Athens.
  3. ↑ M.I. Shamos. Computational geometry. PhD thesis, Yale University, 1978.
  4. ↑ Binay 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.
  5. ↑ Binay K. Bhattacharya and Godfried T. Toussaint, "A counter example to a diameter algorithm for convex polygons," IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. PAMI-4, No. 3, May 1982, pp. 306–309.
  6. ↑ Michael E. Houle and Godfried T. Toussaint, “Computing the width of a set,” IEEE Transactions Pattern Analysis & Machine Intelligence, Vol. 10, no. 5, September 1988, pp. 761–765.
  7. ↑ Godfried 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.
  8. ↑ 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.
  9. ↑ Godfried 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.
  10. ↑ Godfried T. Toussaint, "A simple linear algorithm for intersecting convex polygons, The Visual Computer, Vol. 1, 1985, pp. 118–123.
  11. ↑ Tomas Lozano-Perez, "Spatial planning: A configuration space approach," IEEE Transactions on Computers, Vol. 32, No. 2, 1983, pp. 108–120.
  12. ↑ Binay K. Bhattacharya and Godfried T. Toussaint, "Computing shortest transversals," Computing, vol. 46, 1991, pp. 93–119.
  13. ↑ 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.
  14. ↑ Jean-Marc Robert and Godfried T. Toussaint, "Linear approximation of simple objects," Computational Geometry: Theory and Applications, Vol. 4, 1994, pp. 27–52.

See also