Boost logo

Geometry :

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?


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

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();
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();

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.

-------------- next part --------------
A non-text attachment was scrubbed...
Type: application/x-zip-compressed
Size: 5825 bytes
Desc: not available
Url :

Geometry list run by mateusz at