Geometry Boost List: Re: [geometry] Rtree in a Hierarchical Method

Subject: Re: [geometry] Rtree in a Hierarchical Method
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-02-20 19:59:02

zaz1588 wrote:
> Adam Wulkiewicz wrote
>> By hierarchical method do you mean that you'd like to traverse the rtree
>> internal structure, i.e. internal nodes and leafs by yourself?
>>
>> If the answer to the above is yes, then there of course is a method. But
>> it's not a part of the 'official' interface and is hidden in the
>> details. Since it's in the details, it may be changed in the future.
>> That's why it's prefered to use the official interface whenever
>> possible. Maybe if you shared what you wanted to do it could be possible
>> to find different solution?
> My application is completely different but the classical example for the
> method I am working on is this:
> Suppose we wanted to compute the gravitational force on the earth from the
> known stars and planets. A dauntingly large number of stars must be included
> in the calculation, each one contributing a term to the force sum.
> In our sum the Andromeda galaxy, which itself consist of billions of stars,
> would be included. Since it is so far away it is good enough to treat the
> Andromeda galaxy as a single point with a mass equal to the total mass of
> the Andromeda galaxy.
>
> More mathematically, since the ratio
>
>                  size of box containing Andromeda
>        D/r  = -------------------------------------
>               distance of center of mass from Earth
> is so small, we can safely and accurately replace the sum over all stars in
> Andromeda with one term at their center of mass.
>
> within the Andromeda galaxy itself, this geometric picture repeats itself:
> the stars inside a smaller box can be replaced by their center of mass in
> order to compute the gravitational force on a different planet inside the
> Andromeda galaxy.
>
>   What I would would like to do is to use Rtree to subdivide space and use
> the information on each node. The closer we are to the Andromeda Galaxy,
> higher level nodes, with smaller bounding boxes, would be needed.
>
> If the planet is on the same leaf than normal calculation is carried out.
>
> The problem becomes even worse if we want the gravitational force on all
> known planets instead of only one.
>
> I hope this clarifies what I need to do. I thought acquiring the members for
> each node would be a straightforward matter. But, apparently and
> unfortunately , that is not the case...
>
> thank you for the prompt aswer

Thanks for the explanation. This is indeed an interesting use-case!

So besides your own traversing routine you'd like to store additional 
information in the Rtree nodes, I see.
This of course also could be done but would be more complicated. In the 
rtree it's possible to use arbitrary types of internal nodes and leafs.

If you didn't give up yet, this is what needs to be done to use you own 
nodes in the rtree. In fact, in the tests of rtree exception safety 
there are defined special nodes which contains a container of elements 
throwing in some specific moments. The important thing is that you can 
see here, how this is implemented:

https://github.com/boostorg/geometry/blob/master/index/test/rtree/exceptions/test_throwing_node.hpp

Lines 31-38: types of rtree parameters which passed to the rtree would 
enable the new type of nodes.
Line 44: a tag for new type of nodes
Lines 46-74: specialization of options for rtree parameters, notice that 
the tag defined above is passed as the last tempalte parameter
Lines 82-103: the definition of internal node, dynamic nodes are used 
(hierarchy made using dynamic polimorphism, it's also possible to use 
variants from Boost.Variant)
Lines 105-123: the definition of leaf node
Lines 126-256: required traits and utils

The rest isn't needed as long as you don't want to do something specific 
during the creation of each node.

Then the rtree with the new type of nodes is used just by passing the 
correct parameters, like in here:
https://github.com/boostorg/geometry/blob/master/index/test/rtree/exceptions/rtree_exceptions_rst.cpp
parameters are passed:

test_rtree_elements_exceptions<  bgi::rstar_throwing<4,  2>  >();

and here:
https://github.com/boostorg/geometry/blob/master/index/test/rtree/exceptions/test_exceptions.hpp
they're used to define an Rtree:

template<typenameParameters>
voidtest_rtree_value_exceptions(Parametersconst&parameters=Parameters())
{
//...
typedefbgi::rtree<Value,Parameters>Tree;
//...

But in the file mentioned above there is some unneeded code related to 
the throwing of exceptions so maybe it woudl be better if you checked 
this file:

https://github.com/boostorg/geometry/blob/master/include/boost/geometry/index/detail/rtree/node/node_d_mem_static.hpp

This is the definition of nodes used by the rtree when static versions 
of parameters are passed to the rtree.
Only node-related stuff is defined here (without the rtree parameters 
and options), it's more clear than the throwing test example.

So you might just:
1. copy the whole file node_d_mem_static.hpp
2. add a new tag for your nodes
3. replace all "node_d_mem_static_tag" with your tag,
4. define your parameters type
5. specialize index::detail::rtree::options<> for your parameters

Then you'd be able to use the rtree with your alternative nodes just by 
passing correct parameters:

bgi::rtree<some_value, my_rstar<...> > tree;

Additional reading:
https://github.com/boostorg/geometry/blob/master/include/boost/geometry/index/parameters.hpp
https://github.com/boostorg/geometry/blob/master/include/boost/geometry/index/detail/rtree/options.hpp

I hope it helps. Don't hesitate to ask additional questions.

Regards,
Adam