Boost logo

Boost Users :

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)
_______________________________________________


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net