Boost logo

Geometry :

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


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:

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:
After applying this visitor to the R-tree, or to be precise to the root
for each internal node this member function is called:
and for each leaf node this member function is called:
in a depth-first tree traversal manner.

This visitor for each internal node's child:
sets member box as a box of this child:
and passes itself into this lower node recursively:
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:
from a backup made earlier:
then it calculates the bounding box of children nodes:
and checks if it's correct:

For leaf node it simply calculates the bounding box of stored values:
and checks the correctness of leaf's bounding box set by higher-level
recursive call (in member function handling visitation of internal node):

In order to access bounding box of a child node of internal node you
have to go through elements container storing BoundingBox/NodePtr pairs,
elements container:
loop iterating through elements:
accessing box:

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:

When you have visitor implemented you have to apply it to the R-tree
root node like this:

Let me know if you need more help. Btw, what would you like to do with
these boxes?


Geometry list run by mateusz at