Implementacja kd-drzewa.

kdtree.js

class Point extends Array {
  get x() { return this[0] }
  get y() { return this[1] }
  set x(x) { this[0] = x }
  set y(y) { this[1] = y }
}

const pointInRange = (point, min, max) => point.every((val, ax) => min[ax] <= val && val <= max[ax])

function medianPart(arr, ax) {
  arr.sort((a, b) => a[ax] - b[ax])
  let split = arr.length / 2 | 0
  const sp = arr[split][ax]
  while (split > 1 && arr[split - 1][ax] == sp) 
    split--
  return [arr.slice(0, split), arr[split], arr.slice(split + 1)]
}

function buildTree (dim, points, depth = 0) {
  if (points.length == 0) return null
  const ax = depth % dim
  const [low, median, high] = medianPart(points, ax)
  return {
    low: buildTree(dim, low, depth + 1),
    high: buildTree(dim, high, depth + 1),
    value: median
  }
}

function query(dim, tree, min, max) {
  const points = []
  const query = (tree, depth) => {
    if (tree == null) return
    const ax = depth % dim
    if (tree.value[ax] < min[ax]) query(tree.high, depth + 1)
    else if (tree.value[ax] > max[ax]) query(tree.low, depth + 1)
    else {
      if (pointInRange(tree.value, min, max)) points.push(tree.value)
      query(tree.low, depth + 1)
      query(tree.high, depth + 1)
    }
  }
  query(tree, 0)
  return points
}