Boost logo

Geometry :

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



Geometry list run by mateusz at loskot.net