Rotating calipers: Difference between revisions

In computational geometry, rotating calipers is the method that has been found useful in solving number of problems.

The method is so named because the idea is analogous to rotating a spring-loaded vernier caliper around the outside of a convex polygon.^[1]. 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.

Rotating calipers method was first used in the dissertation of the Michael Shamos in 1978^[2]. The algorithm in that dissertation uses this method for generating all antipodal pairs of points on a convex polygon for computing the diameter of a convex polygon in ${\displaystyle O(n)}$ time. Godfried Toussaint coined the phrase "rotating calipers" and also demonstrated that the method was applicable in solving many computational geometry problems involving wide range of areas.^[3]

Toussaint^[4] and Pirzadeh^[5] describes various applications of rotating calipers method.

• Diameter (maximum width) of a convex polygon^[6][7]
• Width (minimum width) of a convex polygon^[8]
• Maximum distance between two convex polygons^[9][10]
• Minimum distance between two convex polygons^[11]
• 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^[12]
• Optimal strip separation (used in medical imaging and solid modeling)^[13]

• Minimum area oriented bounding box
• Minimum perimeter oriented bounding box

• Onion triangulations
• Spiral triangulations
• Quadrangulation
• Nice triangulation
• Art gallery problem
• Wedge placement optimization problem^[14]

• Union of two convex polygons
• Common tangents to two convex polygons
• Intersection of two convex polygons^[15]
• Critical support lines of two convex polygons
• Vector sums (or Minkowski sum) of two convex polygons^[16]
• Convex hull of two convex polygons

• Shortest transversals^[17][18]
• Thinnest-strip transversals^[19]

• Non parametric decision rules for machine learned classification^[20]
• Aperture angle optimizations for visibility problems in computer vision^[21]
• Finding longest cells in millions of biological cells^[22]
• Comparing precision of two people at firing range
• Classify 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;

• Convex polygon
• Convex hull
• Smallest enclosing box
• es:Rotating calipers