Introduction

Picture a handful of pins stuck into a corkboard. Now imagine stretching a piece of gift-wrap ribbon taut against the outermost pin, then swinging it around like a rigid arm until it snaps flat against the next outermost pin, then the next, and so on until the ribbon has come full circle. That physical motion — sweep, snap, sweep, snap — is precisely the gift wrapping algorithm, discovered by R. A. Jarvis in 1973 and often called the Jarvis march.

It solves the same problem as the convex hull: find the smallest convex polygon that encloses every point. But instead of sorting everything up front, gift wrapping builds the boundary one vertex at a time by always asking a single local question: "starting from the edge I just placed, which point is furthest around to the outside?"

It's slower than the fastest hull algorithms in the worst case, but it has a charming property: its running time scales with the size of the answer (the hull), not just the size of the input. Wrap a cloud of a million points that happens to have only five points on the boundary, and gift wrapping barely breaks a sweat.

Try It

Below is a scatter of points, with the leftmost (guaranteed to be on the hull) marked as the starting anchor. Press Step to pivot the wrapping ray one point at a time — watch it sweep counter-clockwise from the current hull edge until it locks onto the most extreme point, exactly like a taut ribbon snapping into place. Press Wrap fully to run the whole march at once, or Reset to scatter a fresh set of points.

<p class="hint">The gold point is the leftmost point — guaranteed to be on the hull, and where the wrap begins. Press <b>Step</b> to pivot one point at a time, or <b>Wrap fully</b> to run the whole march. The dashed red ray shows the candidate edge being tested before it locks in.</p>
<canvas id="cv" width="360" height="280"></canvas>
<div class="status" id="status">Press Step to begin wrapping.</div>
<div class="btns">
  <button id="step" type="button">Step</button>
  <button id="wrap" type="button">Wrap fully</button>
  <button id="reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
canvas { background: #f4f7fa; border: 1px solid #cdd9e3; border-radius: 10px;
         touch-action: none; max-width: 100%; display: block; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.status.done { color: #0a7d33; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .5; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Gift wrapping (Jarvis march): start at the leftmost point (guaranteed to be
// on the hull) and repeatedly pivot to whichever remaining point is furthest
// around, using only the sign of a cross product. Cost is O(n*h).
const cv = document.getElementById('cv');
const ctx = cv.getContext('2d');
const W = cv.width, H = cv.height, R = 6;

// A fixed base layout jittered randomly each reset, so the hull size h varies.
function scatter(){
  const base = [
    [60,60],[300,50],[330,210],[70,230],[180,140],
    [200,70],[120,180],[260,160],[150,90],[240,210],[40,150]
  ];
  return base.map(([x,y]) => [x + (Math.random()*36-18), y + (Math.random()*36-18)]);
}
let pts = scatter();

// Cross product: positive means c is to the left of the ray a->b.
function cross(o,a,b){ return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0]); }
function dist2(a,b){ const dx=a[0]-b[0], dy=a[1]-b[1]; return dx*dx + dy*dy; }

// current = index of the last confirmed hull vertex; candidate = point being tested.
let startIdx = 0, current = 0, hullIdx = [], candidate = -1, finished = false;

function findStart(){
  let s = 0;
  for(let i=1;i<pts.length;i++){
    if(pts[i][0] < pts[s][0] || (pts[i][0]===pts[s][0] && pts[i][1] < pts[s][1])) s = i;
  }
  return s;
}

function resetWalk(){
  startIdx = findStart();
  current = startIdx;
  hullIdx = [];
  candidate = -1;
  finished = false;
  document.getElementById('wrap').disabled = false;
  document.getElementById('step').disabled = false;
}

// One pivot step. From `current`, scan every other point and keep whichever is
// furthest to the left of the ray so far -- that point becomes the next hull vertex.
function pivotOnce(){
  if(finished) return false;
  hullIdx.push(current);
  let next = current === 0 ? (pts.length > 1 ? 1 : 0) : 0;
  if(next === current) next = pts.length > 1 ? 1 : 0;
  for(let cand = 0; cand < pts.length; cand++){
    if(cand === current) continue;
    const c = cross(pts[current], pts[next], pts[cand]);
    if(c > 0){
      next = cand;
    } else if(c === 0 && dist2(pts[current], pts[cand]) > dist2(pts[current], pts[next])){
      next = cand;
    }
  }
  candidate = next;
  current = next;
  if(current === startIdx){ finished = true; }
  return true;
}

function step(){
  if(finished){ return; }
  const wasEmpty = hullIdx.length === 0;
  pivotOnce();
  draw();
  if(finished){
    setStatus(fmt('Hull closed after %h% pivot(s) — that’s exactly h, the hull size.', { h: hullIdx.length }), 'done');
    document.getElementById('step').disabled = true;
    document.getElementById('wrap').disabled = true;
  } else {
    setStatus(fmt('Placed %h% hull point(s) so far — press Step again.', { h: hullIdx.length }), '');
  }
}

function wrapFully(){
  let guard = 0;
  while(!finished && guard < pts.length + 2){ pivotOnce(); guard++; }
  draw();
  setStatus(fmt('Hull closed after %h% pivot(s) — that’s exactly h, the hull size.', { h: hullIdx.length }), 'done');
  document.getElementById('step').disabled = true;
  document.getElementById('wrap').disabled = true;
  console.log('Final hull vertices, in order:', hullIdx.map(i => pts[i]));
}

function setStatus(t, cls){
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + cls;
}

function draw(){
  ctx.clearRect(0,0,W,H);
  // Draw the hull edges confirmed so far.
  if(hullIdx.length > 1){
    ctx.beginPath();
    ctx.moveTo(pts[hullIdx[0]][0], pts[hullIdx[0]][1]);
    for(let i=1;i<hullIdx.length;i++) ctx.lineTo(pts[hullIdx[i]][0], pts[hullIdx[i]][1]);
    if(finished) ctx.closePath();
    ctx.strokeStyle = '#1d3557';
    ctx.lineWidth = 2.5;
    ctx.stroke();
  }
  // Draw the current candidate ray being swept before it locks in.
  if(!finished && hullIdx.length > 0 && candidate >= 0){
    ctx.beginPath();
    ctx.moveTo(pts[hullIdx[hullIdx.length-1]][0], pts[hullIdx[hullIdx.length-1]][1]);
    ctx.lineTo(pts[candidate][0], pts[candidate][1]);
    ctx.strokeStyle = '#e63946';
    ctx.lineWidth = 1.5;
    ctx.setLineDash([4,3]);
    ctx.stroke();
    ctx.setLineDash([]);
  }
  // Draw every point; hull vertices are larger and dark, the start is gold.
  pts.forEach((p, i) => {
    const onHull = hullIdx.includes(i);
    ctx.beginPath();
    ctx.arc(p[0], p[1], onHull ? R+1 : R, 0, Math.PI*2);
    ctx.fillStyle = i === startIdx ? '#e9c46a' : (onHull ? '#1d3557' : '#adb5bd');
    ctx.fill();
    if(onHull || i === startIdx){
      ctx.lineWidth = 1.5;
      ctx.strokeStyle = '#fff';
      ctx.stroke();
    }
  });
}

document.getElementById('step').addEventListener('click', step);
document.getElementById('wrap').addEventListener('click', wrapFully);
document.getElementById('reset').addEventListener('click', () => {
  pts = scatter();
  resetWalk();
  draw();
  setStatus('Press Step to begin wrapping.', '');
});

resetWalk();
draw();
Result
Console

Notice what the ray is doing at every step: for each candidate point it checks whether that point lies clockwise or counter-clockwise of the current best guess, using nothing more than a cross product (no trigonometry, no sorting). The wrap finishes the moment the ray swings back to the anchor. Count the steps it took — that's exactly the number of vertices on the hull, no more, no less.

The Real Complexity

How hard is gift wrapping, really?

  • Each pivot is cheap. To find the next hull point from the current one, scan all nn candidate points and keep whichever is most counter-clockwise, using the sign of a cross product to compare directions. That's an O(n)O(n) scan per pivot.
  • The number of pivots equals hh, the number of vertices on the final hull. So the whole march costs O(n⋅h)O(n \cdot h) — this is the classic gift wrapping / Jarvis march bound (Jarvis, 1973).
  • It's in P, comfortably tractable — but notice the bound depends on two quantities, not just nn. In the worst case h=nh = n (every point sits on the hull) and gift wrapping degrades to O(n2)O(n^{2}), slower than the O(nlog⁡n)O(n \log n) of Graham scan or Andrew's monotone chain. But when hh is small — a handful of extreme points surrounding a dense cloud — gift wrapping can be dramatically faster than sorting everything.
  • This is called an output-sensitive algorithm: its cost scales with the size of what you're computing, not only with the size of what you feed it. Kirkpatrick and Seidel later showed an O(nlog⁡h)O(n \log h) algorithm (the "ultimate convex hull algorithm," 1986) and proved that Ω(nlog⁡h)\Omega(n \log h) is optimal — so gift wrapping's simplicity comes at a real, provable cost when hh grows large, but it is unbeatable in spirit when hh stays small.

The lesson generalizes far beyond geometry: sometimes the right question isn't "how big is the input?" but "how big is the answer?" — and an algorithm tuned to the second can beat one tuned only to the first.

Where It Matters

Gift wrapping's output-sensitive nature makes it the natural choice whenever the hull is expected to be small compared to the input:

  • Collision boundaries in games and physics engines: bounding shapes for clusters of objects are often small polygons wrapped around thousands of vertices, exactly gift wrapping's sweet spot.
  • Higher-dimensional hulls: the same "pivot to the most extreme neighbor" idea generalizes to 3D and beyond, where output-sensitive behavior matters even more because point counts explode.
  • GIS and cartography: tracing the outer boundary of a scattered set of survey points or sensor readings.
  • Teaching computational geometry: because the algorithm mirrors a physical action anyone can picture, it's often the first hull algorithm students implement, before moving on to the faster but less intuitive sweep-based methods.

Understand gift wrapping and you've grasped the core idea behind output-sensitive algorithms — designs that adapt their cost to the size of the answer, a theme that echoes through the wider study of the convex hull and the limits explored across P vs NP.

Conclusion

Gift wrapping turns a childhood-simple physical motion — sweeping a taut ribbon around a scatter of pins — into a rigorous O(nh)O(nh) algorithm for the convex hull. Each pivot asks one honest local question (which point is furthest around?) and answers it with nothing fancier than a cross product.

It won't always be the fastest hull algorithm — when the hull is large, sorting-based methods like Graham scan win outright. But its output-sensitive cost is a small window into a bigger idea: sometimes the smartest algorithm is the one that measures its work against the size of the answer, not just the size of the input.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/gift-wrapping-algorithm/Content licensed under CC BY-NC 4.0.