simple-quadtree
Advanced tools
Comparing version 0.1.1 to 0.1.2
{ | ||
"name": "simple-quadtree", | ||
"version": "0.1.1", | ||
"version": "0.1.2", | ||
"description": "quadtree data structure", | ||
@@ -8,13 +8,13 @@ "main": "qtree.js", | ||
"type": "git", | ||
"url": "https://github.com/asaarinen/qtree.git" | ||
"url": "https://github.com/asaarinen/qtree.git" | ||
}, | ||
"author": "Antti Saarinen <antti.p.saarinen@gmail.com>", | ||
"keywords": [ | ||
"quadtree", | ||
"spatial", | ||
"tree", | ||
"data structure" | ||
"quadtree", | ||
"spatial", | ||
"tree", | ||
"data structure" | ||
], | ||
"scripts": { | ||
"test": "node test/test-qtree.js" | ||
"test": "node test/test-qtree.js" | ||
}, | ||
@@ -21,0 +21,0 @@ "license": "MIT", |
453
qtree.js
function QuadTree(x, y, w, h, options) { | ||
if( typeof x != 'number' || isNaN(x) ) | ||
x = 0; | ||
x = 0; | ||
if( typeof y != 'number' || isNaN(y) ) | ||
y = 0; | ||
y = 0; | ||
if( typeof w != 'number' || isNaN(w) ) | ||
w = 10; | ||
w = 10; | ||
if( typeof h != 'number' || isNaN(h) ) | ||
h = 10; | ||
h = 10; | ||
var maxchildren = 25; | ||
var maxc = 25; | ||
var leafratio = 0.5; | ||
if( options ) { | ||
if( typeof options.maxchildren == 'number' ) | ||
if( options.maxchildren > 0 ) | ||
maxchildren = options.maxchildren; | ||
if( typeof options.leafratio == 'number' ) | ||
if( options.leafratio >= 0 ) | ||
leafratio = options.leafratio; | ||
if( typeof options.maxchildren == 'number' ) | ||
if( options.maxchildren > 0 ) | ||
maxc = options.maxchildren; | ||
if( typeof options.leafratio == 'number' ) | ||
if( options.leafratio >= 0 ) | ||
leafratio = options.leafratio; | ||
} | ||
@@ -25,13 +25,13 @@ | ||
function validate(obj) { | ||
if( !obj ) | ||
return false; | ||
if( typeof obj.x != 'number' || | ||
typeof obj.y != 'number' || | ||
typeof obj.w != 'number' || | ||
typeof obj.h != 'number' ) | ||
return false; | ||
if( isNaN(obj.x) || isNaN(obj.y) || | ||
isNaN(obj.w) || isNaN(obj.h) ) | ||
return false; | ||
return true; | ||
if( !obj ) | ||
return false; | ||
if( typeof obj.x != 'number' || | ||
typeof obj.y != 'number' || | ||
typeof obj.w != 'number' || | ||
typeof obj.h != 'number' ) | ||
return false; | ||
if( isNaN(obj.x) || isNaN(obj.y) || | ||
isNaN(obj.w) || isNaN(obj.h) ) | ||
return false; | ||
return true; | ||
} | ||
@@ -41,8 +41,8 @@ | ||
function isequal(o1, o2) { | ||
if( o1.x == o2.x && | ||
o1.y == o2.y && | ||
o1.w == o2.w && | ||
o1.h == o2.h ) | ||
return true; | ||
return false; | ||
if( o1.x == o2.x && | ||
o1.y == o2.y && | ||
o1.w == o2.w && | ||
o1.h == o2.h ) | ||
return true; | ||
return false; | ||
} | ||
@@ -52,11 +52,11 @@ | ||
function createnode(x, y, w, h) { | ||
return { | ||
x: x, | ||
y: y, | ||
w: w, | ||
h: h, | ||
children: [], | ||
leafs: [], | ||
nodes: [] | ||
} | ||
return { | ||
x: x, | ||
y: y, | ||
w: w, | ||
h: h, | ||
c: [], | ||
l: [], | ||
n: [] | ||
} | ||
} | ||
@@ -69,3 +69,3 @@ | ||
function distance(x1, y1, x2, y2) { | ||
return Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)); | ||
return Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)); | ||
} | ||
@@ -75,42 +75,42 @@ | ||
function distancePL(x, y, x1, y1, dx1, dy1, len1 ) { | ||
if( !len1 ) // in case length is not provided, assume a line | ||
len1 = -1; | ||
// x = x1 + s * dx1 + t * dy1 | ||
// y = y1 + s * dy1 - t * dx1 | ||
// x * dy1 - y * dx1 = x1 * dy1 - y1 * dx1 + | ||
if( !len1 ) // in case length is not provided, assume a line | ||
len1 = -1; | ||
// x = x1 + s * dx1 + t * dy1 | ||
// y = y1 + s * dy1 - t * dx1 | ||
// x * dy1 - y * dx1 = x1 * dy1 - y1 * dx1 + | ||
// t * ( dy1 * dy1 + dx1 * dx1 ) | ||
var t = dx1 * dx1 + dy1 * dy1; | ||
if( t == 0 ) | ||
return null; | ||
else { | ||
t = ( x * dy1 - y * dx1 - x1 * dy1 + y1 * dx1 ) / t; | ||
if( Math.abs(dx1) > Math.abs(dy1) ) | ||
var s = ( x - x1 - t * dy1 ) / dx1; | ||
else | ||
var s = ( y - y1 + t * dx1 ) / dy1; | ||
if( ( s >= 0 && s <= len1 ) || len1 < 0 ) | ||
return { | ||
s: s, | ||
t: t, | ||
x: x1 + s * dx1, | ||
y: y1 + s * dy1, | ||
dist: Math.abs(t) | ||
}; | ||
else if( s < 0 ) { | ||
var dist = distance(x, y, x1, y1); | ||
return { | ||
s: s, | ||
dist: dist | ||
}; | ||
} else { | ||
var dist = distance(x, y, | ||
x1 + len1*dx1, | ||
y1 + len1*dy1); | ||
return { | ||
s: s, | ||
dist: dist | ||
}; | ||
} | ||
} | ||
var t = dx1 * dx1 + dy1 * dy1; | ||
if( t == 0 ) | ||
return null; | ||
else { | ||
t = ( x * dy1 - y * dx1 - x1 * dy1 + y1 * dx1 ) / t; | ||
if( Math.abs(dx1) > Math.abs(dy1) ) | ||
var s = ( x - x1 - t * dy1 ) / dx1; | ||
else | ||
var s = ( y - y1 + t * dx1 ) / dy1; | ||
if( ( s >= 0 && s <= len1 ) || len1 < 0 ) | ||
return { | ||
s: s, | ||
t: t, | ||
x: x1 + s * dx1, | ||
y: y1 + s * dy1, | ||
dist: Math.abs(t) | ||
}; | ||
else if( s < 0 ) { | ||
var dist = distance(x, y, x1, y1); | ||
return { | ||
s: s, | ||
dist: dist | ||
}; | ||
} else { | ||
var dist = distance(x, y, | ||
x1 + len1*dx1, | ||
y1 + len1*dy1); | ||
return { | ||
s: s, | ||
dist: dist | ||
}; | ||
} | ||
} | ||
} | ||
@@ -120,15 +120,15 @@ | ||
function overlap_line(o1, o2, buf) { | ||
if( !o1 || !o2 ) | ||
return true; | ||
var dist = distancePL(o2.x + 0.5 * o2.w, | ||
o2.y + 0.5 * o2.h, | ||
o1.x, o1.y, o1.dx, o1.dy, o1.dist); | ||
if( dist ) { | ||
dist.dist -= buf; | ||
if( dist.dist < 0 ) | ||
return true; | ||
if( dist.dist * dist.dist <= o2.w * o2.w + o2.h * o2.h ) | ||
return true; | ||
} | ||
return false; | ||
if( !o1 || !o2 ) | ||
return true; | ||
var dist = distancePL(o2.x + 0.5 * o2.w, | ||
o2.y + 0.5 * o2.h, | ||
o1.x, o1.y, o1.dx, o1.dy, o1.dist); | ||
if( dist ) { | ||
dist.dist -= buf; | ||
if( dist.dist < 0 ) | ||
return true; | ||
if( dist.dist * dist.dist <= o2.w * o2.w + o2.h * o2.h ) | ||
return true; | ||
} | ||
return false; | ||
} | ||
@@ -138,10 +138,10 @@ | ||
function overlap_rect(o1, o2, buf) { | ||
if( !o1 || !o2 ) | ||
return true; | ||
if( o1.x + o1.w < o2.x - buf || | ||
o1.y + o1.h < o2.y - buf || | ||
o1.x - buf > o2.x + o2.w || | ||
o1.y - buf > o2.y + o2.h ) | ||
return false; | ||
return true; | ||
if( !o1 || !o2 ) | ||
return true; | ||
if( o1.x + o1.w < o2.x - buf || | ||
o1.y + o1.h < o2.y - buf || | ||
o1.x - buf > o2.x + o2.w || | ||
o1.y - buf > o2.y + o2.h ) | ||
return false; | ||
return true; | ||
} | ||
@@ -151,24 +151,24 @@ | ||
var leaf = false; | ||
if( obj.w * obj.h > node.w * node.h * leafratio ) | ||
leaf = true; | ||
var leaf = false; | ||
if( obj.w * obj.h > node.w * node.h * leafratio ) | ||
leaf = true; | ||
if( obj.x < node.x || | ||
obj.y < node.y || | ||
obj.x + obj.w > node.x + node.w || | ||
obj.y + obj.h > node.y + node.h ) | ||
leaf = true; | ||
if( obj.x < node.x || | ||
obj.y < node.y || | ||
obj.x + obj.w > node.x + node.w || | ||
obj.y + obj.h > node.y + node.h ) | ||
leaf = true; | ||
var childnode = null; | ||
for( var ni = 0; ni < node.nodes.length; ni++ ) | ||
if( overlap_rect(obj, node.nodes[ni], 0) ) { | ||
if( childnode ) { // multiple hits | ||
leaf = true; | ||
break; | ||
} else | ||
childnode = node.nodes[ni]; | ||
} | ||
return { leaf: leaf, | ||
childnode: childnode }; | ||
var childnode = null; | ||
for( var ni = 0; ni < node.n.length; ni++ ) | ||
if( overlap_rect(obj, node.n[ni], 0) ) { | ||
if( childnode ) { // multiple hits | ||
leaf = true; | ||
break; | ||
} else | ||
childnode = node.n[ni]; | ||
} | ||
return { leaf: leaf, | ||
childnode: childnode }; | ||
} | ||
@@ -178,9 +178,9 @@ | ||
function put_to_nodes(node, obj) { | ||
var leaf = isleaf(node, obj); | ||
if( leaf ) | ||
node.leafs.push(obj); | ||
else if( leaf.childnode ) | ||
put(leaf.childnode, obj); | ||
else | ||
return; | ||
var leaf = isleaf(node, obj); | ||
if( leaf ) | ||
node.l.push(obj); | ||
else if( leaf.childnode ) | ||
put(leaf.childnode, obj); | ||
else | ||
return; | ||
} | ||
@@ -190,31 +190,31 @@ | ||
function remove(node, obj, attr) { | ||
if( !validate(obj) ) | ||
return 0; | ||
if( !validate(obj) ) | ||
return 0; | ||
if( !attr ) | ||
attr = false; | ||
else if( typeof attr != 'string' ) | ||
attr = 'id'; | ||
if( !attr ) | ||
attr = false; | ||
else if( typeof attr != 'string' ) | ||
attr = 'id'; | ||
var count = 0; | ||
for( var ci = 0; ci < node.children.length; ci++ ) | ||
if( ( attr && node.children[ci][attr] == obj[attr] ) || | ||
( !attr && isequal(node.children[ci], obj) ) ) { | ||
count++; | ||
node.children.splice(ci, 1); | ||
ci--; | ||
} | ||
var count = 0; | ||
for( var ci = 0; ci < node.c.length; ci++ ) | ||
if( ( attr && node.c[ci][attr] == obj[attr] ) || | ||
( !attr && isequal(node.c[ci], obj) ) ) { | ||
count++; | ||
node.c.splice(ci, 1); | ||
ci--; | ||
} | ||
for( var ci = 0; ci < node.leafs.length; ci++ ) | ||
if( ( attr && node.leafs[ci][attr] == obj[attr] ) || | ||
( !attr && isequal(node.leafs[ci], obj) ) ) { | ||
count++; | ||
node.leafs.splice(ci, 1); | ||
ci--; | ||
} | ||
for( var ci = 0; ci < node.l.length; ci++ ) | ||
if( ( attr && node.l[ci][attr] == obj[attr] ) || | ||
( !attr && isequal(node.l[ci], obj) ) ) { | ||
count++; | ||
node.l.splice(ci, 1); | ||
ci--; | ||
} | ||
var leaf = isleaf(node, obj); | ||
if( !leaf.leaf && leaf.childnode ) | ||
return count + remove(leaf.childnode, obj, attr); | ||
return count; | ||
var leaf = isleaf(node, obj); | ||
if( !leaf.leaf && leaf.childnode ) | ||
return count + remove(leaf.childnode, obj, attr); | ||
return count; | ||
} | ||
@@ -225,22 +225,22 @@ | ||
if( !validate(obj) ) | ||
return; | ||
if( !validate(obj) ) | ||
return; | ||
if( node.nodes.length == 0 ) { | ||
node.children.push(obj); | ||
// subdivide | ||
if( node.children.length > maxchildren ) { | ||
var w2 = node.w / 2; | ||
var h2 = node.h / 2; | ||
node.nodes.push(createnode(node.x, node.y, w2, h2), | ||
createnode(node.x + w2, node.y, w2, h2), | ||
createnode(node.x, node.y + h2, w2, h2), | ||
createnode(node.x + w2, node.y + h2, w2, h2)); | ||
for( var ci = 0; ci < node.children.length; ci++ ) | ||
put_to_nodes(node, node.children[ci]); | ||
node.children = []; | ||
} | ||
} else | ||
put_to_nodes(node, obj); | ||
if( node.n.length == 0 ) { | ||
node.c.push(obj); | ||
// subdivide | ||
if( node.c.length > maxc ) { | ||
var w2 = node.w / 2; | ||
var h2 = node.h / 2; | ||
node.n.push(createnode(node.x, node.y, w2, h2), | ||
createnode(node.x + w2, node.y, w2, h2), | ||
createnode(node.x, node.y + h2, w2, h2), | ||
createnode(node.x + w2, node.y + h2, w2, h2)); | ||
for( var ci = 0; ci < node.c.length; ci++ ) | ||
put_to_nodes(node, node.c[ci]); | ||
node.c = []; | ||
} | ||
} else | ||
put_to_nodes(node, obj); | ||
} | ||
@@ -250,16 +250,18 @@ | ||
// function | ||
function getter(overlapfun, node, obj, buf, callback) { | ||
for( var li = 0; li < node.leafs.length; li++ ) | ||
if( !callback(node.leafs[li]) ) | ||
return false; | ||
for( var li = 0; li < node.children.length; li++ ) | ||
if( !callback(node.children[li]) ) | ||
return false; | ||
for( var ni = 0; ni < node.nodes.length; ni++ ) { | ||
if( overlapfun(obj, node.nodes[ni], buf) ) { | ||
if( !getter(overlapfun, node.nodes[ni], obj, buf, callback) ) | ||
return false; | ||
} | ||
} | ||
return true; | ||
function getter(overlapfun, node, obj, buf, strict, callback) { | ||
for( var li = 0; li < node.l.length; li++ ) | ||
if( !strict || overlapfun(obj, node.l[li], buf) ) | ||
if( !callback(node.l[li]) ) | ||
return false; | ||
for( var li = 0; li < node.c.length; li++ ) | ||
if( !strict || overlapfun(obj, node.c[li], buf) ) | ||
if( !callback(node.c[li]) ) | ||
return false; | ||
for( var ni = 0; ni < node.n.length; ni++ ) { | ||
if( overlapfun(obj, node.n[ni], buf) ) { | ||
if( !getter(overlapfun, node.n[ni], obj, buf, strict, callback) ) | ||
return false; | ||
} | ||
} | ||
return true; | ||
} | ||
@@ -269,3 +271,3 @@ | ||
function get_rect(node, obj, buf, callback) { | ||
return getter(overlap_rect, node, obj, buf, callback); | ||
return getter(overlap_rect, node, obj, buf, true, callback); | ||
} | ||
@@ -276,3 +278,3 @@ | ||
function get_line(node, obj, buf, callback) { | ||
return getter(overlap_line, node, obj, buf, callback); | ||
return getter(overlap_line, node, obj, buf, false, callback); | ||
} | ||
@@ -284,20 +286,20 @@ | ||
if( typeof buf == 'function' && typeof callback == 'undefined' ) { | ||
callback = buf; | ||
buf = 0; | ||
} | ||
if( obj == null ) | ||
get_rect(node, obj, buf, callback); | ||
else if( typeof obj.x == 'number' && | ||
typeof obj.y == 'number' && | ||
!isNaN(obj.x) && !isNaN(obj.y) ) { | ||
if( typeof obj.dx == 'number' && | ||
typeof obj.dy == 'number' && | ||
!isNaN(obj.dx) && !isNaN(obj.dy) ) | ||
get_line(node, obj, buf, callback); | ||
else if( typeof obj.w == 'number' && | ||
typeof obj.h == 'number' && | ||
!isNaN(obj.w) && !isNaN(obj.h) ) | ||
get_rect(node, obj, buf, callback); | ||
} | ||
if( typeof buf == 'function' && typeof callback == 'undefined' ) { | ||
callback = buf; | ||
buf = 0; | ||
} | ||
if( obj == null ) | ||
get_rect(node, obj, buf, callback); | ||
else if( typeof obj.x == 'number' && | ||
typeof obj.y == 'number' && | ||
!isNaN(obj.x) && !isNaN(obj.y) ) { | ||
if( typeof obj.dx == 'number' && | ||
typeof obj.dy == 'number' && | ||
!isNaN(obj.dx) && !isNaN(obj.dy) ) | ||
get_line(node, obj, buf, callback); | ||
else if( typeof obj.w == 'number' && | ||
typeof obj.h == 'number' && | ||
!isNaN(obj.w) && !isNaN(obj.h) ) | ||
get_rect(node, obj, buf, callback); | ||
} | ||
} | ||
@@ -307,11 +309,38 @@ | ||
return { | ||
get: function(obj, buf, callback) { | ||
get(root, obj, buf, callback); | ||
}, | ||
put: function(obj) { | ||
put(root, obj); | ||
}, | ||
remove: function(obj, attr) { | ||
return remove(root, obj, attr); | ||
} | ||
get: function(obj, buf, callback) { | ||
get(root, obj, buf, callback); | ||
}, | ||
put: function(obj) { | ||
put(root, obj); | ||
}, | ||
remove: function(obj, attr) { | ||
return remove(root, obj, attr); | ||
}, | ||
stringify: function() { | ||
var strobj = { | ||
x: x, y: y, w: w, h: h, | ||
maxc: maxc, | ||
leafratio: leafratio, | ||
root: root | ||
}; | ||
try { | ||
return JSON.stringify(strobj); | ||
} catch(err) { | ||
// could not stringify | ||
// probably due to objects included in qtree being non-stringifiable | ||
return null; | ||
} | ||
}, | ||
parse: function(str) { | ||
if( typeof str == 'string' ) | ||
str = JSON.parse(str); | ||
x = str.x; | ||
y = str.y; | ||
w = str.w; | ||
h = str.h; | ||
maxc = str.maxc; | ||
leafratio = str.leafratio; | ||
root = str.root; | ||
} | ||
}; | ||
@@ -318,0 +347,0 @@ } |
@@ -49,3 +49,3 @@ simple-quadtree | ||
Iterating over objects continues until all of them have been iterated, or the callback function returns `false`. | ||
Iterating over objects continues as long as there are remaining objects and the callback function returns `true`. If the callback does not return `true`, the iteration is interrupted. | ||
@@ -70,2 +70,4 @@ You can also give a buffer threshold, indicating that you want to iterate over all objects in the area expanded by the threshold to all directions: | ||
Please also note that getting objects close to a line segment will guarantee that all objects close to the line will be iterated over, but other non-overlapping objects may also be returned. | ||
You can also use a buffer threshold when iterating based on a line segment. | ||
@@ -72,0 +74,0 @@ |
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
20056
406
109
5