Skip to content

Instantly share code, notes, and snippets.

@DavidBruant
Created August 25, 2013 21:36
Show Gist options
  • Save DavidBruant/6336472 to your computer and use it in GitHub Desktop.
Save DavidBruant/6336472 to your computer and use it in GitHub Desktop.
2D BSP in JavaScript
// assumes some d3 is already there
function splitIfTooManyPoints(node){
if(node.children){
node.children.forEach(splitIfTooManyPoints);
return;
}
if(node.points.length >= THRESHOLD){
node.split();
splitIfTooManyPoints(node);
}
}
console.time('BSP tree');
var tree = new ScreenTreeNode(0, width, height, 0, nodes);
splitIfTooManyPoints(tree);
console.timeEnd('BSP tree');
function displayTree(node){
svg.insert("rect")
.attr('x', node.left)
.attr('y', node.top)
.attr('width', Math.abs(node.left - node.right))
.attr('height', Math.abs(node.top - node.bottom))
.attr('fill-opacity', 0)
.attr('stroke', 'black')
.attr('stroke-width', '1')
if(node.children){
node.children.forEach(displayTree)
}
}
displayTree(tree);
(function(global){
"use strict";
function constEnumPropValueDesc(v){
return {
value: v,
enumerable: true,
configurable: false,
writable: false
};
}
var abs = Math.abs, max = Math.max, min = Math.min, sqrt = Math.sqrt; // WANT DESTRUCTURING!!
function square(x){
return x*x;
}
/*
+------ top ------+
| | |
| | |
left -----+------>right
| | |
| v |
+---- bottom -----+
*/
// points is {x, y}[]
function ScreenTreeNode(top, right, bottom, left, points){
Object.defineProperty(this, 'top', constEnumPropValueDesc(top));
Object.defineProperty(this, 'right', constEnumPropValueDesc(right));
Object.defineProperty(this, 'bottom', constEnumPropValueDesc(bottom));
Object.defineProperty(this, 'left', constEnumPropValueDesc(left));
this.points = points || []; // default arguments, whaddup'?
}
ScreenTreeNode.prototype = {
/*
Important property: after split, each point belongs to exactly one child
*/
split: function(){
var bottom = this.bottom, top = this.top, right = this.right, left = this.left; // WANT DESTRUCTURING!!
var verticalHalfDiff = (bottom - top)/2; // not gonna end well with odd numbers...
var horizontalHalfDiff = (right - left)/2;
// create children
if(verticalHalfDiff > horizontalHalfDiff){
this.children = [
new ScreenTreeNode(top, right, bottom - verticalHalfDiff, left),
new ScreenTreeNode(top + verticalHalfDiff, right, bottom, left)
];
}
else{
this.children = [
new ScreenTreeNode(top, right - horizontalHalfDiff, bottom, left),
new ScreenTreeNode(top, right, bottom, left + horizontalHalfDiff)
];
}
// split points across children
this.points.forEach(function(e){
// find which child this point belongs to and put it there
this.children.some(function(child){
if(child.contains(e.x, e.y)){
child.points.push(e);
return true;
}
return false;
});
}, this); // WANT ARROW FUNCTION!!
Object.defineProperty(this, 'points', {
get: function(){
return this.children.reduce(function(acc, child){
return acc.concat(child.points);
}, []);
}
});
},
contains: function(x, y){
return y > this.top && y <= this.bottom && x > this.left && x <= this.right;
},
distanceFromPoint: function(x, y){
var bottom = this.bottom, top = this.top, right = this.right, left = this.left; // WANT DESTRUCTURING!!
if(this.contains(x, y))
return 0;
var toTop = y - top;
var toBottom = y - bottom;
var toLeft = x - left;
var toRight = x - right;
// "vertically inside"
if(toTop > 0 && toBottom <= 0){
return min(
abs(toRight),
abs(toLeft)
);
}
// "horizontally inside"
if(toLeft > 0 && toRight <= 0){
return min(
abs(toTop),
abs(toBottom)
);
}
// completely outside, find closest diagonal
var sqrToTop = square(toTop);
var sqrToBottom = square(toBottom);
var sqrToLeft = square(toLeft);
var sqrToRight = square(toRight);
return sqrt(
min(
sqrToTop + sqrToLeft,
sqrToTop + sqrToRight,
sqrToBottom + sqrToLeft,
sqrToBottom + sqrToRight
)
);
}
}
global.ScreenTreeNode = ScreenTreeNode;
})(this);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment