Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2010-08-17 13:23:37

Adam Wulkiewicz wrote:
> Simonson, Lucanus J wrote:
>> Adam Wulkiewicz wrote:
>>> I have a few possible solutions in mind:
>>> 
>>> 1. nodes' structure,
>>> 
>>> a) store nodes in a std::vector and inside nodes store indexes of
>>> left and right child, b) store nodes in a std::list and store
>>> pointers/iterators (or maby use intrusive std::list), c) create the
>>> structure by my own, 
>>> 
>>> 2. nodes,
>>> 
>>> a) store vectors of objects(IDs, ptrs) in all nodes - there will be
>>> empty containers inside the internal nodes,
>>> b) store pointers to vectors and create them in runtime,
>>> c) store lists of objects in all nodes - slower than vectors?,
>>> d) implement simple container defined by 2 values e.g. pointers to
>>> the beginning and the end or number of elements,
>>> e) store only internal nodes in the structure and store pointers to
>>> leafs inside them (vectors only in leafs),
>>> f) use run-time polimorphism - this may be only used with 1c.
>>> 
>>> I don't know which one is the best. I'd like to avoid 1c, 2f and
>>> everything that requires using allocator by my own.
>>> 
>>> Memory allocation (pointers) could be implemented as 1-element std
>>> lists. 
>>> 
>>> I'd rather use 1a and 2b (2e eventually but it's more complicated).
>>> Although, this means that there would be e.g. vector of nodes
>>> containing 1-element lists of vectors. What do you think?
>> 
>> If we provide an iterator semantic for the interface of the tree it
>> is very important to decide if the iterators are invalidated by
>> operations that modify the tree (like push_back on a vector
>> invalidates iterators) or not (like insert in a map does not
>> invalidate iterators.)  Using vectors in the leaves implies that
>> iterators to the vector elements cannot be used in data structures
>> returned by our interface if we are to avoid invalidating them.  If
>> you plan to bound the size of the vector in the leaves you should
>> use a boost array instead.        
> 
> Should there be a way to modify spacial index (push_back(), erase(),
> etc.) after creation? Or just a constructor and rebuild(first, last)
> method? Does it make sense to use the 'old' iterator since the
> structure is changed? There may be additional objects or (what is
> worse) the objects 
> may dissapear.

Yes, there should be insert(object) and erase(iterator) interfaces.  Std map and set don't invalidate iterators except when erasing an element, and then only the iterator erased is invalidated.  Ideally I'd like to mimic the std map and set interfaces to make the containers intuitive.  In the long run we would like to have a spacial index that is able to rebalances itself.  This could be as simple as identifying a subtree that is out of balance and rebuilding that sub tree, or more complicated where minimal changes to the tree structure are made to keep it in balance.  Having data attached to the nodes to track the balance/size/depth of each sub tree my be needed to make this work.  A tree that doesn't rebalance itself doesn't need nodes that are objects individually allocated.  It can be one vector like a heap.  Typically such a data structure is based on a space filling curve such as Z-order, Hilbert or Sierpinski, and will outperform quad trees or KD trees for lookup, but need to be rebuilt each time they
 are modified.  It is reasonable to provide both, but is should be very clear whether the data structure is a container that can be mutated or a static lookup table that cannot.

Regards,
Luke