k-Nearest Neighbours Classifier

// k-Nearest-Neighbours on 2D points, 3 classes.
// Decision boundary is rendered by classifying every 8x8 block via
// majority vote among its k closest training points. When the user
// taps/clicks/moves the cursor, mouse X = query and mouse Y scrubs k.
// Otherwise (idle / touch device with no hover) the query sweeps the
// plot on a slow Lissajous curve and k cycles 1 → ~20 → 1.

const N_PER_CLASS = 28;
const N_CLASSES = 3;
const N_POINTS = N_PER_CLASS * N_CLASSES;
const BLOCK = 8;
const K_MIN = 1;
const K_MAX = 25;
// How long after the last user input we keep honoring mouse-driven mode
// before falling back to the autopilot sweep. ~3.5s is long enough that
// a probe-and-pause-to-read doesn't feel like it snaps away, short enough
// that an accidental tap on a touch device doesn't freeze the demo for
// minutes.
const INTERACT_HOLD_S = 3.5;

// class colors (RGB triples for the boundary fill, plus a CSS string)
const COLORS = [
  { r: 230, g: 70, b: 90, css: '#e6465a' }, // red
  { r: 70, g: 160, b: 235, css: '#46a0eb' }, // blue
  { r: 90, g: 210, b: 130, css: '#5ad282' }, // green
];

let W, H;
let pts; // Float32Array, [x0,y0,x1,y1,...] in canvas px
let labels; // Uint8Array, class index per point
let field; // Uint8Array(cols*rows) majority class per block
let cols, rows;
let dists; // scratch Float32Array(N_POINTS) for kNN
let order; // scratch Uint16Array(N_POINTS) indices for sort
let k;
// Interaction tracking. We treat ANY of these as "user interacted":
//   - mouseDown is true this frame
//   - a click was queued (consumeClicks)
//   - mouseX/mouseY moved since last frame
// On any of those, we stamp lastInteractTime; while now - lastInteractTime
// is below INTERACT_HOLD_S we drive the query from mouseX/Y. Otherwise
// we fall through to the autopilot sweep.
let lastInteractTime = -Infinity;
let lastMouseX = 0;
let lastMouseY = 0;
let autoElapsed = 0; // seconds accumulated for the autopilot phase

function rng() { return Math.random(); }

function placeClusters() {
  pts = new Float32Array(N_POINTS * 2);
  labels = new Uint8Array(N_POINTS);
  // 3 cluster centroids placed roughly equidistant in the canvas
  const centers = [
    [W * 0.28, H * 0.34],
    [W * 0.72, H * 0.34],
    [W * 0.50, H * 0.74],
  ];
  const spread = Math.min(W, H) * 0.13;
  let idx = 0;
  for (let c = 0; c < N_CLASSES; c++) {
    const [cx, cy] = centers[c];
    for (let i = 0; i < N_PER_CLASS; i++) {
      // box-muller-ish: two uniforms summed gives a softened gaussian
      const r = spread * Math.sqrt(-2 * Math.log(1 - 0.999 * rng()));
      const a = rng() * Math.PI * 2;
      pts[idx * 2] = cx + r * Math.cos(a);
      pts[idx * 2 + 1] = cy + r * Math.sin(a);
      labels[idx] = c;
      idx++;
    }
  }
}

function classifyAt(px, py, kk) {
  // partial selection: find kk smallest distances among N_POINTS
  for (let i = 0; i < N_POINTS; i++) {
    const dx = pts[i * 2] - px;
    const dy = pts[i * 2 + 1] - py;
    dists[i] = dx * dx + dy * dy;
    order[i] = i;
  }
  // partial selection sort — only need first kk entries ordered enough
  // to read their labels. kk ≤ 25, N = 84, so this is ~25*84 = 2100 ops.
  for (let s = 0; s < kk; s++) {
    let best = s;
    let bestD = dists[order[s]];
    for (let j = s + 1; j < N_POINTS; j++) {
      const d = dists[order[j]];
      if (d < bestD) { bestD = d; best = j; }
    }
    if (best !== s) {
      const tmp = order[s]; order[s] = order[best]; order[best] = tmp;
    }
  }
  // majority vote
  let c0 = 0, c1 = 0, c2 = 0;
  for (let i = 0; i < kk; i++) {
    const lab = labels[order[i]];
    if (lab === 0) c0++; else if (lab === 1) c1++; else c2++;
  }
  if (c0 >= c1 && c0 >= c2) return 0;
  if (c1 >= c2) return 1;
  return 2;
}

function rebuildField(kk) {
  cols = Math.ceil(W / BLOCK);
  rows = Math.ceil(H / BLOCK);
  if (!field || field.length !== cols * rows) {
    field = new Uint8Array(cols * rows);
  }
  for (let r = 0; r < rows; r++) {
    const cy = r * BLOCK + BLOCK * 0.5;
    for (let c = 0; c < cols; c++) {
      const cx = c * BLOCK + BLOCK * 0.5;
      field[r * cols + c] = classifyAt(cx, cy, kk);
    }
  }
}

function init({ ctx, width, height }) {
  W = width;
  H = height;
  dists = new Float32Array(N_POINTS);
  order = new Uint16Array(N_POINTS);
  k = 5;
  placeClusters();
  rebuildField(k);
  ctx.fillStyle = '#0a0c12';
  ctx.fillRect(0, 0, W, H);
}

function tick({ ctx, width, height, input, frame, dt, time }) {
  if (width !== W || height !== H) {
    W = width;
    H = height;
    placeClusters();
    rebuildField(k);
  }

  // ---- detect interaction ----
  // consumeClicks() also drains the queue, which is fine — we don't use
  // them for anything else in this sim.
  const clicks = input.consumeClicks();
  const mouseMoved =
    input.mouseX !== lastMouseX || input.mouseY !== lastMouseY;
  if (clicks.length > 0 || input.mouseDown || mouseMoved) {
    lastInteractTime = time;
  }
  lastMouseX = input.mouseX;
  lastMouseY = input.mouseY;

  const interacting = time - lastInteractTime < INTERACT_HOLD_S;

  // ---- choose query position + k ----
  // When interacting, mouseX = query, mouseY scrubs k.
  // When idle, drive query along a slow Lissajous and breathe k
  // 1 → ~20 → 1 on a separate slower cycle.
  let qx, qy, targetK;
  if (interacting) {
    qx = Math.max(0, Math.min(W, input.mouseX));
    qy = Math.max(0, Math.min(H, input.mouseY));
    targetK = Math.max(
      K_MIN,
      Math.min(K_MAX, K_MIN + Math.round((qy / H) * (K_MAX - K_MIN))),
    );
  } else {
    autoElapsed += dt;
    // Lissajous in normalized [0.12, 0.88] of the canvas so the marker
    // never hugs the very edges (and stays clear of the HUD in the
    // top-left). 2:3 frequency ratio gives a non-trivial weave.
    const t = autoElapsed * 0.35; // overall sweep speed
    const nx = 0.5 + 0.38 * Math.sin(t * 2);
    const ny = 0.5 + 0.38 * Math.sin(t * 3 + 1.1);
    qx = nx * W;
    qy = ny * H;
    // k cycles 1 → 20 → 1 every 8s. Triangle wave is more legible
    // than sine — flat extrema would let viewers actually read each k.
    const kCycle = (autoElapsed * (1 / 8)) % 1; // 0..1 over 8s
    const tri = kCycle < 0.5 ? kCycle * 2 : 2 - kCycle * 2; // 0..1..0
    targetK = Math.max(
      K_MIN,
      Math.min(20, K_MIN + Math.round(tri * (20 - K_MIN))),
    );
  }

  if (targetK !== k) {
    k = targetK;
    rebuildField(k);
  }

  // paint boundary as an ImageData built from `field`
  ctx.fillStyle = '#0a0c12';
  ctx.fillRect(0, 0, W, H);

  ctx.globalAlpha = 0.42;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      const cls = field[r * cols + c];
      const col = COLORS[cls];
      ctx.fillStyle = `rgb(${col.r},${col.g},${col.b})`;
      ctx.fillRect(c * BLOCK, r * BLOCK, BLOCK, BLOCK);
    }
  }
  ctx.globalAlpha = 1;

  // draw training points
  for (let i = 0; i < N_POINTS; i++) {
    const x = pts[i * 2];
    const y = pts[i * 2 + 1];
    const col = COLORS[labels[i]];
    ctx.fillStyle = col.css;
    ctx.strokeStyle = 'rgba(8,10,16,0.9)';
    ctx.lineWidth = 1.25;
    ctx.beginPath();
    ctx.arc(x, y, 4.2, 0, Math.PI * 2);
    ctx.fill();
    ctx.stroke();
  }

  // find k nearest to (qx, qy) — same selection routine
  for (let i = 0; i < N_POINTS; i++) {
    const dx = pts[i * 2] - qx;
    const dy = pts[i * 2 + 1] - qy;
    dists[i] = dx * dx + dy * dy;
    order[i] = i;
  }
  for (let s = 0; s < k; s++) {
    let best = s;
    let bestD = dists[order[s]];
    for (let j = s + 1; j < N_POINTS; j++) {
      const d = dists[order[j]];
      if (d < bestD) { bestD = d; best = j; }
    }
    if (best !== s) {
      const tmp = order[s]; order[s] = order[best]; order[best] = tmp;
    }
  }

  // votes for HUD + winning class color for the query marker
  let c0 = 0, c1 = 0, c2 = 0;
  for (let i = 0; i < k; i++) {
    const lab = labels[order[i]];
    if (lab === 0) c0++; else if (lab === 1) c1++; else c2++;
  }
  const winner = (c0 >= c1 && c0 >= c2) ? 0 : (c1 >= c2 ? 1 : 2);
  const winCol = COLORS[winner];

  // lines to k nearest neighbours
  ctx.strokeStyle = 'rgba(255,255,255,0.85)';
  ctx.lineWidth = 1;
  for (let i = 0; i < k; i++) {
    const ni = order[i];
    ctx.beginPath();
    ctx.moveTo(qx, qy);
    ctx.lineTo(pts[ni * 2], pts[ni * 2 + 1]);
    ctx.stroke();
  }

  // query marker
  ctx.fillStyle = winCol.css;
  ctx.strokeStyle = '#ffffff';
  ctx.lineWidth = 2;
  ctx.beginPath();
  ctx.arc(qx, qy, 7, 0, Math.PI * 2);
  ctx.fill();
  ctx.stroke();

  // HUD
  ctx.fillStyle = 'rgba(8,10,16,0.78)';
  ctx.fillRect(8, 8, 168, 64);
  ctx.fillStyle = '#e8eaf0';
  ctx.font = 'bold 13px ui-sans-serif, system-ui, sans-serif';
  ctx.fillText(`k = ${k}`, 16, 26);
  ctx.font = '12px ui-sans-serif, system-ui, sans-serif';
  ctx.fillStyle = COLORS[0].css;
  ctx.fillText(`red: ${c0}`, 16, 44);
  ctx.fillStyle = COLORS[1].css;
  ctx.fillText(`blue: ${c1}`, 76, 44);
  ctx.fillStyle = COLORS[2].css;
  ctx.fillText(`green: ${c2}`, 16, 60);
  ctx.fillStyle = winCol.css;
  ctx.fillText(`→ ${['red','blue','green'][winner]}`, 92, 60);
}