Geometry Boost List: [ggl] spacial index

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 
index/rtree/rstar)
- 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:
https://svn.boost.org/svn/boost/sandbox-branches/geometry/index_080_new/

Regards,
Adam