Introduction

Every time a video game character lands on a platform, a car crumples in a crash simulation, or a robot arm avoids a wall, a question has to be answered in microseconds: do these two objects overlap?

The naive answer โ€” sample thousands of points and check whether any lie inside both objects โ€” is far too slow for real time. The clever answer, found by Elmer Gilbert, Daniel Johnson, and S. Sathiya Keerthi in 1988, reduces the whole question to a single geometric fact:

Two convex shapes overlap if and only if their Minkowski difference contains the origin.

The GJK algorithm (named for its three inventors) exploits that fact by building a small simplex โ€” a triangle in 2-D, a tetrahedron in 3-D โ€” that tries to enclose the origin inside the Minkowski difference. It converges in a handful of steps, touching at most a few support points per iteration, making it one of the fastest collision tests known.

Like closest-pair or convex-hull algorithms, GJK belongs to the world of computational geometry: problems where the answer is proven to exist and the challenge is finding it as cheaply as possible.

Try It

Drag the blue shape toward the orange one. The algorithm runs on every mouse move and reports whether the shapes are Separate or Colliding, colouring the canvas accordingly.

<div class="hint">Drag the <b>blue</b> shape toward the <b>orange</b> one. GJK runs on every move and reports whether the shapes are separate or colliding.</div>
<canvas id="c" width="480" height="320"></canvas>
<div id="status" class="status">โœ“ Separate</div>
<div class="btns">
  <button id="reset" type="button">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 10px; cursor: grab; background: #f6f8fa; max-width: 100%; touch-action: none; }
canvas.dragging { cursor: grabbing; }
.status { font: 700 1.05rem system-ui; margin: .6rem 0 .5rem; padding: .35rem .8rem; display: inline-block; border-radius: 6px; }
.status.sep  { background: #e8f5e9; color: #1b5e20; }
.status.col  { background: #ffebee; color: #b71c1c; }
button { font: 600 14px system-ui; padding: .4rem .9rem; background: #1d3557; color: #fff; border: none; border-radius: 8px; cursor: pointer; }
.btns { margin-top: .3rem; }

// โ”€โ”€ GJK collision detection demo โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Two convex polygons; the blue one is draggable.
// GJK tests whether their Minkowski difference contains the origin.
// We use the standard 2-D GJK loop with a simplex of up to 3 points.

const canvas = document.getElementById('c');
const ctx = canvas.getContext('2d');
const statusEl = document.getElementById('status');

// โ”€โ”€ shapes โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Vertices are LOCAL (centered at origin); position is a separate offset.
function hexagon(r) {
  const pts = [];
  for (let i = 0; i < 6; i++) {
    const a = (Math.PI / 3) * i - Math.PI / 6;
    pts.push([r * Math.cos(a), r * Math.sin(a)]);
  }
  return pts;
}
function pentagon(r) {
  const pts = [];
  for (let i = 0; i < 5; i++) {
    const a = (2 * Math.PI / 5) * i - Math.PI / 2;
    pts.push([r * Math.cos(a), r * Math.sin(a)]);
  }
  return pts;
}

const BLUE = { verts: hexagon(62), pos: [130, 160], color: '#3b82f6', fill: '#bfdbfe' };
const ORANGE = { verts: pentagon(58), pos: [340, 160], color: '#f97316', fill: '#fed7aa' };
const BLUE_RESET = [130, 160];

// โ”€โ”€ math helpers โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function add(a, b) { return [a[0]+b[0], a[1]+b[1]]; }
function sub(a, b) { return [a[0]-b[0], a[1]-b[1]]; }
function dot(a, b) { return a[0]*b[0] + a[1]*b[1]; }
function neg(a)    { return [-a[0], -a[1]]; }
// Triple product: (Aร—B)ร—C = B*(AยทC) - A*(BยทC) for 2D perpendicular-to-AB toward C
function tripleProduct(a, b, c) {
  const ac = dot(a, c), bc = dot(b, c);
  return [b[0]*ac - a[0]*bc, b[1]*ac - a[1]*bc];
}
// Perpendicular to v, pointing toward a reference point
function perpToward(v, toward) {
  const p = [-v[1], v[0]];
  return dot(p, toward) >= 0 ? p : [-p[0], -p[1]];
}

// โ”€โ”€ support function โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Returns the vertex of shape (local verts + offset pos) furthest in direction d.
function support(shape, d) {
  let best = -Infinity, bv = null;
  for (const v of shape.verts) {
    const w = add(v, shape.pos);
    const s = dot(w, d);
    if (s > best) { best = s; bv = w; }
  }
  return bv;
}
// Minkowski difference support: support of A in d minus support of B in -d
function minkSupport(A, B, d) {
  return sub(support(A, d), support(B, neg(d)));
}

// โ”€โ”€ GJK algorithm โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// Returns true if A and B overlap.
function gjk(A, B) {
  let d = sub(B.pos, A.pos);              // initial direction: Aโ†’B
  if (d[0] === 0 && d[1] === 0) d = [1, 0];

  let simplex = [];
  let a = minkSupport(A, B, d);
  simplex.push(a);
  d = neg(a);                              // toward origin

  for (let iter = 0; iter < 32; iter++) {
    a = minkSupport(A, B, d);
    if (dot(a, d) < 0) return false;       // origin is beyond the support โ€” no overlap
    simplex.push(a);

    const result = doSimplex(simplex, d);
    d = result.dir;
    if (result.containsOrigin) return true;
    simplex = result.simplex;
  }
  return false;
}

// โ”€โ”€ simplex nearest-feature update โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function doSimplex(simplex, dir) {
  if (simplex.length === 2) return lineCase(simplex);
  return triangleCase(simplex);
}

function lineCase(simplex) {
  // simplex = [B, A]  (A is newest)
  const [B, A] = simplex;
  const AB = sub(B, A);
  const AO = neg(A);
  if (dot(AB, AO) > 0) {
    // origin is in the region of edge AB
    return { simplex, dir: tripleProduct(AB, AO, AB), containsOrigin: false };
  }
  // origin closest to A alone
  return { simplex: [A], dir: AO, containsOrigin: false };
}

function triangleCase(simplex) {
  // simplex = [C, B, A] (A is newest)
  const [C, B, A] = simplex;
  const AB = sub(B, A), AC = sub(C, A), AO = neg(A);
  const ABperp = tripleProduct(AC, AB, AB);
  const ACperp = tripleProduct(AB, AC, AC);
  if (dot(ABperp, AO) > 0) {
    // outside edge AB
    return { simplex: [B, A], dir: ABperp, containsOrigin: false };
  }
  if (dot(ACperp, AO) > 0) {
    // outside edge AC
    return { simplex: [C, A], dir: ACperp, containsOrigin: false };
  }
  // origin is inside the triangle
  return { simplex, dir: [0,0], containsOrigin: true };
}

// โ”€โ”€ drawing โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
function drawShape(shape, colliding) {
  const verts = shape.verts.map(v => add(v, shape.pos));
  ctx.beginPath();
  ctx.moveTo(verts[0][0], verts[0][1]);
  for (let i = 1; i < verts.length; i++) ctx.lineTo(verts[i][0], verts[i][1]);
  ctx.closePath();
  ctx.fillStyle = colliding ? (shape === BLUE ? '#93c5fd' : '#fdba74') : shape.fill;
  ctx.fill();
  ctx.strokeStyle = colliding ? (shape === BLUE ? '#1d4ed8' : '#c2410c') : shape.color;
  ctx.lineWidth = 2.2;
  ctx.stroke();
}

function render() {
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);
  const colliding = gjk(BLUE, ORANGE);
  drawShape(BLUE, colliding);
  drawShape(ORANGE, colliding);

  if (colliding) {
    statusEl.textContent = 'โšก Colliding';
    statusEl.className = 'status col';
  } else {
    statusEl.textContent = 'โœ“ Separate';
    statusEl.className = 'status sep';
  }
}

// โ”€โ”€ drag interaction โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
let dragging = false, dragStart = null, posStart = null;

function canvasXY(e) {
  const r = canvas.getBoundingClientRect();
  const scaleX = canvas.width / r.width;
  const scaleY = canvas.height / r.height;
  const cx = (e.clientX ?? e.touches[0].clientX) - r.left;
  const cy = (e.clientY ?? e.touches[0].clientY) - r.top;
  return [cx * scaleX, cy * scaleY];
}
function insideShape(shape, px, py) {
  // Point-in-convex-polygon via cross product winding
  const verts = shape.verts.map(v => add(v, shape.pos));
  for (let i = 0; i < verts.length; i++) {
    const a = verts[i], b = verts[(i+1) % verts.length];
    const cross = (b[0]-a[0])*(py-a[1]) - (b[1]-a[1])*(px-a[0]);
    if (cross < 0) return false;
  }
  return true;
}
canvas.addEventListener('pointerdown', e => {
  const [px, py] = canvasXY(e);
  if (insideShape(BLUE, px, py)) {
    dragging = true;
    dragStart = [px, py];
    posStart = [...BLUE.pos];
    canvas.classList.add('dragging');
    canvas.setPointerCapture(e.pointerId);
  }
});
canvas.addEventListener('pointermove', e => {
  if (!dragging) return;
  const [px, py] = canvasXY(e);
  BLUE.pos = [posStart[0] + px - dragStart[0], posStart[1] + py - dragStart[1]];
  render();
});
canvas.addEventListener('pointerup', () => { dragging = false; canvas.classList.remove('dragging'); });
canvas.addEventListener('pointercancel', () => { dragging = false; canvas.classList.remove('dragging'); });

document.getElementById('reset').addEventListener('click', () => {
  BLUE.pos = [...BLUE_RESET];
  render();
});

render();

// โ”€โ”€ Node.js verification (console only) โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€โ”€
// When run under node, check core GJK logic without DOM.
if (typeof window === 'undefined') {
  // Reconstruct minimal helpers
  const _add=(a,b)=>[a[0]+b[0],a[1]+b[1]],_sub=(a,b)=>[a[0]-b[0],a[1]-b[1]],_dot=(a,b)=>a[0]*b[0]+a[1]*b[1],_neg=a=>[-a[0],-a[1]],_tri=(a,b,c)=>{const ac=_dot(a,c),bc=_dot(b,c);return[b[0]*ac-a[0]*bc,b[1]*ac-a[1]*bc]};
  const _sup=(sh,d)=>{let best=-Infinity,bv=null;for(const v of sh.verts){const w=_add(v,sh.pos),s=_dot(w,d);if(s>best){best=s;bv=w;}}return bv;};
  const _mink=(A,B,d)=>_sub(_sup(A,d),_sup(B,_neg(d)));
  function _lineCase(s){const[B,A]=s,AB=_sub(B,A),AO=_neg(A);if(_dot(AB,AO)>0)return{simplex:s,dir:_tri(AB,AO,AB),containsOrigin:false};return{simplex:[A],dir:AO,containsOrigin:false};}
  function _triCase(s){const[C,B,A]=s,AB=_sub(B,A),AC=_sub(C,A),AO=_neg(A),ABp=_tri(AC,AB,AB),ACp=_tri(AB,AC,AC);if(_dot(ABp,AO)>0)return{simplex:[B,A],dir:ABp,containsOrigin:false};if(_dot(ACp,AO)>0)return{simplex:[C,A],dir:ACp,containsOrigin:false};return{simplex:s,dir:[0,0],containsOrigin:true};}
  function _gjk(A,B){let d=_sub(B.pos,A.pos);if(!d[0]&&!d[1])d=[1,0];let simplex=[],a=_mink(A,B,d);simplex.push(a);d=_neg(a);for(let i=0;i<32;i++){a=_mink(A,B,d);if(_dot(a,d)<0)return false;simplex.push(a);const r=simplex.length===2?_lineCase(simplex):_triCase(simplex);d=r.dir;if(r.containsOrigin)return true;simplex=r.simplex;}return false;}
  function _hex(r){const p=[];for(let i=0;i<6;i++){const a=(Math.PI/3)*i-Math.PI/6;p.push([r*Math.cos(a),r*Math.sin(a)]);}return p;}
  function _pent(r){const p=[];for(let i=0;i<5;i++){const a=(2*Math.PI/5)*i-Math.PI/2;p.push([r*Math.cos(a),r*Math.sin(a)]);}return p;}
  const A={verts:_hex(62),pos:[130,160]},B={verts:_pent(58),pos:[340,160]};
  // Test 1: shapes far apart (distance=210, hex+pent radii~120) โ€” should NOT collide
  const farApart=_gjk(A,B); console.assert(!farApart,'shapes far apart should NOT collide');
  // Test 2: deeply overlapping (distance=100, well inside both radii) โ€” SHOULD collide
  A.pos=[240,160];
  const deepOverlap=_gjk(A,B); console.assert(deepOverlap,'shapes deeply overlapping SHOULD collide');
  // Test 3: significantly overlapping (distance=50) โ€” SHOULD collide
  A.pos=[290,160];
  const overlapping=_gjk(A,B); console.assert(overlapping,'shapes overlapping SHOULD collide');
  // Test 4: same position (distance=0) โ€” SHOULD collide
  A.pos=[340,160];
  const samePos=_gjk(A,B); console.assert(samePos,'shapes at same position SHOULD collide');
  // Test 5: clearly separated (distance=200) โ€” should NOT collide
  A.pos=[140,160];
  const justSep=_gjk(A,B); console.assert(!justSep,'shapes clearly separated should NOT collide');
  console.log('All GJK assertions passed.');
}
Result
Console

The key insight is that GJK never iterates over interior points. It only ever calls the support function โ€” "which vertex of this shape is furthest in direction d?" โ€” and builds a simplex from those extreme vertices in the Minkowski difference. When the simplex can no longer grow toward the origin the test terminates, usually in two or three iterations.

The Real Complexity

GJK is a solved algorithm โ€” it always terminates with the correct answer for convex shapes. Its performance story is striking:

  • Support function calls per iteration: exactly one per shape, so two total. Each call scans the shape's vertices once: O(n)O(n) for a polygon with n vertices, O(1)O(1) for a circle or capsule with a closed-form support.
  • Number of iterations: in practice one to four for well-separated shapes. In the worst case, O(n)O(n) iterations are possible for degenerate configurations, but this is rarely seen in games.
  • Overall cost: roughly O(n)O(n) support-function evaluations per query, and for smooth convex bodies (spheres, capsules) it is effectively O(1)O(1).
  • Limitation: GJK only works on convex shapes. Non-convex meshes must first be decomposed into convex pieces โ€” a hard preprocessing step โ€” before GJK can be applied to each piece.

The Minkowski difference itself has O(nโ‹…m)O(n \cdot m) vertices (n and m are the vertex counts of each shape), but GJK never constructs it explicitly. That implicit treatment is the algorithmic magic: a potentially enormous object is navigated using only its support function, keeping memory and time lean.

Compare this to testing every triangle pair between two meshes: O(nโ‹…m)O(n \cdot m) with large constants. GJK is why modern physics engines can handle hundreds of collisions per frame.

Where It Matters

GJK is one of the few algorithms that went straight from a research paper to production use in virtually every real-time physics system:

  • Game physics engines: Bullet, PhysX, Havok, and Box2D all use GJK (or its extension EPA for penetration depth) at their collision-detection core. Every platform game, racing sim, and fighting game relies on it running thousands of times per frame.
  • Robotics motion planning: checking whether a robot link collides with an obstacle is a continuous stream of convex-vs-convex queries. Libraries like FCL (Flexible Collision Library) wrap GJK for this purpose.
  • CAD and engineering simulation: interference checking between mechanical parts โ€” does this bolt thread clear the housing? โ€” uses the same convex-decomposition + GJK pipeline.
  • Medical simulation: virtual surgery tools that must feel realistic to trainees need haptic-speed (>1 kHz) collision feedback; GJK's low constant makes that feasible.
  • Animation and cloth: broad-phase collision detection in cloth and hair simulation uses bounding-volume hierarchies of ellipsoids, with GJK at the leaf level.

The extension EPA (Expanding Polytope Algorithm, by Gino van den Bergen, 2001) builds on GJK to compute the exact penetration depth and contact normal once a collision is confirmed โ€” completing the information needed to resolve the collision with an impulse response.

Conclusion

GJK is a beautiful example of an algorithm that wins by changing the question. Instead of asking "do any points of A lie inside B?", it asks "does the Minkowski difference AโŠ–B contain the origin?" โ€” and then answers that by building a tiny simplex one support point at a time.

The result is an O(1)O(1)-to-O(n)O(n) algorithm that works in any number of dimensions, handles every convex shape through a single abstraction (the support function), and has remained the industry standard for almost four decades. When your game character lands safely on a ledge, it is this 1988 idea โ€” turned into a handful of dot products and a simplex update โ€” that made it happen.

For shapes beyond convex, the next challenge is convex decomposition: splitting an arbitrary mesh into pieces GJK can handle. That is a harder, open-research problem โ€” a reminder that even elegant solved algorithms leave interesting questions just past their boundary.

Share this article

Pick a channel โ€” or use your device's native share sheet.

Comments

Loading comments...

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