Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More
Socket
Sign inDemoInstall
Socket

simple-quadtree

Package Overview
Dependencies
Maintainers
1
Versions
4
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

simple-quadtree - npm Package Compare versions

Comparing version 0.1.1 to 0.1.2

14

package.json
{
"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",

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 @@

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

Packages

npm

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc