Boost logo

Geometry :

Subject: [ggl] spacial index
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-03-24 20:37:11

Bruno Lalande wrote:
> Hi
> However, Bruno's remark about copying the whole underlying subtree
> triggered me - depending on the number of levels this might become
> substantial... If the nodes are small (bbox + index), it might
> be worth
> it. Just depends on the size of the nodes vs. the gain we get from
> avoiding dynamic memory for each node.
> We might examine this behaviour first in a minimal test.
> If I'm right, only values have to be copied. I'll have some basic
> version soon.
> I was not talking about intended copies, these should indeed not happen.
> But a vector can make a copy of itself any time it needs to expand its
> buffer, so copies happen virtually all the time inside a vector. Of
> course you can always tell your vector to reserve the maximum allowed
> number of nodes when you create it, if this maximum number is reasonable
> (have no idea what it usually is)...
> I wouldn't say the impact only depends on the size of nodes. It also
> (and maybe much more) depends on the depth of your tree, which will make
> the performance hit increase exponentially.

Yes, of course you're right. I thought I'll be able to avoid vectors
copying but it's not possible. I've implemented some basic version of
Rtree based on boost::variant. Key features are:

- I've added 4th template parameter indicating type of r-tree. There is
only one valid tag for now - rtree_rstar_tag.

- Another types may be created by defining new tag and implementing
rtree_insert<..., Tag> and rtree_remove<..., Tag> + some nodes types +
traits if needed, but new nodes probably won't be needed.

- Nodes are created by operator new for now. Allocator will be used
later. (see: index/rtree/rtree_node.hpp)

- Default node type is boost::variant<leaf, internal_node> where leaf is
std::vector<Value> and internal_leaf is std::vector<std::pair<Box,
node*>> (see: index/rtree/rtree_node.hpp)

- Default box type is geometry::box<geometry::point> because it's all
what's needed.

- Only inserting of new elements, deleting of the entire tree and
searching is implemented for now. (see folders: index/visitors and
- I'haven't implemented forced reinsertions yet. (inserting visitor for
r*tree is in index/rtree/rstar/rtree_insert.hpp)

- R-tree is n-dimensional now. I've implemented n-dimensional area and
margin for boxes.(see folder: index/algorithms)

- Text output using std::ostream and drawing using OpenGL is done by
passing proper visitor to the r-tree but this won't be a part of the
official interface. In the same files functions passing those visitors
are defined. They take rtree as a parameter, i.e. gl_draw(tree) and cout
<< tree. (see folder: index/rtree/visitors)

- All in tests folder.

Code can be found in:


Geometry list run by mateusz at