simple-quadtree - npm Package Compare versions

Comparing version 0.1.2 to 0.1.3

package.json

 {
     "name": "simple-quadtree",
-    "version": "0.1.2",
+    "version": "0.1.3",
     "description": "quadtree data structure",
@@ -5,0 +5,0 @@ "main": "qtree.js",

qtree.js

@@ -0,1 +1,10 @@
+/**
+*
+* simple-quadtree is a minimal quadtree implementation that supports simple put, get,
+* remove and clear operations on objects having a x, y position and w, h dimension.
+*
+* Copyright (c) 2013 Antti Saarinen <[e-mail]>
+* https://github.com/asaarinen/qtree
+*
+*/
 function QuadTree(x, y, w, h, options) {
@@ -35,2 +44,4 @@
             return false;
+        if( obj.w < 0 || obj.h < 0 )
+            return false;
         return true;
@@ -172,3 +183,3 @@ }
         var leaf = isleaf(node, obj);
-        if( leaf )
+        if( leaf.leaf )
             node.l.push(obj);
@@ -180,3 +191,74 @@ else if( leaf.childnode )
     }
+    
+    function update_coords(obj, updatedcoords) {
+        obj.x = ((typeof updatedcoords.x == 'number') ? updatedcoords.x : obj.x);
+        obj.y = ((typeof updatedcoords.y == 'number') ? updatedcoords.y : obj.y);
+        obj.w = ((typeof updatedcoords.w == 'number') ? updatedcoords.w : obj.w);
+        obj.h = ((typeof updatedcoords.h == 'number') ? updatedcoords.h : obj.h);
+    }
 
+    function update(node, obj, attr, updatedcoords) {
+        if( typeof attr == 'object' && typeof updatedcoords == 'undefined' ) {
+            updatedcoords = attr;
+            attr = false;
+        }
+
+        if( !validate(obj) || typeof updatedcoords == 'undefined' )
+            return false;
+
+        if( !attr )
+            attr = false;
+        else if( typeof attr != 'string' )
+            attr = 'id';
+
+        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) ) ) {
+
+                // found the object to be updated
+                var orig = node.c[ci];
+                update_coords(orig, updatedcoords);
+                
+                if( orig.x > node.x + node.w ||
+                    orig.y > node.y + node.h ||
+                    orig.x + orig.w < node.x ||
+                    orig.y + orig.h < node.y ) {
+
+                    // this object needs to be removed and added
+                    node.c.splice(ci, 1);
+                    put(root, orig);
+                } // updated object is still inside same node
+                
+                return true;
+            }
+        
+        for( var ci = 0; ci < node.l.length; ci++ )
+            if( ( attr && node.l[ci][attr] == obj[attr] ) ||
+                ( !attr && isequal(node.l[ci], obj) ) ) {
+                
+                var orig = node.l[ci];
+                update_coords(orig, updatedcoords);
+                
+                // found the object to be updated
+                if( orig.x > node.x + node.w ||
+                    orig.y > node.y + node.h ||
+                    orig.x + orig.w < node.x ||
+                    orig.y + orig.h < node.y ) {
+
+                    // this object needs to be removed and added 
+                    node.l.splice(ci, 1);
+                    put(root, orig);
+                } // updated object is still inside same node
+                
+                return true;
+            }
+
+        var leaf = isleaf(node, obj);
+        if( !leaf.leaf && leaf.childnode )
+            if( update(leaf.childnode, obj, attr) )
+                return true;
+        return false;
+    }
+
     // remove an object from this node
@@ -216,3 +298,3 @@ function remove(node, obj, attr) {
     // put an object to this node
-    function put(node, obj, removeflag) {
+    function put(node, obj) {
 
@@ -243,14 +325,20 @@ if( !validate(obj) )
     // function
-    function getter(overlapfun, node, obj, buf, strict, callback) {
+    function getter(overlapfun, node, obj, buf, strict, callbackOrArray) {
         for( var li = 0; li < node.l.length; li++ )
             if( !strict || overlapfun(obj, node.l[li], buf) )
-                if( !callback(node.l[li]) )
+                if( typeof callbackOrArray == 'object' )
+                    callbackOrArray.push(node.l[li]);
+                else if( !callbackOrArray(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]) )
+                if( typeof callbackOrArray == 'object' )
+                    callbackOrArray.push(node.c[li]);
+                else if( !callbackOrArray(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) )
+                if( typeof callbackOrArray == 'object' )
+                    callbackOrArray.concat(getter(overlapfun, node.n[ni], obj, buf, strict, callbackOrArray));
+                else if( !getter(overlapfun, node.n[ni], obj, buf, strict, callbackOrArray) )
                     return false;
@@ -263,4 +351,4 @@ }
     // iterate through all objects in this node matching the given rectangle
-    function get_rect(node, obj, buf, callback) {
-        return getter(overlap_rect, node, obj, buf, true, callback);
+    function get_rect(node, obj, buf, callbackOrArray) {
+        return getter(overlap_rect, node, obj, buf, true, callbackOrArray);
     }
@@ -270,4 +358,4 @@
     // line (segment)
-    function get_line(node, obj, buf, callback) {
-        return getter(overlap_line, node, obj, buf, false, callback);
+    function get_line(node, obj, buf, callbackOrArray) {
+        return getter(overlap_line, node, obj, buf, false, callbackOrArray);
     }
@@ -277,10 +365,14 @@
     // geometry, either a rectangle or a line segment
-    function get(node, obj, buf, callback) {
+    function get(node, obj, buf, callbackOrArray) {
 
-        if( typeof buf == 'function' && typeof callback == 'undefined' ) {
-            callback = buf;
+        if( (typeof buf == 'function' || typeof buf == 'object') && typeof callbackOrArray == 'undefined' ) {
+            callbackOrArray = buf;
             buf = 0;
         }
+        if( typeof callbackOrArray == 'undefined' ) {
+            callbackOrArray = [];
+            buf = 0;
+        }
         if( obj == null )
-            get_rect(node, obj, buf, callback);
+            get_rect(node, obj, buf, callbackOrArray);
         else if( typeof obj.x == 'number' &&
@@ -292,8 +384,10 @@ typeof obj.y == 'number' &&
                 !isNaN(obj.dx) && !isNaN(obj.dy) )
-                get_line(node, obj, buf, callback);
+                get_line(node, obj, buf, callbackOrArray);
             else if( typeof obj.w == 'number' &&
                      typeof obj.h == 'number' &&
                      !isNaN(obj.w) && !isNaN(obj.h) )
-                get_rect(node, obj, buf, callback);
+                get_rect(node, obj, buf, callbackOrArray);
         }
+        if( typeof callbackOrArray == 'object' ) 
+            return callbackOrArray;
     }
@@ -303,4 +397,4 @@
     return {
-        get: function(obj, buf, callback) {
-            get(root, obj, buf, callback);
+        get: function(obj, buf, callbackOrArray) {
+            return get(root, obj, buf, callbackOrArray);
         },
@@ -310,5 +404,11 @@ put: function(obj) {
         },
+        update: function(obj, attr, updatedcoords) {
+            return update(root, obj, attr, updatedcoords);
+        },
         remove: function(obj, attr) {
             return remove(root, obj, attr);
         },
+        clear: function() {
+            root = createnode(x, y, w, h);
+        },
         stringify: function() {
@@ -315,0 +415,0 @@ var strobj = {

README.md

 simple-quadtree
 =====
 
-`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. 
+`simple-quadtree` is a minimal quadtree implementation that supports simple `put`, `get`, `remove` and `clear` operations on objects having a `x, y` position and `w, h` dimension. 
 
@@ -39,2 +39,4 @@ Installation
 
+Each `w` and `h` property must be nonnegative.
+
 ### Getting objects
@@ -47,3 +49,3 @@
     // obj == {x: 5, y: 5, w: 0, h: 0, string: 'test'}
-});	     
+});
 ```
@@ -53,2 +55,9 @@
 
+Alternatively you can omit the callback to return an array of all matching objects:
+
+```javascript
+var result = qt.get({x:0, y: 0, w: 10, h: 10});
+    // result == [{x: 5, y: 5, w: 0, h: 0, string: 'test'}]
+```
+
 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:
@@ -76,15 +85,34 @@
 
-### Removing objects
+### Modifying objects
 
-To remove objects, call `remove` with the original object that was passed to `put`:
+In order to remove or update an object already in the quadtree, you have to identify the object. By default, `update` and `remove` affect all objects with `x, y, w, h` identical to the passed object. 
 
+If you want to remove only a specific object, you can should pass the name of the uniquely identifying property to `update` and `remove`.
+
+### Updating objects
+
+If the coordinates of an object already put into the quadtree change, you should call `update` to make sure it is still indexed in the right location:
+
 ```javascript
 var obj = { x: 5, y: 5, w: 0, h: 0, string: 'test', id: 4233 };
 qt.put(obj);
-qt.remove(obj); // removed
+
+assert(obj.x == 5);
+qt.update(obj, 'id', { x: 10 }); // change obj.x to 10
+assert(obj.x == 10); 
 ```
 
-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`:
+Call to `update` also modifies the coordinates of the object to be updated, and returns `true` if the object was correctly updated and `false` if the object to be updated was not found.
 
+Please note that despite passing `'id'` as the identifying attribute, the object passed to `update` must still have the same `x, y, w, h` properties as the original inserted object. `update` traverses the tree similarly as `put`, so if these properties are not the same, it is possible that the object to be updated is not found.
+
+### 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); // remove all objects with matching coordinates
+
 var obj1 = { x: 5, y: 5, w: 0, h: 0, string: 'test', id: 4233 };
@@ -96,2 +124,3 @@ var obj2 = { x: 5, y: 5, w: 0, h: 0, string: 'test', id: 4234 };
 
+// remove by uniquely identifying attribute
 qt.remove(obj1, 'id'); // only obj1 removed
@@ -103,2 +132,12 @@ qt.remove(obj1); // obj2 removed
 
+### Clearing the quadtree
+
+To clear the quadtree call clear:
+
+```
+qt.clear();
+```
+
+This creates a new root node effectively putting the existing one up for garbage collection.
+
 License
@@ -105,0 +144,0 @@ ---

test/test-qtree.js

@@ -32,87 +32,126 @@ var QuadTree = require('../qtree.js');
     for( var pi = 0; pi < 10000; pi++ ) {
-	var pt = {
-	    x: ( Math.random() - 0.5 ) * 100,
-	    y: ( Math.random() - 0.25 ) * 100,
-	    w: Math.pow(Math.random(), 3) * 100,
-	    h: Math.pow(Math.random(), 3) * 100,
-	    i: pi
-	}
-	pts.push(pt);
-	qt.put(pt);
+        var pt = {
+            x: ( Math.random() - 0.5 ) * 100,
+            y: ( Math.random() - 0.25 ) * 100,
+            w: Math.pow(Math.random(), 3) * 100,
+            h: Math.pow(Math.random(), 3) * 100,
+            i: pi
+        }
+        pts.push(pt);
+        qt.put(pt);
     }
 
+    // make some updates
+    for( var pi = 0; pi < pts.length; pi++ ) {
+        var newc = {};
+
+        if( Math.random() < 0.2 )
+            newc.x = pts[pi].x + (Math.random() - 0.5) * 60;
+        if( Math.random() < 0.2 )
+            newc.y = pts[pi].y + (Math.random() - 0.5) * 60;
+        if( Math.random() < 0.2 )
+            newc.w = pts[pi].w * 2 * Math.random();
+        if( Math.random() < 0.2 )
+            newc.h = pts[pi].h * 2 * Math.random();
+        for( var c in newc ) {
+            assert(qt.update(pts[pi], 'i', newc));
+            for( var c2 in newc ) 
+                assert(pts[pi][c2] == newc[c2]);
+            break;
+        }
+    }
+    
     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;
-	}
+        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;
+        }
     }
-    
+
     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;
     }
-    
-    var areas = [];
-    for( var ai = 0; ai < 100; ai++ ) {
-	//process.stderr.write('testing area ' + ai + '\n');
-	var area = {
-	    x: ( Math.random() - 0.5 ) * 100,
-	    y: ( Math.random() - 0.25 ) * 100,
-	    w: Math.pow(Math.random(), 3) * 100,
-	    h: Math.pow(Math.random(), 3) * 100
-	};
 
-	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;
-	    return true;
-	});
-	var result2 = {};
-	qt.get(area, 0, function(obj) {
-	    assert(!result2[obj.i + ''], 'duplicate get return');
-	    assert(!removed3[obj.i + ''], 'deleted object returned');
-	    result2[obj.i + ''] = true;
-	    return true;
-	});
+    // get all objects
+    for( var pi = 0; pi < pts.length; pi++ ) {
+        var area = {
+            x: pts[pi].x - 0.5,
+            y: pts[pi].y - 0.5,
+            w: 1, h: 1
+        };
+        var res = [];
+        qt.get(area, res);
 
-	assert.deepEqual(result1, result2, 'passing buffer fails');
+        for( var ri = 0; ri < res.length; ri++ ) {
+            if( res[ri].i == pts[pi].i )
+                break;
+        }
 
-	var result3 = {};
-	qt.get(area, buf, function(obj) {
-	    assert(!result3[obj.i + ''], 'duplicate get return');
-	    assert(!removed3[obj.i + ''], 'deleted object returned');
-	    result3[obj.i + ''] = true;
-	    return true;
-	});
-	for( var pi = 0; pi < pts.length; pi++ ) {
-	    var pt = pts[pi];
-	    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+'']; 
-	    }
-	}
+        assert((removed3[pts[pi].i+''] && ri == res.length) ||
+               (!removed3[pts[pi].i+''] && ri < res.length));
     }
+    
+    var areas = [];
+    for( var ai = 0; ai < 100; ai++ ) {
+        //process.stderr.write('testing area ' + ai + '\n');
+        var area = {
+            x: ( Math.random() - 0.5 ) * 100,
+            y: ( Math.random() - 0.5 ) * 100,
+            w: Math.pow(Math.random(), 3) * 100,
+            h: Math.pow(Math.random(), 3) * 100
+        };
+        
+        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;
+            return true;
+        });
+        var result2 = {};
+        qt.get(area, 0, function(obj) {
+            assert(!result2[obj.i + ''], 'duplicate get return');
+            assert(!removed3[obj.i + ''], 'deleted object returned');
+            result2[obj.i + ''] = true;
+            return true;
+        });
+        
+        assert.deepEqual(result1, result2, 'passing buffer fails');
+        
+        var result3 = {};
+        qt.get(area, buf, function(obj) {
+            assert(!result3[obj.i + ''], 'duplicate get return');
+            assert(!removed3[obj.i + ''], 'deleted object returned');
+            result3[obj.i + ''] = true;
+            return true;
+        });
+        for( var pi = 0; pi < pts.length; pi++ ) {
+            var pt = pts[pi];
+            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+'']; 
+            }
+        }
+    }
 }
 process.stdout.write('tests ok\n');

New alerts

License Policy Violation

License

This 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

License

This 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

27261

increased by35.92%

Lines of code

525

increased by29.31%

Number of lines in readme file

148

increased by35.78%

No dependency changes