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

From: martin f krafft (madduck_at_[hidden])
Date: 2005-05-16 10:13:04

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