Simple recursive quadtree (slow)

Readme.md

Simple recursive quadtree

This one is quite slow due to function calls in recursion, and naive splitting.

It runs in about 300ms for 125k points (MBP 2.7 GHz Intel Core i5)

• 1 more Array per node → +100ms
• implement as a class → +100ms

simple-quadtree.js

function getIndexesBBox (indexes, X, Y) {
  let xmin = Infinity, ymin = Infinity, xmax = -Infinity, ymax = -Infinity;
  for (let i = 0; i < indexes.length; i++) {
    const v = indexes[i];
    const x = X[v], y = Y[v];
    if (x < xmin) xmin = x;
    if (y < ymin) ymin = y;
    if (x > xmax) xmax = x;
    if (y > ymax) ymax = y;
  }
  return [xmin, ymin, xmax, ymax];
}


function simpleQuadTree(parent = null, xmin, ymin, xmax, ymax, X, Y, vertices, minSize = 0) {
  //const reverseMap = (parent === null) ? {} : parent.reverseMap;
  const node = { parent, xmin, ymin, xmax, ymax, vertices/*, reverseMap*/ };
  const width = (xmax - xmin);
  const height = (ymax - ymin);
  const cx = xmin + width / 2;
  const cy = ymin + height / 2;

  if (vertices.length > 1 && width * height > minSize) { // inner node
    const quadrants = [[], [], [], []];
    for (let i = 0; i < vertices.length; i++) {
      const v = vertices[i];
      const x = X[v], y = Y[v];
      if (x < cx) quadrants[y < cy ? 0 : 1].push(v);
      else        quadrants[y < cy ? 2 : 3].push(v);
    }
    node.nw = simpleQuadTree(node, xmin, ymin, cx, cy, X, Y, quadrants[0]);
    node.sw = simpleQuadTree(node, xmin, cy, cx, ymax, X, Y, quadrants[1]);
    node.ne = simpleQuadTree(node, cx, ymin, xmax, cy, X, Y, quadrants[2]);
    node.se = simpleQuadTree(node, cx, cy, xmax, ymax, X, Y, quadrants[3]);
  } else { // leaf
    //for (let i = 0; i < vertices.length; i++) reverseMap[vertices[i]] = node;
    node.nw = node.sw = node.ne = node.se = null;
  }
  return node;
}

const N = 125589;
const indexes = new Array(N).fill(0).map((_, i) => i);
const X = indexes.map(() => Math.random() * N);
const Y = indexes.map(() => Math.random() * N);
const M = indexes.map(() => Math.round(Math.random() * 5));

console.time('simple recursive quadtree');
const bbox = getIndexesBBox(indexes, X, Y);
const V = simpleQuadTree(null, bbox[0], bbox[1], bbox[2], bbox[3], X, Y, indexes);
console.timeEnd('simple recursive quadtree');