Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2010-08-18 19:30:32

Simonson, Lucanus J wrote:
> Adam Wulkiewicz wrote:
>>>> 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, b
>> ut 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.
>>
>> I see that you'd like to have a container of objects with spacial
>> search
>> functionality. What do you think about a data structure storing just
>> IDs? I think that it should be this way. Invalidation would depend on
>> the container defined by the user. There could be an adaptor
>> connecting
>> the container with the index.
>
> If the user wants to hold the objects in the spacial index by reference instead of by value they should be able to do that by providing an adaptor to lookup coordinates.  By default the adaptor can use the point concept or rectangle concept depending on the type of index and expect that the object is stored in the index by value.  If you provide a way for the user to parameterize which container they specify you should provide a default that is reasonable.  Personally I would like to see a rationale for why the user needs to be able to specify which data structure to use.  If we are talking about static lookup spacial indexes then vector is always best and we should just provide an optional allocator parameter to let them specify which allocator the vector uses.  If we are talking about dynamic, mutable, self reballancing spacial indexes there should be boost arrays in the leaves with a parameterized number of elments stored together by value and a reasonable default for t
he bucket size provided.  Nodes and leaves should be dynamically allocated using a parameterized allocation with default of std allocator.  If the user wants to store geometric objects in the container by reference then they will need to provide an adaptor for how to access the coordinates of their geometric objects.  The default adaptor can be chosen by checking the geometry concent type of T at compile time and a compiler error would result if T has no regisered geometry concept type and no adaptor is provided by the user.  By analogy, std::set uses std::less<T>  by default and if you want to store pointers to strings instead of strings by value in the set you can provide your less_by_dereference<T>  comparison functor.  The idea here is to make the spacial index "just work" by default in a way that is intuitive with geometry types it recognizes while still providing all the options to override the default behavior for those who bother to read the documentation and learn ho
w to use all the features they could want.

Assuming that this is self-balancing kd-tree storing volumetric objects.
To have valid iterators all objects should be kept e.g. on lists or 
pointers to the allocated memory kept in vectors. There is always a 
possibility that some of them will have to be moved to the other node 
and the same object may be present in some number of nodes. In the 
std::set, individual values are stored in nodes which are created by the 
allocator. In the kd-tree, objects are stored in leafs because there is 
no good way to calculate if one volumetric object is lesser than the 
other one so splitting planes are compared.

I must think about it. I don't know if kd-tree is good for this purpose. 
Some other data structure maby, e.g. BVH-tree.

Regards,
Adam