Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2010-09-09 19:40:28

Barend Gehrels wrote:
> hi Adam,
>
>>
>>
>> Yes, I'm using the old version, thanks. But I don't know if I'll make
>> corrections now. It seems that dynamic self balancing spacial index is
>> desirable. What do you think about it?
>>
>
> I don't know, it (whether or not self balancing) is probably dependent
> on the situation and should ideally be configurable.
>
> It is of course no problem not making the corrections instantly, I
> however cannot have a thorough look then (this is usually how I do it,
> walking through). At least the main program should compile, and I can
> use the old version, the last time it was sent in two mails, can you
> send one consistent (compiling) set again?

Hi,

Sorry that I haven't written to you sooner. I'd like to show you 
something else instead of kd-tree.
The community said that spacial index should work like std::set and even 
if I feel different the first data structure should be implemented this way.
The spacial index may be e.g. a dynamic AABBTree. Leaf and internal 
nodes should be different classes derived from one Node class and 
created by allocator or possibly two different allocators defined by the 
user.

I've implemented a generic tree which I'd like to use as a base of this 
container. I've taken the idea from "Game programming gems 4" but my 
version is an intrusive container without memory allocation. It's not 
the 'final' container it's just an implementation of some needed 
algorithms and iterators. Users could use this generic tree class to 
build their own trees.

I had two designs in mind. First one was the tree which contains pointer 
to root. The tree structure would be defined only by nodes. Nodes could 
be manipulated only by use of the tree class and an iterator to node:

child_iterator begin_child(Iter nodeit)
void push_back_child(node *n, Iter nodeit)

tree t;
node *n = (node*)create_internal_node();
t.push_back(n);
n = (node*)create_leaf_node();
t.push_back_child(n, t.root());

The second one is a tree derived from node, which I've chosen. The main 
drawbacks are that the tree creation isn't intuitive, there is more 
pointers casting and in this case the tree isn't a container actually:

node *n = (node*)create_internal_node();
tree *t = (tree*)n;
n = create_leaf_node();
t.push_back_child((tree*)n);

I think that enclosing it inside a container class containing pointer to 
root tree would be sufficient.

The example of use can be found in main.cpp and spar/test/test_gtree.hpp
Tree is defined in spar/gtree.hpp.

I'll appreciate any suggestions.

Regards,
Adam
-------------- next part --------------
A non-text attachment was scrubbed...
Name: spar.zip
Type: application/x-zip-compressed
Size: 5825 bytes
Desc: not available
Url : http://lists.osgeo.org/pipermail/ggl/attachments/20100910/e4cc7b77/spar.bin