Geometry Boost List: [ggl] spacial index

Subject: [ggl] spacial index
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-03-25 18:19:28

>> 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/

One more thing, min and max elements could be template parameters 
instead of runtime parameters. Choosing them in run-time would be harder 
but maby this would allow to perform further optimizations.

Regards,
Adam