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 |
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 |
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 |
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¶meters=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 |
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 |
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 |
Free forum by Nabble | Edit this page |