Geometry Boost List: [ggl] spacial index construction interface

Subject: [ggl] spacial index construction interface
From: Barend Gehrels (barend)
Date: 2011-03-13 07:36:59

Hi Adam,

On 13-3-2011 11:19, Adam Wulkiewicz wrote:
> 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).

Trying to use it sounds OK to me.

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.

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

OK for me, I've never done measurements on it but according to the 
descriptions it is more efficient.

>
> 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).

If necessary or convenient, OK for me.

Thanks for all your work on this.

For your information, I just renamed the combine algorithm to expand and 
processed all tests, examples and docs, so you can use "expand" now. 
That name is much better. Parameter order is unchanged as that was the 
feeling of everyone. I also renamed it in the rtree index on trunk, but 
not in the sandboxes. If I somehow missed anything please contact me. 
Besides this I also did the WKT-move from extensions to domains, as 
announced here before.

Regards, Barend