[Boost-users] Is an iterator the answer?

Subject: [Boost-users] Is an iterator the answer?
From: Eric Fowler (eric.fowler_at_[hidden])
Date: 2010-06-02 05:57:12

I have a bit of a problem here, and would like some input.

I am working on an optimization algorithm that makes much use of
shortest-paths and near-neighbor concepts.

To get a reasonable near-neighbor search on points on the Euclidean plane, I
have implemented (mostly) a Delaunay tree as a Boost graph. The points on
the graph represent points in space, and are unique. I make use of angles
and cosines and such to find neighbors and so on. The Delaunay graph is a
basis for the optimization and shortest-paths stuff, which encompasses
concepts other than just points-in-space, like type-of-point and so on. The
basic idea is that when I am traversing my graph looking for optimal paths
and such, I use the Delaunay graph to find near neighbors.

Now, here is the problem: my graph really needs for vertices to share points
in space. Each vertex has a location and other properties, so there needs to
be several vertices at one point. To have a Delaunay graph with coincident
points is not really meaningful; the geometry gets really weird (e.g. what
is the angle between three coincident points?).

So I had figured I could build the Delaunay graph, and put a thin layer on
it that handled reference counts for points in space, and stored vertices
with all their attendant extra information. So I would make a class that had
a map<> of points-in-space and their refcounts, and as I added or deleted
points I would bump the counter. As far as the Dr. Delaunay knew, all points
would be unique; every coincident point would share it's neighbors with it's
brothers.

Problem is, how to do a (for instance) breadth-first search over this graph,
in which the graph algorithm needs to "see" each point individually?

My thinking right now is that I can have my structure as described and build
a custom iterator, then pass the iterator to the various search algorithms
and visitors and what not. The iterator would have the intelligence to sort
out the non-unique points.

So the simple question is: am I on the right track? Is this kind of thing
feasible or supported by the library? If it is, how do I specify my iterator
to the various algorithms?

Alternatively, does anyone know if it is possible to build a Delaunay graph
with coincident points that has geometric meaning, i.e. preserves the
properties we associate with Delaunay graphs? This is really a math question
...

Sorry if this is incoherent, it is late and I need to get it off my chest.

Eric