Basic quadtree implementation in JS

quadtree.js

// Utilities

const distance = (x1, y1, x2, y2) =>
  Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));

// The quadtree

export default class QuadTree {
  constructor(x, y, width, height, capacity = 4) {
    this.x = x;
    this.y = y;
    this.width = width;
    this.height = height;
    this.capacity = capacity;
    this.points = [];
    this.divided = false;
  }

  subdivide() {
    const { x, y, height, width } = this;
    const h = height,
      w = width;
    this.nw = new QuadTree(x, y, w / 2, h / 2, this.capacity);
    this.ne = new QuadTree(x + w / 2, y, w / 2, h / 2, this.capacity);
    this.se = new QuadTree(x + w / 2, y + h / 2, w / 2, h / 2, this.capacity);
    this.sw = new QuadTree(x, y + h / 2, w / 2, h / 2, this.capacity);
    this.divided = true;
  }

  // Externally used methods:

  insert(point) {
    if (!"x" in point || !"y" in point) {
      console.log("This point doesn't have X and Y coordinates!", point);
      return;
    }

    if (this.points.length < this.capacity) {
      this.points.push(point);
    } else {
      if (!this.divided) {
        this.subdivide();
      }

      if (point.x <= this.x + this.width / 2) {
        if (point.y <= this.y + this.height / 2) {
          this.nw.insert(point);
        } else {
          this.sw.insert(point);
        }
      } else {
        if (point.y <= this.y + this.height / 2) {
          this.ne.insert(point);
        } else {
          this.se.insert(point);
        }
      }
    }
  }

  queryRect(x, y, w, h, found = []) {
    if (
      x > this.x + this.width ||
      x + w < this.x ||
      y > this.y + this.height ||
      y + h < this.y
    ) {
      return;
    } else {
      this.points.forEach((point) => {
        if (point.x > x && point.x < x + w && point.y > y && point.y < y + h) {
          found.push(point);
        }
      });

      if (this.divided) {
        this.nw.queryRect(x, y, w, h, found);
        this.ne.queryRect(x, y, w, h, found);
        this.sw.queryRect(x, y, w, h, found);
        this.se.queryRect(x, y, w, h, found);
      }
    }
    return found;
  }

  queryCircle(x, y, r) {
    const roughFound = this.queryRect(x - r, y - r, r * 2, r * 2);
    return roughFound.filter((p) => distance(p.x, p.y, x, y) <= r);
  }

  forEach(callback) {
    if (this.points.length >= 1) {
      this.points.forEach((point) => callback(point));
    }

    if (this.divided) {
      this.nw.forEach(callback);
      this.ne.forEach(callback);
      this.se.forEach(callback);
      this.sw.forEach(callback);
    }
  }

  clear() {
    delete this.nw;
    delete this.ne;
    delete this.se;
    delete this.sw;
  }
}