On 27 October 2014 00:34, Adam Wulkiewicz wrote:

Hi,

Jeremy Murphy wrote:

...

I see that a fourth node splitting algorithm for bulk loading is documented in the Introduction to spatial indexes but not listed elsewhere (such as Creation and Modification). Is it hiding in the library somewhere or is the introduction just a tantalizing sneak preview?

The packing algorithm is used if the R-tree is created with a constructor taking a range e.g. as a pair of Iterators:

http://www.boost.org/doc/libs/1_56_0/libs/geometry/doc/html/ geometry/reference/spatial_indexes/boost__geometry__ index__rtree/rtree_iterator__iterator_.html

Yes, maybe it should be explicitly stated in the "Creation..." section.

Ah, fantastic. Hah, turns out I was already using that constructor. So what should I write as the second required template parameter, which is usually linear<N>, quadratic<N>, etc? Is it just ignored in the packing case? If so, that's a bit confusing. Thanks, cheers. Jeremy

Jeremy Murphy wrote:

And, on a tangent, how does the packing algorithm cope with having values removed from the index? Does it readjust the packing or does the index become suboptimal?

The packing algorithm is only used during creation of the r-tree, elements are processed top-down. During insertion or removal of an element, splitting algorithm is used, elements are processed bottom-up. So yes, in general case (insert/remove) the index becomes "suboptimal". Though removal shouldn't affect the tree that much, since only the nodes at the bottom of the tree would be split on underflow. During the insertion all nodes on the path from a leaf to the root would have to be split on overflow, and the probability of such is high in a rtree containing packed elements/nodes. Regards, Adam