Efficient creation of ON_RTree ("bulk insert")

Rhino Developer
1

I was hoping to get an example or more information on how to create an ON_RTree when I have a large list of points to insert. Currently, I insert the points one-by-one starting from an empty ON_RTree made by using the parameter-less constructor of ON_RTree.

Maybe the question is whether it is more efficient to use ON_MEMORY_POOL and leaf_count, and, if so, how to do this.

class ON_CLASS ON_RTree
{
public:
  ON_RTree( ON_MEMORY_POOL* heap = 0, size_t leaf_count = 0 );
2

I’m not sure there is a better way, being that everything goes through some version of “Insert.” @dalelear, any ideas?

I doubt this is much more efficient…

ON_3dPointArray points = ...;
ON_RTree tree;
FillTree(points.Count(), points.Array(), tree);

void FillTree(int count, const ON_3dPoint* point, ON_RTree& tree)
{
  if (count > 0 && 0 != point)
  {
    const double* p = &point[0].x;
    for (int i = 0; i < count; i++)
    {   
      tree.Insert(p, p, i);
      p += 3;
    }
  }
}
3

Seeing the constructor for ON_RTree with a leaf count and an ON_MEMORY_POOL made me thinking that if I know the leaf count before I create the tree that the inserting would be more efficient.

Also, some references seem to suggest that bulk insert can be made more efficient than one-by-one insert.

4

Comment on the ON_RTree constructor:

ON_MEMORY_POOL parameter:
There is no efficiency gain in creation or use of an ON_RTree for using a custom memory pool. That parameter is provided so you can skip the destruction step and not leak heap by simply destroying the heap. In general, this is useful when you want to cancel a large and complicated calculation that you have carefully designed to use all heap from an ON_MEMORY_POOL you are managing. When canceling, you can simple destroy the heap and skip carefully cleaning up all the bits and pieces that may be in use when the user decided to cancel.

leaf_count
If you are lucky enough to know the number of leaves in the tree, then specifying the leaf count can marginally reduce the amount of memory overhead. However, using this parameter will not improve creation or use performance.

You need to insert the items one at a time so the spatial decomposition tree can be properly balanced.

General use:

The ON_RTree is designed to provide a tool that can be used for multiple high speed searches through a collection of lots of smallish objects that are spread over a largish region.

If you are doing a single search, or all the leaves are in the same place, or there are only a few leaves, then ON_RTree is not the correct tool.

1 Like
5

Ok, thanks for your clear explanation. I am indeed using the R-tree for multiple fast searches, as described in