Basic quadtree implementation in JS

quadtree.js

const CAPACITY = 8;

class QuadTree {
  constructor(x, y, w, h) {
    // the rect (x,y,w,h) defines the product of two half-open intervals: [x, x+w) × [y, y+h)
    this.x = x; this.xe = x + w;  
    this.y = y; this.ye = y + h;
    this.w = w;
    this.h = h;
    this.pts = [];
    this.length = 0;
    this.nw = null; // todo: test if this helps perf
    this.ne = null;
    this.se = null;
    this.sw = null;    
  }

  add(p) {
    if (this.pts.length < CAPACITY) {
      this.pts.push(p);
    } else {
      const hw = this.w * .5, hh = this.h * .5;
      const x0 = this.x, y0 = this.y;
      const x1 = x0 + hw, y1 = y0 + hh;
      if (this.nw === null) { 
        this.nw = new QuadTree(x0, y0, hw, hh);
        this.ne = new QuadTree(x1, y0, hw, hh);
        this.se = new QuadTree(x1, y1, hw, hh);
        this.sw = new QuadTree(x0, y1, hw, hh);
      }
      if (p.x < x1) {
        if (p.y < y1) { this.nw.add(p); } else { this.sw.add(p); }
      } else {
        if (p.y < y1) { this.ne.add(p); } else { this.se.add(p); }
      }
    }
    this.length++;
  }

  *rect(x, y, w, h) {
    const xe = x + w, ye = y + h;
    if (x <= this.xe && xe >= this.x && y <= this.ye && ye >= this.y ) {
      yield* this.pts.filter(
        ({x:px, y:py}) => px >= x && px <= xe && py >= y && py <= ye);
      if (this.nw !== null) {
        yield* this.nw.rect(x, y, w, h);
        yield* this.ne.rect(x, y, w, h);
        yield* this.sw.rect(x, y, w, h);
        yield* this.se.rect(x, y, w, h);
      }
    }
  }

  hit(x, y, w, h) {
    // yeah!
    const xe = x + w, ye = y + h;
    return ((x <= this.xe && xe >= this.x && y <= this.ye && ye >= this.y)
      && (this.pts.some(({x:px, y:py}) => px >= x && px <= xe && py >= y && py <= ye)
          || (this.nw !== null
              && (this.nw.hit(x, y, w, h) || this.ne.hit(x, y, w, h) 
                  || this.sw.hit(x, y, w, h) || this.se.hit(x, y, w, h))))
      );
  }

  *circle(x, y, r) {
    const r2 = r * r;
    yield* this.rect(x - r, y - r, r * 2, r * 2)
      .filter(({x:px, y:py}) => (px - x) ** 2 + (py - y) ** 2 < r2);
  }

  // circle_hit(x, y, r) {
  //   const r2 = r * r;
  //   const result = this.rect(x - r, y - r, r * 2, r * 2);
  //   return result.some((p) => (p.x - x) ** 2 + (p.y - y) ** 2 < r2);
  // }

  *[Symbol.iterator]() {
    yield* this.pts;
    if (this.nw) {
      yield* this.nw;
      yield* this.ne;
      yield* this.se;
      yield* this.sw;
    }
  }

  clear() {
    this.pts = [];
    this.length = 0;
    this.nw = null;
    this.ne = null;
    this.se = null;
    this.sw = null;
  }
}