Re: [Boost-users] Is an iterator the answer?

Subject: Re: [Boost-users] Is an iterator the answer?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2010-06-02 15:13:42

On Wed, 2 Jun 2010, Eric Fowler wrote:

> 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. 

How dynamic is your point set?  How large?

> 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?). 

Do you logically have several points at one location (just merged into one 
for Delauney to work) with each one as a vertex, or actually have several 
vertices mapped to the same point?

> 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.

I think the answer depends on your data size and how dynamic it is.  For 
small data, the naive solution of just keeping the graph explicitly and 
putting in whatever edges between vertices are suggested by your 
triangulation is probably the easiest approach (and the easiest to ensure 
the correctness of).  If you have very large data sets you might need a 
graph that uses less storage and we can discuss that in more detail.

> 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?

You would need to build your own graph type, with your iterators as its 
vertex, edge, out edge, ... iterators.  But let's make sure a simpler 
solution isn't feasible before we discuss that level of effort.

> 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 ... 

This is not my area of expertise, so I can't answer this question.

-- Jeremiah Willcock