JS快速檢索碰撞圖形之四元樹碰撞檢測

function Quadtree(bounds, max_objects, max_levels, level) {
  this.max_objects = max_objects || 10; // 節點內最大物件數量
  this.max_levels = max_levels || 4; // 樹的最大深度
  this.level = level || 0;
  this.bounds = bounds; // 區域，結構為 {x, y, width, height}
  this.objects = []; // 儲存圖形的地方
  this.nodes = []; // 4 個子節點，到達閥值時才建立
}

// 切割：生成 4 個子節點
Quadtree.prototype.split = function () {
  var nextLevel = this.level + 1,
    subWidth = this.bounds.width / 2,
    subHeight = this.bounds.height / 2,
    x = this.bounds.x,
    y = this.bounds.y;
  // 右上
  this.nodes[0] = new Quadtree(
    {
      x: x + subWidth,
      y: y,
      width: subWidth,
      height: subHeight,
    },
    this.max_objects,
    this.max_levels,
    nextLevel
  );
  // 左上
  this.nodes[1] = new Quadtree(
    {
      x: x,
      y: y,
      width: subWidth,
      height: subHeight,
    },
    this.max_objects,
    this.max_levels,
    nextLevel
  );
  // 左下
  this.nodes[2] = new Quadtree(
    {
      x: x,
      y: y + subHeight,
      width: subWidth,
      height: subHeight,
    },
    this.max_objects,
    this.max_levels,
    nextLevel
  );
  // 右下
  this.nodes[3] = new Quadtree(
    {
      x: x + subWidth,
      y: y + subHeight,
      width: subWidth,
      height: subHeight,
    },
    this.max_objects,
    this.max_levels,
    nextLevel
  );
};

// 找到某個 box 落在在哪個區域
Quadtree.prototype.getIndex = function (pRect) {
  var indexes = [],
    verticalMidpoint = this.bounds.x + this.bounds.width / 2,
    horizontalMidpoint = this.bounds.y + this.bounds.height / 2;
  var startIsNorth = pRect.y < horizontalMidpoint,
    startIsWest = pRect.x < verticalMidpoint,
    endIsEast = pRect.x + pRect.width > verticalMidpoint,
    endIsSouth = pRect.y + pRect.height > horizontalMidpoint;
  // top-right quad
  if (startIsNorth && endIsEast) {
    indexes.push(0);
  }
  // top-left quad
  if (startIsWest && startIsNorth) {
    indexes.push(1);
  }
  // bottom-left quad
  if (startIsWest && endIsSouth) {
    indexes.push(2);
  }
  // bottom-right quad
  if (endIsEast && endIsSouth) {
    indexes.push(3);
  }
  return indexes;
};

Quadtree.prototype.insert = function (pRect) {
  var i = 0,
    indexes;
  // 存在子節點，則插入到子節點
  if (this.nodes.length) { 
    indexes = this.getIndex(pRect); // 找到索引位置
    for (i = 0; i < indexes.length; i++) {
      this.nodes[indexes[i]].insert(pRect); // 遞迴 insert
    }
    return;
  }
  // 沒有子節點，不是索引層，圖形放到前節點下
  // （有個小 BUG，就是不在範圍內的圖形也加上去了）
  this.objects.push(pRect);
  // 如果物件太多，構建子節點
  if (
    this.objects.length > this.max_objects &&
    this.level < this.max_levels
  ) {
    if (!this.nodes.length) {
      this.split();
    }
    // 將 objects 取出，放入這些子節點中
    for (i = 0; i < this.objects.length; i++) {
      indexes = this.getIndex(this.objects[i]);
      for (var k = 0; k < indexes.length; k++) {
        this.nodes[indexes[k]].insert(this.objects[i]);
      }
    }
    this.objects = [];
  }
};

// 傳入一個矩形，取出它所在節點的所有矩形
// 這個方法能返回
Quadtree.prototype.retrieve = function (pRect) {
  // 提取目標矩形所在區間下的所有矩形
  var indexes = this.getIndex(pRect),
    returnObjects = this.objects;
  // 可能需要遞迴。
  //if we have subnodes, retrieve their objects
  if (this.nodes.length) {
    for (var i = 0; i < indexes.length; i++) {
      returnObjects = returnObjects.concat(
        this.nodes[indexes[i]].retrieve(pRect)
      );
    }
  }
  // 移除重複的節點
  returnObjects = returnObjects.filter(function (item, index) {
    return returnObjects.indexOf(item) >= index;
  });
  return returnObjects;
};