In computational geometry

Computational geometry

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...

, 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

Antipodal point

In mathematics, the antipodal point of a point on the surface of a sphere is the point which is diametrically opposite to it — so situated that a line drawn from the one to the other passes through the centre of the sphere and forms a true diameter....

 pairs of points and vertices on a convex polygon

Convex polygon

In geometry, a polygon can be either convex or concave .- Convex polygons :A convex polygon is a simple polygon whose interior is a convex set...

.
The term "rotating calipers" was later coined in 1983 by the computer scientist Godfried Toussaint

Godfried Toussaint

Godfried T. Toussaint is a Research Professor of Computer Science at New York University Abu Dhabi in Abu Dhabi, United Arab Emirates. He is an expert on various aspects of computational geometry, discrete geometry, and their applications: pattern recognition , motion planning, visualization ,...

, who applied this approach to a number of other geometric problems. 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

Antipodal point

In mathematics, the antipodal point of a point on the surface of a sphere is the point which is diametrically opposite to it — so situated that a line drawn from the one to the other passes through the centre of the sphere and forms a true diameter....

 with the point or edge touching the opposite blade. It turns out that the complete "rotation" of the caliper around the polygon detects all antipodal pairs and may be carried out in O(n) time.

Applicable problems

• Diameter (maximum width) of a convex polygon
• Width (minimum width) of a convex polygon
• Maximum distance between two convex polygons
• Minimum distance
  Minimum distance
  The term minimum distance is used in several ways:* In geometry, the minimum distance of a collection of points P in a space is the smallest distance between any two points of the space....
  
   between two convex polygons
• Minimum area oriented bounding box
• Minimum perimeter oriented bounding box
• Onion triangulations
  Polygon triangulation
  In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....
  
  
• Spiral triangulations
  Polygon triangulation
  In computational geometry, polygon triangulation is the decomposition of a polygonal area P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P....
  
  
• Quadrangulations
• Union of two convex polygons
• Common tangents to two convex polygons
• Intersection of two convex polygons
• Critical support lines of two convex polygons
• Vector sums of two convex polygons
• Shortest transversals
• Thinnest-strip transversals

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;