Geometry Boost List: [geometry] [index] rtree news

Subject: [geometry] [index] rtree news
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-05-14 21:53:34

Hi,

I have some news regarding the rtree:

1. Segments are now supported by the rtree. They can be used as 
Indexables and stored directly in the spatial index.

2. nearest() predicate now uses the geometry::comparable_distance() 
which means that all combination of parameters supported by this 
algorithm are automatically supported by the rtree.
This means that geometries other than Point can be passed to the 
predicate. And that it should now work properly for non-cartesian 
coordinate systems.

The above 2 means that it should be possible to search e.g. for k 
Segments nearest to some other Segment, or to some Box, etc.

Synthetic benchmarking for random Segments shows that the rtree is 
slower than in the case when Boxes are stored however the results could 
be different for a real-life use-case. Without the Segment support the 
user would be be forced to store bounding Boxes of Segments. During a 
query some operations would be performed and then the user would be 
forced to perform them second time for the Segments coresponding of the 
returned Boxes. As usual benchmarking should be done for a specific use 
case.

Those are some synthetic results gathered for 1M random Values and rtree 
using linear balancing algorithm 
(http://github.com/boostorg/geometry/blob/develop/index/example/benchmark_experimental.cpp):

BOXES 	SEGMENTS 	
0.436803 seconds 	0.468003 seconds 	pack 1000000
0.0624004 seconds 	0.0780005 seconds 	query(B)* 100000 found 100046
1.43521 seconds 	1.49761 seconds 	insert 1000000
0.748805 seconds 	0.967206 seconds 	query(B) 100000 found 100046
0.780005 seconds 	0.998406 seconds 	range queried(B) 100000 found 100046
1.01401 seconds 	1.24801 seconds 	qbegin(B) qend(B) 100000 found 100046
0.998406 seconds 	1.20121 seconds 	qbegin(B) qend() 100000 found 100046
1.04521 seconds 	1.24801 seconds 	range qbegin(B) qend(B)100000 found 
100046
1.06081 seconds 	1.27921 seconds 	type-erased qbegin(B) qend() 100000 
found 100046
1.07641 seconds 	1.27921 seconds 	range type-erased qbegin(B) qend() 
100000 found 100046
0.405603 seconds 	-
        query(i && !w && !c) 100000 found 50025
0.717605 seconds 	0.717605 seconds 	query(nearest(P, 10)) 20000 found 
200000
0.764405 seconds 	0.842405 seconds 	qbegin(nearest(P, 10)) qend(n) 20000 
found 200000
0.748805 seconds 	0.811205 seconds 	qbegin(nearest(P, 10)) qend() 20000 
found 200000
0.780005 seconds 	0.858006 seconds 	type-erased qbegin(nearest(P, 10)) 
qend() 20000 found 200000
0.358802 seconds 	0.468003 seconds 	remove 100000

* query(B) is a short form of query(intersects(box))

Regards,
Adam