​

class Point {

  constructor(x, y, userData) {

    this.x = x;

    this.y = y;

    this.userData = userData;

  }

}

​

class Rectangle {

  constructor(x, y, w, h) {

    this.x = x;

    this.y = y;

    this.w = w;

    this.h = h;

  }

​

  contains(point) {

    return (point.x >= this.x - this.w &&

      point.x <= this.x + this.w &&

      point.y >= this.y - this.h &&

      point.y <= this.y + this.h);

  }

​

  intersects(range) {

    return !(range.x - range.w > this.x + this.w ||

      range.x + range.w < this.x - this.w ||

      range.y - range.h > this.y + this.h ||

      range.y + range.h < this.y - this.h);

  }

}

​

// circle class for a circle shaped query

class Circle {

  constructor(x, y, r) {

    this.x = x;

    this.y = y;

    this.r = r;

    this.rSquared = this.r * this.r;

  }

​

  contains(point) {

    // check if the point is in the circle by checking if the euclidean distance of

    // the point and the center of the circle if smaller or equal to the radius of

    // the circle

    let d = Math.pow((point.x - this.x), 2) + Math.pow((point.y - this.y), 2);

    return d <= this.rSquared;

  }

​

  intersects(range) {

​

    var xDist = Math.abs(range.x - this.x);

    var yDist = Math.abs(range.y - this.y);

​

    // radius of the circle

    var r = this.r;

​

    var w = range.w;

    var h = range.h;

​

    var edges = Math.pow((xDist - w), 2) + Math.pow((yDist - h), 2);

​

    // no intersection

    if (xDist > (r + w) || yDist > (r + h))

      return false;

​

    // intersection within the circle

    if (xDist <= w || yDist <= h)

      return true;

​

    // intersection on the edge of the circle

    return edges <= this.rSquared;

  }

}

​

// ##### Quadtree Class

​

class QuadTree {

  constructor(boundary, capacity) {

    if (!boundary) {

      throw TypeError('boundary is null or undefined');

    }

    if (!(boundary instanceof Rectangle)) {

      throw TypeError('boundary should be a Rectangle');

    }

    if (typeof capacity !== 'number') {

      throw TypeError(`capacity should be a number but is a ${typeof capacity}`);

    }

    if (capacity < 1) {

      throw RangeError('capacity must be greater than 0');

    }

    this.boundary = boundary;

    this.capacity = capacity;

    this.points = [];

    this.divided = false;

  }

​

  subdivide() {

    let x = this.boundary.x;

    let y = this.boundary.y;

    let w = this.boundary.w / 2;

    let h = this.boundary.h / 2;

​

    let ne = new Rectangle(x + w, y - h, w, h);

    this.northeast = new QuadTree(ne, this.capacity);

    let nw = new Rectangle(x - w, y - h, w, h);

    this.northwest = new QuadTree(nw, this.capacity);

    let se = new Rectangle(x + w, y + h, w, h);

    this.southeast = new QuadTree(se, this.capacity);

    let sw = new Rectangle(x - w, y + h, w, h);

    this.southwest = new QuadTree(sw, this.capacity);

​

    this.divided = true;

  }

​

  insert(point) {

    if (!this.boundary.contains(point)) {

      return false;

    }

​

    if (this.points.length < this.capacity) {

      this.points.push(point);

      return true;

    }

​

    if (!this.divided) {

      this.subdivide();

    }

​

    if (this.northeast.insert(point) || this.northwest.insert(point) ||

      this.southeast.insert(point) || this.southwest.insert(point)) {

      return true;

    }

  }

​

  query(range, found) {

    if (!found) {

      found = [];

    }

​

    if (!range.intersects(this.boundary)) {

      return found;

    }

​

    for (let p of this.points) {

      if (range.contains(p)) {

        found.push(p);

      }

    }

    if (this.divided) {

      this.northwest.query(range, found);

      this.northeast.query(range, found);

      this.southwest.query(range, found);

      this.southeast.query(range, found);

    }

​

    return found;

  }

​

  render() {

    noFill();

    strokeWeight(0.5);

    stroke(100);

    rectMode(CENTER);

​

    if (this.divided) {

      this.northwest.render();

      this.northeast.render();

      this.southwest.render();

      this.southeast.render();

    }

    else{

          rect(this.boundary.x, this.boundary.y, this.boundary.w*2-3, this.boundary.h*2-3);

    }

  }

}

​

// ##### Particle Class

​

class Particle {

  constructor(x, y) {

    this.x = x;

    this.y = y;

    this.r = 4;

    this.highlight = false;

  }

​

  intersects(other) {

    let d = dist(this.x, this.y, other.x, other.y);

    return (d < this.r + other.r);

  }

​

  setHighlight(value) {

    this.highlight = value;

  }

​

  move() {

    this.x += random(-1, 1);

    this.y += random(-1, 1);

  }

​

  render() {

    noStroke();

    if (this.highlight) {

      fill(0,255,0);

    } else {

      fill(100);

    }

    circle(this.x, this.y, this.r);

  }

​

}

​

// ##### Main Sketch

​

let particles = [];

​

function setup() {

  createCanvas(600, 600);

  for (let i = 0; i < width; i++) {

    particles[i] = new Particle(random(width), random(height));

  }

}

​

function draw() {

  background(255);

​

​

  let boundary = new Rectangle(width/2, height/2, width, height);

  let qtree = new QuadTree(boundary, 5);

​

  for (let p of particles) {

    let point = new Point(p.x, p.y, p);

    qtree.insert(point);

​

​

    p.move();

    p.render();

    p.setHighlight(false);

  }

​

  for (let p of particles) {

    let range = new Circle(p.x, p.y, p.r * 2);

    let points = qtree.query(range);

    for (let point of points) {

      let other = point.userData;

      // for (let other of particles) {

      if (p !== other && p.intersects(other)) {

        p.setHighlight(true);

      }

    }

  }

    qtree.render();

}