
Geometry : 
Subject: Re: [geometry] RTree to GIST
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 20160129 09:02:07
Please don't toppost. All Boost mailing lists discourages this.
Vladimir Voznesensky wrote:
> GiST could be seen as a generalization of Rtree. 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 Rtree 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 dynamicsized containers of elements 
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/node/variant_dynamic.hpp
 storing staticsized 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
Geometry list run by mateusz at loskot.net