Geometry Boost List: Re: [geometry] R-Tree to GIST

Subject: Re: [geometry] R-Tree to GIST
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2016-01-29 09:02:07

Please don't top-post. All Boost mailing lists discourages this.

Vladimir Voznesensky wrote:
> GiST could be seen as a generalization of R-tree. In the common case, tree internal nodes are not restricted to describe their subtrees by bounding rectangular boxes. Some things could be described by ellipsoids or, even more exotic, by Bloom filters.
>
> I would like to add some traits defining algorithms for calculation of:
>   - Subtrees overlapping cost;
>   - Insertion cost and resulting internal node subtree aggregate;
>   - Querying criteria.
>
> User could also need to have weighted points and be able to calculate an overall sum weight of all points in a given region, so internal tree nodes could have aggregate weights of each subtree.

I think doing the above should be possible out of the box, maybe with 
small changes. However everything I'm going to describe here sits in the 
details so it's not officially released interface.

INSERTION:

As you know the rtree along with Value takes Parameters. Those 
parameters are defined here:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/parameters.hpp#L74

Based on Parameters passed into the rtree<> template algorithms and 
nodes are picked, this is done here:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/options.hpp

So by specialization of options_type<> struct for some specific 
Parameters the following is defined:

1. inserting algorithm - high level part of insertion algorithm, there 
are 2 implemented:
   - default one simply inserting new value - 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/visitors/insert.hpp#L230
   - forcibly reinserting one on overflow used by the R*-tree - 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/rstar/insert.hpp

2. subtrees choosing algorithm - an algorithm choosing the best subtree 
while inserting, there are 2 implemented:
   - used by classic R-tree variants - 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/visitors/insert.hpp#L30
   - used by R*-tree - 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/rstar/choose_next_node.hpp

3. splitting algorithm - an algorithm splitting elements of a node into 
2 nodes
   - currently only one version is implemented, creating an additional 
node and calling redistribution algorithm - 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/visitors/insert.hpp#L114

4. redistribution algorithm - an algorithm redistributing elements 
stored in one node into 2 nodes or rather as many nodes as aplitting 
algorithm requires (currently 3)
   - Guttman's linear - 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp#L309
   - Guttman's quadratic - 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/quadratic/redistribute_elements.hpp#L84
   - R*-tree - 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/rstar/redistribute_elements.hpp#L368

5. nodes - the internal structure of nodes, (currently 2)
   - storing dynamic-sized containers of elements - 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/node/variant_dynamic.hpp
   - storing static-sized containers of elements - 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/node/variant_static.hpp

So you could create your own Parameters, specialize whatever algorithms 
you like, at any level, then specialize options_type<> in order to bind 
Parameters with your algorithms and it should work. Just keep in mind 
that you're messing with details which may be changed in the future, 
though I think if they was changed in the future it would not be a 
radical change.

QUERYING:

As for querying, you could write your own tree visitor but I guess it 
would be enough to write and support your own predicate. And the way how 
this would be done depends slightly on what you'd like to do exactly. 
But let's keep it simple and consider spatial predicates, for instance 
intersects().

Here is a function returning predicate object (for convenience):
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/predicates.hpp#L169

here are tags and spatial_predicate class:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/predicates.hpp#L58

then predicate checking struct is specialized:
- for values stored in leafs - 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/predicates.hpp#L236
- for nodes bounding boxes - 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/predicates.hpp#L312

So again, you should be able to specialize those and they would be used 
by the default query visitor.

Regards,
Adam