Geometry Boost List: Re: [geometry] 答复: How could I get nodes(MBRs) of the R Tree

Subject: Re: [geometry] 答复: How could I get nodes(MBRs) of the R Tree
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2018-01-26 14:32:41

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