欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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è)計有所幫助。

相關(guān)文章

  • javascript實現(xiàn)別踩白塊兒小游戲程序

    javascript實現(xiàn)別踩白塊兒小游戲程序

    我們先看到的未開始的頁面黑色和白色方塊是隨機生成的，完了這么多把沒有發(fā)現(xiàn)時固定不變的。點擊一次方塊，程序需要判斷是黑色還是白色的。如果是黑色的，當然程序也是實現(xiàn)了一次自減，在動畫中是實現(xiàn)一次下移的，下移的時候點擊的方塊到黃顏色的區(qū)域會變成灰色
    2015-11-11
  • 實例解析ES6 Proxy使用場景介紹

    實例解析ES6 Proxy使用場景介紹

    本篇文章主要介紹了ES6 Proxy使用場景介紹，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
    2018-01-01
  • 微信小程序圖片左右擺動效果詳解

    微信小程序圖片左右擺動效果詳解

    這篇文章主要介紹了微信小程序圖片左右擺動效果詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
    2019-07-07
  • JavaScript輸出所選擇起始與結(jié)束日期的方法

    JavaScript輸出所選擇起始與結(jié)束日期的方法

    這篇文章主要介紹了JavaScript輸出所選擇起始與結(jié)束日期的方法,涉及javascript結(jié)合HTML5元素操作日期運算的相關(guān)實現(xiàn)技巧,需要的朋友可以參考下
    2017-07-07
  • 從父頁面讀取和操作iframe中內(nèi)容方法

    從父頁面讀取和操作iframe中內(nèi)容方法

    在父頁面中訪問iframe中的各個元素與一般的訪問頁面元素無本質(zhì)區(qū)別，無非是需要在父頁面中事先獲取需要處理的iframe對象，在獲取iframe對象后，其操作基本沒什么特別之處。
    2009-07-07
  • JS加ASP二級域名轉(zhuǎn)向的代碼

    JS加ASP二級域名轉(zhuǎn)向的代碼

    JS加ASP二級域名轉(zhuǎn)向的代碼...
    2007-05-05
  • JS打字效果的動態(tài)菜單代碼分享

    JS打字效果的動態(tài)菜單代碼分享

    這篇文章主要介紹了JS打字效果的動態(tài)菜單，推薦給大家，有需要的小伙伴可以參考下。
    2015-08-08
  • Ionic學習日記實現(xiàn)驗證碼倒計時

    Ionic學習日記實現(xiàn)驗證碼倒計時

    本篇文章主要介紹了Ionic學習日記實現(xiàn)驗證碼倒計時，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
    2018-02-02
  • file-loader打包圖片文件時路徑錯誤輸出為[object-module]的解決方法

    file-loader打包圖片文件時路徑錯誤輸出為[object-module]的解決方法

    這篇文章主要介紹了file-loader打包圖片文件時路徑錯誤輸出為[object-module]的解決方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
    2020-01-01
  • js多維數(shù)組降維的5種方法

    js多維數(shù)組降維的5種方法

    本文主要介紹了js多維數(shù)組降維的5種方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
    2023-04-04

最新評論