Introduction

Imagine gripping a convex polygon between the flat jaws of a physical caliper. If you slowly rotate the caliper all the way around the shape without letting go, you will slide across every extreme point at least once. When the jaws are widest apart, you have just found the diameter — the two vertices that are farthest from each other.

This physical intuition is the heart of rotating calipers, a computational geometry technique published by Michael Shamos in 1978. In its algorithmic form, two parallel "support lines" are initialized touching the topmost and bottommost vertices of a convex hull, and then rotated together in small angular steps. At each step the gap between the lines is measured and the maximum recorded. One full revolution costs only O(n)O(n) time — a single linear pass over the polygon's n vertices.

Before rotating calipers, computing the diameter of a convex polygon required checking all O(n2)O(n^{2}) pairs of vertices. Shamos's insight was that the extremal pair always appears as the lines co-rotate, so no pair needs to be checked twice.

Try It

Click Step to advance the calipers by one vertex at a time, or Animate to watch the full rotation. The highlighted vertex pair in red is the current candidate for the diameter; when the rotation is complete the true diameter is locked in.

<div class="controls">
  <button id="stepBtn" type="button">Step</button>
  <button id="animBtn" type="button">Animate</button>
  <button id="resetBtn" type="button" class="ghost">Reset</button>
  <span class="sep">|</span>
  <label class="lbl">Polygon:
    <select id="shapeSelect">
      <option value="hex">Hexagon</option>
      <option value="oct">Octagon</option>
      <option value="irregular">Irregular</option>
      <option value="rect">Rectangle</option>
    </select>
  </label>
</div>
<canvas id="cv" width="460" height="300"></canvas>
<div class="info" id="info">Press Step or Animate to start.</div>

* { box-sizing: border-box; margin: 0; padding: 0; }
body { font-family: system-ui, sans-serif; color: #222; background: #fff; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; padding: .4rem 0; }
button { font: 600 13px system-ui; padding: .35rem .75rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.sep { color: #bbb; }
.lbl { font-size: .85rem; color: #444; display: flex; align-items: center; gap: .3rem; }
select { font: 13px system-ui; border: 1px solid #ccc; border-radius: 5px; padding: .2rem .4rem; }
#cv { display: block; border: 1px solid #d0d8e4; border-radius: 8px; background: #f7f9fb;
      max-width: 100%; }
.info { margin-top: .45rem; font-size: .86rem; line-height: 1.5; color: #333; min-height: 2.6em; }
.info b { color: #1d3557; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Rotating Calipers – find the diameter of a convex polygon in O(n).
// Shamos (1978): initialize two parallel support lines at the bottom/top vertices,
// then advance the pointer whose next edge subtends a smaller angle,
// tracking the maximum distance across all antipodal pairs.
//
// Implementation note: canvas uses screen coordinates (Y increases downward).
// Convex hull built by Andrew's monotone chain gives CCW order in math (Y-up),
// which appears CW on screen (Y-down). For a CCW-math polygon the correct
// advance rule is: advance p when cross(ep, eq) < 0; advance q when > 0.

const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
const W = cv.width, H = cv.height;

// ── Polygon definitions (raw points; hull is computed automatically) ────────
const SHAPES = {
  hex:  [230,50, 330,100, 330,200, 230,250, 130,200, 130,100],
  oct:  [200,30, 280,30,  350,100, 350,200, 280,270, 200,270, 130,200, 130,100],
  irregular: [160,50, 300,60, 380,160, 320,270, 170,280, 80,190, 100,90],
  rect: [100,80, 360,80,  360,220, 100,220]
};

// Andrew's monotone chain – produces CCW hull in math / CW on screen
function convexHull(rawPts) {
  const pts = rawPts.slice().sort((a,b) => a[0]-b[0] || a[1]-b[1]);
  const cross = (O,A,B) => (A[0]-O[0])*(B[1]-O[1]) - (A[1]-O[1])*(B[0]-O[0]);
  const lower = [], upper = [];
  for (const p of pts) {
    while (lower.length >= 2 && cross(lower[lower.length-2],lower[lower.length-1],p) <= 0) lower.pop();
    lower.push(p);
  }
  for (let i = pts.length-1; i >= 0; i--) {
    const p = pts[i];
    while (upper.length >= 2 && cross(upper[upper.length-2],upper[upper.length-1],p) <= 0) upper.pop();
    upper.push(p);
  }
  upper.pop(); lower.pop();
  return lower.concat(upper); // CCW-math / CW-screen
}

function parsePts(flat) {
  const out = [];
  for (let i = 0; i < flat.length; i += 2) out.push([flat[i], flat[i+1]]);
  return out;
}

function dist2(a, b) { return (a[0]-b[0])**2 + (a[1]-b[1])**2; }

// ── Algorithm state ─────────────────────────────────────────────────────────
let hull = [], n = 0;
let pIdx = 0, qIdx = 0;
let stepN = 0;
let maxD2 = 0, maxP = 0, maxQ = 0;
let done = false;
let animId = null;

function initShape(key) {
  clearAnim();
  hull = convexHull(parsePts(SHAPES[key]));
  n = hull.length;
  // p = bottommost on screen (max screen-Y), q = topmost (min screen-Y)
  pIdx = 0; qIdx = 0;
  for (let i = 1; i < n; i++) {
    if (hull[i][1] > hull[pIdx][1]) pIdx = i;
    if (hull[i][1] < hull[qIdx][1]) qIdx = i;
  }
  maxD2 = dist2(hull[pIdx], hull[qIdx]);
  maxP = pIdx; maxQ = qIdx;
  stepN = 0; done = false;
  draw();
  setInfo(fmt('Calipers initialized. <b>p</b> (red) = vertex %pIdx%, <b>q</b> (green) = vertex %qIdx%. Press <b>Step</b> to begin.', { pIdx: pIdx, qIdx: qIdx }));
}

function doStep() {
  if (done) return;
  // Measure current pair
  const d = dist2(hull[pIdx], hull[qIdx]);
  if (d > maxD2) { maxD2 = d; maxP = pIdx; maxQ = qIdx; }

  // Decide which pointer to advance
  const np = (pIdx+1) % n, nq = (qIdx+1) % n;
  const epx = hull[np][0]-hull[pIdx][0], epy = hull[np][1]-hull[pIdx][1];
  const eqx = hull[nq][0]-hull[qIdx][0], eqy = hull[nq][1]-hull[qIdx][1];
  const c = epx*eqy - epy*eqx;
  // CCW-math polygon (CW-screen): advance p if c < 0, q if c > 0
  if (c < 0) pIdx = np;
  else if (c > 0) qIdx = nq;
  else { pIdx = np; qIdx = nq; } // parallel edges: advance both

  stepN++;
  if (stepN >= n) done = true;
  draw();
  const diam = Math.sqrt(maxD2).toFixed(1);
  if (done) {
    setInfo(fmt('Done! Diameter = <b>%diam% px</b> between vertex %maxP% and vertex %maxQ% — checked <b>%n%</b> antipodal pairs (brute force: <b>%v%</b> pairs).', { diam: diam, maxP: maxP, maxQ: maxQ, n: n, v: n*(n-1)/2 }));
  } else {
    setInfo(fmt('Step %stepN%/%n%: p=%pIdx%, q=%qIdx% | current distance = <b>%sqrt% px</b> | best so far = <b>%diam% px</b>.', { stepN: stepN, n: n, pIdx: pIdx, qIdx: qIdx, sqrt: Math.sqrt(d).toFixed(1), diam: diam }));
  }
}

function clearAnim() { if (animId) { clearInterval(animId); animId = null; } }
function setInfo(html) { document.getElementById('info').innerHTML = html; }

function draw() {
  ctx.clearRect(0, 0, W, H);

  // Polygon fill
  ctx.beginPath();
  ctx.moveTo(hull[0][0], hull[0][1]);
  for (let i = 1; i < n; i++) ctx.lineTo(hull[i][0], hull[i][1]);
  ctx.closePath();
  ctx.fillStyle = '#dde6f0';
  ctx.fill();
  ctx.strokeStyle = '#3a5f8a';
  ctx.lineWidth = 1.8;
  ctx.stroke();

  // Best diameter line (gold)
  if (stepN > 0) {
    ctx.save();
    ctx.strokeStyle = '#e8a020';
    ctx.lineWidth = 2.5;
    ctx.setLineDash([]);
    ctx.beginPath();
    ctx.moveTo(hull[maxP][0], hull[maxP][1]);
    ctx.lineTo(hull[maxQ][0], hull[maxQ][1]);
    ctx.stroke();
    [maxP, maxQ].forEach(i => {
      ctx.beginPath();
      ctx.arc(hull[i][0], hull[i][1], 7, 0, Math.PI*2);
      ctx.strokeStyle = '#e8a020'; ctx.lineWidth = 2.5;
      ctx.stroke();
    });
    ctx.restore();
  }

  // Current caliper pair (red dashed line)
  ctx.save();
  ctx.strokeStyle = '#e63946';
  ctx.lineWidth = 1.8;
  ctx.setLineDash([5,3]);
  ctx.beginPath();
  ctx.moveTo(hull[pIdx][0], hull[pIdx][1]);
  ctx.lineTo(hull[qIdx][0], hull[qIdx][1]);
  ctx.stroke();
  ctx.restore();

  // Support lines (extend across full canvas width)
  function supportLine(idx, color, dash) {
    ctx.save();
    ctx.strokeStyle = color; ctx.lineWidth = 1.2; ctx.setLineDash(dash);
    ctx.beginPath(); ctx.moveTo(0, hull[idx][1]); ctx.lineTo(W, hull[idx][1]);
    ctx.stroke(); ctx.restore();
  }
  supportLine(pIdx, '#e63946', [6,4]);
  supportLine(qIdx, '#1d7d4a', [6,4]);

  // Vertices
  hull.forEach((p, i) => {
    const isActive = i === pIdx || i === qIdx;
    ctx.beginPath();
    ctx.arc(p[0], p[1], isActive ? 5.5 : 4, 0, Math.PI*2);
    ctx.fillStyle = i === pIdx ? '#e63946' : i === qIdx ? '#1d7d4a' : '#3a5f8a';
    ctx.fill();
    ctx.fillStyle = '#555'; ctx.font = '11px system-ui';
    ctx.fillText(i, p[0]+6, p[1]-5);
  });

  // Legend
  const ly = H - 8;
  ctx.font = '11px system-ui';
  ctx.fillStyle = '#e63946'; ctx.fillText('● p (red)', 8, ly-18);
  ctx.fillStyle = '#1d7d4a'; ctx.fillText('● q (green)', 72, ly-18);
  ctx.fillStyle = '#e8a020'; ctx.fillText('━ best diameter', 160, ly-18);
}

// ── Controls ─────────────────────────────────────────────────────────────
document.getElementById('stepBtn').addEventListener('click', () => { clearAnim(); doStep(); });
document.getElementById('animBtn').addEventListener('click', () => {
  if (done) initShape(document.getElementById('shapeSelect').value);
  clearAnim();
  animId = setInterval(() => { doStep(); if (done) clearAnim(); }, 380);
});
document.getElementById('resetBtn').addEventListener('click', () =>
  initShape(document.getElementById('shapeSelect').value));
document.getElementById('shapeSelect').addEventListener('change', e => initShape(e.target.value));

initShape('hex');

// ── Node.js self-test (skipped in browser) ───────────────────────────────────────────────────────────
if (typeof module !== 'undefined') {
  function chull(rawPts) {
    const pts = rawPts.slice().sort((a,b)=>a[0]-b[0]||a[1]-b[1]);
    const cr=(O,A,B)=>(A[0]-O[0])*(B[1]-O[1])-(A[1]-O[1])*(B[0]-O[0]);
    const lo=[],up=[];
    for(const p of pts){while(lo.length>=2&&cr(lo[lo.length-2],lo[lo.length-1],p)<=0)lo.pop();lo.push(p);}
    for(let i=pts.length-1;i>=0;i--){const p=pts[i];while(up.length>=2&&cr(up[up.length-2],up[up.length-1],p)<=0)up.pop();up.push(p);}
    up.pop();lo.pop();return lo.concat(up);
  }
  function caliper(rawPts) {
    const h=chull(rawPts),n=h.length;
    let p=0,q=0;
    for(let i=1;i<n;i++){if(h[i][1]>h[p][1])p=i;if(h[i][1]<h[q][1])q=i;}
    let maxD2=(h[p][0]-h[q][0])**2+(h[p][1]-h[q][1])**2;
    for(let s=0;s<n;s++){
      const np=(p+1)%n,nq=(q+1)%n;
      const epx=h[np][0]-h[p][0],epy=h[np][1]-h[p][1];
      const eqx=h[nq][0]-h[q][0],eqy=h[nq][1]-h[q][1];
      const c=epx*eqy-epy*eqx;
      if(c<0)p=np;else if(c>0)q=nq;else{p=np;q=nq;}
      const d=(h[p][0]-h[q][0])**2+(h[p][1]-h[q][1])**2;
      if(d>maxD2)maxD2=d;
    }
    return Math.sqrt(maxD2);
  }
  function bf(pts){let m=0;for(let i=0;i<pts.length;i++)for(let j=i+1;j<pts.length;j++){const d=Math.sqrt((pts[i][0]-pts[j][0])**2+(pts[i][1]-pts[j][1])**2);if(d>m)m=d;}return m;}

  // unit square: diameter = sqrt(2)
  const sq=[[0,0],[1,0],[1,1],[0,1]];
  console.assert(Math.abs(caliper(sq)-Math.SQRT2)<1e-9,'Square failed');

  // 3-4-5 rectangle: diameter = 5
  const r345=[[0,0],[3,0],[3,4],[0,4]];
  console.assert(Math.abs(caliper(r345)-5)<1e-9,'Rectangle 3x4 failed');

  // regular hexagon (unit circle): diameter = 2
  const hex6=Array.from({length:6},(_,i)=>[Math.cos(i*Math.PI/3),Math.sin(i*Math.PI/3)]);
  console.assert(Math.abs(caliper(hex6)-2)<1e-9,'Hexagon failed');

  // irregular polygon matches brute force
  const irr=[[160,50],[300,60],[380,160],[320,270],[170,280],[80,190],[100,90]];
  const cd=caliper(irr),bfd=bf(irr);
  console.assert(Math.abs(cd-bfd)<1e-4,'Irregular mismatch: '+cd+' vs '+bfd);

  // octagon (approx unit circle, 8 sides)
  const oct8=Array.from({length:8},(_,i)=>[Math.cos(i*Math.PI/4),Math.sin(i*Math.PI/4)]);
  const cd8=caliper(oct8),bfd8=bf(oct8);
  console.assert(Math.abs(cd8-bfd8)<1e-4,'Octagon mismatch: '+cd8+' vs '+bfd8);

  console.log('All rotating calipers assertions passed.',
    'sq='+caliper(sq).toFixed(6),
    'rect='+caliper(r345).toFixed(6),
    'hex='+caliper(hex6).toFixed(6),
    'irr='+caliper(irr).toFixed(4)+'(bf='+bf(irr).toFixed(4)+')');
}
Result
Console

Notice that the calipers only jump to the next vertex when one of the two support lines is about to touch it — the algorithm never revisits a vertex. Every vertex is processed exactly once per caliper, giving the O(n)O(n) guarantee. Compare this with the O(n2)O(n^{2}) brute-force "check every pair" approach shown in the info panel.

The Real Complexity

How fast can you find the diameter of a convex polygon, and how do we know rotating calipers achieve the best possible speed?

  • Brute force checks every pair of vertices: O(n2)O(n^{2}) distance computations — already impractical for a polygon with thousands of vertices.
  • Rotating calipers run in O(n)O(n) once the convex hull is available. The key insight is the concept of antipodal pairs: two vertices are antipodal if parallel support lines can simultaneously touch both. As the calipers rotate by one full turn, every antipodal pair is visited exactly once — and the diameter must be one of them.
  • It is optimal. Any algorithm for this problem must inspect all n vertices at least once (otherwise it could miss an endpoint of the diameter), so Ω(n) is a lower bound. Rotating calipers match it exactly.
  • The convex hull is the bottleneck. If you start from raw points rather than a pre-computed hull, you first need O(nlog⁡n)O(n \log n) to build it. The overall pipeline is thus O(nlog⁡n)O(n \log n), dominated by sorting.

Rotating calipers also solve many related problems in the same O(n)O(n) pass: minimum-width (the narrowest pair of parallel lines enclosing the polygon), minimum bounding rectangle, and the closest pair of antipodal features — all without extra cost. The convex hull is the prerequisite; once you have it, calipers extract an entire family of geometric properties for free.

Where It Matters

"Find the extremal geometry of a convex shape efficiently" is a surprisingly common task in software systems:

  • Robotics and collision detection: the minimum bounding rectangle of an obstacle — computed via rotating calipers — is a fast first-pass proxy for whether two objects might collide.
  • Geographic information systems: axis-aligned and oriented bounding boxes for spatial queries over polygons rely on the same one-pass extremal scan.
  • Computer vision: the diameter and minimum enclosing rectangle of a detected object region are used for shape classification and pose estimation.
  • Computational geometry pipelines: rotating calipers are a subroutine in algorithms for the closest pair of points, Minkowski sum computation, and polygon intersection tests.
  • Manufacturing and packing: the minimum-width direction tells a factory the optimal orientation to cut a part from sheet material with the least waste.

The algorithm's elegance lies in reducing a two-dimensional sweep to a one-dimensional scan along the polygon boundary. Once the convex hull exists, calipers give you diameter, width, and bounding rectangle in a single O(n)O(n) pass — all three results for the price of one rotation.

Conclusion

Rotating calipers are a lesson in listening to the geometry. The diameter of a convex polygon cannot hide — it must be an antipodal pair, and all antipodal pairs parade past in a single O(n)O(n) rotation. By exploiting that structure, Shamos turned an O(n2)O(n^{2}) brute-force sweep into a clean linear pass.

The deeper message is algorithmic: the best solutions are often found not by working harder but by identifying the invariant that limits where the answer can be. Here the invariant is convexity — and two spinning lines are enough to harvest it completely.

Next time you need the width, diameter, or bounding rectangle of a convex shape, remember: you don't have to check every pair. Just spin the calipers once.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/rotating-calipers/Content licensed under CC BY-NC 4.0.