Rotating Calipers

The Algorithm

Given a convex polygon's vertices in counterclockwise order, walk two indices i (the current base edge) and j (the current farthest vertex from that edge) around the hull together. The key test at each step: is vertex j+1 farther from edge (i, i+1) than j is? "Farther" is measured with the same cross product from orientation() — the magnitude of the cross product of the edge vector and the vector to the candidate vertex is twice the triangle area, which is proportional to perpendicular distance for a fixed edge.

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


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


def polygon_diameter(hull):
    """hull: convex polygon vertices in counterclockwise order, no repeats."""
    n = len(hull)
    if n == 2:
        return dist_sq(hull[0], hull[1]), (hull[0], hull[1])

    j = 1
    best = 0.0
    best_pair = (hull[0], hull[0])
    for i in range(n):
        ni = (i + 1) % n
        # Advance j while it keeps increasing the triangle area against edge (i, ni).
        while abs(cross(hull[i], hull[ni], hull[(j + 1) % n])) > abs(cross(hull[i], hull[ni], hull[j])):
            j = (j + 1) % n
        d = dist_sq(hull[i], hull[j])
        if d > best:
            best, best_pair = d, (hull[i], hull[j])
        d2 = dist_sq(hull[ni], hull[j])
        if d2 > best:
            best, best_pair = d2, (hull[ni], hull[j])
    return best, best_pair


square = [(0, 0), (4, 0), (4, 4), (0, 4)]
best_sq, pair = polygon_diameter(square)
print(best_sq ** 0.5, pair)  # 4*sqrt(2), a diagonal pair

#include <cmath>
#include <vector>

struct Point { double x, y; };

double cross(const Point& o, const Point& a, const Point& b) {
    return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}

double distSq(const Point& a, const Point& b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

double polygonDiameterSq(const std::vector<Point>& hull) {
    int n = hull.size();
    if (n == 2) return distSq(hull[0], hull[1]);

    int j = 1;
    double best = 0.0;
    for (int i = 0; i < n; ++i) {
        int ni = (i + 1) % n;
        while (std::abs(cross(hull[i], hull[ni], hull[(j + 1) % n])) >
               std::abs(cross(hull[i], hull[ni], hull[j]))) {
            j = (j + 1) % n;
        }
        best = std::max({best, distSq(hull[i], hull[j]), distSq(hull[ni], hull[j])});
    }
    return best;
}

Core Insight: j never moves backward and never restarts from 0 on a new i — across the whole outer loop, j advances at most $n$ total steps, which is exactly why the whole algorithm is $O(n)$ rather than $O(n^2)$, even though it looks like a nested loop.

Worked Example

Trace It Yourself

Run polygon_diameter on the unit square [(0,0),(4,0),(4,4),(0,4)]. The diameter pair should be a diagonal (distance $4\sqrt2$), not an edge (distance $4$) — confirm j skips past the adjacent vertices and lands on the opposite corner as i advances around each edge.

The same i/j walking pattern, applied to the polygon's width instead of its diameter (tracking the perpendicular extent rather than the farthest vertex), gives the width and minimum-area enclosing rectangle computations described in the parent part.

Cookie Consent

Rotating Calipers

The Algorithm

Trace It Yourself

Related Reading

Rotating Calipers and Convex-Polygon Optimization