Geometry Boost List: [ggl] space partitioning

Subject: [ggl] space partitioning
From: Adam Wulkiewicz (adam.wulkiewicz)
Date: 2010-08-21 13:37:32

Simonson, Lucanus J wrote:
> Adam Wulkiewicz wrote:
>>> 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.
>
> You are right.  The desire to preserve iterator validity is somewhat at odds with the optimization of bucketing.  I can think of ways to get both, but it is complicated and adds an overhead to the iterators and possibly the nodes as well.  Bucketing turns out to be a good optimization for lookup and iteration, but not for insertion and removal.  A bucketed std::set is easy to implement on top of std::set and boost::array, for example, but you lose the property of iterators remaining valid after insertions and erase operations.  I could go either way on this one.
>
> I just had an interesting thought.  Is it possible to define a less_hilbert or less_morton functor that could be used to adapt a regular std container to get a spacial index almost for free?  For morton you just interleave the bits (of an integer) from all the coordinates of a point and do a compare.  For floating point it would be a little trickier.  This would give us both mutable rebalancing spcial indexes and static fast lookup indexes.  We would probably want to cache the morton number instead of recalculating it every time in the comparison functor.

Nodes of this kind of tree must contain the information about 
corresponding space in order to accelerate searching. Points may be used 
as nodes in this case since their position may represent the relation 
with other points in space, or the subspace if you like. For volumetric 
objects is can't be done. One might use some rule describing relative 
placement of objects. It could be based on relative positions of corners 
of AABBs and centres but it would have big number of spacial cases and I 
believe that the resulting structure would have bad qualities. Therefore 
AABBs or splitting planes are stored in nodes and objects are stored in 
leafs in this kind of structures.
I think that self balancing spacial index should be a structure based on 
volumes hierarchy (R-tree, BVH-tree, AABB-tree etc.) with objects stored 
as leafs created by the allocator in order to prevent iterators 
invalidation.

Regards,
Adam