Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
simple-quadtree
Advanced tools
simple-quadtree - npm Package Compare versions
Comparing version 0.1.0 to 0.1.1
| { | ||
| "name": "simple-quadtree", | ||
| "version": "0.1.0", | ||
| "version": "0.1.1", | ||
| "description": "quadtree data structure", | ||
@@ -5,0 +5,0 @@ "main": "qtree.js", |
117
qtree.js
@@ -13,7 +13,37 @@ function QuadTree(x, y, w, h, options) { | ||
| var maxchildren = 25; | ||
| if( options ) | ||
| 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; | ||
| } | ||
| // validate an input object | ||
| 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; | ||
| } | ||
| // test for deep equality for x,y,w,h | ||
| 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; | ||
| } | ||
| // create a new quadtree node | ||
@@ -113,5 +143,8 @@ function createnode(x, y, w, h) { | ||
| // put an object to one of the child nodes of this node | ||
| function put_to_nodes(node, obj) { | ||
| function isleaf(node, obj) { | ||
| var leaf = false; | ||
| if( obj.w * obj.h > node.w * node.h * leafratio ) | ||
| leaf = true; | ||
| if( obj.x < node.x || | ||
@@ -122,18 +155,67 @@ obj.y < node.y || | ||
| leaf = true; | ||
| var found = false; | ||
| var childnode = null; | ||
| for( var ni = 0; ni < node.nodes.length; ni++ ) | ||
| if( overlap_rect(obj, node.nodes[ni], 0) ) { | ||
| put(node.nodes[ni], obj); | ||
| found = true; | ||
| if( childnode ) { // multiple hits | ||
| leaf = true; | ||
| break; | ||
| } else | ||
| childnode = node.nodes[ni]; | ||
| } | ||
| if( !found || leaf ) | ||
| return { leaf: leaf, | ||
| childnode: childnode }; | ||
| } | ||
| // put an object to one of the child nodes of this node | ||
| 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; | ||
| } | ||
| // remove an object from this node | ||
| function remove(node, obj, attr) { | ||
| if( !validate(obj) ) | ||
| return 0; | ||
| 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--; | ||
| } | ||
| 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--; | ||
| } | ||
| var leaf = isleaf(node, obj); | ||
| if( !leaf.leaf && leaf.childnode ) | ||
| return count + remove(leaf.childnode, obj, attr); | ||
| return count; | ||
| } | ||
| // put an object to this node | ||
| function put(node, obj) { | ||
| if( obj.w * obj.h >= node.w * node.h ) { | ||
| node.leafs.push(obj); | ||
| function put(node, obj, removeflag) { | ||
| if( !validate(obj) ) | ||
| return; | ||
| } | ||
| if( node.nodes.length == 0 ) { | ||
@@ -190,2 +272,3 @@ node.children.push(obj); | ||
| function get(node, obj, buf, callback) { | ||
| if( typeof buf == 'function' && typeof callback == 'undefined' ) { | ||
@@ -198,8 +281,11 @@ callback = buf; | ||
| else if( typeof obj.x == 'number' && | ||
| typeof obj.y == 'number' ) { | ||
| typeof obj.y == 'number' && | ||
| !isNaN(obj.x) && !isNaN(obj.y) ) { | ||
| if( typeof obj.dx == 'number' && | ||
| typeof obj.dy == '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' ) | ||
| typeof obj.h == 'number' && | ||
| !isNaN(obj.w) && !isNaN(obj.h) ) | ||
| get_rect(node, obj, buf, callback); | ||
@@ -216,2 +302,5 @@ } | ||
| put(root, obj); | ||
| }, | ||
| remove: function(obj, attr) { | ||
| return remove(root, obj, attr); | ||
| } | ||
@@ -218,0 +307,0 @@ }; |
@@ -1,5 +0,5 @@ | ||
| qtree - a simple JavaScript quadtree | ||
| simple-quadtree | ||
| ===== | ||
| `qtree` is a minimal quadtree implementation that supports simple `put` and `get` operations on objects having a `x, y` position and `w, h` dimension. | ||
| `simple-quadtree` is a minimal quadtree implementation that supports simple `put`, `get` and `remove` operations on objects having a `x, y` position and `w, h` dimension. | ||
@@ -13,3 +13,3 @@ Installation | ||
| Should also work in all browsers as is. `qtree` has no dependencies. | ||
| Should also work in all browsers as is. `simple-quadtree` has no dependencies. | ||
@@ -22,7 +22,7 @@ Usage | ||
| ```javascript | ||
| var QuadTree = require('qtree'); | ||
| var QuadTree = require('simple-quadtree'); | ||
| var qt = QuadTree(0, 0, 100, 100); | ||
| ``` | ||
| You can also give `QuadTree` some options, the only option currently is the maximum number of children in a quadtree node until it is subdivided: | ||
| You can also give `QuadTree` some options; currently, the only option is the maximum number of children in a quadtree node until it is subdivided: | ||
@@ -33,2 +33,4 @@ ```javascript | ||
| ### Putting objects | ||
| Put objects into the quadtree by using `put`. The objects can be anything as long as they have `x, y, w, h` properties as numbers indicating the bounding area of that object: | ||
@@ -40,2 +42,4 @@ | ||
| ### Getting objects | ||
| Iterate over the objects by giving an area and a callback: | ||
@@ -71,2 +75,27 @@ | ||
| ### Removing objects | ||
| To remove objects, call `remove` with the original object that was passed to `put`: | ||
| ```javascript | ||
| var obj = { x: 5, y: 5, w: 0, h: 0, string: 'test', id: 4233 }; | ||
| qt.put(obj); | ||
| qt.remove(obj); // removed | ||
| ``` | ||
| In fact, `remove` removes all objects with `x, y, w, h` identical to the passed object. If you want to remove only a specific object, you can pass the name of the uniquely identifying property to `remove`: | ||
| ```javascript | ||
| var obj1 = { x: 5, y: 5, w: 0, h: 0, string: 'test', id: 4233 }; | ||
| var obj2 = { x: 5, y: 5, w: 0, h: 0, string: 'test', id: 4234 }; | ||
| qt.put(obj1); | ||
| qt.put(obj2); | ||
| qt.remove(obj1, 'id'); // only obj1 removed | ||
| qt.remove(obj1); // obj2 removed | ||
| ``` | ||
| Please note that despite passing `'id'` as the identifying attribute, the object passed to `put` must still have the same `x, y, w, h` properties as the object to be removed. `remove` traverses the tree similarly as `put`, so if these properties are not the same, it is possible that the object to be removed is not found. | ||
| License | ||
@@ -73,0 +102,0 @@ --- |
@@ -21,2 +21,11 @@ var QuadTree = require('../qtree.js'); | ||
| var obj1 = { x: 5, y: 5, w: 0, h: 0, string: 'test', id: 4233 }; | ||
| var obj2 = { x: 5, y: 5, w: 0, h: 0, string: 'test', id: 4234 }; | ||
| qt.put(obj1); | ||
| qt.put(obj2); | ||
| assert(qt.remove(obj1, 'id') == 1); // only obj1 removed | ||
| assert(qt.remove(obj1) == 1); // obj2 removed | ||
| var pts = []; | ||
@@ -34,2 +43,16 @@ for( var pi = 0; pi < 10000; pi++ ) { | ||
| } | ||
| var removed3 = {}; | ||
| for( var pi = 0; pi < pts.length; pi++ ) { | ||
| if( Math.random() < 0.1 ) { | ||
| if( Math.random() < 0.5 ) { | ||
| assert(qt.remove(pts[pi]) == 1); // remove without attr | ||
| assert(qt.remove(pts[pi], 'i') == 0); // remove with attr | ||
| } else { | ||
| assert(qt.remove(pts[pi], 'i') == 1); // remove with attr | ||
| assert(qt.remove(pts[pi]) == 0); // remove without attr | ||
| } | ||
| removed3[pts[pi].i + ''] = true; | ||
| } | ||
| } | ||
@@ -56,5 +79,8 @@ function overlap_rect(o1, o2, buf) { | ||
| }; | ||
| var buf = Math.max(0, Math.random() - 0.25); | ||
| var result1 = {}; | ||
| qt.get(area, function(obj) { | ||
| assert(!result1[obj.i + ''], 'duplicate get return'); | ||
| assert(!removed3[obj.i + ''], 'deleted object returned'); | ||
| result1[obj.i + ''] = true; | ||
@@ -65,2 +91,4 @@ return true; | ||
| qt.get(area, 0, function(obj) { | ||
| assert(!result2[obj.i + ''], 'duplicate get return'); | ||
| assert(!removed3[obj.i + ''], 'deleted object returned'); | ||
| result2[obj.i + ''] = true; | ||
@@ -74,2 +102,4 @@ return true; | ||
| qt.get(area, buf, function(obj) { | ||
| assert(!result3[obj.i + ''], 'duplicate get return'); | ||
| assert(!removed3[obj.i + ''], 'deleted object returned'); | ||
| result3[obj.i + ''] = true; | ||
@@ -80,6 +110,11 @@ return true; | ||
| var pt = pts[pi]; | ||
| if( overlap_rect(area, pt, buf) ) | ||
| assert(result3[pt.i+''], 'invalid result: ' + | ||
| if( removed3[pt.i+''] ) | ||
| continue; | ||
| if( overlap_rect(area, pt, buf) ) { | ||
| assert(result3[pt.i+''], | ||
| 'invalid result: ' + | ||
| JSON.stringify(area) + ' ' + JSON.stringify(pt) + ' ' + | ||
| buf + ' ' + qti + ' ' + result3[pt.i+'']); | ||
| delete result3[pt.i+'']; | ||
| } | ||
| } | ||
@@ -86,0 +121,0 @@ } |
New alerts
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
Fixed alerts
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
Improved metrics
- Total package byte prevSize
- increased by37.3%
17506
- Number of package files
- increased by20%
6
- Lines of code
- increased by37.96%
378
- Number of lines in readme file
- increased by37.18%
107
No dependency changes