Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2010-09-10 13:36:41

Simonson, Lucanus J wrote:
> 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.          

In addition to relying on undefined behavior it is also poor design.  The first design looks better.  Tree should not inherit from node.  Tree should have-a node member named "root" or something similarly clear.  That member should probably be private and no public interface of tree should include reference to node type.  Node could even be decared as a private sub-class of tree to keep people's hands off of it and make it eaiser to implement by allowing it to share the template parameters of tree.

I don't think that internal_node and leaf_node should inherit from a base node class either.  Instead let the node contain a union of leaf* and node* in an array (perhaps of size two but could be made template parameter) and a bitfield that indicates whether each element in the array of union is leaf type or node type.  Dynamic polymporism is overkill and wasteful of both memory and runtime for this application and I can't really see any benefit to having a common base class for leaves and nodes.  Ideally the leaf type would be a template parameter and no requirement about base classes placed upon it.

We should steer the discussion of design away from focusing on what is wrong and make constructive suggestions about what good alternatives might be.  Then we can discuss how various design options meet the design goals Adam may have, which is a much more interesting conversation.

Regards,
Luke