Geometry Boost List: [ggl] space partitioning

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

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

Maby I'll describe the original idea. There may be a lot of different 
tree structures so I'd like to design a generic tree template which 
might be used as an internal structure of various containers. This tree 
should probably be the intrusive container. Base node structure I've 
used has 4 pointers:

struct node
{
   node *next;
   node *parent;
   node *previous_sibling;
   node *last_descendant;
};

Various types of trees may be created using this node, all navigation 
algorithms has constant complexity, pre-order iterator is very fast (one 
redirection), post-order and child iterators are fast. Tree container 
works on objects of node class. Node may have arbitrary structure. User 
must only implement some node traits and pass it to the tree template.

To define leaf and internal nodes one may derive from some basic node 
and wrapp the creation and manipulation of two types of nodes inside 
some container(e.g. AABBTree). Following code presents how to create 
nodes and manipulate them inside two containers (generic tree and some 
container using it) not the real internals of any of them.

// user defined types
struct node { node *n1, *n2, *n3, *n4; };
struct node_traits { /*...*/ };

struct internal_node : public node {/*...*/};
struct leaf_node : public node {/*...*/};

// tree creation
typedef node_algorithms<node_traits> na;

node *root = create_internal_node();
leaf_node *l = create_leaf_node();
na::push_back_as_child(root, l);

// pre order iteration
for(node *n = root; n; n = na::next(n))
{
   if ( na::is_leaf(n) )
   {
     leaf_node *ln = static_cast<leaf_node*>(n);
     // do something
   }
   else
   {
     internal_node *in = static_cast<internal_node*>(n);
     // do something
   }
}

The nodes might have different structure e.g.:

struct leaf;
struct node;

struct node_base
{
   union next_
   {
     leaf *l;
     node *n;
   } next;

   node *parent;

   union previous_sibling_
   {
     leaf *l;
     node *n;
   } previous_sibling;

   struct are_leafs_
   {
     unsigned char next             : 1;
     unsigned char previous_sibling : 1;	
   } are_leafs;
};

template <typename T>
struct node : public node_base
{
   leaf *last_descendant;
   T value;
};

template <typename T>
struct leaf : public node_base
{
   // leaf node's last descendant is equal to this pointer
   // so it musn't be stored in this case
   T value;
};

But I think the previous design is more 'elegant' and effective.

Regards,
Adam