Re: [Boost-users] [BGL] combining kdtree-style operations

From: Jeremy Siek (jsiek_at_[hidden])
Date: 2005-05-16 11:10:37

Hi Martin,

Sounds neat! Though at this time I can do no more than
give you my encouragement!

Cheers,
Jeremy

On May 16, 2005, at 10:13 AM, martin f krafft wrote:

> I am looking at a complex project I am about to implement with BGL.
> Among regular graph operations, we need each vertex/edge to be
> located in Cartesian space (a Coordinate property will do) and for
> any point P in this Cartesian space (which may coincide with
> a vertex or edge) determine the set of geographically close
> vertices/edges (within the sphere of radius r, centred at P). Thus,
> the result set is essentially completely independent of the graph's
> structure, only dependent on the Coordinate property of the graph
> elements.
>
> The classic algorithm for this type of problem is the KD-Tree,
> a structure optimised for spatial lookups in K-dimensional space.
> It uses the same technique as a binary search, but at each level,
> the next dimension is compared... until K, at which point the
> iteration starts again from 0.
>
>   Bentley, J. L., Multidimensional binary search trees used for
>   associative searching, Communications of the ACM, v.18 n.9,
>   p.509-517, Sept. 1975
>
>   A demo for 2 dimensional search:
>     http://www.rolemaker.dk/nonRoleMaker/uni/algogem/kdtree.htm
>
> I have written a nice, flexible STL-container-style KDTree
> implementation:
>   http://freshmeat.net/projects/libkdtree
>
> This uses its own tree implementation along with bidirectional
> iterators. Since it stores edges and vertices in the same data
> structure, it does not really make for a good base container for the
> BGL. It would be possible to use separate trees for edges and
> vertices, but another problem makes that really difficult: changes
> to the Cartesian coordinates basically require the object to be
> removed and reinserted into the tree, and erasure does not work
> reliably currently (I have not found a viable update strategy).
>
> Now I am faced with the task of combining that with the BGL. Thus,
> I am weighing options:
>
>   - does anyone work with KD Trees and the BGL who'd be willing to
>     share experiences with me? In particular, I wonder whether it is
>     possible
>
>       * to use the same data structures for both, such that I do not
>         have to store multiple pointers for my objects, one in the
>         graph and one in the KD tree?
>
>       * to implement KD trees with BGL?
>
>   - would this library be a candidate for Boost and/or the BGL?
>     I realise that it's way too STL-centric right now (I somehow got
>     a kick out of using the same variable naming scheme as the SGI
>     STL implementation, which was made by people with obvious
>     psychiatric needs (</humour>). Basically, between its current
>     version and a final version ("1.0"), the following needs to be
>     done:
>
>       * clean up the source code to make it less cryptic (1 day)
>       * figure out how to implement erase-and-optimise efficiently
>         (1 week)
>       * figure out a way to make the coordinates mutable so that the
>         tree can accomodate moving objects (although it's probably
>         not the best container for e.g. particle systems).
>       * push decisions down into policies (it already uses
>         comparator and allocator policies).
>
> So this email does two things:
>
> If you are familiar with KD trees and the BGL, please give me some
> insight into your approach.
>
> If you are interested in the KD tree implementation and think that
> it would be a good candidate for boost, consider helping out to
> attack the TODO list, and if only with conceptual discussion.
>
> Thanks for your time and patience.
>
> -- 
> martin;              (greetings from the heart of the sun.)
>   \____ echo mailto: !#^."<*>"|tr "<*> mailto:" net_at_madduck
>
> invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver!
> spamtraps: madduck.bogus_at_[hidden]
>
> "half a bee, philosophically,
>  must ipso facto half not be."
>                                                      -- monty python
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
_______________________________________________
Jeremy Siek <jsiek_at_[hidden]>
http://www.osl.iu.edu/~jsiek
Ph.D. Student, Indiana University Bloomington
C++ Booster (http://www.boost.org)
_______________________________________________