Rotating Calipers — The >= vs > Bug Warps Bounding Boxes

Rotating calipers, introduced by Michael Shamos in 1978, is an O(n) technique for computing geometric properties of convex polygons that would naively require O(n²) comparisons. The key insight: many geometric properties depend only on antipodal vertex pairs — pairs of vertices with parallel supporting lines. As you rotate 360°, each vertex becomes antipodal to at most 2 other vertices, so the total number of antipodal pairs is O(n).

The algorithm works by advancing two pointers around the convex hull, tracking which edge's supporting line defines the current antipodal vertex. The cross product between the current edge and the candidate vertex tells you when the antipodal relationship changes. Get that comparison wrong — use the wrong vertex as the origin — and your diameter comes out wrong. It's one of those algorithms where the intuition is clear but the implementation is finicky.

Here's the thing: you'll likely use a library in production. But when you need to debug why your bounding box is tilted or why the width estimate is off, understanding the antipodal pair loop is what saves your afternoon.

Rotating Calipers — The Geometry Trick That Squeezes Bounding Boxes

Rotating calipers is a computational geometry technique that finds the minimum-area enclosing rectangle of a convex polygon in O(n) time. The core mechanic: simulate a pair of parallel lines (calipers) rotating around the polygon, tracking which edges and vertices define the current width and height. At each step, the calipers pivot to align with the next edge, updating the bounding rectangle only when a new vertex becomes the limiting support point. This avoids the naive O(n²) approach of checking every possible orientation.

In practice, the algorithm exploits the convex hull's monotonicity: as one caliper rotates, the opposite support point advances monotonically along the hull. This property guarantees that each vertex is visited at most once per caliper, yielding linear total work. The critical implementation detail is the angle comparison — using cross products to decide which edge to rotate to next, not actual trigonometric functions. A common trap: using >= instead of > when comparing cross products, which can cause infinite loops or missed rotations when multiple edges share the same support point.

Use rotating calipers when you need the tightest bounding box for collision detection, object tracking, or packing optimization. It's the standard for computing minimum-area rectangles, minimum-width annuli, and the diameter of a convex set. In real-time systems like game physics or lidar processing, the O(n) runtime is essential — the naive O(n²) alternative would drop frames or miss sensor updates.

Polygon Diameter — Farthest Pair of Points

The diameter of a convex polygon is the maximum distance between any two vertices. Naively O(n²) — but with rotating calipers, O(n) after the hull is built. The algorithm maintains an index j for the antipodal vertex of edge (i, i+1). As i moves around the hull, j advances only in one direction (mod n), ensuring total O(n) steps.

The cross product between the edge vector and the vector from edge start to candidate vertex tells you if the distance to the candidate line is increasing. When that distance starts decreasing, j has passed the antipodal point for that edge. You then check distances between vertices i and j, and (i+1) and j — one of these will be the maximum for that edge.

from math import dist

def polygon_diameter(hull: list[tuple]) -> float:
    """Maximum distance between any two hull vertices. O(n)."""
    n = len(hull)
    if n == 1: return 0
    if n == 2: return dist(hull[0], hull[1])
    def cross_len(o, a, b):
        return abs((a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]))
    max_dist = 0
    j = 1
    for i in range(n):
        # Advance j while cross product increases (antipodal tracking)
        while cross_len(hull[i], hull[(i+1)%n], hull[(j+1)%n]) > \
              cross_len(hull[i], hull[(i+1)%n], hull[j]):
            j = (j + 1) % n
        max_dist = max(max_dist,
                       dist(hull[i], hull[j]),
                       dist(hull[(i+1)%n], hull[j]))
    return max_dist

hull = [(0,0),(3,0),(3,4),(0,4)]  # 3x4 rectangle — diameter = 5
print(f'Diameter: {polygon_diameter(hull):.3f}')  # 5.0 (diagonal)

Minimum Width — The Smallest Enclosing Strip

The minimum width of a convex polygon is the smallest distance between two parallel lines that enclose the entire polygon. This is the minimum over all antipodal pairs of the perpendicular distance from the antipodal vertex to the current edge. For each edge (i,i+1), the width in that direction is the distance from the antipodal vertex j to the line defined by that edge — exactly the cross product length divided by the edge length.

The algorithm is identical to the diameter loop, but instead of tracking maximum distance between vertices, you track the minimum of the perpendicular distances. The cross_len function already gives you twice the area of the triangle (edge, j), which is proportional to the perpendicular distance.

from math import sqrt, dist

def polygon_width(hull: list[tuple]) -> float:
    """Minimum width of convex hull. O(n)."""
    n = len(hull)
    if n < 3: return 0.0
    def cross_len(o, a, b):
        return abs((a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]))
    def edge_len(i):
        return dist(hull[i], hull[(i+1)%n])
    min_width = float('inf')
    j = 1
    for i in range(n):
        while cross_len(hull[i], hull[(i+1)%n], hull[(j+1)%n]) > \
              cross_len(hull[i], hull[(i+1)%n], hull[j]):
            j = (j + 1) % n
        width = cross_len(hull[i], hull[(i+1)%n], hull[j]) / edge_len(i)
        min_width = min(min_width, width)
    return min_width

hull = [(0,0),(4,0),(4,3),(0,3)]  # 4x3 rectangle — width = 3
print(f'Width: {polygon_width(hull):.3f}')

Closest Pair Between Two Convex Hulls

Two convex polygons can be separated in O(n + m) using rotating calipers extended to handle two independent hulls. The algorithm maintains two pointers, one on each hull, and finds the pair of points (one per hull) that are closest together. The naive approach is O(nm) — for each vertex of hull A, find the closest vertex on hull B. But with a rotating calipers variant, you can find the minimum distance in linear total time.

The method: start with the vertex of hull A with the smallest x-coordinate and the vertex of hull B with the largest x-coordinate (assuming hulls are disjoint). Then, as you traverse A, you advance B's pointer when the distance starts decreasing. The condition uses the orientation of the edge of A relative to the candidate vertices on B.

This is trickier than the single-hull version because you must handle the case where the closest pair involves a vertex from one hull and an edge of the other. The full solution (Edelsbrunner's algorithm) returns both distance and which points form the closest pair.

from math import dist

def closest_pair_convex_hulls(hull_a: list[tuple], hull_b: list[tuple]) -> float:
    """Minimum distance between two convex polygons. O(n+m)."""
    # Ensure hulls are sorted CCW
    n, m = len(hull_a), len(hull_b)
    if n == 0 or m == 0: return float('inf')
    # Start with extreme x vertices
    i = min(range(n), key=lambda idx: hull_a[idx][0])
    j = max(range(m), key=lambda idx: hull_b[idx][0])
    min_dist = dist(hull_a[i], hull_b[j])
    def cross(o, a, b):
        return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])
    # Rotate both pointers, advancing when the other hull's next vertex reduces distance
    for _ in range(n + m):
        dist_curr = dist(hull_a[i], hull_b[j])
        if dist_curr < min_dist:
            min_dist = dist_curr
        # Try advancing on hull A and B
        next_i = (i+1) % n
        next_j = (j+1) % m
        # Determine which hull's next vertex is more promising
        # Use orientation of edge (i, next_i) relative to candidate from B
        # Simplified: advance the hull where the next vertex is closer?
        # (In production, use the more robust criterion based on support lines)
        if cross(hull_a[i], hull_b[next_j], hull_a[next_i]) >= 0:
            j = next_j
        else:
            i = next_i
    return min_dist

# Example: two squares separated horizontally
hull_a = [(0,0),(2,0),(2,2),(0,2)]
hull_b = [(5,0),(7,0),(7,2),(5,2)]
print(f'Closest distance: {closest_pair_convex_hulls(hull_a, hull_b):.3f}')  # 3.000

Minimum Enclosing Rectangle — The Bounding Box Problem

The minimum-area enclosing rectangle (minimum bounding box) of a convex polygon can be found in O(n) using rotating calipers. The rectangle must have one side collinear with a hull edge (the theorem: the optimal rectangle's edge coincides with some hull edge). For each hull edge, you need four antipodal points: the farthest point in the direction perpendicular to the edge (height), and the farthest points in the parallel directions (width extension left and right of the edge's projection).

The algorithm: maintain three antipodal pointers — one for the farthest vertex in the direction of the edge normal (height), and two for the extreme vertices in the direction parallel to the edge (left and right extremes). As the edge rotates, these pointers update. The area of the candidate rectangle = width * height, where width is the projection span and height is the perpendicular distance.

This is used everywhere: packing objects for shipping, collision detection hulls, image processing for bounding oriented objects.

from math import dist, sqrt, acos, pi

def min_enclosing_rectangle(hull: list[tuple]):
    """Return (area, corners) of minimum-area enclosing rectangle."""
    n = len(hull)
    if n < 3: return (0.0, [])
    # Helper: dot product
    def dot(a, b): return a[0]*b[0] + a[1]*b[1]
    def edge_vec(i): return (hull[(i+1)%n][0]-hull[i][0],
                            hull[(i+1)%n][1]-hull[i][1])
    def normalize(v):
        l = sqrt(v[0]*v[0] + v[1]*v[1])
        return (v[0]/l, v[1]/l) if l != 0 else (0,0)
    # Initial pointers: antipodal for height, and extreme left/right along edge
    j = 1  # farthest in normal direction
    k = 1  # farthest in -edge direction (left)
    l = 1  # farthest in +edge direction (right)
    min_area = float('inf')
    best_rect = []
    for i in range(n):
        e = edge_vec(i)
        e_norm = normalize(e)
        # Normal perpendicular (outward)
        perp = (-e_norm[1], e_norm[0])
        # Advance j while cross product increases
        while True:
            next_j = (j+1)%n
            # Use distance to the line defined by e from hull[i]
            cur_d = abs((hull[j][0]-hull[i][0])*perp[0] + (hull[j][1]-hull[i][1])*perp[1])
            nxt_d = abs((hull[next_j][0]-hull[i][0])*perp[0] + (hull[next_j][1]-hull[i][1])*perp[1])
            if nxt_d <= cur_d:
                break
            j = next_j
        # Advance k (left extreme) using dot with -e
        while True:
            next_k = (k+1)%n
            cur_dot = dot((hull[k][0]-hull[i][0], hull[k][1]-hull[i][1]), e)
            nxt_dot = dot((hull[next_k][0]-hull[i][0], hull[next_k][1]-hull[i][1]), e)
            if nxt_dot >= cur_dot:  # moving away from hull[i] in e direction
                break
            k = next_k
        # Advance l (right extreme) using dot with +e
        while True:
            next_l = (l+1)%n
            cur_dot = dot((hull[l][0]-hull[i][0], hull[l][1]-hull[i][1]), e)
            nxt_dot = dot((hull[next_l][0]-hull[i][0], hull[next_l][1]-hull[i][1]), e)
            if nxt_dot <= cur_dot:
                break
            l = next_l
        # Compute rectangle dimensions
        height = abs((hull[j][0]-hull[i][0])*perp[0] + (hull[j][1]-hull[i][1])*perp[1])
        # Width = projection of hull onto e
        left_dot = dot((hull[k][0]-hull[i][0], hull[k][1]-hull[i][1]), e_norm)
        right_dot = dot((hull[l][0]-hull[i][0], hull[l][1]-hull[i][1]), e_norm)
        width = right_dot - left_dot
        area = width * height
        if area < min_area:
            min_area = area
            # Compute corners (not shown for brevity)
    return min_area

Implementation Pitfalls and Debugging Pattern

Rotating calipers looks simple on paper but bites you in subtle ways. The most common bugs: wrong while loop condition, off-by-one in pointer advancement, integer overflow in cross product (especially with large coordinates), and ignoring collinear hull points. Also, the algorithm requires a strictly convex hull in counterclockwise order — if your points are convex but in clockwise order, the antipodal relationship reverses.

The antipodal pointer j should never move backward — if it does, your cross product comparison is wrong or the hull is not convex.

Intersection Detection — When Two Hulls Collide

You've built two convex hulls and now you need to know if they intersect. The naive O(n*m) check is fine for a hackathon but will get you paged at 3 AM when someone shoves 10,000 points into your geometry pipeline.

Rotating calipers solves this in O(n+m) by walking both hulls simultaneously. The trick: maintain a separating line between the hulls. If you can slide that line through the gap without crossing either hull, they don't intersect. The calipers rotate, tracking the supporting lines of both polygons, and you check for separation at each vertex transition.

Here's the production insight: most collision detection systems cache the convex hull and only rebuild on mutation. The calipers intersection check runs so fast it's often cheaper than bailing early on a brute-force bounding-box test. Use it when your hulls are dynamic but convexity is preserved — think physics engines, GIS boundary checks, or any game where hitboxes matter.

// io.thecodeforge — dsa tutorial

import java.awt.geom.Point2D;
import java.util.List;

public class HullIntersectionCheck {
    public static boolean hullsIntersect(List<Point2D> hullA, List<Point2D> hullB) {
        int n = hullA.size(), m = hullB.size();
        if (n < 3 || m < 3) return false;
        
        int i = 0, j = 0;
        for (int step = 0; step < 2 * (n + m); step++) {
            Point2D a1 = hullA.get(i), a2 = hullA.get((i + 1) % n);
            Point2D b1 = hullB.get(j), b2 = hullB.get((j + 1) % m);
            
            double crossA = cross(a2.x - a1.x, a2.y - a1.y,
                                    b2.x - b1.x, b2.y - b1.y);
            
            if (segmentsIntersect(a1, a2, b1, b2)) {
                return true;
            }
            
            // advance the hull with the "more left" edge
            if (crossA >= 0) {
                i = (i + 1) % n;
            } else {
                j = (j + 1) % m;
            }
        }
        return false;
    }
    
    private static double cross(double x1, double y1, double x2, double y2) {
        return x1 * y2 - y1 * x2;
    }
    
    // segment intersection logic omitted for brevity
}

Width of a Polygon — How Fat Is Your Shape?

Minimum width of a convex polygon is the smallest distance between two parallel supporting lines that enclose it. This isn't academic — CNC machining, crash boxes in automotive, and even typography hinting use width to decide whether a shape fits through a gap.

Rotating calipers nails O(n) by pairing each edge with the farthest vertex on the opposite side. The distance from that vertex to the edge line is a candidate width. Rotate the calipers through all edges, track the minimum. That's your tightest strip.

The naive approach computes per-edge distances to every vertex — O(n²). With calipers, the farthest vertex advances monotonically as you rotate, same as the diameter algorithm. The key difference: you're measuring perpendicular distance to the edge, not Euclidean distance between vertices.

Real-world gotcha: the minimum width is often determined by a single edge and its antipodal vertex, not a pair of edges. Implement the distance function with infinite precision — one floating-point error and your tolerance stack collapses on the assembly line.

// io.thecodeforge — dsa tutorial

import java.awt.geom.Point2D;
import java.util.List;

public class PolygonMinWidth {
    public static double minWidth(List<Point2D> hull) {
        int n = hull.size();
        if (n < 3) return 0;
        
        double minW = Double.MAX_VALUE;
        int anti = 1;
        for (int edge = 0; edge < n; edge++) {
            Point2D a = hull.get(edge);
            Point2D b = hull.get((edge + 1) % n);
            
            // advance antipodal while distance increases
            while (true) {
                double dist = distToLine(hull.get(anti), a, b);
                double nextDist = distToLine(hull.get((anti + 1) % n), a, b);
                if (nextDist <= dist) break;
                anti = (anti + 1) % n;
            }
            
            minW = Math.min(minW, distToLine(hull.get(anti), a, b));
        }
        return minW;
    }
    
    private static double distToLine(Point2D p, Point2D a, Point2D b) {
        double dx = b.getX() - a.getX();
        double dy = b.getY() - a.getY();
        return Math.abs(dx * (a.getY() - p.getY()) - dy * (a.getX() - p.getX()))
                / Math.hypot(dx, dy);
    }
}