Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2010-09-09 22:45:32

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

This syntax isn't technially "legal" because the C++ standard says that the results of casting a pointer of base type to a pointer of derived type if the object pointed to is of base type is undefined.  That means there is no guarentee that the code will do what you expect even if it compiles.  In reality it does compile and usually does what you expect, but it is against boost coding standards to do with sort of thing.  I'm not sure what type your create_internal_node() returns, but I assume it is not tree*.  I also don't think the public interface should provide access to internal nodes, but regardless, the design of the internals cannot rely on undefined behavior.

Regards,
Luke