
Boost Users : 
Subject: [Boostusers] Is an iterator the answer?
From: Eric Fowler (eric.fowler_at_[hidden])
Date: 20100602 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
shortestpaths and nearneighbor concepts.
To get a reasonable nearneighbor 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 shortestpaths stuff, which encompasses
concepts other than just pointsinspace, like typeofpoint 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 pointsinspace 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) breadthfirst 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 nonunique 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
Boostusers 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