I have a bit of a problem here, and would like some input. <div><br></div><div>I am working on an optimization algorithm that makes much use of shortest-paths and near-neighbor concepts. </div><div><br></div><div>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. </div>
<meta http-equiv="content-type" content="text/html; charset=utf-8"><div><br></div><div>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?). </div>
<div><br></div><div>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&lt;&gt; 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&#39;s neighbors with it&#39;s brothers. </div>
<div><br></div><div>Problem is, how to do a (for instance) breadth-first search over this graph, in which the graph algorithm needs to &quot;see&quot; each point individually? </div><div><br></div><div>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.</div>
<div><br></div><div>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?</div><div><br></div><div>
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 ... </div>
<div><br></div><div>Sorry if this is incoherent, it is late and I need to get it off my chest. </div><div><br></div><div>Eric</div>