Rotating Calipers, in depth: antipodal pairs, diameter, width and the minimum-area bounding rectangle in linear time

Antipodal pairs and the caliper sweep

A supporting line touches a convex polygon and has the whole polygon on one side. Two vertices are an antipodal pair if parallel supporting lines can pass through them. Two facts make the technique work. First, the farthest pair of points in any set is an antipodal pair of its convex hull, and so are the critical pairs for width and for several other measures. Second, a convex polygon with n vertices has at most ⌊3n/2⌋ antipodal pairs (Preparata and Shamos), and they can be listed by rotation. Rotate the jaws so that one rests flush on edge i. The opposite contact is the vertex farthest from that edge's line. As i advances counter-clockwise, the farthest vertex also advances counter-clockwise and never moves back. One pointer, j, therefore moves at most once around the polygon over the whole sweep, and the total work is O(n) after the hull is built.

Prerequisite: a clean hull

Every caliper routine assumes a clean hull: vertices in counter-clockwise order, no duplicates, and no three consecutive points collinear. Collinear points create zero-length advances that can stall the pointer or double-count pairs. Andrew's monotone chain with a strict turn test (pop on cross <= 0) produces exactly that, as described in the monotone chain article:

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def hull(points):
    # Andrew's monotone chain: CCW, no collinear points, no duplicates.
    pts = sorted(set(points))
    if len(pts) <= 2:
        return pts
    lower, upper = [], []
    for p in pts:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    for p in reversed(pts):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

With integer input, cross is exact, and it equals twice the area of the triangle (o, a, b). For a fixed edge (a, b), |cross(a, b, q)| is proportional to q's distance from the edge's line, so comparing distances needs no division and no square root.

Diameter

For each edge (h[i], h[i+1]), advance j while the next vertex is strictly farther from the edge, then compare the edge's two endpoints with h[j]. Squared distances keep everything in integers:

def d2(a, b):
    return (a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2

def diameter_sq(h):
    # Squared diameter of a strictly convex CCW polygon, O(n).
    n = len(h)
    if n == 1:
        return 0
    if n == 2:
        return d2(h[0], h[1])
    best, j = 0, 1
    for i in range(n):
        a, b = h[i], h[(i + 1) % n]
        while abs(cross(a, b, h[(j + 1) % n])) > abs(cross(a, b, h[j])):
            j = (j + 1) % n
        best = max(best, d2(a, h[j]), d2(b, h[j]))
    return best

The strict > matters. When two hull edges are parallel, two vertices tie for farthest. Stopping at the first of them is safe, because both edge endpoints are compared with h[j], and the next edge picks up the other vertex. With >= on a degenerate input, such as all points identical after a buggy hull, the loop can spin forever. The test suite compared this function with the O(n²) all-pairs maximum on 4,000 random inputs, including collinear sets and n ≤ 2, and every result matched exactly.

Width

The width is the minimum distance between two parallel supporting lines, taken over all directions. For a convex polygon the minimum is always reached with one line flush on an edge, so it is the minimum over edges of the farthest vertex's distance from that edge. The same pointer gives it:

import math

def width(h):
    n = len(h)
    if n <= 2:
        return 0.0
    best, j = math.inf, 1
    for i in range(n):
        a, b = h[i], h[(i + 1) % n]
        while abs(cross(a, b, h[(j + 1) % n])) > abs(cross(a, b, h[j])):
            j = (j + 1) % n
        best = min(best, abs(cross(a, b, h[j])) / math.dist(a, b))
    return best

Only the final division is floating point. To compare widths exactly, compare cross² / |edge|² as integer fractions. Width answers questions like "will this part fit through the slot" and "how thick is this point cloud", and it is the standard flatness test for scanned surfaces.

Minimum-area bounding rectangle

Freeman and Shapira (1975) proved that the minimum-area enclosing rectangle of a convex polygon has one side collinear with a polygon edge. The same holds for minimum perimeter. So only n candidate orientations exist, and for each one we need four extremes: the edge itself (bottom), the farthest vertex (top), and the vertices with the largest and smallest projection onto the edge direction (right and left). All three moving contacts are monotone, so this uses three calipers instead of two:

def min_area_rect(h):
    # (area, edge index) of the minimum-area enclosing rectangle, O(n).
    n = len(h)
    if n <= 2:
        return 0.0, 0
    def dot(a, b, q):                      # projection of q - a onto a->b, scaled by |ab|
        return (b[0] - a[0]) * (q[0] - a[0]) + (b[1] - a[1]) * (q[1] - a[1])
    best, arg, top, right, left = math.inf, 0, 1, 1, None
    for i in range(n):
        a, b = h[i], h[(i + 1) % n]
        while abs(cross(a, b, h[(top + 1) % n])) > abs(cross(a, b, h[top])):
            top = (top + 1) % n
        while dot(a, b, h[(right + 1) % n]) > dot(a, b, h[right]):
            right = (right + 1) % n
        if left is None:
            left = top                     # the minimum lies past the top contact
        while dot(a, b, h[(left + 1) % n]) < dot(a, b, h[left]):
            left = (left + 1) % n
        area = abs(cross(a, b, h[top])) * (dot(a, b, h[right]) - dot(a, b, h[left])) / d2(a, b)
        if area < best:
            best, arg = area, i
    return best, arg

The area formula is exact until the final division. Height times |ab| is the cross product, the projection span times |ab| is the dot difference, and the two factors of |ab| cancel against d2(a, b). Starting the left pointer at the top contact is what keeps it from stopping at a local minimum near the bottom edge. The function matched a per-edge brute force on all 4,000 fuzz inputs, and on 30 random 15-point inputs it was never beaten by a 20,000-angle sweep over all orientations.

Worked example

Seven input points (0,0), (6,1), (8,4), (5,7), (1,5), (3,3) and (4,2) give a five-vertex hull; (3,3) and (4,2) are interior. Shoelace area 35. One caliper position per hull edge:

Reading the table: the width is the smallest height, 5.814, on edge (5,7)→(1,5). The minimum rectangle has area 52, reached on two edges. Ties are common, so report the first one or all of them, but decide which. The diameter is the largest distance over the antipodal pairs visited: (0,0)–(8,4) at √80 ≈ 8.944, which is also the projection span on edge (5,7)→(1,5), because that edge happens to be parallel to the diameter. The rectangle is 52/35 ≈ 1.49 times the hull's area. That ratio is a cheap measure of how well a bounding box represents the shape.

The wider caliper family

The same sweep, with different bookkeeping, solves a family of problems (Toussaint 1983 lists most of them):

• Minimum-perimeter rectangle: the same loop with height + span in place of the product, compared after normalising by |ab|.
• Maximum distance between two convex polygons: calipers with one jaw on each polygon. The minimum distance between disjoint convex polygons uses the same co-rotation.
• Bridges and merging hulls: the common tangents of two convex polygons, used in divide-and-conquer hull algorithms.
• Minkowski sum of convex polygons: merging the two edge sequences by angle is the calipers idea in another form, and the basis of collision detection and motion planning for convex shapes.
• Farthest pair of a point set: build the hull in O(n log n) and run the diameter. The closest pair needs a different technique; see closest pair of points.

Operational guidance

Real uses include oriented bounding boxes for 2D collision and sprite culling, minimum bounding rectangles of building footprints in GIS (many libraries offer a "minimum rotated rectangle" built on this method), the caliper diameter and width used in particle-shape and metrology measurements, and object orientation in image analysis. Habits that keep it correct:

• Snap coordinates to an integer grid (for example millimetres, or fixed-point degrees) before building the hull. Exact cross values remove most of the trouble.
• In floating point, use a tolerance-free orientation predicate (Shewchuk's adaptive predicates) or accept that nearly parallel edges may pick a neighbouring vertex. The diameter is stable under that error; the identity of the arg-min edge is not.
• Handle n ≤ 2 explicitly. A hull of one point or a segment has no edge to rest a jaw on.
• Test against brute force. The O(n²) diameter and per-edge rectangle oracles are ten lines each and catch every pointer bug.
• Remember the cost is dominated by the O(n log n) hull. For streaming or moving points, maintain the hull incrementally and rerun the linear sweep.

Failure modes

• Non-strict hull. Collinear or duplicate vertices make cross ties that stall or double-step the pointer. Pop on <= 0 when building the hull.
• Clockwise input. The formulas use |cross| and survive, but code that uses a signed cross for the farthest test breaks. Normalise the orientation once.
• Resetting the pointer per edge. That works but is O(n²). The monotone pointer is the whole point.
• Comparing true distances. sqrt adds rounding for no benefit. Compare squared distances and cross products.
• Assuming a unique answer. Squares, regular polygons and the example above all have ties. Downstream code that uses the chosen edge's angle must handle ties deterministically.
• Confusing width with the shortest side of the minimum-area rectangle. They can coincide, but they are different problems with different arg-min edges.

Trade-offs

Calipers turn O(n²) pair searches into one linear sweep, but only on a convex polygon, so the cost is the hull (O(n log n), or O(n log h) output-sensitive) plus O(n). For an axis-aligned box, skip all of this and take min and max of the coordinates. For a rough oriented box, PCA on the points is O(n) and simpler, but it can be noticeably larger than the optimum, and outliers pull it. For non-convex shapes the hull-based answers are still correct for diameter and enclosing boxes, but not for internal measures such as the narrowest neck, which need medial-axis or distance-transform methods. In 3D the analogous minimum-volume box (O'Rourke, 1985) takes cubic time, and most systems use approximations instead.

What to do next

1. Implement cross, the strict monotone-chain hull and diameter_sq, and fuzz them against the all-pairs maximum on random integer points, including collinear sets and n ≤ 2.
2. Add width and min_area_rect, fuzz both against per-edge brute force, and confirm on the five-vertex example that you get 5.814 and 52.
3. Return the rectangle's four corners (edge direction, normal, the four extremes) and draw them over your data to check by eye.
4. Decide and document a tie-breaking rule for the arg-min edge.
5. Apply it to a real problem: oriented boxes for shapes in your game or map data, or the farthest pair in a point cloud. Compare against the axis-aligned box and PCA box areas.
6. Read the 2D geometry primitives article and Graham scan to strengthen the predicates and hull construction underneath.