Boost logo

Geometry :

Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2010-09-11 07:02:27

Simonson, Lucanus J wrote:
> Adam Wulkiewicz wrote:
>>> 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;
>> };
> Sorry, the design doesn't make sense to me. I don't see the point of any of these four pointers. Why wouldn't the node just have an array of N child nodes? Why a base class not and not a template parameter and traits? If you are inheriting without a virtual destructor people will ask why. I can't see any answer. Inheritance requires a strong rationale in boost and Liskov substitution principle gets thrown around a lot. You never explained how your is_leaf and is_node traits work, but I see no obvious mechanism.

The original idea was presented in "Game programming gems 4" by Bill
Budge from Electronic Arts. This tree is intended to be a multi-purpose
generic tree which enables to traverse it in various ways. The original
node has this structure:

template <typename T>
struct node
   /*four pointers*/
   T value;


I just thought, I'll do intrusive container. User musn't use
inheritance. He must just implement some traits and may use arbitrary
node e.g. described above. The inheritance is not required.

Deriving tree from node is not required. It was used in the original
idea but tree may be just a container with pointer to root node and all
iterators may work on nodes instead of trees.

- pre-order iterator uses one redirection - next pointer,
- post-order iterator iterates in constant time,
- tree traversing doesn't require recursion, use of implicitly defined
stack or skipping the nodes (the exception is level-order iterator but
it's used rarely),
- node may have arbitrary number of children nodes.

- children iterator is slower than in the case if node has just array of
pointers to children nodes and it isn't random_access_iterator,
- inserting in top-bottom building algorithm may have non-constant
complexity. If the node is inserted from the back, last_descendant
pointers of parent nodes must be updated. Worst case scenario is if
someone puts the node behind the root's last_descendant, all parents
must be updated (but the user may build bottom-up or insert nodes from
right to left in top-down algorithm).

The structure of the node:

next points to the node next in pre-order iteration.
previous_sibling points to the node if parent node has only one child.
previous_sibling of the first child points to the last child.
last_descendant of leaf node points to this node.

If we have a tree

     / \
    b d
   / /|\
  c e f g

pointers points to:

this | a b c d e f g
parent | 0 a b a d d d
next | b c d e f g 0
previous_sibling | a d c b g e f
last_descendant | g c c g e f g

Default node's values:

void init(node *n)
   n->parent = null_ptr;
   n->next = null_ptr;
   n->previous_sibling = n;
   n->last_descendant = n;

Navigational functions has constant complexity:

node * next(node * n)
   return n->next;

// next node in pre-order iteration
node * next(node * n)
   return n->next;

// previous node in pre-order iteration or
// next node in post-order iteration from right to left
node * previous(node * n)
   node *parent = n->parent;
   if ( parent )
     return parent->next == n ?
       parent :
     return null_ptr;

node * first_child(node *n)
   node *next = n->next;
   return (next && (next->parent == n)) ? next : null_ptr;

node * last_child(node *n)
   node *child = first_child(n);
   return child ? child->preious_sibling : null_ptr;

node * next_sibling(node *n)
   node *sibling = n->last_descendant->next;
   return (sibling && (sibling->parent != n->parent)) ?
     null_ptr : sibling;

node * previous_sibling(node *n)
   node *parent = n->parent;
   return (parent && (parent->next != n)) ?
     n->previous_sibling : null_ptr;

bool is_root(node *n) { return !n->parent; }
bool is_leaf(node *n) { return n->last_descendant == n; }

Spacial index will be used mainly for search and be updated rarely.
Moreover, pre-order traverse algorithm will be used.

But spacial index should have children random access iterator because
e.g. in quadtree or kd-tree there are often checks of certain nodes e.g.
left or right. One of the nodes may even not be created. In the node
which have previously described structure there must have been some flag
describing which one child is it.

Recursion is slower than iteration and uses more memory. And there may
be a tree with large number of children. Take e.g. this node:

template <typename T, size_t D>
struct n_tree_node
   boost::array<n_tree_node*, static_pow<2, D>::ret> children;
   T value;

The number of pointers in n-dimensional quadtree is 2^n, so for octree
we have node with 8 pointers, 4d - 16 etc.

There is an overhead when using both types of nodes. Maby some hybrid of
these two nodes would give us children random iterator and fast
pre-order iterator. But then the node may be large.


Geometry list run by mateusz at