On Fri, May 23, 2014 at 4:47 PM, Adam Wulkiewicz <adam.wulkiewicz@gmail.com> wrote:
Andrew Hundt wrote:
I was hoping to find out a bit about the similarities and differences in capability between R-tree and an octomap, which is a bit like a volumetric or voxel base octree.

Octomap:
https://octomap.github.io/

Does anyone have thoughts on the use cases and overlapping advantages/disadvantages of an R-tree and octomap?

AFAIU it's an octree. The difference between an octree and rtree is that the first one partions space and stores the objects occupying some space in a node, and the second one gathers some close objects together and encloses them in nodes.

I think that from a user-point of view all space-indexes could allow doing the same things, not only those two.

Since octomap is used in robotics to store measurements from various 3D point-sample-based sensors it probably only allows to store Points. But since it's specialized, it may be somehow optimized to work well with some of the algorithms used in robotics/SLAM like the Iterative Closest Point algorithm which AFAIK is used in 3D SLAM.


It does have optimizations to allow stuff like ray casting (tracing). Also I believe that instead of storing an actual point and the value of the sensor data at that point in a node, typically I believe just the sensor data value is stored there since the node represents a region of space. This makes it possible to do ray casting through the volume, which wouldn't be as effective with a simple point based model.

Perhaps with the R-tree the way to get similar functionality would be to place an appropriate geometry like a box circle or perhaps an ellipse in an appropriate region, then use segment queries to simulate something like ray tracing. 

I'm not sure how performance would compare, and I haven't tested it. It may vary a lot based on how sparse/dense the data is and the number of entries. I would hypothetically expect the octomap to have an advantage as density increases since with fixed voxels repeated entries at the same location would affect confidence levels rather than increasing the total amount of data stored. Perhaps there would also be a similar way to elide data with R-trees as well and thus mitigate that possible source of performance differences.
 

Did you check it out? E.g. did you do some benchmarking?


I know others who do actually use octomap and if I recall correctly the performance is reasonably good but could improve for situations with millions of data points, although I don't have more specific data.


Cheers!
Andrew Hundt