leaflet-extras / rtree

R-Tree Library for Javascript, optimized for maps.

#rTree

A non-recursive R-Tree library in pure JavaScript with no dependencies. Fork of Jon-Carlos Rivera's fantastic library which sadly seems not to be maintained. MIT Licensed.

##So far:

• Bug fix when deleting points.
• Common.js module.
• Updated tests.
• Factory function for constructor.
• Method for dealing with GeoJSON.
• All methods now accept callbacks.
• Query by bbox instead of rectangle.
• Submit to NPM.
• Update examples.
• add closure
• add GruntFile
• fix syntax (make it pass jslint)
• more modular
• that bug with deleting

##API

• RTree ( [ Number max_node_width, Function callback ] )

###Parameters:

• max_node_width : optional : The maximum width of a node before a split is performed¹.

###Returns:

• An empty rTree object.

###Usage:

• Make a new rTree with a max node width of 10:
• var myRTree = RTree(10);

##rTree.insert

• rTree.insert ( Rectangle³ bounds, Object element)

###Parameters:

• bounds : required : A minimally bounding box for element.
• element : required : An object to add to the R-Tree.

###Returns:

• True.

###Usage:

• Insert a 10x10 object that starts at position 10x10:
• myRTree.insert({x:10, y:10, w:10, h:10}, myObject);

##rTree.remove

• rTree.remove ( Rectangle³ area _[, Object element)

###Parameters:

• area : required : An area to search within.
• element : optional : An object to remove from the R-Tree. If no object is specified, all elements that touch area are deleted.

###Returns:

• An array of leafs deleted from the R-Tree.

###Usage:

• Deletes all object that touch the 10x10 rectangle starting at position 10x10:
• var myDelCount = myRTree.delete({x:10, y:10, w:10, h:10});
• Delete only specific object if it touches the 10x10 rectangle starting at position 10x10:
• var myDelCount = myRTree.delete({x:10, y:10, w:10, h:10}, specific_object);

##rTree.geoJSON:

• rTree.geoJSON ( Object or Array geoJSON)

###Parameters

• geoJSON : required : Either an Object representing a GeoJSON feature collection or an Array representing a list of GeoJSON features.

###Usage:

myRTree.geoJSON({
	"type":"FeatureCollection",
	"features":[
		{
			"type":"Feature",
			"geometry":{
				"type":"Point",
				"coordinates":[100,1]
			},
			"properties":{
				"prop0":"value0"
			}
		},
		{
			"type":"Feature",
			"geometry":{
				"type":"LineString",
				"coordinates":[
					[100,0],
					[101,1]
				]
			},
			"properties":{
				"prop0":"value0"
			}
		}
	]
});

##rTree.bbox:

• rTree.bbox ( Bounds area)

###Parameters

• area : required : Area to search, this can either be represented by a single parameter bounds array [[x1,y1],[x2,y2]], two parameters representing the southwest and northeast corners [x1,y1],[x2,y2], or 4 parameters of [x1,y1,x2,y2].

###Returns:

• An array of matched features.

###Usage:

• Search a 10x10 area that starts at position 10x10 (these are all equivalent):
• var myObjects1 = myRTree.bbox([[10,10],[20,20]]);
• var myObjects2 = myRTree.bbox([[10,10],[20,20]]);
• var myObjects3 = myRTree.bbox([10,10],[20,20]);
• var myObjects4 = myRTree.bbox([10,10],[20,20]);
• var myObjects5 = myRTree.bbox(10,10,20,20);
• var myObjects6 = myRTree.bbox(10,10,20,20);

##rTree.search

• RTree.search ( Rectangle³ area [, Boolean return node, Array return_array ])

###Parameters:

• area : required : An area to search within.
• return node : optional : Whether to return the entire node, mainly internal option.
• return array : optional : An existing array to add the results to, defaults to [], mainly internal option.

###Returns:

• An array of objects that overlap or touch area.

###Usage:

• Search a 10x10 area that starts at position 10x10:
• var myObjects = myRTree.search({x:10, y:10, w:10, h:10});

###Notes

¹ Default max node width is currently 6.

³ A Rectangle is any object with public x, y, w, h properties. The object itself is not saved or used directly but copies are made of its x, y, w, h properties.

rtree's Issues

Comparison with rbush?

The README.md says that is is a port of Jon-Carlos Rivera's library. We used Jon-Carlos's RTree library in OpenLayers 3, but found that @mourner's rbush was much, much better. Compare the two screenshots below: the first is RTree, the second is rbush:


If this library is based on RTree, you may wish to consider switching to rbush.

Indicate in Readme that it's a fork, add what's new/different

MiRaC

Good

more tests

need tests for rTree.geoJSON and rTree.bbox

Floating point precision issues when searching for exact points

Hi there, so I've run into an issue with floating point precision when searching for exact points in an rtree. For a demonstration of this bug, grab my test case located on my fork here and run it a few times on the current build. You'll get some output similar to this:

$ node searchexact.test.js
TAP version 13
# RTree Searching for exact point
not ok 1 1k In-Bounds Searches
  ---
    operator: equal
    expected: 1000
    actual:   997
    at: Test.<anonymous> (/home/centos/proj/rtree/RTree/test/searchexact.test.js:23:5)
  ...

1..1
# tests 1
# pass  0
# fail  1

$ node searchexact.test.js
TAP version 13
# RTree Searching for exact point
not ok 1 1k In-Bounds Searches
  ---
    operator: equal
    expected: 1000
    actual:   997
    at: Test.<anonymous> (/home/centos/proj/rtree/RTree/test/searchexact.test.js:23:5)
  ...

1..1
# tests 1
# pass  0
# fail  1

$ node searchexact.test.js
TAP version 13
# RTree Searching for exact point
not ok 1 1k In-Bounds Searches
  ---
    operator: equal
    expected: 1000
    actual:   998
    at: Test.<anonymous> (/home/centos/proj/rtree/RTree/test/searchexact.test.js:23:5)
  ...

1..1
# tests 1
# pass  0
# fail  1

I've created a patch and submitted a PR (#34) for review. My solution was to introduce an epsilon and to check bounds relative to this epsilon.

Node tests

Should probably have a version of the tests that runs in node.

IE8 bug: Array.isArray does not exist

When using the library in IE8, it fails on Array.isArray. Possibly also true for IE7.

First Insertion

I've been tinkering with this module. In my tests this happens:

1. insert initial node
2. insert more nodes
3. perform searches for those nodes

Any nodes inserted after the first will not be revealed in a search if they do not intersect with the initial rectangle. The initial insert is the root bounding box. Is this by design?

Question: Choosing best node when inserting

Hi,

As far as I can see, when inserting an object to structure, algorithm chooses best node based on squarifiedRatio (rtree.js#L144-L161) . So the more square the region is better, right? Why?

IE7/8 support

I noticed references to JSON.parse and JSON.stringify, which are not available on IE7 and 8. Which kind of browsers do you intent to support?

Pass GeoJSON feature to rtree.geoJSON fails

When passing a single geojson feature to the rtree, it fails with the message "this isn't what we're looking for".
I propose a patch which checks if 'prelim' is an Object. If so, we expect it to be a single feature, and then we put it in an Array, so it fits in the rest of the code nicely. Would that be acceptable? If so, how to clone (see #23): Do I implement a pure javascript clone function, or JSON.parse(JSON.stringify(prelim))? See http://heyjavascript.com/4-creative-ways-to-clone-objects/. I would be happy to contribute this patch.
The patch I proposed yesterday I did in lib/rtree.js because I assumed dist/rtree.min.js and dist/rtree.js are build from there. Was that correct?

how to limit the count of search rtree.bbox(area, limit) ?

how to limit the count of search rtree.bbox(area, limit) ?

I want to limit max 5 feature returned by rtree.bbox(area, 5) or rtree.search(area, 5)

How to do that?

geometry collections

currently rTree.geoJSON can't handle geometry collections, this should be fixed.

clean up examples and test

• examples
• tests

Extract GeoJSON stuff into an extension

It would be nice to have a separate supported RTree implementation without the GeoJSON stuff that can be used for general use cases, and additionally a rtree-geojson.js extension or something like this.

I don't see any reason to have them combined if this is going to become a standard RTree JS implementation.

not all deleted nodes are returned

As can be seen in the tests, not all of the deleted nodes are returned. The actual circumstances seem to be depended on both the nodes and the shape of pages as adding the same data into the tree in a different order can effect this.

Remove callbacks in methods

What is the reason behind adding the callback arguments to purely synchronous methods? It doesn't add any value since all the methods are still sync, but complicates the code.

how to make indoor map by leaflet.

how to make indoor map by leaflet. i want to learn how to make it.

What happened to 'delete' function?

The examples show how to use delete function

###Usage:
•Deletes all object that touch the 10x10 rectangle starting at position 10x10:
• var myDelCount = myRTree.delete({x:10, y:10, w:10, h:10});
•Delete only specific object if it touches the 10x10 rectangle starting at position 10x10:
• var myDelCount = myRTree.delete({x:10, y:10, w:10, h:10}, specific_object);

But no such function appears to be defined.

NPM module

We can either try to see if @maxogden (ping) wants to update the current one, or think up a witty name for this on npm, if it's the latter case I'm thinking "arrTree"