Quadtree Spatial Partitioning Visualizer — Free Interactive Canvas Demo

<div class="qt">
  <div class="qt-top">
    <div>
      <h2>Quadtree: find nearby points without checking all of them</h2>
      <p>Move the pointer (or drag on touch) to query the box around it. Click to add points.</p>
    </div>
    <div class="qt-ctrl">
      <label>Points <input type="range" id="qtN" min="50" max="2000" step="50" value="600"><output id="qtNOut"></output></label>
      <label>Capacity <input type="range" id="qtCap" min="1" max="16" value="4"><output id="qtCapOut"></output></label>
      <label><input type="checkbox" id="qtMove" checked> Moving</label>
    </div>
  </div>
  <canvas id="qtCanvas" width="900" height="480" aria-label="Quadtree of moving points"></canvas>
  <div class="qt-stats" id="qtStats" aria-live="off"></div>
</div>

*{box-sizing:border-box;margin:0;padding:0}
body{font-family:system-ui,-apple-system,sans-serif;background:#020617;color:#e2e8f0;min-height:100vh;display:flex;align-items:center;justify-content:center;padding:20px}
.qt{width:100%;max-width:940px}
.qt-top{display:flex;justify-content:space-between;align-items:flex-end;gap:14px;flex-wrap:wrap;margin-bottom:10px}
.qt h2{font-size:17px}
.qt-top p{font-size:12px;color:#94a3b8;margin-top:4px}
.qt-ctrl{display:flex;gap:14px;flex-wrap:wrap;font-size:12px;color:#cbd5e1}
.qt-ctrl label{display:flex;align-items:center;gap:6px}
.qt-ctrl input[type=range]{width:110px;accent-color:#22d3ee}
.qt-ctrl output{width:34px;font-variant-numeric:tabular-nums}
#qtCanvas{width:100%;height:auto;display:block;background:#0b1224;border:1px solid #1e293b;border-radius:14px;touch-action:none;cursor:crosshair}
.qt-stats{display:grid;grid-template-columns:repeat(4,1fr);gap:10px;margin-top:10px}
@media (max-width:640px){.qt-stats{grid-template-columns:repeat(2,1fr)}}
.qt-stat{background:#0b1224;border:1px solid #1e293b;border-radius:10px;padding:8px 10px}
.qt-stat b{display:block;font-size:20px;font-variant-numeric:tabular-nums}
.qt-stat small{font-size:11px;color:#94a3b8}
.qt-stat.good b{color:#4ade80}

var canvas = document.getElementById('qtCanvas');
var ctx = canvas.getContext('2d');
var W = canvas.width, H = canvas.height;
var points = [];
var query = { x: W / 2, y: H / 2, w: 150, h: 110 };
var reduce = window.matchMedia('(prefers-reduced-motion: reduce)').matches;
if (reduce) document.getElementById('qtMove').checked = false;

// A quadtree node covers a rectangle. It holds up to CAP points; when one
// more arrives it splits into four equal children and hands points down.
function QT(x, y, w, h, cap, depth) {
  this.x = x; this.y = y; this.w = w; this.h = h;
  this.cap = cap; this.depth = depth;
  this.pts = [];
  this.kids = null;
}
QT.prototype.contains = function (p) {
  return p.x >= this.x && p.x < this.x + this.w && p.y >= this.y && p.y < this.y + this.h;
};
QT.prototype.insert = function (p) {
  if (!this.contains(p)) return false;
  if (!this.kids) {
    // Depth limit stops endless splitting when many points share a spot.
    if (this.pts.length < this.cap || this.depth >= 9) { this.pts.push(p); return true; }
    this.split();
  }
  for (var i = 0; i < 4; i++) if (this.kids[i].insert(p)) return true;
  return false;
};
QT.prototype.split = function () {
  var hw = this.w / 2, hh = this.h / 2, d = this.depth + 1;
  this.kids = [
    new QT(this.x, this.y, hw, hh, this.cap, d), new QT(this.x + hw, this.y, hw, hh, this.cap, d),
    new QT(this.x, this.y + hh, hw, hh, this.cap, d), new QT(this.x + hw, this.y + hh, hw, hh, this.cap, d),
  ];
  var old = this.pts;
  this.pts = [];
  old.forEach(function (p) { this.insert(p); }, this);
};
// Query: skip any node whose rectangle doesn't overlap the query box —
// that's where the savings come from. Count every point actually tested.
QT.prototype.query = function (r, out, stats) {
  stats.nodes++;
  if (r.x > this.x + this.w || r.x + r.w < this.x || r.y > this.y + this.h || r.y + r.h < this.y) return out;
  stats.visited.push(this);
  for (var i = 0; i < this.pts.length; i++) {
    var p = this.pts[i];
    stats.checks++;
    if (p.x >= r.x && p.x <= r.x + r.w && p.y >= r.y && p.y <= r.y + r.h) out.push(p);
  }
  if (this.kids) for (var k = 0; k < 4; k++) this.kids[k].query(r, out, stats);
  return out;
};
QT.prototype.draw = function () {
  ctx.strokeRect(this.x + 0.5, this.y + 0.5, this.w, this.h);
  if (this.kids) this.kids.forEach(function (k) { k.draw(); });
};
QT.prototype.count = function () { return 1 + (this.kids ? this.kids.reduce(function (s, k) { return s + k.count(); }, 0) : 0); };

function makePoints(n) {
  points = [];
  for (var i = 0; i < n; i++) {
    // Clustered distribution: real spatial data is rarely uniform.
    var cx = [200, 620, 420][i % 3], cy = [150, 320, 240][i % 3];
    var a = Math.random() * Math.PI * 2, r = Math.pow(Math.random(), 0.7) * 190;
    points.push({ x: Math.min(W - 1, Math.max(0, cx + Math.cos(a) * r)), y: Math.min(H - 1, Math.max(0, cy + Math.sin(a) * r * 0.8)),
      vx: (Math.random() - 0.5) * 1.1, vy: (Math.random() - 0.5) * 1.1 });
  }
}

function stat(label, value, good) {
  return '<div class="qt-stat' + (good ? ' good' : '') + '"><b>' + value + '</b><small>' + label + '</small></div>';
}

var frameCount = 0;
function frame() {
  var cap = Number(document.getElementById('qtCap').value);
  if (document.getElementById('qtMove').checked) {
    points.forEach(function (p) {
      p.x += p.vx; p.y += p.vy;
      if (p.x < 0 || p.x >= W) { p.vx *= -1; p.x = Math.min(W - 1, Math.max(0, p.x)); }
      if (p.y < 0 || p.y >= H) { p.vy *= -1; p.y = Math.min(H - 1, Math.max(0, p.y)); }
    });
  }
  // Rebuilding every frame is simple and, for thousands of points, fast.
  var tree = new QT(0, 0, W, H, cap, 0);
  points.forEach(function (p) { tree.insert(p); });

  var q = { x: query.x - query.w / 2, y: query.y - query.h / 2, w: query.w, h: query.h };
  var stats = { nodes: 0, checks: 0, visited: [] };
  var found = tree.query(q, [], stats);

  ctx.clearRect(0, 0, W, H);
  ctx.strokeStyle = 'rgba(56,189,248,.22)';
  ctx.lineWidth = 1;
  tree.draw();
  ctx.fillStyle = 'rgba(34,211,238,.06)';
  stats.visited.forEach(function (n) { if (!n.kids) ctx.fillRect(n.x, n.y, n.w, n.h); });
  ctx.fillStyle = '#475569';
  points.forEach(function (p) { ctx.fillRect(p.x - 1.5, p.y - 1.5, 3, 3); });
  ctx.fillStyle = '#facc15';
  found.forEach(function (p) { ctx.beginPath(); ctx.arc(p.x, p.y, 3, 0, Math.PI * 2); ctx.fill(); });
  ctx.strokeStyle = '#facc15';
  ctx.lineWidth = 2;
  ctx.strokeRect(q.x, q.y, q.w, q.h);

  if (frameCount++ % 6 === 0) {
    var pct = points.length ? Math.round((stats.checks / points.length) * 100) : 0;
    document.getElementById('qtStats').innerHTML =
      stat('points found in the box', found.length) +
      stat('points tested with the quadtree', stats.checks, true) +
      stat('points a brute-force scan tests', points.length) +
      stat('work compared with brute force', pct + '%', true);
  }
  requestAnimationFrame(frame);
}

function toCanvas(e) {
  var r = canvas.getBoundingClientRect();
  return { x: (e.clientX - r.left) * (W / r.width), y: (e.clientY - r.top) * (H / r.height) };
}
canvas.addEventListener('pointermove', function (e) { var p = toCanvas(e); query.x = p.x; query.y = p.y; });
canvas.addEventListener('click', function (e) {
  var p = toCanvas(e);
  for (var i = 0; i < 12; i++) points.push({ x: p.x + (Math.random() - 0.5) * 30, y: p.y + (Math.random() - 0.5) * 30, vx: (Math.random() - 0.5), vy: (Math.random() - 0.5) });
});

function syncOutputs() {
  document.getElementById('qtNOut').textContent = document.getElementById('qtN').value;
  document.getElementById('qtCapOut').textContent = document.getElementById('qtCap').value;
}
document.getElementById('qtN').addEventListener('input', function () { makePoints(Number(this.value)); syncOutputs(); });
document.getElementById('qtCap').addEventListener('input', syncOutputs);
makePoints(600);
syncOutputs();
requestAnimationFrame(frame);