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-21 07:18:26

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