Rtree in a Hierarchical Method

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Rtree in a Hierarchical Method

zaz1588
I found the Rtree implementation really really easy to use and robust.

However I am planing on using Rtrees on a hierarchical method. And for it I need to know all leaves and its members on all different levels. I can't find a way to do it. I looked around but could not understand how this information is stored or how to retrieve it. Can anyone help me out?

thank you
Reply | Threaded
Open this post in threaded view
|

Re: Rtree in a Hierarchical Method

Adam Wulkiewicz
Hi,

zaz1588 wrote:
> I found the Rtree implementation really really easy to use and robust.

I'm glad to hear that you like it.

> However I am planing on using Rtrees on a hierarchical method. And for it I
> need to know all leaves and its members on all different levels. I can't
> find a way to do it. I looked around but could not understand how this
> information is stored or how to retrieve it. Can anyone help me out?
>

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?

Nevertheless, here is how you can access the rtree internals and mess
around a little bit. To traverse nodes, the rtree is using a visitor
pattern. The interface is similar to the Boost.Variant's
static_visitor<>. E.g. check out the utilities here:

https://github.com/boostorg/geometry/tree/master/include/boost/geometry/index/detail/rtree/utilities

e.g. here is a visitor which traverses all of the nodes and checks if
the bounding boxes of all nodes are correct:

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

So there must be a visitor class which knows how to handle internal
nodes and leafs. And then the visitor object msut be created and applied
to some node. E.g. the one above is applied to the root node (by the
rtree) and for each internal node it applies itself recursively to all
children nodes. To apply the visitor to the root node, in the example
above index::detail::utilities::view<> is used (see line 122-133).

Regards,
Adam
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: Rtree in a Hierarchical Method

zaz1588
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
Reply | Threaded
Open this post in threaded view
|

Re: Rtree in a Hierarchical Method

Adam Wulkiewicz
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
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: Rtree in a Hierarchical Method

zaz1588
I don't understand why I need my own nodes.
The example I used is a very simple one my actual problem is much more complicated.
No actual calculation would be done on the Rtree.
What is really needed is:

for the leaves:
members contained
bounding box

for the nodes:
leaves contained
members contained
bounding box

the bounding box would be used to see if it was far enough and the calculations would be performed using the actual members.

I thought that this information would be easily accessible since it should also be used in a query. or am I wrong.

thank you  
Reply | Threaded
Open this post in threaded view
|

Re: Rtree in a Hierarchical Method

Adam Wulkiewicz
zaz1588 wrote:

> I don't understand why I need my own nodes.
> The example I used is a very simple one my actual problem is much more
> complicated.
> No actual calculation would be done on the Rtree.
> What is really needed is:
>
> for the leaves:
> members contained
> bounding box
>
> for the nodes:
> leaves contained
> members contained
> bounding box
>
> the bounding box would be used to see if it was far enough and the
> calculations would be performed using the actual members.
>
> I thought that this information would be easily accessible since it should
> also be used in a query. or am I wrong.

Of course you're right (see below).

AFAIU you'd like to divide the space with the R-tree to calculate the
gravitional force from many stars in some point in space. And at this
point, when the rtree is created, you'd like to traverse it, and if some
internal-node's bounding box (at some higher level) is distant enough
(and probably small enough), you'd like to use the sum of the force from
all underlying objects covered by this node. So there must be some way
to retrieve this force from this node, because otherwise you'd be forced
to traverse all of the children. But if you're able to esstimate the
force somehow or check it elsewhere, this is of course not needed.

As I've written before, just to traverse the nodes you need a Visitor
and apply it to the node. Indeed I didn't write how to access the
elements because I assumed it would be clear after reading the
example/utility. E.g. this:

https://github.com/boostorg/geometry/blob/feature/relate/include/boost/geometry/index/detail/rtree/utilities/are_levels_ok.hpp

Each node contains the random access range/container of children nodes
or values. An internal node stores std::pair<Box, NodePtr> elements, and
a leaf stores value_type elements. To get the reference to this
container, assuming that you have the Visitor and all of the required
types in it (see the example) you can just do the following:

voidoperator()(internal_nodeconst&n)
{
     
typedeftypenameindex::detail::rtree::elements_type<internal_node>::typeelements_type;
     elements_typeconst&elements=index::detail::rtree::elements(n);

     // do something with the children nodes - std::pair<Box, NodePtr>
     for ( auto child : elements )
     {
         if ( is_a_box_ok(child.first) )
         {
             // the result is a member of the Visitor
             m_result += ...
         }
         else
         {
             // apply itself recursively
index::detail::rtree::apply_visitor(*this,*(child.second));
         }
     }
}

voidoperator()(leafconst&n)
{
     
typedeftypenameindex::detail::rtree::elements_type<leaf>::typeelements_type;
     elements_typeconst&elements=index::detail::rtree::elements(n);

     // do something with values - your value_type
for ( auto value : elements )
     {
         // the result is a member of the Visitor
m_result+= ...
     }
}

Regards,
Adam
_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry