Quadtree

四叉树的划分

const WIDTH = Math.min(window.innerWidth, window.innerHeight, 480);

let qtree;

function setup() {
  createCanvas(400, 400);
  let boundary = new Rectangle(200, 200, 200, 200);
  qtree = new QuadTree(boundary, 4);
  for (let i = 0; i < 20; i++) {
    let p = new Point(random(width), random(height));
    qtree.insert(p);
  }
}

function draw() {
  if (mouseIsPressed) {
    let p = new Point(mouseX, mouseY);
    qtree.insert(p);
  }
  background(51);
  qtree.show();
}

QuadTree.js

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

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
    );
  }
}

class QuadTree {
  constructor(boundary, n) {
    this.boundary = boundary;
    this.capacity = n;
    this.points = [];
    this.divided = false;
  }

  subdivide() {
    let x = this.boundary.x;
    let y = this.boundary.y;
    let w = this.boundary.w;
    let h = this.boundary.h;
    // 右下角 第一象限 ++
    let se = new Rectangle(x + w / 2, y + h / 2, w / 2, h / 2);
    this._southeast = new QuadTree(se, this.capacity);
    // 左下角 第二象限 +-
    let sw = new Rectangle(x - w / 2, y + h / 2, w / 2, h / 2);
    this._southwest = new QuadTree(sw, this.capacity);
    // 左上角 第三象限 --
    let nw = new Rectangle(x - w / 2, y - h / 2, w / 2, h / 2);
    this._northwest = new QuadTree(nw, this.capacity);
    // 右上角 第四象限 -+
    let ne = new Rectangle(x + w / 2, y - h / 2, w / 2, h / 2);
    this._northeast = new QuadTree(ne, 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;
    } else {
      if (!this.divided) {
        this.subdivide();
      }
      if (this._southeast.insert(point)) {
        return true;
      } else if (this._southwest.insert(point)) {
        return true;
      } else if (this._northwest.insert(point)) {
        return true;
      } else if (this._northeast.insert(point)) {
        return true;
      }
    }
  }

  show() {
    stroke(255, 10);
    strokeWeight(1);
    noFill();
    rectMode(CENTER);
    rect(
      this.boundary.x,
      this.boundary.y,
      this.boundary.w * 2,
      this.boundary.h * 2
    );
    if (this.divided) {
      this._southwest.show();
      this._southeast.show();
      this._northwest.show();
      this._northeast.show();
    }
    stroke(255);
    strokeWeight(2);
    this.points.forEach((p) => {
      point(p.x, p.y);
    });
  }
}

四叉树的矩形搜索

const WIDTH = Math.min(window.innerWidth, window.innerHeight, 480);

let qtree;

function setup() {
  createCanvas(WIDTH, WIDTH);
  let boundary = new Rectangle(width / 2, height / 2, width / 2, height / 2);
  qtree = new QuadTree(boundary, 4);
  for (let i = 0; i < 1024; i++) {
    let x = randomGaussian(width / 2, width / 8);
    let y = randomGaussian(height / 2, height / 8);
    let p = new Point(x, y);
    qtree.insert(p);
  }
}

function draw() {
  background(51);
  qtree.show();
  let range = new Rectangle(mouseX, mouseY, width / 8, height / 8);
  stroke(0, 255, 0);
  rectMode(CENTER);
  strokeWeight(1);
  rect(range.x, range.y, range.w * 2, range.h * 2);
  let found = qtree.queryRange(range);
  found.forEach((p) => {
    strokeWeight(2);
    point(p.x, p.y);
  });
}

QuadTree.js

class Point {
  constructor(x, y) {
    this.x = x;
    this.y = y;
  }
}

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
    )
  }
}

class QuadTree {
  constructor(boundary, n) {
    this.boundary = boundary;
    this.capacity = n;
    this.points = [];
    this.divided = false;
  }

  subdivide() {
    let x = this.boundary.x;
    let y = this.boundary.y;
    let w = this.boundary.w;
    let h = this.boundary.h;
    // 右下角 第一象限 ++
    let se = new Rectangle(x + w / 2, y + h / 2, w / 2, h / 2);
    this._southeast = new QuadTree(se, this.capacity);
    // 左下角 第二象限 +-
    let sw = new Rectangle(x - w / 2, y + h / 2, w / 2, h / 2);
    this._southwest = new QuadTree(sw, this.capacity);
    // 左上角 第三象限 --
    let nw = new Rectangle(x - w / 2, y - h / 2, w / 2, h / 2);
    this._northwest = new QuadTree(nw, this.capacity);
    // 右上角 第四象限 -+
    let ne = new Rectangle(x + w / 2, y - h / 2, w / 2, h / 2);
    this._northeast = new QuadTree(ne, 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;
    } else {
      if (!this.divided) {
        this.subdivide();
      }
      if (this._southeast.insert(point)) {
        return true;
      } else if (this._southwest.insert(point)) {
        return true;
      } else if (this._northwest.insert(point)) {
        return true;
      } else if (this._northeast.insert(point)) {
        return true;
      }
    }
  }

  queryRange(range, found = []) {
    if( !this.boundary.intersects(range)) {
      // empty array
      return found;
    } else {
      // check point
      this.points.forEach(p => {
        if(range.contains(p)){
          found.push(p)
        }
      })
      // check divide
      if (this.divided) {
        this._northeast.queryRange(range, found);
        this._northwest.queryRange(range, found);
        this._southeast.queryRange(range, found);
        this._southwest.queryRange(range, found);
      }
      return found;
    }
  }

  show() {
    stroke(255, 10);
    strokeWeight(1);
    noFill();
    rectMode(CENTER);
    rect(
      this.boundary.x,
      this.boundary.y,
      this.boundary.w * 2,
      this.boundary.h * 2
    );
    if (this.divided) {
      this._southwest.show();
      this._southeast.show();
      this._northwest.show();
      this._northeast.show();
    }
    stroke(255);
    strokeWeight(2);
    this.points.forEach((p) => {
      point(p.x, p.y);
    });
  }
}

四叉树运用在碰撞检测中

const WIDTH = Math.min(window.innerWidth, window.innerHeight, 480);

const particles = [];

function setup() {
  createCanvas(WIDTH, WIDTH);

  for (let i = 0; i < 1024; i++) {
    const particle = new Particle(random(width), random(height), random(2, 4));
    particles.push(particle);
  }
}

function draw() {
  background(51);

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

  particles.forEach((p) => {
    const point = new Point(p.x, p.y, p);
    qtree.insert(point);
  });
  particles.forEach((p) => {
    p.move();
    p.render();
    p.setHighlight(false);
  });

  qtree.show();

  // n
  for (let p of particles) {
    let range = new Rectangle(p.x, p.y, 16, 16);
    // log(n)
    let points = qtree.queryRange(range);
    for (let point of points) {
      let other = point.userData;
      if (p !== other && p.intersects(other)) {
        p.setHighlight(true);
      }
    }
  }
}

Particle.js

class Particle {
  constructor(x, y, r = 8) {
    this.x = x;
    this.y = y;
    this.r = r;
    this.highlight = false;
  }

  move() {
    this.x += random(-1, 1);
    this.y += random(-1, 1);
  }

  intersects(other) {
    let d = dist(this.x, this.y, other.x, other.y);
    return d < this.r + other.r;
  }
  setHighlight(value) {
    this.highlight = value;
  }

  render() {
    noStroke();
    if (this.highlight) {
      fill(255);
    } else {
      fill(128);
    }
    ellipse(this.x, this.y, this.r * 2);
  }
}

Quadtree.js

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
    )
  }
}

class QuadTree {
  constructor(boundary, capacity = 4) {
    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;
    let h = this.boundary.h;
    // 右下角 第一象限 ++
    let se = new Rectangle(x + w / 2, y + h / 2, w / 2, h / 2);
    this._southeast = new QuadTree(se, this.capacity);
    // 左下角 第二象限 +-
    let sw = new Rectangle(x - w / 2, y + h / 2, w / 2, h / 2);
    this._southwest = new QuadTree(sw, this.capacity);
    // 左上角 第三象限 --
    let nw = new Rectangle(x - w / 2, y - h / 2, w / 2, h / 2);
    this._northwest = new QuadTree(nw, this.capacity);
    // 右上角 第四象限 -+
    let ne = new Rectangle(x + w / 2, y - h / 2, w / 2, h / 2);
    this._northeast = new QuadTree(ne, 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;
    } else {
      if (!this.divided) {
        this.subdivide();
      }
      if (this._southeast.insert(point)) {
        return true;
      } else if (this._southwest.insert(point)) {
        return true;
      } else if (this._northwest.insert(point)) {
        return true;
      } else if (this._northeast.insert(point)) {
        return true;
      }
    }
  }

  queryRange(range, found = []) {
    if( !this.boundary.intersects(range)) {
      // empty array
      return found;
    } else {
      // check point
      this.points.forEach(p => {
        if(range.contains(p)){
          found.push(p)
        }
      })
      // check divide
      if (this.divided) {
        this._northeast.queryRange(range, found);
        this._northwest.queryRange(range, found);
        this._southeast.queryRange(range, found);
        this._southwest.queryRange(range, found);
      }
      return found;
    }
  }

  show() {
    stroke(255, 10);
    strokeWeight(1);
    noFill();
    rectMode(CENTER);
    rect(
      this.boundary.x,
      this.boundary.y,
      this.boundary.w * 2,
      this.boundary.h * 2
    );
    if (this.divided) {
      this._southwest.show();
      this._southeast.show();
      this._northwest.show();
      this._northeast.show();
    }
    stroke(255);
    strokeWeight(2);
    this.points.forEach((p) => {
      point(p.x, p.y);
    });
  }
}