Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2011-03-13 06:19:12

Bruno Lalande wrote:
> Yep, if you rewrite the tree using Boost.Variant or any other approach
> different from the current one, you'll have to re-write your algorithms
> from scratch unfortunately. I think the right approach is to keep your
> current design handy, and reimplement the algorithms progressively with
> the new design, using the current ones as a base for regression testing.
>
> So thanks to variants we might be able to get rid of virtualily. Now,
> what about dynamic memory? The biggest problem is that if you manage
> your nodes with a vector, each copy of an element copies the whole
> underlying subtree. A solution would then be to switch from vector to
> list, but it defeats the purpose of avoiding dynamically allocated
> memory since list nodes are dynamically allocated themselves... So I'd
> be inclined to keep dynamic memory but maybe I'm overlooking another
> solution?

We should at least try to use std::vectors, to build the tree on 
variants, without run-time polimorphism. This is a new approach but it 
will be benefitial (if it'll work).

Another thing is that this is a good moment to start implementing R*tree 
instead of R-tree. They're just slightly different.

Rewriting the tree is the only way we can implement algorithms working 
on entirely different data. If we work on previous design we'll be 
focused on providing backward compatibility (in algorithms to data 
relation).

Regards,
Adam