JS實現(xiàn)的四叉樹算法詳解
本文實例講述了JS實現(xiàn)的四叉樹算法。分享給大家供大家參考，具體如下：
最近在看canvas動畫方面教程，里面提到了采用四叉樹檢測碰撞。之前也看到過四叉樹這個名詞，但是一直不是很懂。于是就又找了一些四叉樹方面的資料看了看，做個筆記，就算日后忘了，也可以回來看看。
QuadTree四叉樹顧名思義就是樹狀的數(shù)據(jù)結(jié)構(gòu)，其每個節(jié)點有四個孩子節(jié)點，可將二維平面遞歸分割子區(qū)域。QuadTree常用于空間數(shù)據(jù)庫索引，3D的椎體可見區(qū)域裁剪，甚至圖片分析處理，我們今天介紹的是QuadTree最常被游戲領域使用到的碰撞檢測。采用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
更多關于JavaScript相關內(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程序設計有所幫助。
- C++實現(xiàn)四叉樹效果(附源碼下載)
- 四叉樹有損位圖壓縮處理程序示例
- JS實現(xiàn)的二叉樹算法完整實例
- JavaScript數(shù)據(jù)結(jié)構(gòu)和算法之二叉樹詳解
- JavaScript實現(xiàn)多叉樹的遞歸遍歷和非遞歸遍歷算法操作示例
- JavaScript數(shù)據(jù)結(jié)構(gòu)之二叉樹的刪除算法示例
- JavaScript數(shù)據(jù)結(jié)構(gòu)之二叉樹的遍歷算法示例
- JavaScript數(shù)據(jù)結(jié)構(gòu)之二叉樹的查找算法示例
- JavaScript數(shù)據(jù)結(jié)構(gòu)之二叉樹的計數(shù)算法示例
相關文章
JavaScript快速排序(quickSort)算法的實現(xiàn)方法總結(jié)
快速排序的思想式 分治法,選一個基準點,然后根據(jù)大小進行分配,分配然完畢之后,對已經(jīng)分配的進行遞歸操作,最終形成快速排序,所以遞歸也是快速排序思想的一個重要組成部分,本文主要給大家介紹了JavaScript實現(xiàn)快速排序的寫法,需要的朋友可以參考下2023-11-11
這篇文章主要介紹了原生js實現(xiàn)拖拽功能基本思路詳解,而拖拽的基本原理就是根據(jù)鼠標的移動來移動被拖拽的元素。需要的朋友可以參考下2018-04-04
這篇文章主要介紹了純js代碼實現(xiàn)簡單計算器，功能超簡單，實現(xiàn)加減乘除簡單運算，感興趣的小伙伴們可以參考一下2015-12-12
這篇文章主要介紹了原生javascript實現(xiàn)百葉窗效果的方法及原理介紹，感興趣的小伙伴們可以參考一下2016-04-04
用js控件div的滾動條,讓它在內(nèi)容更新時自動滾到底部的實現(xiàn)方法
下面小編就為大家?guī)硪黄胘s控件div的滾動條,讓它在內(nèi)容更新時自動滾到底部的實現(xiàn)方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-10-10
這篇文章主要為大家詳細介紹了localStorage實現(xiàn)便簽小程序的相關資料,具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-11-11
這篇文章主要介紹了微信小程序 swiper組件輪播圖詳解及實例的相關資料,需要的朋友可以參考下，希望能給你帶來幫助2021-08-08
這篇文章主要介紹了微信小程序與公眾號卡券/會員打通的問題，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-07-07
本文主要分享了js實現(xiàn)文字無縫向上滾動的示例代碼，具有很好的參考價值，下面跟著小編一起來看下吧2017-02-02
js replace與正則表達式結(jié)合，可以有效發(fā)揮replace的功效，可以幫助用戶解決替換中的復制問題，接下來詳細介紹使用方法，感興趣的朋友可以了解下2013-01-01