Skip to content

Instantly share code, notes, and snippets.

@06wj

06wj/QuadTree.js

Last active December 21, 2015 22:42
Show Gist options
  • Save 06wj/6376555 to your computer and use it in GitHub Desktop.
Save 06wj/6376555 to your computer and use it in GitHub Desktop.
Download ZIP
quad
Raw
QuadTree.js
//copied and modified from http://www.nshen.net/article/2011-08-25/as3-DataStructure/
var Rectangle = require("./Rectangle");
var QuadTree = function(rect, maxDepth, currentDepth) {
this._rect = rect;
this._depth = currentDepth || 0;
this._maxDepth = maxDepth || 3;
this._hw = rect.width >> 1;
this._hh = rect.height >> 1;
this._midX = rect.x + this._hw;
this._midY = rect.y + this._hh;
this.clear();
};
QuadTree.prototype.clear = function() {
this._children = [];
this._topLeft = this._topRight = this._bottomLeft = this._bottomRight = null;
};
QuadTree.prototype.toString = function() {
var s = "[QuadTreeNode> "
var l = this._children.length;
s += l > 1 ? (l + " children") : (l + " child")
return s;
};
/**
* 节点按 <左上，右上，左下，右下>输出
*/
QuadTree.prototype.dump = function() {
var s = "";
this.preorder(this, function(node){
var d = node._depth;
for (var i = 0; i < d; i++) {
if (i == d - 1)
s += "+---";
else
s += "| ";
}
s += node + "\n";
});
return s;
};
QuadTree.prototype.preorder = function(node, process) {
process(node);
if (node._topLeft) {
this.preorder(node._topLeft, process);
}
if (node._topRight) {
this.preorder(node._topRight, process);
}
if (node._bottomLeft) {
this.preorder(node._bottomLeft, process);
}
if (node._bottomRight) {
this.preorder(node._bottomRight, process);
}
};
// obj {rect:{x, y, width, height}}
QuadTree.prototype.retrieve = function(obj) {
var r = []
if (!this._topLeft) {
r.push.apply(r, this._children)
return r;
}
var rect = obj.rect;
var rx = rect.x;
var ry = rect.y;
var rw = rect.width;
var rh = rect.height;
var rr = rx + rw;
var rb = ry + rh;
//如果所取区块比本身区域还大，那么它所有子树的children都取出
if (rx <= this._rect.x && ry <= this._rect.y && rr >= this._rect.right && rb >= this._rect.bottom) {
r.push.apply(r, this._children)
r.push.apply(r, this._topLeft.retrieve(obj))
r.push.apply(r, this._topRight.retrieve(obj))
r.push.apply(r, this._bottomLeft.retrieve(obj))
r.push.apply(r, this._bottomRight.retrieve(obj))
return r;
}
//否则就只取对应的区域子树
// 完全在分区里
if ((rx > this._rect.x) && (rr < this._midX)) {
if (ry > this._rect.y && rb < this._midY) {
r.push.apply(r, this._topLeft.retrieve(obj))
return r;
}
if (ry > this._midY && rb < this._rect.bottom) {
r.push.apply(r, this._bottomLeft.retrieve(obj))
return r;
}
}
if (rx > this._midX && rr < this._rect.right) {
if (ry > this._rect.y && rb < this._midY) {
r.push.apply(r, this._topRight.retrieve(obj))
return r
}
if (ry > this._midY && rb < this._rect.bottom) {
r.push.apply(r, this._bottomRight.retrieve(obj))
return r
}
}
//只要有部分在分区里，也放到对应分区里，但注意可以重复放
//上边
if (rb > this._rect.y && ry < this._midY) {
if (rx < this._midX && rr > this._rect.x) {
r.push.apply(r, this._topLeft.retrieve(obj));
}
if (rx < this._rect.right && rr > this._midX) {
r.push.apply(r, this._topRight.retrieve(obj));
}
}
// 下边
if (rb > this._midY && ry < this._rect.bottom) {
if (rx < this._midX && rr > this._rect.x) {
r.push.apply(r, this._bottomLeft.retrieve(obj));
}
if (rx < this._rect.right && rr > this._midX) {
r.push.apply(r, this._bottomRight.retrieve(obj));
}
}
return r;
};
// obj {rect:{x, y, width, height}} or [obj, obj, obj]
QuadTree.prototype.insert = function(obj) {
if (Object.prototype.toString.call(obj) === "[object Array]") {
for (var i = 0, l = obj.length; i < l; i++) {
this.insert(obj[i]);
}
return;
}
var rect = obj.rect;
var rx = rect.x;
var ry = rect.y;
var rw = rect.width;
var rh = rect.height;
var rr = rx + rw;
var rb = ry + rh;
// 如果不能切分或者obj比整个区域还大，就放到children里
if (this._depth >= this._maxDepth || (rx <= this._rect.x && ry <= this._rect.y && rx + rw >= this._rect.right && ry + rh >= this._rect.bottom)) {
this._children.push(obj);
return;
}
if (!this._topLeft) {
var d = this._depth + 1
this._topLeft = new QuadTree(new Rectangle(this._rect.x, this._rect.y, this._hw, this._hh), this._maxDepth, d);
this._topRight = new QuadTree(new Rectangle(this._rect.x + this._hw, this._rect.y, this._hw, this._hh), this._maxDepth, d);
this._bottomLeft = new QuadTree(new Rectangle(this._rect.x, this._rect.y + this._hh, this._hw, this._hh), this._maxDepth, d);
this._bottomRight = new QuadTree(new Rectangle(this._rect.x + this._hw, this._rect.y + this._hh, this._hw, this._hh), this._maxDepth, d);
}
// 可以完全放到分区里就递归放到对应分区里
if ((rx > this._rect.x) && (rr < this._midX)) {
if (ry > this._rect.y && rb < this._midY) {
this._topLeft.insert(obj);
return;
}
if (ry > this._midY && rb < this._rect.bottom) {
this._bottomLeft.insert(obj);
return;
}
}
if (rx > this._midX && rr < this._rect.right) {
if (ry > this._rect.y && rb < this._midY) {
this._topRight.insert(obj);
return;
}
if (ry > this._midY && rb < this._rect.bottom) {
this._bottomRight.insert(obj);
return;
}
}
//只要有部分在分区里，也放到对应分区里，但注意可以重复放
//上边
if (rb > this._rect.y && ry < this._midY) {
if (rx < this._midX && rr > this._rect.x) {
this._topLeft.insert(obj);
}
if (rx < this._rect.right && rr > this._midX) {
this._topRight.insert(obj);
}
}
// 下边
if (rb > this._midY && ry < this._rect.bottom) {
if (rx < this._midX && rr > this._rect.x) {
this._bottomLeft.insert(obj);
}
if (rx < this._rect.right && rr > this._midX) {
this._bottomRight.insert(obj);
}
}
}
module.exports = QuadTree;
Raw
Rectangle.js
var Rectangle = function(x, y, width, height) {
this.set(x, y, width, height);
};
Rectangle.prototype.set = function(x, y, width, height){
this.x = x;
this.y = y;
this.width = width;
this.height = height;
this.bottom = this.y + this.height;
this.right = this.x + this.width;
};
Rectangle.prototype.intersects = function(rect){
return rect.x <= this.right && this.x <= rect.right&&
rect.y <= this.bottom && this.y <= rect.bottom;
};
module.exports = Rectangle;
Raw
t.html
<!doctype html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>test</title>
</head>
<body>
<canvas></canvas>
<script>
var Rectangle = function(x, y, width, height) {
this.set(x, y, width, height);
};
Rectangle.prototype.set = function(x, y, width, height){
this.x = x;
this.y = y;
this.width = width;
this.height = height;
this.bottom = this.y + this.height;
this.right = this.x + this.width;
};
Rectangle.prototype.intersects = function(rect){
return rect.x <= this.right && this.x <= rect.right&&
rect.y <= this.bottom && this.y <= rect.bottom;
};
var QuadTree = function(rect, maxDepth, currentDepth) {
this._rect = rect;
this._depth = currentDepth || 0;
this._maxDepth = maxDepth || 3;
this._hw = rect.width >> 1;
this._hh = rect.height >> 1;
this._midX = rect.x + this._hw;
this._midY = rect.y + this._hh;
this.clear();
};
QuadTree.prototype.clear = function() {
this._children = [];
this._topLeft = this._topRight = this._bottomLeft = this._bottomRight = null;
};
QuadTree.prototype.toString = function() {
var s = "[QuadTreeNode> "
var l = this._children.length;
s += l > 1 ? (l + " children") : (l + " child")
return s;
};
/**
* 节点按 <左上，右上，左下，右下>输出
*/
QuadTree.prototype.dump = function() {
var s = "";
this.preorder(this, function(node){
var d = node._depth;
for (var i = 0; i < d; i++) {
if (i == d - 1)
s += "+---";
else
s += "| ";
}
s += node + "\n";
});
return s;
};
QuadTree.prototype.preorder = function(node, process) {
process(node);
if (node._topLeft) {
this.preorder(node._topLeft, process);
}
if (node._topRight) {
this.preorder(node._topRight, process);
}
if (node._bottomLeft) {
this.preorder(node._bottomLeft, process);
}
if (node._bottomRight) {
this.preorder(node._bottomRight, process);
}
};
// obj {rect:{x, y, width, height}}
QuadTree.prototype.retrieve = function(obj) {
var r = []
if (!this._topLeft) {
r.push.apply(r, this._children)
return r;
}
var rect = obj.rect;
var rx = rect.x;
var ry = rect.y;
var rw = rect.width;
var rh = rect.height;
var rr = rx + rw;
var rb = ry + rh;
//如果所取区块比本身区域还大，那么它所有子树的children都取出
if (rx <= this._rect.x && ry <= this._rect.y && rr >= this._rect.right && rb >= this._rect.bottom) {
r.push.apply(r, this._children)
r.push.apply(r, this._topLeft.retrieve(obj))
r.push.apply(r, this._topRight.retrieve(obj))
r.push.apply(r, this._bottomLeft.retrieve(obj))
r.push.apply(r, this._bottomRight.retrieve(obj))
return r;
}
//否则就只取对应的区域子树
// 完全在分区里
if ((rx > this._rect.x) && (rr < this._midX)) {
if (ry > this._rect.y && rb < this._midY) {
r.push.apply(r, this._topLeft.retrieve(obj))
return r;
}
if (ry > this._midY && rb < this._rect.bottom) {
r.push.apply(r, this._bottomLeft.retrieve(obj))
return r;
}
}
if (rx > this._midX && rr < this._rect.right) {
if (ry > this._rect.y && rb < this._midY) {
r.push.apply(r, this._topRight.retrieve(obj))
return r
}
if (ry > this._midY && rb < this._rect.bottom) {
r.push.apply(r, this._bottomRight.retrieve(obj))
return r
}
}
//只要有部分在分区里，也放到对应分区里，但注意可以重复放
//上边
if (rb > this._rect.y && ry < this._midY) {
if (rx < this._midX && rr > this._rect.x) {
r.push.apply(r, this._topLeft.retrieve(obj));
}
if (rx < this._rect.right && rr > this._midX) {
r.push.apply(r, this._topRight.retrieve(obj));
}
}
// 下边
if (rb > this._midY && ry < this._rect.bottom) {
if (rx < this._midX && rr > this._rect.x) {
r.push.apply(r, this._bottomLeft.retrieve(obj));
}
if (rx < this._rect.right && rr > this._midX) {
r.push.apply(r, this._bottomRight.retrieve(obj));
}
}
return r;
};
// obj {rect:{x, y, width, height}} or [obj, obj, obj]
QuadTree.prototype.insert = function(obj) {
if (Object.prototype.toString.call(obj) === "[object Array]") {
for (var i = 0, l = obj.length; i < l; i++) {
this.insert(obj[i]);
}
return;
}
var rect = obj.rect;
var rx = rect.x;
var ry = rect.y;
var rw = rect.width;
var rh = rect.height;
var rr = rx + rw;
var rb = ry + rh;
// 如果不能切分或者obj比整个区域还大，就放到children里
if (this._depth >= this._maxDepth || (rx <= this._rect.x && ry <= this._rect.y && rx + rw >= this._rect.right && ry + rh >= this._rect.bottom)) {
this._children.push(obj);
return;
}
if (!this._topLeft) {
var d = this._depth + 1
this._topLeft = new QuadTree(new Rectangle(this._rect.x, this._rect.y, this._hw, this._hh), this._maxDepth, d);
this._topRight = new QuadTree(new Rectangle(this._rect.x + this._hw, this._rect.y, this._hw, this._hh), this._maxDepth, d);
this._bottomLeft = new QuadTree(new Rectangle(this._rect.x, this._rect.y + this._hh, this._hw, this._hh), this._maxDepth, d);
this._bottomRight = new QuadTree(new Rectangle(this._rect.x + this._hw, this._rect.y + this._hh, this._hw, this._hh), this._maxDepth, d);
}
// 可以完全放到分区里就递归放到对应分区里
if ((rx > this._rect.x) && (rr < this._midX)) {
if (ry > this._rect.y && rb < this._midY) {
this._topLeft.insert(obj);
return;
}
if (ry > this._midY && rb < this._rect.bottom) {
this._bottomLeft.insert(obj);
return;
}
}
if (rx > this._midX && rr < this._rect.right) {
if (ry > this._rect.y && rb < this._midY) {
this._topRight.insert(obj);
return;
}
if (ry > this._midY && rb < this._rect.bottom) {
this._bottomRight.insert(obj);
return;
}
}
//只要有部分在分区里，也放到对应分区里，但注意可以重复放
//上边
if (rb > this._rect.y && ry < this._midY) {
if (rx < this._midX && rr > this._rect.x) {
this._topLeft.insert(obj);
}
if (rx < this._rect.right && rr > this._midX) {
this._topRight.insert(obj);
}
}
// 下边
if (rb > this._midY && ry < this._rect.bottom) {
if (rx < this._midX && rr > this._rect.x) {
this._bottomLeft.insert(obj);
}
if (rx < this._rect.right && rr > this._midX) {
this._bottomRight.insert(obj);
}
}
}
var width = 600;
var height = 600;
var canvas = document.querySelector("canvas");
var ctx = canvas.getContext("2d");
canvas.width = width;
canvas.height = height;
function Obj(x, y, width, height){
this.x = x;
this.y = y;
this.width = width;
this.height = height;
this.isHit = false;
this.vx = Math.random()*1 - .5;
this.vy = Math.random()*1 - .5;
arr.push(this);
this.rect = new Rectangle(x, y, width, height);
};
Obj.prototype.draw = function(){
ctx.save();
ctx.fillStyle = this.isHit?"red":"#f96";
ctx.strokeStyle = "black";
ctx.translate(this.x, this.y);
ctx.fillRect(0, 0, this.width, this.height);
ctx.strokeRect(0, 0, this.width, this.height);
ctx.restore();
};
Obj.prototype.hitTest = function(obj){
return !(obj.x > this.width + this.x || obj.y > this.height + this.y || obj.x + obj.width < this.x || obj.y + obj.height < this.y);
};
Obj.prototype.update = function(){
this.rect.set(this.x, this.y, this.width, this.height);
this.x -= this.vx;
this.y -= this.vy;
if(this.x < 0){
this.x = 0;
this.vx *= -1;
}
if(this.x > width - this.width){
this.x = width - this.width;
this.vx *= -1;
}
if(this.y < 0){
this.y = 0;
this.vy *= -1;
}
if(this.y > height - this.height){
this.y = height - this.height;
this.vy *= -1;
}
this.isHit = false;
};
var arr = [];
var quad = new QuadTree(new Rectangle(0, 0, width, height), 3, 0);
function update(){
ctx.clearRect(0, 0, width, height);
quad.clear();
for(var i = 0,l = arr.length;i < l;i ++){
var obj = arr[i];
obj.update();
quad.insert(obj);
}
for(var i = 0,l = arr.length;i < l;i ++){
var obj = arr[i];
var quarArr = quad.retrieve(obj);
for(var j = 0, jl = quarArr.length;j < jl;j ++)
{
var obj2 = quarArr[j];
if(obj2 === obj)continue;
if(obj2.isHit && obj.isHit) continue
if(obj.hitTest(obj2))
{
obj.isHit = obj2.isHit = true;
}
}
}
for(var i = 0,l = arr.length;i < l;i ++){
arr[i].draw();
}
}
var interval = setInterval(update, 16);
function create(num){
while(num --){
new Obj(Math.random()*width, Math.random()*height, Math.random()*10+5, Math.random()*10+5)
}
}
create(1000);
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment