Introduction to Alpha Shapes

Introduction

Imagine scattering a handful of sand on a table and then asking: what shape are those grains forming? If you draw the tightest shrink-wrap around them, you get the convex hull — a rubber-band outline that ignores every bay and hollow. But the real silhouette could be a crescent, a ring, a star, or something with fingers and holes.

Alpha shapes, introduced by Herbert Edelsbrunner, David Kirkpatrick, and Raimund Seidel in 1983, answer that question with one tunable parameter, $\alpha$ (alpha). Imagine rolling a disk of radius $r = 1/\alpha$ across the outside and inside of the point cloud. Any part of space that the disk can reach without touching a point gets carved away. What remains is the alpha shape.

Set $\alpha = 0$ (infinite disk): nothing gets carved — you recover the full convex hull.
Increase $\alpha$ (shrink the disk): the boundary starts to dip into concavities, revealing bays, peninsulas, and eventually holes.
Increase $\alpha$ far enough: some points become isolated — the shape fragments into individual vertices.

The magic is that a single dial sweeps the full spectrum from "lump" to "skeleton" without any ambiguity. Alpha shapes sit at the heart of computational geometry and are the workhorse behind 3-D printing, molecular surface reconstruction, and geographic boundary estimation.

Try It

Click anywhere on the canvas to add points, then drag the alpha slider. The gray disk shows the rolling ball — wherever a disk of that radius fits without touching a point, the space is carved away.

<div class="controls">
  <label for="alpha-slider">Alpha (α): <span id="alpha-val">0.05</span></label>
  <input type="range" id="alpha-slider" min="0" max="100" value="5" step="1">
  <span class="hint-label" id="shape-label">Convex hull</span>
</div>
<canvas id="canvas" width="460" height="320"></canvas>
<p class="hint">Click on the canvas to add points. Drag the slider to change α — the rolling-disk radius is <b>r = 1/α</b>. At α → 0 the disk is infinite: convex hull. As α grows the boundary tucks into concavities.</p>
<div class="btns">
  <button id="btn-preset" type="button">Load example</button>
  <button id="btn-clear" type="button" class="ghost">Clear</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .4rem; }
label { font-size: .9rem; font-weight: 600; white-space: nowrap; }
input[type=range] { flex: 1; min-width: 120px; max-width: 260px; accent-color: #1d3557; cursor: pointer; }
.hint-label { font-size: .82rem; color: #1d3557; font-weight: 700; min-width: 110px; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; background: #f4f7fa;
         cursor: crosshair; touch-action: none; max-width: 100%; }
.hint { font-size: .84rem; color: #555; margin: .45rem 0; line-height: 1.45; }
.btns { display: flex; gap: .5rem; }
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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Alpha shapes via Delaunay triangulation:
// A triangle/edge belongs to the alpha complex if its circumradius <= 1/alpha.
// At alpha=0 (infinite disk) => convex hull. As alpha grows, boundary tucks in.

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const slider = document.getElementById('alpha-slider');
const alphaVal = document.getElementById('alpha-val');
const shapeLabel = document.getElementById('shape-label');

let pts = [];

// ── Geometry helpers ────────────────────────────────────────────────────────
function circumcircle(ax, ay, bx, by, cx, cy) {
  const dx = bx - ax, dy = by - ay;
  const ex = cx - ax, ey = cy - ay;
  const bl = dx * dx + dy * dy;
  const cl = ex * ex + ey * ey;
  const d = 0.5 / (dx * ey - dy * ex);
  if (Math.abs(d) > 1e9) return null; // degenerate
  const ux = (ey * bl - dy * cl) * d;
  const uy = (dx * cl - ex * bl) * d;
  return { cx: ax + ux, cy: ay + uy, r: Math.sqrt(ux * ux + uy * uy) };
}

function edgeCircumradius(ax, ay, bx, by) {
  // The smallest circle through two points has diameter = distance.
  return Math.sqrt((bx - ax) ** 2 + (by - ay) ** 2) / 2;
}

// ── Bowyer–Watson Delaunay triangulation ────────────────────────────────────
function superTriangle(pts) {
  let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
  for (const [x, y] of pts) {
    if (x < minX) minX = x; if (y < minY) minY = y;
    if (x > maxX) maxX = x; if (y > maxY) maxY = y;
  }
  const dx = maxX - minX, dy = maxY - minY;
  const delta = Math.max(dx, dy) * 10;
  const mx = (minX + maxX) / 2, my = (minY + maxY) / 2;
  return [
    [mx - 20 * delta, my - delta],
    [mx,              my + 20 * delta],
    [mx + 20 * delta, my - delta]
  ];
}

function delaunay(points) {
  if (points.length < 3) return [];
  const st = superTriangle(points);
  const all = [...points, ...st];
  const idx = points.length; // super-triangle vertex indices start here
  let triangles = [[idx, idx + 1, idx + 2]];

  for (let pi = 0; pi < points.length; pi++) {
    const [px, py] = points[pi];
    const badTri = [];
    const polygon = [];

    for (const tri of triangles) {
      const [a, b, c] = tri;
      const cc = circumcircle(all[a][0], all[a][1], all[b][0], all[b][1], all[c][0], all[c][1]);
      if (!cc) continue;
      const dx = px - cc.cx, dy = py - cc.cy;
      if (dx * dx + dy * dy <= cc.r * cc.r + 1e-10) {
        badTri.push(tri);
        polygon.push([a, b], [b, c], [c, a]);
      }
    }

    // Remove bad triangles
    for (const bt of badTri) {
      const i = triangles.indexOf(bt);
      if (i !== -1) triangles.splice(i, 1);
    }

    // Find boundary edges of the polygon hole
    const boundary = polygon.filter(e =>
      polygon.filter(f => (f[0] === e[1] && f[1] === e[0])).length === 0
    );

    for (const [a, b] of boundary) {
      triangles.push([a, b, pi]);
    }
  }

  // Remove triangles that share a vertex with the super-triangle
  return triangles.filter(([a, b, c]) => a < idx && b < idx && c < idx);
}

// ── Alpha shape extraction ───────────────────────────────────────────────────
function alphaShape(pts, alpha) {
  if (pts.length === 0) return { edges: [], triangles: [] };
  if (pts.length === 1) return { edges: [], triangles: [], vertices: [0] };

  const r = alpha <= 0 ? Infinity : 1 / alpha;

  if (pts.length === 2) {
    const d = edgeCircumradius(pts[0][0], pts[0][1], pts[1][0], pts[1][1]);
    return { edges: d <= r ? [[0, 1]] : [], triangles: [] };
  }

  const tris = delaunay(pts);
  const edgeSet = new Set();
  const boundaryEdges = new Map(); // edge -> count of adjacent triangles in alpha complex
  const includedTris = [];

  for (const [a, b, c] of tris) {
    const cc = circumcircle(pts[a][0], pts[a][1], pts[b][0], pts[b][1], pts[c][0], pts[c][1]);
    if (!cc) continue;
    const inComplex = cc.r <= r;
    if (inComplex) {
      includedTris.push([a, b, c]);
      for (const [p, q] of [[a, b], [b, c], [c, a]]) {
        const key = p < q ? p + ',' + q : q + ',' + p;
        boundaryEdges.set(key, (boundaryEdges.get(key) || 0) + 1);
      }
    } else {
      // Try edges of this triangle independently
      for (const [p, q] of [[a, b], [b, c], [c, a]]) {
        const er = edgeCircumradius(pts[p][0], pts[p][1], pts[q][0], pts[q][1]);
        if (er <= r) {
          const key = p < q ? p + ',' + q : q + ',' + p;
          edgeSet.add(key);
        }
      }
    }
  }

  // Boundary edges of alpha complex = edges belonging to exactly one triangle
  const boundary = [];
  for (const [key, count] of boundaryEdges) {
    if (count === 1) boundary.push(key.split(',').map(Number));
  }
  // Add isolated edges
  for (const key of edgeSet) {
    if (!boundaryEdges.has(key)) boundary.push(key.split(',').map(Number));
  }

  return { edges: boundary, triangles: includedTris };
}

// ── Convex hull (for label) ──────────────────────────────────────────────────
function convexHullEdgeCount(pts) {
  if (pts.length < 3) return pts.length;
  // Just need the count for label; use Jarvis march
  let start = 0;
  for (let i = 1; i < pts.length; i++) if (pts[i][0] < pts[start][0]) start = i;
  let current = start, hull = 0;
  do {
    let next = (current + 1) % pts.length;
    for (let i = 0; i < pts.length; i++) {
      const ax = pts[next][0] - pts[current][0], ay = pts[next][1] - pts[current][1];
      const bx = pts[i][0] - pts[current][0], by = pts[i][1] - pts[current][1];
      if (ax * by - ay * bx < 0) next = i;
    }
    current = next; hull++;
  } while (current !== start && hull < pts.length + 1);
  return hull;
}

// ── Rendering ────────────────────────────────────────────────────────────────
function draw() {
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  if (pts.length === 0) {
    ctx.fillStyle = '#aaa';
    ctx.font = '14px system-ui';
    ctx.textAlign = 'center';
    ctx.fillText('Click to add points', W / 2, H / 2);
    return;
  }

  const sliderPct = parseInt(slider.value, 10); // 0..100
  // alpha mapping: 0 -> 0 (convex hull), 100 -> 0.15
  const alpha = sliderPct === 0 ? 0 : sliderPct * 0.0015;
  const r = alpha <= 0 ? Infinity : 1 / alpha;
  alphaVal.textContent = alpha === 0 ? '0 (∞)' : alpha.toFixed(4);

  const shape = alphaShape(pts, alpha);

  // Fill included triangles
  ctx.fillStyle = 'rgba(29,53,87,0.12)';
  for (const [a, b, c] of shape.triangles) {
    ctx.beginPath();
    ctx.moveTo(pts[a][0], pts[a][1]);
    ctx.lineTo(pts[b][0], pts[b][1]);
    ctx.lineTo(pts[c][0], pts[c][1]);
    ctx.closePath();
    ctx.fill();
  }

  // Draw boundary edges
  ctx.strokeStyle = '#1d3557';
  ctx.lineWidth = 2;
  ctx.lineJoin = 'round';
  ctx.lineCap = 'round';
  for (const [a, b] of shape.edges) {
    ctx.beginPath();
    ctx.moveTo(pts[a][0], pts[a][1]);
    ctx.lineTo(pts[b][0], pts[b][1]);
    ctx.stroke();
  }

  // Draw points
  for (const [x, y] of pts) {
    ctx.beginPath();
    ctx.arc(x, y, 4, 0, 2 * Math.PI);
    ctx.fillStyle = '#e63946';
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 1.5;
    ctx.stroke();
  }

  // Rolling disk indicator (top-right, capped for display)
  if (alpha > 0 && r < 200) {
    const dr = Math.min(r, 60);
    ctx.beginPath();
    ctx.arc(W - dr - 10, dr + 10, dr, 0, 2 * Math.PI);
    ctx.strokeStyle = 'rgba(100,160,230,0.55)';
    ctx.lineWidth = 1.5;
    ctx.setLineDash([4, 4]);
    ctx.stroke();
    ctx.setLineDash([]);
  }

  // Label
  const edgeCount = shape.edges.length;
  if (alpha === 0) {
    shapeLabel.textContent = 'Convex hull';
  } else if (edgeCount === 0) {
    shapeLabel.textContent = 'Only vertices';
  } else {
    shapeLabel.textContent = fmt('Alpha complex (%edgeCount% edges)', { edgeCount: edgeCount });
  }
}

// ── Preset example (crescent shape) ─────────────────────────────────────────
function loadPreset() {
  pts = [];
  const W = canvas.width, H = canvas.height;
  // Crescent / C-shape point cloud
  const cx = W * 0.5, cy = H * 0.5;
  const R = 110, r2 = 60;
  for (let a = Math.PI * 0.15; a <= Math.PI * 1.85; a += Math.PI / 14) {
    pts.push([cx + R * Math.cos(a) + (Math.random() - 0.5) * 12,
              cy + R * Math.sin(a) + (Math.random() - 0.5) * 12]);
  }
  for (let a = Math.PI * 0.4; a <= Math.PI * 1.6; a += Math.PI / 10) {
    pts.push([cx + r2 * Math.cos(a) + (Math.random() - 0.5) * 10,
              cy + r2 * Math.sin(a) + (Math.random() - 0.5) * 10]);
  }
  slider.value = 30;
  draw();
}

// ── Events ───────────────────────────────────────────────────────────────────
canvas.addEventListener('click', e => {
  const rect = canvas.getBoundingClientRect();
  const scaleX = canvas.width / rect.width;
  const scaleY = canvas.height / rect.height;
  pts.push([(e.clientX - rect.left) * scaleX, (e.clientY - rect.top) * scaleY]);
  draw();
});

slider.addEventListener('input', draw);
document.getElementById('btn-preset').addEventListener('click', loadPreset);
document.getElementById('btn-clear').addEventListener('click', () => { pts = []; slider.value = 5; draw(); });

loadPreset();

<div class="controls">
  <label for="alpha-slider">Alpha (α): <span id="alpha-val">0.05</span></label>
  <input type="range" id="alpha-slider" min="0" max="100" value="5" step="1">
  <span class="hint-label" id="shape-label">Convex hull</span>
</div>
<canvas id="canvas" width="460" height="320"></canvas>
<p class="hint">Click on the canvas to add points. Drag the slider to change α — the rolling-disk radius is <b>r = 1/α</b>. At α → 0 the disk is infinite: convex hull. As α grows the boundary tucks into concavities.</p>
<div class="btns">
  <button id="btn-preset" type="button">Load example</button>
  <button id="btn-clear" type="button" class="ghost">Clear</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #fff; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .4rem; }
label { font-size: .9rem; font-weight: 600; white-space: nowrap; }
input[type=range] { flex: 1; min-width: 120px; max-width: 260px; accent-color: #1d3557; cursor: pointer; }
.hint-label { font-size: .82rem; color: #1d3557; font-weight: 700; min-width: 110px; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; background: #f4f7fa;
         cursor: crosshair; touch-action: none; max-width: 100%; }
.hint { font-size: .84rem; color: #555; margin: .45rem 0; line-height: 1.45; }
.btns { display: flex; gap: .5rem; }
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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Alpha shapes via Delaunay triangulation:
// A triangle/edge belongs to the alpha complex if its circumradius <= 1/alpha.
// At alpha=0 (infinite disk) => convex hull. As alpha grows, boundary tucks in.

const canvas = document.getElementById('canvas');
const ctx = canvas.getContext('2d');
const slider = document.getElementById('alpha-slider');
const alphaVal = document.getElementById('alpha-val');
const shapeLabel = document.getElementById('shape-label');

let pts = [];

// ── Geometry helpers ────────────────────────────────────────────────────────
function circumcircle(ax, ay, bx, by, cx, cy) {
  const dx = bx - ax, dy = by - ay;
  const ex = cx - ax, ey = cy - ay;
  const bl = dx * dx + dy * dy;
  const cl = ex * ex + ey * ey;
  const d = 0.5 / (dx * ey - dy * ex);
  if (Math.abs(d) > 1e9) return null; // degenerate
  const ux = (ey * bl - dy * cl) * d;
  const uy = (dx * cl - ex * bl) * d;
  return { cx: ax + ux, cy: ay + uy, r: Math.sqrt(ux * ux + uy * uy) };
}

function edgeCircumradius(ax, ay, bx, by) {
  // The smallest circle through two points has diameter = distance.
  return Math.sqrt((bx - ax) ** 2 + (by - ay) ** 2) / 2;
}

// ── Bowyer–Watson Delaunay triangulation ────────────────────────────────────
function superTriangle(pts) {
  let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
  for (const [x, y] of pts) {
    if (x < minX) minX = x; if (y < minY) minY = y;
    if (x > maxX) maxX = x; if (y > maxY) maxY = y;
  }
  const dx = maxX - minX, dy = maxY - minY;
  const delta = Math.max(dx, dy) * 10;
  const mx = (minX + maxX) / 2, my = (minY + maxY) / 2;
  return [
    [mx - 20 * delta, my - delta],
    [mx,              my + 20 * delta],
    [mx + 20 * delta, my - delta]
  ];
}

function delaunay(points) {
  if (points.length < 3) return [];
  const st = superTriangle(points);
  const all = [...points, ...st];
  const idx = points.length; // super-triangle vertex indices start here
  let triangles = [[idx, idx + 1, idx + 2]];

  for (let pi = 0; pi < points.length; pi++) {
    const [px, py] = points[pi];
    const badTri = [];
    const polygon = [];

    for (const tri of triangles) {
      const [a, b, c] = tri;
      const cc = circumcircle(all[a][0], all[a][1], all[b][0], all[b][1], all[c][0], all[c][1]);
      if (!cc) continue;
      const dx = px - cc.cx, dy = py - cc.cy;
      if (dx * dx + dy * dy <= cc.r * cc.r + 1e-10) {
        badTri.push(tri);
        polygon.push([a, b], [b, c], [c, a]);
      }
    }

    // Remove bad triangles
    for (const bt of badTri) {
      const i = triangles.indexOf(bt);
      if (i !== -1) triangles.splice(i, 1);
    }

    // Find boundary edges of the polygon hole
    const boundary = polygon.filter(e =>
      polygon.filter(f => (f[0] === e[1] && f[1] === e[0])).length === 0
    );

    for (const [a, b] of boundary) {
      triangles.push([a, b, pi]);
    }
  }

  // Remove triangles that share a vertex with the super-triangle
  return triangles.filter(([a, b, c]) => a < idx && b < idx && c < idx);
}

// ── Alpha shape extraction ───────────────────────────────────────────────────
function alphaShape(pts, alpha) {
  if (pts.length === 0) return { edges: [], triangles: [] };
  if (pts.length === 1) return { edges: [], triangles: [], vertices: [0] };

  const r = alpha <= 0 ? Infinity : 1 / alpha;

  if (pts.length === 2) {
    const d = edgeCircumradius(pts[0][0], pts[0][1], pts[1][0], pts[1][1]);
    return { edges: d <= r ? [[0, 1]] : [], triangles: [] };
  }

  const tris = delaunay(pts);
  const edgeSet = new Set();
  const boundaryEdges = new Map(); // edge -> count of adjacent triangles in alpha complex
  const includedTris = [];

  for (const [a, b, c] of tris) {
    const cc = circumcircle(pts[a][0], pts[a][1], pts[b][0], pts[b][1], pts[c][0], pts[c][1]);
    if (!cc) continue;
    const inComplex = cc.r <= r;
    if (inComplex) {
      includedTris.push([a, b, c]);
      for (const [p, q] of [[a, b], [b, c], [c, a]]) {
        const key = p < q ? p + ',' + q : q + ',' + p;
        boundaryEdges.set(key, (boundaryEdges.get(key) || 0) + 1);
      }
    } else {
      // Try edges of this triangle independently
      for (const [p, q] of [[a, b], [b, c], [c, a]]) {
        const er = edgeCircumradius(pts[p][0], pts[p][1], pts[q][0], pts[q][1]);
        if (er <= r) {
          const key = p < q ? p + ',' + q : q + ',' + p;
          edgeSet.add(key);
        }
      }
    }
  }

  // Boundary edges of alpha complex = edges belonging to exactly one triangle
  const boundary = [];
  for (const [key, count] of boundaryEdges) {
    if (count === 1) boundary.push(key.split(',').map(Number));
  }
  // Add isolated edges
  for (const key of edgeSet) {
    if (!boundaryEdges.has(key)) boundary.push(key.split(',').map(Number));
  }

  return { edges: boundary, triangles: includedTris };
}

// ── Convex hull (for label) ──────────────────────────────────────────────────
function convexHullEdgeCount(pts) {
  if (pts.length < 3) return pts.length;
  // Just need the count for label; use Jarvis march
  let start = 0;
  for (let i = 1; i < pts.length; i++) if (pts[i][0] < pts[start][0]) start = i;
  let current = start, hull = 0;
  do {
    let next = (current + 1) % pts.length;
    for (let i = 0; i < pts.length; i++) {
      const ax = pts[next][0] - pts[current][0], ay = pts[next][1] - pts[current][1];
      const bx = pts[i][0] - pts[current][0], by = pts[i][1] - pts[current][1];
      if (ax * by - ay * bx < 0) next = i;
    }
    current = next; hull++;
  } while (current !== start && hull < pts.length + 1);
  return hull;
}

// ── Rendering ────────────────────────────────────────────────────────────────
function draw() {
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  if (pts.length === 0) {
    ctx.fillStyle = '#aaa';
    ctx.font = '14px system-ui';
    ctx.textAlign = 'center';
    ctx.fillText('Click to add points', W / 2, H / 2);
    return;
  }

  const sliderPct = parseInt(slider.value, 10); // 0..100
  // alpha mapping: 0 -> 0 (convex hull), 100 -> 0.15
  const alpha = sliderPct === 0 ? 0 : sliderPct * 0.0015;
  const r = alpha <= 0 ? Infinity : 1 / alpha;
  alphaVal.textContent = alpha === 0 ? '0 (∞)' : alpha.toFixed(4);

  const shape = alphaShape(pts, alpha);

  // Fill included triangles
  ctx.fillStyle = 'rgba(29,53,87,0.12)';
  for (const [a, b, c] of shape.triangles) {
    ctx.beginPath();
    ctx.moveTo(pts[a][0], pts[a][1]);
    ctx.lineTo(pts[b][0], pts[b][1]);
    ctx.lineTo(pts[c][0], pts[c][1]);
    ctx.closePath();
    ctx.fill();
  }

  // Draw boundary edges
  ctx.strokeStyle = '#1d3557';
  ctx.lineWidth = 2;
  ctx.lineJoin = 'round';
  ctx.lineCap = 'round';
  for (const [a, b] of shape.edges) {
    ctx.beginPath();
    ctx.moveTo(pts[a][0], pts[a][1]);
    ctx.lineTo(pts[b][0], pts[b][1]);
    ctx.stroke();
  }

  // Draw points
  for (const [x, y] of pts) {
    ctx.beginPath();
    ctx.arc(x, y, 4, 0, 2 * Math.PI);
    ctx.fillStyle = '#e63946';
    ctx.fill();
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 1.5;
    ctx.stroke();
  }

  // Rolling disk indicator (top-right, capped for display)
  if (alpha > 0 && r < 200) {
    const dr = Math.min(r, 60);
    ctx.beginPath();
    ctx.arc(W - dr - 10, dr + 10, dr, 0, 2 * Math.PI);
    ctx.strokeStyle = 'rgba(100,160,230,0.55)';
    ctx.lineWidth = 1.5;
    ctx.setLineDash([4, 4]);
    ctx.stroke();
    ctx.setLineDash([]);
  }

  // Label
  const edgeCount = shape.edges.length;
  if (alpha === 0) {
    shapeLabel.textContent = 'Convex hull';
  } else if (edgeCount === 0) {
    shapeLabel.textContent = 'Only vertices';
  } else {
    shapeLabel.textContent = fmt('Alpha complex (%edgeCount% edges)', { edgeCount: edgeCount });
  }
}

// ── Preset example (crescent shape) ─────────────────────────────────────────
function loadPreset() {
  pts = [];
  const W = canvas.width, H = canvas.height;
  // Crescent / C-shape point cloud
  const cx = W * 0.5, cy = H * 0.5;
  const R = 110, r2 = 60;
  for (let a = Math.PI * 0.15; a <= Math.PI * 1.85; a += Math.PI / 14) {
    pts.push([cx + R * Math.cos(a) + (Math.random() - 0.5) * 12,
              cy + R * Math.sin(a) + (Math.random() - 0.5) * 12]);
  }
  for (let a = Math.PI * 0.4; a <= Math.PI * 1.6; a += Math.PI / 10) {
    pts.push([cx + r2 * Math.cos(a) + (Math.random() - 0.5) * 10,
              cy + r2 * Math.sin(a) + (Math.random() - 0.5) * 10]);
  }
  slider.value = 30;
  draw();
}

// ── Events ───────────────────────────────────────────────────────────────────
canvas.addEventListener('click', e => {
  const rect = canvas.getBoundingClientRect();
  const scaleX = canvas.width / rect.width;
  const scaleY = canvas.height / rect.height;
  pts.push([(e.clientX - rect.left) * scaleX, (e.clientY - rect.top) * scaleY]);
  draw();
});

slider.addEventListener('input', draw);
document.getElementById('btn-preset').addEventListener('click', loadPreset);
document.getElementById('btn-clear').addEventListener('click', () => { pts = []; slider.value = 5; draw(); });

loadPreset();

Result

Console

Notice the key transitions. When alpha is very small the disk is huge and nothing gets carved — you see the convex hull. As alpha grows the boundary tucks into concavities. Past a critical value the shape may split, and at very high alpha only the points themselves remain. The same cloud, endlessly different readings depending on the scale of the probe.

The Real Complexity

Computing alpha shapes looks expensive — you must decide, for every possible disk position, whether it can slip between the points. In practice the algorithm is elegant and provably optimal.

The key insight: the Delaunay triangulation. For a fixed set of n points, the Delaunay triangulation partitions the plane into triangles so that no point lies inside any triangle's circumcircle. This structure encodes all alpha shapes simultaneously:

A triangle (face) belongs to the alpha shape if and only if its circumradius $\le 1/\alpha$ .
An edge belongs if its circumradius $\le 1/\alpha$ (the circumcircle of the two-point "Gabriel circle").
A vertex always belongs (for any finite $\alpha$ ).

So the full algorithm is:

Build the Delaunay triangulation: $O(n \log n)$ — optimal for comparison-based planar geometry.
For each simplex (vertex, edge, triangle), record its circumradius.
For any query $\alpha$ , filter to simplices with circumradius $\le 1/\alpha$ : $O(n)$ .

The result is the alpha complex — a subcomplex of the Delaunay triangulation — whose boundary is the alpha shape. This construction was proven correct and optimal by Edelsbrunner, Kirkpatrick & Seidel (1983), making alpha shapes a solved problem in computational geometry.

The related alpha-hull concept generalises to higher dimensions, where the Delaunay structure remains the backbone and the complexity stays $O(n^{\lceil d/2 \rceil})$ in $d$ dimensions — polynomial but growing fast.

Where It Matters

The ability to recover a shape's true boundary from scattered samples shows up everywhere:

3-D surface reconstruction: laser scanners and photogrammetry produce raw point clouds. Alpha shapes turn millions of unordered points into a watertight mesh for 3-D printing or game assets.
Molecular biology: the solvent-accessible surface of a protein is exactly the boundary swept by a water-molecule-sized ball rolling over the van der Waals radii of atoms — the Connolly surface is an alpha shape.
LiDAR and autonomous vehicles: street-level point clouds are filtered into road surfaces, building outlines, and tree canopies using alpha-shape extraction at different radii.
Geographic information systems (GIS): given GPS tracks or field measurements, alpha shapes give a non-convex polygon boundary of the surveyed region — far more accurate than a convex hull for elongated coastlines or archipelagos.
Computer graphics and collision detection: alpha shapes identify the concave hull of a 2-D sprite or a 3-D character, enabling tighter bounding volumes and faster collision queries than axis-aligned boxes.
Outlier detection: points that belong to the alpha complex only at very high alpha values are geometrically isolated — natural candidates for flagging as noise or anomalies.

Wherever you have samples and need a boundary, alpha shapes let you tune how much boundary you want — from the coarsest enclosure to the finest detail the data supports.

Conclusion

Alpha shapes give a beautiful answer to a deceptively hard question: what shape is this cloud of points? By rolling a disk of tunable radius and carving away anything the disk can reach, they sweep the full range from convex hull to fine skeleton with a single dial.

The Delaunay triangulation makes the computation optimal — build the structure once in $O(n \log n)$ , then answer any alpha query in $O(n)$ . That combination of geometric elegance and computational efficiency is why alpha shapes, invented in 1983, remain the standard tool for surface reconstruction four decades later.

Next time you see a 3-D printed object or a protein structure viewer, there's a good chance an alpha shape — and one carefully chosen radius — decided exactly where the boundary lies.

Comments

Loading comments...

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

Cookies & privacy

Alpha Shapes

How a rolling disk reveals what a cloud of points really looks like