JS實現(xiàn)的四叉樹算法詳解

更新時間：2018年12月21日 10:00:38 作者：huansky

這篇文章主要介紹了JS實現(xiàn)的四叉樹算法,簡單分析了四叉樹的相關(guān)概念、原理、實現(xiàn)方法及操作注意事項,需要的朋友可以參考下

本文實例講述了JS實現(xiàn)的四叉樹算法。分享給大家供大家參考，具體如下：

最近在看canvas動畫方面教程，里面提到了采用四叉樹檢測碰撞。之前也看到過四叉樹這個名詞，但是一直不是很懂。于是就又找了一些四叉樹方面的資料看了看，做個筆記，就算日后忘了，也可以回來看看。

QuadTree四叉樹顧名思義就是樹狀的數(shù)據(jù)結(jié)構(gòu)，其每個節(jié)點有四個孩子節(jié)點，可將二維平面遞歸分割子區(qū)域。QuadTree常用于空間數(shù)據(jù)庫索引，3D的椎體可見區(qū)域裁剪，甚至圖片分析處理，我們今天介紹的是QuadTree最常被游戲領(lǐng)域使用到的碰撞檢測。采用QuadTree算法將大大減少需要測試碰撞的次數(shù)，從而提高游戲刷新性能，

四叉樹很簡單，就是把一塊2d的區(qū)域，等分成4份,如下圖: 我們把4塊區(qū)域從右上象限開始編號，逆時針。

四叉樹起始于單節(jié)點。對象會被添加到四叉樹的單節(jié)點上。

當更多的對象被添加到四叉樹里時，它們最終會被分為四個子節(jié)點。（我是這么理解的：下面的圖片不是分為四個區(qū)域嗎，每個區(qū)域就是一個孩子或子節(jié)點）然后每個物體根據(jù)他在2D空間的位置而被放入這些子節(jié)點中的一個里。任何不能正好在一個節(jié)點區(qū)域內(nèi)的物體會被放在父節(jié)點。（這點我不是很理解，就這幅圖來說，那根節(jié)點的子節(jié)點豈不是有五個節(jié)點了。）

如果有更多的對象被添加進來，那么每個子節(jié)點要繼續(xù)劃分（成四個節(jié)點）。

正如你看到的，每個節(jié)點僅包括幾個物體。這樣我們就可以明白前面所說的規(guī)則，例如，左上角節(jié)點里的物體是不可能和右下角節(jié)點里的物體碰撞的。所以我們也就沒必要運行消耗很多資源的碰撞檢測算法來檢驗他們之間是否會發(fā)生碰撞。

下面我們對四叉樹進行實現(xiàn)：

主要代碼：（代碼是從整個四叉樹類里面拷貝出來的，所以帶有this，大家不要無視就好，末尾附有完整的代碼）

function QuadTree(boundBox, lvl) {
  var maxObjects = 10;
  this.bounds = boundBox || {
    x: 0,
    y: 0,
    width: 0,
    height: 0
  };
  var objects = [];
  this.nodes = [];
  var level = lvl || 0;
  var maxLevels = 5;
}

maxObjects是每個節(jié)點能容納的最多對象超過則分割4個節(jié)點, 我們并不是事先就分好格子，而是在插入對象的時候才進行劃分。

maxLevels是四叉樹的最大層數(shù) 超過則不再劃分從根節(jié)點開始最多6 層。

level：當前層數(shù)

objects: 當前節(jié)點內(nèi)的待檢測的對象。

bounds：當前節(jié)點所表示的2d區(qū)域的范圍

nodes: 4個子節(jié)點隊列。

四叉樹每個節(jié)點的面積可以為任意形狀。然后，我們會使用五個四叉樹里會用到的方法，分別為：clear,split,getIndex,insert和retrieve。

function clear() {
    objects = [];
    for (var i = 0; i < this.nodes.length; i++) {
      this.nodes[i].clear();
    }
    this.nodes = [];
  };

Clear函數(shù)，是通過循環(huán)來清除四叉樹所有節(jié)點的所有對象。

function split() {
    // Bitwise or [html5rocks]
    var subWidth = (this.bounds.width / 2) | 0;
    var subHeight = (this.bounds.height / 2) | 0;
    this.nodes[0] = new QuadTree({
      x: this.bounds.x + subWidth,
      y: this.bounds.y,
      width: subWidth,
      height: subHeight
    }, level+1);
    this.nodes[1] = new QuadTree({
      x: this.bounds.x,
      y: this.bounds.y,
      width: subWidth,
      height: subHeight
    }, level+1);
    this.nodes[2] = new QuadTree({
      x: this.bounds.x,
      y: this.bounds.y + subHeight,
      width: subWidth,
      height: subHeight
    }, level+1);
    this.nodes[3] = new QuadTree({
      x: this.bounds.x + subWidth,
      y: this.bounds.y + subHeight,
      width: subWidth,
      height: subHeight
    }, level+1);
}

Split 方法，就是用來將節(jié)點分成相等的四份面積，并用新的邊界來初始化四個新的子節(jié)點。

function getIndex(obj) {
    var index = -1;
    var verticalMidpoint = this.bounds.x + this.bounds.width / 2;
    var horizontalMidpoint = this.bounds.y + this.bounds.height / 2;
    // Object can fit completely within the top quadrant
    var topQuadrant = (obj.y < horizontalMidpoint && obj.y + obj.height < horizontalMidpoint);
    // Object can fit completely within the bottom quandrant
    var bottomQuadrant = (obj.y > horizontalMidpoint);
    // Object can fit completely within the left quadrants
    if (obj.x < verticalMidpoint &&
        obj.x + obj.width < verticalMidpoint) {
      if (topQuadrant) {
        index = 1;
      }
      else if (bottomQuadrant) {
        index = 2;
      }
    }
    // Object can fix completely within the right quandrants
    else if (obj.x > verticalMidpoint) {
      if (topQuadrant) {
        index = 0;
      }
      else if (bottomQuadrant) {
        index = 3;
      }
    }
    return index;
};

getIndex 方法是個四叉樹的輔助方法，在四叉樹里，他決定了一個節(jié)點的歸屬，通過檢查節(jié)點屬于哪個象限。（最上面第一幅圖不是逆時針在一個面積里劃分了四塊面積，上面標示了他們的序號，這個方法就是算在一個父節(jié)點里他的子節(jié)點的序號）

比如當前區(qū)域是Rectange(0, 0, 600, 600) 待檢測矩形是Rectangel(0, 0, 30, 30) 那么他就在左上象限 index = 1 如果是Rectange(400, 400, 30, 30) 那么他就在右下象限 index = 3

function insert(obj) {
    if (typeof obj === "undefined") {
      return;
    }
    if (obj instanceof Array) {
      for (var i = 0, len = obj.length; i < len; i++) {
        this.insert(obj[i]);
      }
      return;
    }
    if (this.nodes.length) {
      var index = this.getIndex(obj);
      // Only add the object to a subnode if it can fit completely
      // within one
      if (index != -1) {
        this.nodes[index].insert(obj);
        return;
      }
    }
    objects.push(obj);
    // Prevent infinite splitting
    if (objects.length > maxObjects && level < maxLevels) {
      if (this.nodes[0] == null) {
        this.split();
      }
      var i = 0;
      while (i < objects.length) {
        var index = this.getIndex(objects[i]);
        if (index != -1) {
          this.nodes[index].insert((objects.splice(i,1))[0]);
        }
        else {
          i++;
        }
      }
    }
};

每次插入一個對象我們都先看看當前節(jié)點有沒有子節(jié)點如果有我們就插入子節(jié)點。一直檢測到他沒有子節(jié)點為止我們就把對象插入到這個節(jié)點，如果這個節(jié)點的對象數(shù)量 > 10個并且當前節(jié)點的層數(shù) < MAX_LEVELS 我們就把節(jié)點繼續(xù)劃分4個子節(jié)點。然后把當前對象循環(huán) 刪除并插入子節(jié)點。如果對象在中心線上，getIndex會返回-1，所以這些對象會被插入到父節(jié)點上面。

一旦對象添加上后，要看看這個節(jié)點會不會分裂，可以通過檢查對象被加入節(jié)點后有沒有超過一個節(jié)點最大容納對象的數(shù)量。分裂起源于節(jié)點可以插入任何對象，這個對象只要符合子節(jié)點都可以被加入。否則就加入到父節(jié)點。

function retrieve(returnedObjects, obj) {
    if (typeof obj === "undefined") {
      console.log("UNDEFINED OBJECT");
      return;
    }
    var index = this.getIndex(obj);
    if (index != -1 && this.nodes.length) {
      this.nodes[index].findObjects(returnedObjects, obj);
    }
    for (var i = 0, len = objects.length; i < len; i++) {
      returnedObjects.push(objects[i]);
    }
    return returnedObjects;
};

最后一個四叉樹的方法就是 retrieve 方法，他返回了與指定節(jié)點可能發(fā)生碰撞的所有節(jié)點（就是不停尋找與所給節(jié)點在同樣象限的節(jié)點）。這個方法成倍的減少碰撞檢測數(shù)量。

四叉樹的代碼就到這里為止了。

完整的代碼如下：

完整的代碼中retrieve就是findObjects。

/**
 * QuadTree object.
 *
 * The quadrant indexes are numbered as below:
 *   |
 * 1 | 0
 * ----+----
 * 2 | 3
 *   |
 */
function QuadTree(boundBox, lvl) {
  var maxObjects = 10;
  this.bounds = boundBox || {
    x: 0,
    y: 0,
    width: 0,
    height: 0
  };
  var objects = [];
  this.nodes = [];
  var level = lvl || 0;
  var maxLevels = 5;
  /*
   * Clears the quadTree and all nodes of objects
   */
  this.clear = function() {
    objects = [];
    for (var i = 0; i < this.nodes.length; i++) {
      this.nodes[i].clear();
    }
    this.nodes = [];
  };
  /*
   * Get all objects in the quadTree
   */
  this.getAllObjects = function(returnedObjects) {
    for (var i = 0; i < this.nodes.length; i++) {
      this.nodes[i].getAllObjects(returnedObjects);
    }
    for (var i = 0, len = objects.length; i < len; i++) {
      returnedObjects.push(objects[i]);
    }
    return returnedObjects;
  };
  /*
   * Return all objects that the object could collide with
   */
  this.findObjects = function(returnedObjects, obj) {
    if (typeof obj === "undefined") {
      console.log("UNDEFINED OBJECT");
      return;
    }
    var index = this.getIndex(obj);
    if (index != -1 && this.nodes.length) {
      this.nodes[index].findObjects(returnedObjects, obj);
    }
    for (var i = 0, len = objects.length; i < len; i++) {
      returnedObjects.push(objects[i]);
    }
    return returnedObjects;
  };
  /*
   * Insert the object into the quadTree. If the tree
   * excedes the capacity, it will split and add all
   * objects to their corresponding nodes.
   */
  this.insert = function(obj) {
    if (typeof obj === "undefined") {
      return;
    }
    if (obj instanceof Array) {
      for (var i = 0, len = obj.length; i < len; i++) {
        this.insert(obj[i]);
      }
      return;
    }
    if (this.nodes.length) {
      var index = this.getIndex(obj);
      // Only add the object to a subnode if it can fit completely
      // within one
      if (index != -1) {
        this.nodes[index].insert(obj);
        return;
      }
    }
    objects.push(obj);
    // Prevent infinite splitting
    if (objects.length > maxObjects && level < maxLevels) {
      if (this.nodes[0] == null) {
        this.split();
      }
      var i = 0;
      while (i < objects.length) {
        var index = this.getIndex(objects[i]);
        if (index != -1) {
          this.nodes[index].insert((objects.splice(i,1))[0]);
        }
        else {
          i++;
        }
      }
    }
  };
  /*
   * Determine which node the object belongs to. -1 means
   * object cannot completely fit within a node and is part
   * of the current node
   */
  this.getIndex = function(obj) {
    var index = -1;
    var verticalMidpoint = this.bounds.x + this.bounds.width / 2;
    var horizontalMidpoint = this.bounds.y + this.bounds.height / 2;
    // Object can fit completely within the top quadrant
    var topQuadrant = (obj.y < horizontalMidpoint && obj.y + obj.height < horizontalMidpoint);
    // Object can fit completely within the bottom quandrant
    var bottomQuadrant = (obj.y > horizontalMidpoint);
    // Object can fit completely within the left quadrants
    if (obj.x < verticalMidpoint &&
        obj.x + obj.width < verticalMidpoint) {
      if (topQuadrant) {
        index = 1;
      }
      else if (bottomQuadrant) {
        index = 2;
      }
    }
    // Object can fix completely within the right quandrants
    else if (obj.x > verticalMidpoint) {
      if (topQuadrant) {
        index = 0;
      }
      else if (bottomQuadrant) {
        index = 3;
      }
    }
    return index;
  };
  /*
   * Splits the node into 4 subnodes
   */
  this.split = function() {
    // Bitwise or [html5rocks]
    var subWidth = (this.bounds.width / 2) | 0;
    var subHeight = (this.bounds.height / 2) | 0;
    this.nodes[0] = new QuadTree({
      x: this.bounds.x + subWidth,
      y: this.bounds.y,
      width: subWidth,
      height: subHeight
    }, level+1);
    this.nodes[1] = new QuadTree({
      x: this.bounds.x,
      y: this.bounds.y,
      width: subWidth,
      height: subHeight
    }, level+1);
    this.nodes[2] = new QuadTree({
      x: this.bounds.x,
      y: this.bounds.y + subHeight,
      width: subWidth,
      height: subHeight
    }, level+1);
    this.nodes[3] = new QuadTree({
      x: this.bounds.x + subWidth,
      y: this.bounds.y + subHeight,
      width: subWidth,
      height: subHeight
    }, level+1);
  };
}

參考文章：

Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)學運算用法總結(jié)》、《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)組操作技巧總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯誤與調(diào)試技巧總結(jié)》

希望本文所述對大家JavaScript程序設(shè)計有所幫助。

您可能感興趣的文章: