Geometry Boost List: [ggl] space partitioning

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

Adam Wulkiewicz wrote:
> 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.

One more thing.

Are the static casts I've used safe?

struct node {}
struct internal_node : public node {}
struct leaf_node : public node {}

template<typename Node>
class gtree : public Node {}

internal_node *in = create_internal_node();
gtree<node> *t = static_cast<gtree*>(static_cast<node*>(in));

Regards,
Adam