[Boost-users] [Geometry] Packing algorithm for r-tree?

[Jeremy Murphy]

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?

Thanks, cheers.

Jeremy

[Adam Wulkiewicz]

Hi,

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.

Regards,
Adam
_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Jeremy Murphy]

On 27 October 2014 00:34, Adam Wulkiewicz <adam.wu...@gmail.com> 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]

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?

Thanks, cheers.

Jeremy

[Adam Wulkiewicz]

Jeremy Murphy wrote:

Packing algorithm can be and is used if the R-tree is created from some number of elements. Balancing algorithm is used during splitting of nodes so e.g. when insert() or remove() is called.
Yes, during inserting, packing algorithm is ignored. Just like during creation/packing, balancing algorithm is ignored.
Currently there is only one packing algorithm implemented, so there is no need to pick one like in the case of balancing algorithms. If there were more then it probably somehow would be possible to pass a group of parameters.

Regards,
Adam

 

[Adam Wulkiewicz]

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.