Hi,

FYI, at Boost we discourage top-posting.

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:

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

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 R-tree, 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 depth-first 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 higher-level 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 higher-level 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 higher-level 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 R-tree 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