Introduction

Imagine a building footprint — a polygon drawn on the ground. Now push every wall inward at the same speed, like a slow flood pressing in from all sides at once. The corners of the polygon must move too, and they trace straight-line paths as the walls advance.

When two walls eventually meet, they annihilate each other and the boundary shrinks further, until the whole polygon has collapsed to a single point (or a few isolated points for complex shapes). The union of all those corner paths is the straight skeleton of the polygon.

The concept was introduced in 1995 by Oswin Aichholzer and Franz Aurenhammer, and it immediately explained something architects had been drawing by hand for centuries: the hip roof. The ridges and valleys of a hip roof that sits over any floor plan are exactly the edges of the straight skeleton of that plan.

Unlike the more common Voronoi diagram (which uses circular wavefronts), the straight skeleton uses straight-edge wavefronts. That single difference produces a simpler, more roof-like result — but it also hides a subtle algorithmic challenge.

Try It: Build a Hip Roof

Choose a building footprint from the presets below, then press Run to watch the inward wavefront advance step by step. The colored lines that accumulate are the straight skeleton — the ridge and valley lines of the hip roof.

<!-- Straight skeleton demo — canvas animation of inward-offset wavefront -->
<p class="hint">Each edge of the building footprint moves inward at constant speed. The paths traced by the corners are the <b>straight skeleton</b> — the ridge and valley lines of the hip roof above.</p>
<div class="controls">
  <label for="preset-select">Footprint:</label>
  <select id="preset-select">
    <option value="rectangle">Rectangle</option>
    <option value="lshape">L-shape</option>
    <option value="pentagon">Pentagon</option>
    <option value="tshape">T-shape</option>
  </select>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>
<canvas id="canvas" width="440" height="310"></canvas>
<div id="status" class="status"></div>

/* Layout: hint text, preset selector, canvas, status line */
* { 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; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; margin-bottom: .6rem; }
label { font-size: .85rem; color: #555; }
select { font: 14px system-ui, sans-serif; padding: .3rem .5rem; border: 1px solid #b0b8c4; border-radius: 6px; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 8px; background: #f5f8fb; }
.status { font-size: .9rem; font-weight: 600; margin-top: .5rem; min-height: 1.4em; color: #1d3557; }

// Straight skeleton via iterated inward polygon offset (simplified, visual)
// Each vertex moves along its angle bisector direction — the key insight

// Preset footprint polygons (pixel coords, CCW winding)
const PRESETS = {
  rectangle: [[60,240],[380,240],[380,60],[60,60]],
  lshape:    [[60,240],[240,240],[240,160],[380,160],[380,60],[60,60]],
  pentagon:  [[220,50],[380,160],[320,260],[120,260],[60,160]],
  tshape:    [[60,100],[380,100],[380,170],[260,170],[260,270],[180,270],[180,170],[60,170]]
};

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

let animId = null;
let skeletonEdges = [];
let footprintPoly = [];

// 2D vector helpers
function sub(a,b){ return {x:a.x-b.x, y:a.y-b.y}; }
function add(a,b){ return {x:a.x+b.x, y:a.y+b.y}; }
function scale(v,t){ return {x:v.x*t, y:v.y*t}; }
function len(v){ return Math.sqrt(v.x*v.x+v.y*v.y); }
function norm(v){ const l=len(v); return l<1e-9?{x:0,y:0}:{x:v.x/l,y:v.y/l}; }
function perp(v){ return {x:v.y,y:-v.x}; } // right-hand perpendicular (inward normal for CW polygon in canvas y-down coords)

// Compute the inward bisector direction at vertex curr
function bisectorDir(prev, curr, next){
  const d1 = norm(sub(curr, prev));
  const d2 = norm(sub(next, curr));
  const n1 = perp(d1); // right-hand perpendicular = inward normal for CW winding in canvas coords
  const n2 = perp(d2);
  const bis = norm(add(n1, n2));
  return bis;
}

// Offset every vertex of poly inward by distance t
function offsetPolygon(poly, t){
  const n = poly.length;
  const out = [];
  for(let i=0;i<n;i++){
    const prev = poly[(i-1+n)%n];
    const curr = poly[i];
    const next = poly[(i+1)%n];
    const dir = bisectorDir(prev, curr, next);
    out.push(add(curr, scale(dir, t)));
  }
  return out;
}

// Canvas drawing helpers
function drawPoly(poly, color, lineWidth){
  if(poly.length < 2) return;
  ctx.beginPath();
  ctx.moveTo(poly[0].x, poly[0].y);
  for(let i=1;i<poly.length;i++) ctx.lineTo(poly[i].x, poly[i].y);
  ctx.closePath();
  ctx.strokeStyle = color;
  ctx.lineWidth = lineWidth;
  ctx.stroke();
}

function drawSegment(a, b, color, lineWidth){
  ctx.beginPath();
  ctx.moveTo(a.x, a.y);
  ctx.lineTo(b.x, b.y);
  ctx.strokeStyle = color;
  ctx.lineWidth = lineWidth;
  ctx.stroke();
}

// Stop animation when polygon has collapsed (near-zero area)
function polyArea(poly){
  let a=0;
  const n=poly.length;
  for(let i=0;i<n;i++){
    const j=(i+1)%n;
    a += poly[i].x*poly[j].y - poly[j].x*poly[i].y;
  }
  return Math.abs(a)/2;
}

function resetAnim(){
  if(animId){ cancelAnimationFrame(animId); animId=null; }
}

function getSelectedPoly(){
  const key = document.getElementById('preset-select').value;
  return PRESETS[key].map(([x,y])=>({x,y}));
}

function drawScene(poly, t, edges){
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  // draw accumulated skeleton edges
  for(const e of edges){
    const hue = (e.idx * 47) % 360;
    drawSegment(e.a, e.b, `hsl(${hue},70%,45%)`, 1.8);
  }
  // draw current wavefront polygon
  if(poly.length >= 3) drawPoly(poly, '#1d3557', 2);
  // draw original footprint (faint)
  drawPoly(footprintPoly, '#9fb2c8', 1);
}

function runAnimation(){
  resetAnim();
  footprintPoly = getSelectedPoly();
  skeletonEdges = [];
  statusEl.textContent = '';

  let poly = footprintPoly.map(p=>({...p}));
  let t = 0;
  const STEP = 1.5;
  const MAX_T = 280;
  let idx = 0;

  function step(){
    if(t > MAX_T || polyArea(poly) < 10){
      drawScene([], t, skeletonEdges);
      statusEl.textContent = 'Skeleton complete — these are the roof ridge lines.';
      return;
    }
    const prevPoly = poly.map(p=>({...p}));
    const nextPoly = offsetPolygon(poly, STEP);
    // record skeleton edge for each vertex path segment
    for(let i=0;i<prevPoly.length;i++){
      skeletonEdges.push({a: prevPoly[i], b: nextPoly[i], idx: idx++});
    }
    poly = nextPoly;
    t += STEP;
    drawScene(poly, t, skeletonEdges);
    animId = requestAnimationFrame(step);
  }
  step();
}

document.getElementById('btn-run').addEventListener('click', runAnimation);
document.getElementById('btn-reset').addEventListener('click', ()=>{
  resetAnim();
  skeletonEdges = [];
  footprintPoly = getSelectedPoly();
  ctx.clearRect(0, 0, canvas.width, canvas.height);
  drawPoly(footprintPoly, '#1d3557', 2);
  statusEl.textContent = 'Press Run to animate the wavefront.';
});

// Draw initial footprint on load
footprintPoly = getSelectedPoly();
drawPoly(footprintPoly, '#1d3557', 2);
Result
Console

Each edge of the skeleton is the bisector of two adjacent walls. When a vertex event occurs (two walls meet and one vanishes), a new bisector starts. The final peak where all remaining walls collapse to a point is the roof's highest ridge. Pause at any moment to measure the slope: every ridge rises at exactly 45° above the floor plan.

The Real Complexity

The shrinking-polygon picture feels almost too simple. So how hard is it to compute?

  • The straight-line bisector idea is clean. Each interior angle contributes a bisector ray. Events happen when two advancing edges collide, and the algorithm just has to process those events in order.
  • Reflex vertices complicate everything. When a polygon has a reflex vertex (an inward corner, angle >180°> 180°), its bisector ray points outward and can create a split event — a single edge splits into two sub-edges, spawning a new vertex. Split events are harder to predict and handle than simple vertex collapses.
  • The naive algorithm is O(n2)O(n^2). For a polygon with nn vertices, a straightforward event-queue approach may process O(n2)O(n^2) events in the worst case, because each split event can cascade.
  • O(nlog⁡n)O(n \log n) is achievable. Felkel and Obdrzalek (1998) gave the first practical O(nlog⁡n)O(n \log n) algorithm for simple polygons. For polygons with holes or degenerate configurations, the analysis becomes more involved, and robust implementations require careful handling of near-parallel edges and coincident events.
  • Open problems remain. No algorithm is known to compute straight skeletons of general (non-simple, multiply-connected) polygons in o(n2)o(n^2) time in the worst case, and the problem shares DNA with computational geometry challenges where precision arithmetic is critical.

The contrast with the Voronoi diagram is instructive: Voronoi diagrams of point sets are well-solved in O(nlog⁡n)O(n \log n), but straight skeletons — despite looking similar — required separate, more recent work to reach the same asymptotic bound.

Where It Matters

Once you see the shrinking-polygon idea, you spot it everywhere:

  • Architecture — hip roofs: every traditional hip roof over an irregular floor plan has ridges and valleys that follow the straight skeleton exactly. Architects have always drawn them by hand; software now computes them instantly.
  • Terrain and map generalisation: shrinking a coastline or a contour polygon inward models how a landmass erodes or a lake grows. The skeleton captures the "axis" of the shape.
  • Font and shape offsetting: generating parallel curves around letters and logos — used in engraving, laser cutting and CNC machining — uses the straight skeleton to handle the corners correctly.
  • Urban planning: finding the locus of points equidistant from all surrounding streets, or computing setback lines for construction regulations, is a straight-skeleton computation.
  • Motion planning: a robot navigating the interior of a polygonal room can use the straight skeleton as a roadmap — the skeleton edges are exactly the paths that keep the robot maximally away from all walls.

Wherever a shape needs to be "shrunk uniformly" or you need the medial axis of a polygon with straight edges (rather than circular arcs), the straight skeleton is the right tool — and its connection to convex-hull thinking makes it a natural topic in computational geometry.

Conclusion

The straight skeleton earns its name: it is the skeleton left behind when a polygon shrinks to nothing, and every bone is a perfectly straight line.

What makes it special is how a single physical intuition — push every wall inward at constant speed — produces a structure rich enough to design roofs, offset fonts, plan robot paths and model coastal erosion. The algorithm is elegant in theory and subtle in practice, with reflex vertices and split events hiding real complexity beneath the clean geometry.

The next time you admire a hip roof or trace a parallel curve around a shape, you are looking at the straight skeleton in action — a structure that lives at the intersection of geometry, architecture and the theory of computational geometry.

Share this article

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

Comments

Loading comments...

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