mourner / rbush Goto Github PK

Inserting (maxEntries + 2) empty bboxes in a rbush fails with:

"TypeError: Cannot read property 'leaf' of undefined
at Object.rbush._chooseSubtree (https://rawgit.com/mourner/rbush/master/rbush.js:279:21)
at Object.rbush._insert (https://rawgit.com/mourner/rbush/master/rbush.js:316:25)
at Object.rbush.insert

To trace down the error, I put together this JSBin: http://jsbin.com/bidaqov/15/edit?js,console
It shows that at https://github.com/mourner/rbush/blob/master/rbush.js#L286 ,
the function enlargedArea returns NaN. Because of this, none of the if/else-if statements are matched and targetNode is never initialized.

The next while(true) loop iteration fails when accessing node.leaf

Bounding box is defined as [minX, minY, maxX, maxY]; the _infinite function should be:

_infinite: function () { 
  return [Infinity, -Infinity, Infinity, -Infinity]; 
}

instead of:

_infinite: function () { 
  return [Infinity, Infinity, -Infinity, -Infinity]; 
}

The entries/nodes I store in RBush have many properties, including an 'id' field.
When performing a search-query, I only need a list of ids, rather than a list of entries.

To do so, I currently use the map function:

var entries = tree.search(bbox);
var ids = entries.map(function(val) {
    return val.id;
});

For my specific case, it would be nice if RBush could offer this functionality for me, so that I don't need to convert the result myself anymore. (Note: changing the result.push(child); into an result.push(child.id); in rbush's search method does the trick.)

To do this, the search-function could take a second, optional parameter where I can pass the string ".id". This would work similar to the constructor method that accepts a format (and which is awesome!).

However, I'm not sure if there is enough demand for this feature and if it makes sense to put it into RBush.

RBush is often used for collisions, so lets make a method that does the same as search but without collecting/returning items, just true/false.

A little surprised to find the following…

It's great that I can declare the schema for input data:

tree = rbush(16, ["['x']", "['y']", "['x']", "['y']"]);
tree.insert(point);

But I would expect search (etc.) to use the same schema:

tree.search(point) // []

Instead I need to:

tree.search(tree.toBBox(point)) // [point]

I'm guessing a conscious decision, rather than a bug?

I'm comparing a couple of different approaches for finding all intersections in a set of boxes and am having some trouble with rbush. What I would like to do for this benchmark is just count the number of unique pairs of intersecting boxes in a data set. Here is the code which I am using:

var tree = rbush(9).load(boxes)
var count = 0
for(var i=0, n=boxes.length; i<n; ++i) {
  count += tree.search(boxes[i]).length - 1
}
console.log('num intersections =', count >>> 1)

I think this is correct based on my understanding of the API (though maybe I made a mistake). However it doesn't produce the expected result. The problem is that rbush seems to be missing a bunch of intersections. For example, if I run it on this set of boxes (using the [minX, minY, maxX, maxY] convention):

var boxes= [ [ 0.34745634417049587,
    0.19826999702490866,
    0.4911531714024022,
    0.31181562286801634 ],
  [ 0.3350245540495962,
    0.08664853242225945,
    0.5047857862198726,
    0.24504178347997368 ],
  [ 0.5165957966819406,
    0.8958366981241852,
    0.654163204645738,
    0.9974054682301358 ],
  [ 0.31746723409742117,
    0.05729875573888421,
    0.4619402693584561,
    0.16601366791874173 ],
  [ 0.48703365214169025,
    0.06490733567625284,
    0.591369220148772,
    0.16663535516709088 ],
  [ 0.22250890382565558,
    0.8383511677384377,
    0.35378385097719733,
    0.9443910819012672 ],
  [ 0.1840909782331437,
    0.32956261769868433,
    0.35404338778462263,
    0.4312351857777685 ],
  [ 0.1586302185896784,
    0.4483339211437851,
    0.3295042036101222,
    0.643072936614044 ],
  [ 0.3659458786714822,
    0.9313615325372666,
    0.4676822068169713,
    1.1038383034523576 ],
  [ 0.731653404654935,
    0.9573151601944119,
    0.8854661131510511,
    1.0714723680866882 ] ]

rbush reports only 3 intersections, but by brute force I can find 11.

Is there something I am doing wrong here?

Adding 50000 items to a tree one by one in FF takes about 10s compared to 300ms in Chrome.

To reproduce, open viz/viz-uniform.html and click "Insert 50000 one by one" button. You'll see timing in the console.

Just wanted to say thanks for making rbush and making it so easy to work with. We've never had any major issues with it and have always been impressed by its performance. You have truly made our lives easier. 😄

Now, to add a point, you have to do:

tree.insert([20, 40, 20, 40]);

It would be simplier to do:

tree.insert([20, 40]);

What do you think?

Hi,

I've seen the performance benchmarks on the readme page, which look impressive.
However, when adding cities from "all-the-cities" (as in your geokdbush and geoflatbush test scripts), I am seeing quite slow performance.

I have created a very simple project to test this by creating an empty node.js project with the following code in index.js and running it.

const rbush = require('rbush');
var cities = require('all-the-cities');

console.log("creating new r tree")

tree = rbush(16, ['[0]', '[1]', '[0]', '[1]']);

for(i=0; i<cities.length; i++) {
    console.log("i: "+i);
    var city = cities[i];
    tree.insert(city.lon, city.lat);
}

initially it rattles through the first 300-400 very quickly, but then seems to exponentially slow down with the more data it loads. After ~1000 points it takes roughly 1 second for every insert.

Is this behaviour expected?

Hello, sometimes after many inserts and deletes from tree i recieve strange error

TypeError: Cannot read property 'push' of undefined
at rbush._insert (./node_modules/rbush/index.js:301:22)
at rbush.insert (./node_modules/rbush/index.js:120:24)

Any idea? Config of inserted items seems to be ok.

Thank you

Thanks for these great functions !
I have been playing with rbush for the last few hours and I wonderd whether it was possible to think of an efficient (clever?) way of getting the largest set of elements that do not overlap one with each other.
Or at least a 'big enough' set, obtained by traversing the rbush tree and recursively removing overlapping rectangles?
Have you been thinking of this before? Is it something that could be of interest to others (than me!)?
Cheers,

After removing all items from an rbush, inserting new items fails.

Quick steps to reproduce

• Go to the uniformly distributed random data demo
• Click the "Remove leftmost 10000" button five times
• Click "Insert 1000" button
• Observe that no new items are added

Extra information

The console displays:

Uncaught TypeError: Cannot read property 'leaf' of undefined rbush.js:223
rbush._chooseSubtree rbush.js:223
rbush._insert rbush.js:259
rbush.insert rbush.js:89
(anonymous function) viz-uniform.html:37

Hi,

This is an amazing lib, thanks for working on this!

I just upgraded to 2.0 and noticed that search/collide methods seem to always accept input with only the new minX/minY/maxX/maxY data format properties. Would it make sense to support custom data formats here for consistency?

Wouldn't it be more clear to have rbush.search() take an item (or an object formatted as one) instead of an array of AABB coordinates? This way, search() would take into account the second argument of the rbush constructor, which is more logical (I hunted for an issue for quite some time before I realized I had to pass an Array and not an item).
Also, creating an array for every search is not very memory efficient. I know we could reuse the same array, but that's a pain in the ass. So, as many people will search based on items (I think), having an item-based search is jutifiable.
Additionally, if you want both behaviours, why not have two methods (one for arrays, one for items)?

Hi @mourner

Just wondering if you're open to converting this to an ES6 module as per the approach you've taken with quickselect.

If you are happy I'm willing to put together the pull request.

Thanks,
Rowan

Hey.

First of all, this is a very nice project!

One thing I noted was the fact that the latest version available on bower is several versions behind this repository. This should be updated since a lot of nice feature, tweaks etc. have been made since version 1.3.5 available on bower.

/ Morten

~~

Never mind, I just found it near the bottom of the readme x)

you need to include license text for MIT license

The documentation mentions that rbush can be used with points instead of rectangles by specifying custom accessors:

var tree = rbush(9, ['[0]', '[1]', '[0]', '[1]']); // accept [x, y] points
tree.insert([20, 50]);

But it doesn't explain whether this is a good idea—if I have a million points and want to do bounding box queries, will I be happier using rbush or something less general like a quadtree?

Thanks for the great library!

It's worth testing out non-native sort implementations like non-recursive quicksort for browsers other than Chrome, as we don't care for sorting stability and quicksort is faster than merge sort.

First, absolutely amazing package. Best out there.

I've spent a good part of day debugging my own code and that, combined with increased incidence of bug inversely proportional to specified maximum number of entries in a tree node, leads me to believe it might be related to this package.

To describe use case, every ~20 times a second, I update (remove/add) ~100 entities of tree with ~10000 entries, remove a few, and after a while tree.all().length seems to steadily increase. The lower maximum number of entries in tree node, the higher the incidence. In example, for 2 about 50% of nodes don't get removed, and for 64 just a few percent.

I'll make a minimal reproduction case in next few days if there's need, but just wanted to start discussion.

I want to insert [x,y] items and then remove them if the item to be removed has x and y equal to that of the item in the tree.

I follow the following for inserting:
var tree = rbush(9, ['[0]', '[1]', '[0]', '[1]']); // accept [x, y] points
tree.insert([20, 50]);

Would the following work for removal:
tree.remove([20,50], function(a,b){return a.minX == b.minX && a.minY == b.minY ;})

I made a few trial,errors.
And i wasn't able to use this module with lat/lng coordinates.

Is this normal, should i compute the projection of my coodinates before using rbush?

When bulk-loading 91 items into rbush(10), the very last leaf contains only 1 item (as opposed to at least 4, as in Math.max(2, Math.ceil(this._maxEntries * 0.4))).

I've found that, after adding enough data, MSIE8 creates nodes with infinite/-infinite coordinates (this will make the bush crash when more items are added, or when searching for an item).

The simplest reproducible case I could come up with is this:

var bush = rbush();

// Force the bush to split much earlier
bush._maxEntries = 2;
bush._minEntries = 1;

bush.insert( [-449,235,-329,277,] );
bush.insert( [-449,262,-425,286,] );
bush.insert( [-215,200,-49,242,]  );
bush.insert( [-215,227,-191,251,] );
bush.insert( [222,98,298,140,]    );
bush.insert( [222,125,246,149,]   );

console.log(bush.data.children[1].bbox);

// On MSIE8:          [Infinity, Infinity, -Infinity, -Infinity]
// Any other browser: [ -449, 200, -49, 286 ]

If _minEntries and _maxEntries are set to the default values of 4 and 9, the bug is reproducible after inserting about 30-40 items.

The bug is reproducible with MSIE8, or MSIE11 emulating MSIE8. I haven't tried polyfilling ecmascript5 functionality.

Currently, the bulk loading algorithm partitions each node into approximately sqrt(N) x sqrt(N) child nodes. This becomes a problem if a node is not a perfect square — child nodes will get narrower the deeper you go. I noticed this problem when looking at the viz for a rectangular data space:

Notice the very narrow rectangles at the bottom. We could fix this by designing an algorithm that picks a K x M partitioning that takes the aspect ratio of a node into account, to make child nodes approach square shape no matter how narrow they are. This should make query performance on bulk-loaded trees better.

cc @danpat

This is a question about the proper way to handle an object that is moving around in an r-bush. Would one remove the object and add it every time it moves, or is there a more efficient way? In the documentation it said something about deleted items not actually being removed from the list.

I'm considering a breaking API change that will make RBush more performant, but also more verbose, by replacing internal representation of bounding boxes from a 4-length array to a 4-property object. V8 handles object literals faster, and this also allows simplifying some internal logic. API-wise, this would look like this:

// before
tree.insert([20, 40, 30, 50]);
tree.search([5, 6, 10, 12]);

// after
tree.insert({minX: 20, minY; 40, maxX: 30, maxY: 50});
tree.search({minX: 5, minY: 6, maxX: 10, maxY: 12});

You would still be able to configure a custom format for inserted items, but would have to change search to use object literals for bbox instead of arrays in any case.

The tree node JSON format would also change:

// before
{
  children: [...],
  height: 1,
  bbox: [0, 0, 20, 20],
  leaf: true
}

// after
{
  children: [...],
  height: 1,
  minX: 0,
  minY: 0,
  maxX: 20,
  maxY: 20,
  leaf: true
}

This is implemented in memory-perf branch that I'm increasingly using in my new algorithmic experiments. The benchmark results (in Node 6.2.2) are as follows:

# master, items: 1000000, nodeSize: 16
insert one by one: 4969.933ms
1000 searches 10%: 2534.136ms
1000 searches 1%: 472.504ms
1000 searches 0.01%: 61.429ms
remove 1000 one by one: 26.362ms
bulk-insert 1M more: 1506.807ms
1000 searches 1%: 839.277ms
1000 searches 0.01%: 107.652ms

# memory-perf, items: 1000000, nodeSize: 16
insert one by one: 3523.986ms
1000 searches 10%: 2202.467ms
1000 searches 1%: 345.745ms
1000 searches 0.01%: 31.921ms
remove 1000 one by one: 30.391ms
bulk-insert 1M more: 1226.326ms
1000 searches 1%: 610.299ms
1000 searches 0.01%: 71.066ms

@twpayne @tschaub @mbloch @oscarlorentzon @vkurchatkin @bhousel — does this sound acceptable? I would bump the major version for this of course.

Hello,
I would like to use a query rectangle over the antimeridian as shown in the following example:

• ref. Geographic Bounding Boxes by Jason Davies

Would it be possible to add the browser versions to the repo please?
(It would be useful if we could access this via dependencies since our proxy sometimes prevents us accessing the link.)

it would be nice to have an easy way to tell rbush that it can find the bbox array somewhere besides the root, i.e. if you have an object that has it's bbox in item.bbox, maybe pass a 'string' to format instead of an array and have _initFormat do this for strings, can do a pull.

Hi,

I was glad that I found this powerful and tiny library and from beginning I relied on this statement or feature : "var tree = rbush(9, ['[0]', '[1]', '[0]', '[1]']);" - to incorporate custom element defined by svg paths

so I put together some local test but seems it is not working as I expected - my output from collide detection looks like element is always evaluated as rectangle. Is it expected behavior or am I doing something wrong ? does this algorithm support searching for custom elements let say irregular polygon?

Thank You
BR

I did the following:

var arr = [[1,2],[3,4],[5,6]];
var rtree = new rbush(2);
rtree.load(arr);
var pts = rtree.search({minX:0,minY:0,maxX:10,maxY:10});

This returns 0 points. On investigating I find that this.data of rbush has minX,maxX etc set to NaN.

I did the following modification but got the same result;
. Using arrays of rectangles where minX and maxX were same eg..
var arr = [ {minX:1, minY:2, maxX:1, maxY:2} ....]
var rtree = new rbush(4);

The README mentions that RBush can index points, but it also says that the data format is [minX, minY, maxX, maxY] which seems to also be reflected in the code. How are points indexed? Does it work to set minX = maxX and minY = maxY?

Hi there,

I have a bunch of polygons, and a lineSegment, and I'm using rbush to try and determine if the line segment intersects with any of the polygons. Here's in pseudo code what I do:

1- for each line segment in each polygon, calculate it's bounding box and add it to an array
2- when done, bulk load the array of bboxes to the tree
3- create a bbox around the line segment to search for
4- search for bounding boxes in the tree that are covered by the bounding box of the line segment
5- for all of those, loop through the original line segments and do a simple line intersect check

This gets inefficient if the line i'm looking for is a (long) diagonal, because the bounding box gets large. To counteract this, I actually split the line segment up in to smaller line segments and draw a bounding box around each smaller segment, and then use those to do the search in the tree...

Are there better ways to do this? Is there a way to do a search in the tree for just a line segment so that it returns the bounding boxes the line crosses (which I'd then have to check for true intersection)

Or is there even a completely different, more efficient way you would recommend to check if one line segment intersects with any part of a hundred or so different polygons?

I am trying to use R-bush in a situation where I have a lot of infinitely long lines parallel to the horizontal and vertical axis. It seems like this results into problems with the rectangle assignment.

I am not really sure if it is possible to use an R-tree for this type of data? (I do not have any problems when I use jsts strtee). Would you have any idea what could be going wrong here?

Is the time complelxity of search and insert close to log n ?

Is it better to give the max number of points in constructor than to not provide

it would be nice to be able to delete an item based on it having some value instead of by reference.

Having to do everything by reference complicates things a bit, e.g. loading from json from a server when you also get the same objects in some other way from the server can get different objects which look the same but aren't really the same.

hey! just found your library and I'm trying to figure out if it meets my needs. I have a game with moving creatures and I'm looking to optimize spatial searches, which this looks great at. One thing, though, is that creatures move around a lot, and I'm not sure how performant it would be to constantly remove/add the entry back into the tree. It could be theoretically 1000 times per second.

If it would still perform ok I'd be ok using it, but I'm not sure if there's a fast way to move something in an r-tree as opposed to adding/removing it.

add the ability to pass a function to the format argument, something like a function that returns a bbox given an object

Hello,
I really like this project and it helped me a lot for my Advanced Data Structures course at university :) so thank you for making it!
Anyway, I used your project to make interactive R-tree visualization tool. You can see the details here: http://rtree.tomasjadrny.cz

If you would like it, I could make a pull request to add it to your examples. What do you think?

I've implemented clone this way:

const newTree = rbush();
newTree.fromJSON(JSON.parse(JSON.stringify(tree.toJSON())));

but I imagine there might be a faster way for rbush itself to do this.

(My use case is that I'd like to create a new version of the tree with a few additional locations added.)

The update says:

Breaking: changed the default format of inserted items from [20, 40, 30, 50] to {minX: 20, minY: 40, maxX: 30, maxY: 50}.

Does this mean we cannot add points now but only rectangles? Can we add a point by putting minX = maxX ?

Hi,

Sweet Library! I'm looking at using this library for Geographical data points, so understand that I can't use this as standard, due to the curvature of earth/wrap around at the date line. I'd like to use this library over kdbush/flatbush as I need to be able to dynamically add and remove data points. I only plan on doing short distance radial searches (i.e find all data points within a 100m circle of this point).

Is there any plan to add a "georbush" extension to this library?

Having (very briefly) looked through the source code for your geoflatbush library, I suspect I could alter it to work with this library. However, I also looked at the source code for the geokdbush library and found the underlying trigonometry to be different for the 2 libraries. If I was to repurpose one of these libraries, are either of the libraries better than the other for relatively short distance radial searches?

Publish this library to http://bower.io/

I'm trying to find solutions for same problems in 3d. Do you have any suggestions? Do you see anything blocking that would prevent me from simply making fork of this and adding 1 more axis?