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@madduck
invalid/expired pgp subkeys? use subkeys.pgp.net as keyserver! spamtraps: madduck.bogus@madduck.net
"half a bee, philosophically, must ipso facto half not be." -- monty python _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Jeremy Siek