Work in progress...

quadtree.js

const ArrayExtensions = {
  remove(array, needle) {
    const index = array.indexOf(needle);

    if (index !== -1) {
      array.splice(index, 1);
      return index;
    }

    return false;
  }
};


class Quadtree {
  
  add(entity) {
    this._entities.push(entity);
  }

  remove() {
    ArrayExtensions.remove(this._entities, entity);
  }
  
  update(entity) {

  }

  process() {

  }

}


class Leaf {

  get length() {
    return this._entities.length;
  }

  get shouldSplit() {
    return this._entities.length > this._maxEntities;
  }

  constructor(area, maxEntities) {
    this._area = area;
    this._maxEntities = maxEntities;
    this._entities = [];
  }

  add(entity) {
    this._entities.push(entity);
  }

  remove(entity) {
    ArrayExtensions.remove(this._entities, entity);
  }

  getEntities() {
    return this._entities;
  }

  toBranch() {
    const branch = new Branch(this._area);
    this._entities.forEach(entity => branch.add(entity));
    return branch;
  }

}


class Branch {

  get length() {
    return this.a.length + this.b.length + this.c.length + this.d.length;
  }



  constructor(area) {
    const halfSize = area.size.divideValue(2);

    this._area = area;
    this.center = area.pos.add(halfSize);

    this.a = new Leaf(new Rectangle(area.pos, halfSize));
    this.b = new Leaf(new Rectangle(area.pos.add({ x: halfSize.x }), halfSize));
    this.c = new Leaf(new Rectangle(area.pos.add({ y: halfSize.y }), halfSize));
    this.d = new Leaf(new Rectangle(area.pos.add(halfSize), halfSize));
  }

  add(entity) {
    const leaf = this._getLeafFor(entity)
    leaf.add(entity);
    
    if (leaf.shouldSplit) {
      
    }
  }

  remove(entity) {
    this._getLeafFor(entity).remove(entity);
  }

  getEntities() {
    return [].concat(
      this.a.getEntities(),
      this.b.getEntities(),
      this.c.getEntities(),
      this.d.getEntities(),
    );
  }

  toLeaf() {
    const leaf = new Leaf(this._area);
    leaf._entities = this.getEntities();
    return leaf;
  }

  _getLeafFor(entity) {
    const relative = entity.pos.subtract(this.center);

    if (relative.x < 0 && relative.y < 0) {
      return this.a;
    } else if (relative.y < 0) {
      return this.b;
    } else if (relative.x < 0) {
      return this.c;
    } else {
      return this.d;
    }
  }

}