Introduction

Open any map app and pan to a coastline. That jagged silhouette is built from thousands — sometimes millions — of GPS coordinates recorded by survey ships and satellites. Draw them all and your phone grinds to a halt; throw them all away and the shape becomes a smooth lie.

The Douglas-Peucker algorithm (also called Ramer–Douglas–Peucker, published independently in 1972–73) solves this tension with a single elegant idea: keep a point only if it bends the line enough to matter. Everything else is redundant and can be dropped.

The result is a simplified polyline — a chain of straight segments that approximates the original curve within a user-chosen tolerance. Zoom in and the app quietly swaps in a less simplified version; zoom out and it uses a heavily thinned one. Douglas-Peucker makes that swap possible without storing a different dataset for every zoom level — just re-run the algorithm with a different threshold.

The algorithm is solved and efficient: it was published by David Douglas and Thomas Peucker in 1973, runs in O(nlog⁡n)O(n \log n) time on average, and is guaranteed to produce a result within the specified tolerance. No open questions, no NP-hardness — just a beautifully simple recursion that compresses geography without losing its soul.

Try It

The canvas below shows a jagged polyline. Drag the Tolerance slider to change how aggressively the algorithm simplifies it. Kept points light up in blue; dropped points fade out. Watch how the skeleton of the shape survives even at high tolerance.

<div class="controls">
  <label for="eps">Tolerance: <span id="eps-val">20</span> px</label>
  <input id="eps" type="range" min="1" max="80" value="20" step="1">
  <span id="stats" class="stats"></span>
</div>
<canvas id="c" width="560" height="320"></canvas>
<div class="legend">
  <span class="dot kept"></span> Kept point &nbsp;
  <span class="dot dropped"></span> Dropped point &nbsp;
  <span class="line-seg kept-line"></span> Simplified line &nbsp;
  <span class="line-seg orig-line"></span> Original path
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; background: #f4f6f8; }
.controls { display: flex; align-items: center; gap: .8rem; flex-wrap: wrap;
            padding: .6rem .4rem .4rem; background: #fff; border-bottom: 1px solid #dde3ea; }
label { font-size: .88rem; white-space: nowrap; }
input[type=range] { width: 140px; cursor: pointer; }
.stats { font-size: .82rem; color: #555; }
canvas { display: block; width: 100%; max-width: 560px; margin: 0 auto;
         background: #fff; border-bottom: 1px solid #dde3ea; cursor: crosshair; }
.legend { display: flex; align-items: center; gap: .4rem 1rem; flex-wrap: wrap;
          font-size: .8rem; color: #555; padding: .5rem .6rem; background: #fff; }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; }
.dot.kept   { background: #1d6fc9; }
.dot.dropped { background: #bbb; border: 1.5px solid #999; }
.line-seg { display: inline-block; width: 28px; height: 3px; border-radius: 2px; vertical-align: middle; }
.line-seg.kept-line  { background: #1d6fc9; }
.line-seg.orig-line  { background: #e0e0e0; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Douglas-Peucker algorithm demo
// Given a polyline (array of {x,y}) and a tolerance ε, returns the indices
// of the points that should be KEPT (the simplified polyline).
//
// Core idea:
//  1. Draw the baseline from the first to the last point.
//  2. Find the point farthest from that baseline.
//  3. If that max distance > ε, keep it and recurse on both halves.
//  4. Otherwise, drop everything in between.

function ptSegDist(px, py, ax, ay, bx, by) {
  // Perpendicular distance from point P to segment AB
  const dx = bx - ax, dy = by - ay;
  if (dx === 0 && dy === 0) return Math.hypot(px - ax, py - ay);
  const t = Math.max(0, Math.min(1, ((px - ax) * dx + (py - ay) * dy) / (dx * dx + dy * dy)));
  return Math.hypot(px - (ax + t * dx), py - (ay + t * dy));
}

function douglasPeucker(pts, eps, start, end, kept) {
  if (end <= start + 1) return;
  let maxDist = 0, maxIdx = start;
  const ax = pts[start].x, ay = pts[start].y;
  const bx = pts[end].x,   by = pts[end].y;
  for (let i = start + 1; i < end; i++) {
    const d = ptSegDist(pts[i].x, pts[i].y, ax, ay, bx, by);
    if (d > maxDist) { maxDist = d; maxIdx = i; }
  }
  if (maxDist > eps) {
    kept.add(maxIdx);
    douglasPeucker(pts, eps, start, maxIdx, kept);
    douglasPeucker(pts, eps, maxIdx, end, kept);
  }
}

function simplify(pts, eps) {
  if (pts.length < 2) return new Set([0]);
  const kept = new Set([0, pts.length - 1]);
  douglasPeucker(pts, eps, 0, pts.length - 1, kept);
  return kept;
}

// ── Build a demo polyline: a hand-crafted jagged coastline-like shape ──────
const RAW = [
  {x:20,  y:200}, {x:45,  y:210}, {x:60,  y:195}, {x:75,  y:215},
  {x:90,  y:200}, {x:105, y:185}, {x:115, y:205}, {x:130, y:190},
  {x:145, y:175}, {x:155, y:195}, {x:170, y:165}, {x:185, y:182},
  {x:200, y:155}, {x:215, y:170}, {x:230, y:145}, {x:240, y:162},
  {x:255, y:135}, {x:268, y:150}, {x:280, y:128}, {x:295, y:118},
  {x:305, y:135}, {x:318, y:108}, {x:330, y:122}, {x:342, y:100},
  {x:355, y:115}, {x:368, y:92},  {x:380, y:108}, {x:393, y:85},
  {x:406, y:100}, {x:418, y:78},  {x:430, y:92},  {x:443, y:72},
  {x:456, y:88},  {x:468, y:66},  {x:480, y:80},  {x:495, y:65},
  {x:510, y:72},  {x:525, y:60},  {x:540, y:68}
];

const canvas = document.getElementById('c');
const ctx = canvas.getContext('2d');
const slider = document.getElementById('eps');
const epsVal = document.getElementById('eps-val');
const stats  = document.getElementById('stats');

// Scale canvas to device pixel ratio for sharpness
(function scaleCanvas(){
  const dpr = window.devicePixelRatio || 1;
  const rect = canvas.getBoundingClientRect();
  const W = Math.round(rect.width || 560);
  const H = Math.round(rect.height || 320);
  if (canvas.width !== W * dpr || canvas.height !== H * dpr) {
    canvas.width  = W * dpr;
    canvas.height = H * dpr;
    ctx.scale(dpr, dpr);
    canvas.style.width  = W + 'px';
    canvas.style.height = H + 'px';
  }
})();

function draw(eps) {
  const W = canvas.width  / (window.devicePixelRatio || 1);
  const H = canvas.height / (window.devicePixelRatio || 1);
  ctx.clearRect(0, 0, W, H);

  const kept = simplify(RAW, eps);
  const keptArr = [...kept].sort((a,b) => a - b);

  // Draw original path (light gray)
  ctx.beginPath();
  ctx.moveTo(RAW[0].x, RAW[0].y);
  for (let i = 1; i < RAW.length; i++) ctx.lineTo(RAW[i].x, RAW[i].y);
  ctx.strokeStyle = '#dde3ea';
  ctx.lineWidth = 2;
  ctx.stroke();

  // Draw simplified path (blue)
  ctx.beginPath();
  ctx.moveTo(RAW[keptArr[0]].x, RAW[keptArr[0]].y);
  for (let i = 1; i < keptArr.length; i++) ctx.lineTo(RAW[keptArr[i]].x, RAW[keptArr[i]].y);
  ctx.strokeStyle = '#1d6fc9';
  ctx.lineWidth = 2.5;
  ctx.lineJoin = 'round';
  ctx.stroke();

  // Draw dropped points (gray)
  for (let i = 0; i < RAW.length; i++) {
    if (kept.has(i)) continue;
    ctx.beginPath();
    ctx.arc(RAW[i].x, RAW[i].y, 3.5, 0, 2 * Math.PI);
    ctx.fillStyle = '#bbb';
    ctx.fill();
  }

  // Draw kept points (blue, larger)
  for (const i of keptArr) {
    ctx.beginPath();
    ctx.arc(RAW[i].x, RAW[i].y, 5.5, 0, 2 * Math.PI);
    ctx.fillStyle = '#1d6fc9';
    ctx.fill();
    ctx.beginPath();
    ctx.arc(RAW[i].x, RAW[i].y, 5.5, 0, 2 * Math.PI);
    ctx.strokeStyle = '#fff';
    ctx.lineWidth = 1.5;
    ctx.stroke();
  }

  stats.textContent =
    fmt('%size% kept / %v% dropped  (%round%% reduction)', { size: kept.size, v: RAW.length - kept.size, round: Math.round((1 - kept.size / RAW.length) * 100) });

  console.log(fmt('ε=%eps% kept=%size% of %length% (%round%% reduction)', { eps: eps, size: kept.size, length: RAW.length, round: Math.round((1 - kept.size / RAW.length) * 100) }));
}

slider.addEventListener('input', function() {
  epsVal.textContent = this.value;
  draw(+this.value);
});

draw(+slider.value);
Result
Console

Notice how the algorithm is local and recursive: it never looks at the whole curve at once — it just asks, at each step, whether the farthest point from the current baseline strays far enough to matter. That single question, repeated recursively, is the entire algorithm.

The Real Complexity

Douglas-Peucker is a solved, efficient algorithm — but the surrounding landscape has interesting edges worth exploring.

  • Time complexity: O(nlog⁡n)O(n \log n) on average (when the recursion divides the polyline roughly in half each time), and O(n2)O(n^{2}) in the degenerate worst case (a spiral where every recursive call splits off just one point). For practical geographic data the average case dominates.
  • Correctness: the algorithm is guaranteed to produce a simplified polyline where every dropped point lies within ε of the simplified line. This is a hard mathematical guarantee, not a heuristic — and it was proven by Douglas and Peucker in their 1973 paper.
  • Optimality — a subtler question: Douglas-Peucker does not guarantee the minimum number of points that keep all dropped points within ε. Finding the true minimum-point simplification within a given tolerance is a more expensive problem, solvable in O(n2)O(n^{2}) time using dynamic programming (the Imai–Iri algorithm, 1988). In practice, Douglas-Peucker's output is close enough to optimal that the difference rarely matters.
  • Self-intersections: the simplified polyline can cross itself even when the original does not. This is acceptable for rendering but matters for geometric algorithms that assume simple polygons.

Douglas-Peucker sits in the comfortable zone of P vs NP: it is polynomial, deterministic, and correct. The only price is that it is not always minimal, and a truly optimal simplification costs a bit more to compute. For the billions of map tiles served every day, that trade-off is entirely worth it.

Where It Matters

Douglas-Peucker is one of the most widely deployed geometric algorithms in the world, appearing wherever a curve needs to be approximated cheaply:

  • Web and mobile maps: OpenStreetMap, Google Maps, Apple Maps and every tile-based mapping system use it (or a derivative) to generate simplified geometries at each zoom level. Without it, rendering a world map would require transmitting terabytes of coordinates.
  • GPS track compression: fitness apps and navigation systems record a GPS point every second. Douglas-Peucker strips the redundant samples for storage and display, keeping turns and bends while discarding straight-line noise.
  • SVG and vector graphics: illustration software and CAD tools use it to clean up hand-drawn curves and scanned outlines, reducing the point count before export.
  • Computer vision: contour detection pipelines (OpenCV's approxPolyDP) use Douglas-Peucker to turn pixel-level contours into compact polygons for shape recognition.
  • Robot path planning: motion planners simplify recorded demonstration paths before replaying them, removing jitter while preserving the intended trajectory.
  • Scientific data visualization: time-series charts with millions of samples use it to render only the detail the screen can actually show.

Every time your navigation app draws a smooth road with far fewer vertices than the raw survey data, there is a good chance Douglas-Peucker made that decision — one recursive question at a time.

Conclusion

Douglas-Peucker is a reminder that the most powerful algorithms are often the simplest ones: find the farthest point from the baseline, keep it if it matters, and recurse on the two halves. That is the whole idea, and it is enough to compress the world's coastlines into something a phone can render in milliseconds.

It is also a gentle contrast to harder problems on this site. Unlike P vs NP or the halting problem, Douglas-Peucker is fully solved — fast, correct, and proven. The only open edge is optimality, and even that has a clean polynomial solution. Sometimes computation is kind, and a beautiful recursive idea is genuinely all you need.

Share this article

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

Comments

Loading comments...

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