
Geometry : 
Subject: Re: [geometry] ç”å¤: How could I get nodes(MBRs) of the R Tree
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 20180126 14:32:41
Hi,
FYI, at Boost we discourage topposting.
Li, Richie [Student]Â wrote:
>
> Dear Adam,
>
>
> Thanks for that. But I'm still a bit confused. Could you give me an
> example code of getting all the MBRs from level2 to the leaf nodes?
>
>
In this file:
is the implementation of a utility function checking whether a bounding
box of each node contains all bounding boxes of this node's children
nodes (or is equal to the bounding box of children nodes' bounding
boxes). In other words it checks if the bounding boxes are correct.
In order to traverse the tree you have to create a visitor (similar to
Boost.Variant's visitor). In the case of are_boxes_ok this visitor is
implemented here:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp
After applying this visitor to the Rtree, or to be precise to the root
node:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L121
for each internal node this member function is called:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L33
and for each leaf node this member function is called:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L71
in a depthfirst tree traversal manner.
This visitor for each internal node's child:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L49
sets member box as a box of this child:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L52
and passes itself into this lower node recursively:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L54
This is done because the node doesn't know what's its bounding box,
since bounding box is stored outside in the higherlevel node.
Then, when all lower level nodes are traversed it checks the box stored
in the visitor (which is the bounding box of this node set by a
higherlevel recursive call). So it restores the box:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L60
from a backup made earlier:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L44
then it calculates the bounding box of children nodes:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L63
and checks if it's correct:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L65
For leaf node it simply calculates the bounding box of stored values:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L85
and checks the correctness of leaf's bounding box set by higherlevel
recursive call (in member function handling visitation of internal node):
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L87
In order to access bounding box of a child node of internal node you
have to go through elements container storing BoundingBox/NodePtr pairs,
see:
elements container:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L36
loop iterating through elements:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L49
accessing box:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L52
In order to access bounding box of a value stored in leaf node you have
to access elements and do whatever you like with the value. If the value
is the bounding box then you simply have to access an element of
elements container, see:
values container:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L52
When you have visitor implemented you have to apply it to the Rtree
root node like this:
https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp#L108
Let me know if you need more help. Btw, what would you like to do with
these boxes?
Regards,
Adam
Geometry list run by mateusz at loskot.net