Introduction

Imagine a wide floor scattered with square pillars. You stand at one spot and want to reach the door by the shortest walk possible, without passing through any pillar. Which way do you go?

There is a wonderfully physical answer. Tie a string from your start to the goal and pull it taut. It snaps against the corners of the pillars in its way, and what remains is the shortest obstacle-free route. The taut string never curves in open space — it travels in straight segments and only ever bends at a corner of an obstacle.

That single observation is the whole secret. Because the optimal path only turns at corners, we never have to consider the infinitely many points of the floor — just the start, the goal, and the obstacle corners. A continuous geometry problem collapses into a small, finite graph we can search quickly and exactly.

Pull the String

Below is a floor with a few obstacles. Drag the green start and the red goal anywhere on open ground. The route that lights up is the genuine shortest obstacle-free path — built by connecting every pair of mutually visible corners, then running Dijkstra over that visibility graph.

<p class="hint">Drag the <b class="g">green start</b> and the <b class="r">red goal</b>
    across the open floor. The lit route is the genuine shortest obstacle-free path:
    connect every pair of mutually visible corners, then run Dijkstra. It bends
    <b>only at corners</b> — just like a string pulled taut.</p>
<canvas id="floor" width="420" height="320"></canvas>
<div class="status" id="status"></div>
<div class="btns">
  <button id="graph" type="button">Show visibility graph</button>
  <button id="reset" type="button" class="ghost">Reset endpoints</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; }
.hint .g { color: #0a7d33; }
.hint .r { color: #c92f3c; }
canvas { border: 1px solid #cdd9e3; border-radius: 10px; background: #f4f7fa;
         touch-action: none; display: block; max-width: 100%; cursor: grab; }
canvas.drag { cursor: grabbing; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; color: #1d3557; }
.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.on { background: #0a7d33; border-color: #0a7d33; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Shortest path among polygonal obstacles. The optimum only ever turns at an
    // obstacle CORNER, so the answer lives in the "visibility graph": nodes = start,
    // goal and all corners; an edge joins two nodes when the straight segment between
    // them crosses no obstacle. Dijkstra over that graph gives the EXACT shortest
    // path in polynomial time (Lee, 1978). This is firmly in P.
const cv = document.getElementById('floor'), ctx = cv.getContext('2d');
const W = cv.width, H = cv.height;

// Axis-aligned rectangular obstacles [x, y, w, h].
const OBS = [ [110, 60, 75, 75], [245, 120, 85, 60], [120, 205, 140, 55] ];
const PAD = 2;  // ignore a hair of interior so a path grazing a corner isn't falsely blocked
const E = 6;    // graph nodes sit just OUTSIDE each corner
function corners(o){ const [x,y,w,h]=o; return [
  [x-E,y-E],[x+w+E,y-E],[x+w+E,y+h+E],[x-E,y+h+E] ]; }
const CORNERS = OBS.flatMap(corners);

let start = [40, 40], goal = [380, 290];

// ---- geometry helpers ----
const dist=(a,b)=>Math.hypot(a[0]-b[0],a[1]-b[1]);
function inside(p){ for(const [x,y,w,h] of OBS){ if(p[0]>x&&p[0]<x+w&&p[1]>y&&p[1]<y+h) return true; } return false; }
// Segment AB is "blocked" iff it enters the open interior of some obstacle.
    // We sample densely along AB — simple and obviously correct for this demo.
function blocked(a,b){
  const n=Math.max(2,Math.ceil(dist(a,b)/2));
  for(let k=1;k<n;k++){ const t=k/n, x=a[0]+(b[0]-a[0])*t, y=a[1]+(b[1]-a[1])*t;
    for(const [ox,oy,ow,oh] of OBS){ if(x>ox+PAD&&x<ox+ow-PAD&&y>oy+PAD&&y<oy+oh-PAD) return true; } }
  return false;
}

// ---- visibility graph + Dijkstra ----
function solve(){
  const nodes=[start, goal, ...CORNERS];
  const N=nodes.length, adj=Array.from({length:N},()=>[]);
  for(let i=0;i<N;i++) for(let j=i+1;j<N;j++){
    if(!blocked(nodes[i],nodes[j])){ const w=dist(nodes[i],nodes[j]);
      adj[i].push([j,w]); adj[j].push([i,w]); } }
  // Dijkstra from 0 (start) to 1 (goal)
  const D=Array(N).fill(Infinity), prev=Array(N).fill(-1), done=Array(N).fill(false);
  D[0]=0;
  for(let it=0;it<N;it++){
    let u=-1,best=Infinity;
    for(let k=0;k<N;k++) if(!done[k]&&D[k]<best){best=D[k];u=k;}
    if(u===-1) break; done[u]=true;
    for(const [v,w] of adj[u]) if(D[u]+w<D[v]){ D[v]=D[u]+w; prev[v]=u; }
  }
  let path=null;
  if(D[1]<Infinity){ path=[]; for(let c=1;c!==-1;c=prev[c]) path.push(nodes[c]); path.reverse(); }
  return {nodes, adj, path, len:D[1]};
}

// ---- rendering ----
let showGraph=false;
function draw(){
  ctx.clearRect(0,0,W,H);
  for(const [x,y,w,h] of OBS){ ctx.fillStyle='#c9ccd1'; ctx.strokeStyle='#8a8f97';
    ctx.lineWidth=1; ctx.fillRect(x,y,w,h); ctx.strokeRect(x,y,w,h); }
  const res=solve();
  if(showGraph){ ctx.strokeStyle='rgba(29,53,87,.18)'; ctx.lineWidth=1;
    for(let i=0;i<res.nodes.length;i++) for(const [j] of res.adj[i]) if(j>i){
      ctx.beginPath(); ctx.moveTo(...res.nodes[i]); ctx.lineTo(...res.nodes[j]); ctx.stroke(); } }
  if(res.path){ ctx.strokeStyle='#1d3557'; ctx.lineWidth=3.5; ctx.lineJoin='round';
    ctx.beginPath(); ctx.moveTo(...res.path[0]); res.path.slice(1).forEach(p=>ctx.lineTo(...p)); ctx.stroke();
    setStatus(fmt('Shortest route: %len% px, bending at %v% corner(s).', { len: res.len.toFixed(0), v: res.path.length-2 }));
  } else setStatus('No obstacle-free route — move an endpoint off the walls.');
  dot(start,'#0a7d33'); dot(goal,'#c92f3c');
}
function dot(p,c){ ctx.fillStyle=c; ctx.strokeStyle='#fff'; ctx.lineWidth=2;
  ctx.beginPath(); ctx.arc(p[0],p[1],8,0,7); ctx.fill(); ctx.stroke(); }
function setStatus(t){ document.getElementById('status').textContent=t; }

// ---- dragging ----
let drag=null;
function pos(ev){ const r=cv.getBoundingClientRect(), t=ev.touches?ev.touches[0]:ev;
  return [ (t.clientX-r.left)*W/r.width, (t.clientY-r.top)*H/r.height ]; }
function pick(p){ if(dist(p,start)<16) return 'start'; if(dist(p,goal)<16) return 'goal'; return null; }
function down(ev){ const p=pos(ev); drag=pick(p); if(drag){ ev.preventDefault(); cv.classList.add('drag'); } }
function move(ev){ if(!drag) return; ev.preventDefault();
  let p=pos(ev); p=[Math.max(6,Math.min(W-6,p[0])),Math.max(6,Math.min(H-6,p[1]))];
  if(inside(p)) return; // keep endpoints on open ground
  if(drag==='start') start=p; else goal=p; draw(); }
function up(){ drag=null; cv.classList.remove('drag'); }
cv.addEventListener('mousedown',down); cv.addEventListener('mousemove',move);
window.addEventListener('mouseup',up);
cv.addEventListener('touchstart',down,{passive:false}); cv.addEventListener('touchmove',move,{passive:false});
window.addEventListener('touchend',up);

document.getElementById('graph').addEventListener('click',e=>{ showGraph=!showGraph;
  e.target.classList.toggle('on',showGraph);
  e.target.textContent=showGraph?'Hide visibility graph':'Show visibility graph'; draw(); });
document.getElementById('reset').addEventListener('click',()=>{ start=[40,40]; goal=[380,290]; draw(); });
draw();
Result
Console

Watch how the path behaves. It runs dead straight whenever it can, and bends only at the corners of obstacles — exactly where a real string would catch. Toggle the visibility graph to see every candidate shortcut the algorithm considered; the highlighted route is the cheapest walk through that web of straight lines.

The Real Complexity

How hard is it to find the shortest path around obstacles? Reassuringly easy — this is a solved problem with an exact polynomial-time algorithm.

  • The key theorem. Any shortest path among polygonal obstacles is a sequence of straight segments whose interior turning points are all obstacle vertices. So the optimum lives entirely in the visibility graph: a node for the start, the goal and every corner, with an edge between two nodes whenever the straight segment between them touches no obstacle interior.
  • Build it, then search it. With n corners the visibility graph has at most about n2n^{2} edges; the classic construction (Lee, 1978) builds it in O(n2log⁡n)O(n^{2} \log n), later improved to O(n2)O(n^{2}) by Welzl and others. Running Dijkstra on it then returns the exact shortest path.
  • Total cost. The whole pipeline is comfortably polynomial — roughly O(n2log⁡n)O(n^{2} \log n) — and gives the provably optimal route, not an approximation.
  • Not every "shortest path" is this kind. Restrict turns to a grid, add costs and time, or move to three dimensions among polyhedra, and the picture changes — the 3D version becomes NP-hard (Canny & Reif, 1987).

The contrast worth keeping is with its famous relative, the Traveling Salesman / route problem. Finding the best order to visit many stops is NP-hard; finding the shortest way between two points around obstacles is squarely in P. Geometry, not just graphs, is what makes this one tractable.

Where It Matters

"Get from here to there without bumping into things" is one of the most common tasks in the physical and digital world, and the visibility graph is its workhorse:

  • Robot motion planning: a robot reduced to a point navigates a workspace of obstacles by exactly this construction — one of the founding ideas of motion planning.
  • Video-game navigation: characters route around walls and scenery using visibility graphs or their close cousins (navmeshes), producing those natural corner-hugging paths.
  • Geographic routing: planning a ship's or drone's course around no-go zones is a shortest-path-with-obstacles problem on a map.
  • Chip layout (VLSI): wiring a connection across a board while dodging blocked regions is the same geometric question at microscopic scale.

Learn why the taut string only bends at corners and you have met computational geometry's friendliest result — a continuous problem made finite, then solved exactly with a graph search.

Conclusion

The shortest path around obstacles hides an elegant truth: the answer only ever bends at corners, so the whole continuous floor collapses into a finite visibility graph we can search exactly. No guessing, no approximation — just a string pulled taut and a polynomial-time algorithm that matches it.

It is a refreshing counterpoint to the intractable problems nearby. Visiting many stops in the best order is the NP-hard route problem, and even telling a short path from a long one can hide surprises. But getting from A to B around walls? That one we have fully, provably solved.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/visibility-shortest-path/Content licensed under CC BY-NC 4.0.