Tom - thanks.

Jon - By Voronoi edges, I mean the line segments that will eventually make up the Voronoi diagram. I'm indeed talking about a 2D only diagram - sorry to leave that important bit out. This is being used to generate a province-style map (a la Risk or Dominions), using the Delaunay vertices as the province centers and the Voronoi diagram as the borders.

I'm not having any trouble assigning a given vertex to multiple edges. I'll take another stab at explaining it better here.

In the attached "voronoi example" jpg, I have Delaunay triangles ABE, BDE, and BCD. Looking at each of those, I know that I have Voronoi vertices F, G, and H. So, at this point, I know my triangles, my Voronoi vertices, and the perpendicular bisectors that will become the Voronoi edges.

So I need to know the endpoints of each Voronoi edge. In the program, each edge consists of two sets of X,Y coordinates, each one large enough that the line extends well pass the applicable area.

I can handle that some of the final vertices will be way off-screen (i.e., infinite). What I don't know how to do is figure out which end point I'm assigning at a given time.

One example of this is for point F, which lies inside ABE. My current method is to F, see which side of segment AE it falls on, and then replace the point also on that side. This doesn't work, however, when you get to something like V-edge GH, where both points fall on one side of its Delaunay edge (BD). I'm somewhat at a loss for how to proceed from here.

Hopefully this explains it a bit better.

Thanks,

Scott

------=_Part_70751_18468582.1222886473388--
Jon - By Voronoi edges, I mean the line segments that will eventually make up the Voronoi diagram. I'm indeed talking about a 2D only diagram - sorry to leave that important bit out. This is being used to generate a province-style map (a la Risk or Dominions), using the Delaunay vertices as the province centers and the Voronoi diagram as the borders.

I'm not having any trouble assigning a given vertex to multiple edges. I'll take another stab at explaining it better here.

In the attached "voronoi example" jpg, I have Delaunay triangles ABE, BDE, and BCD. Looking at each of those, I know that I have Voronoi vertices F, G, and H. So, at this point, I know my triangles, my Voronoi vertices, and the perpendicular bisectors that will become the Voronoi edges.

So I need to know the endpoints of each Voronoi edge. In the program, each edge consists of two sets of X,Y coordinates, each one large enough that the line extends well pass the applicable area.

I can handle that some of the final vertices will be way off-screen (i.e., infinite). What I don't know how to do is figure out which end point I'm assigning at a given time.

One example of this is for point F, which lies inside ABE. My current method is to F, see which side of segment AE it falls on, and then replace the point also on that side. This doesn't work, however, when you get to something like V-edge GH, where both points fall on one side of its Delaunay edge (BD). I'm somewhat at a loss for how to proceed from here.

Hopefully this explains it a bit better.

Thanks,

Scott

On Tue, Sep 30, 2008 at 3:29 PM, Jon Watte <jwatte@gmail.com> wrote:

Scott Macmillan wrote:Each vertex in the Delaunay triangulation is exactly the Voronoi region

> I've got a working Delaunay triangulation of a series of points, and

> am working on the Voronoi diagram of the same set. The problem I'm

> really stuck on is that I'm not sure how to make sure each Voronoi

> edge has the correct two endpoints.

>

control point. What kind of "Voronoi" edges are you talking about? Are

you talking about the (possibly infinite) polygons that outline the area

of the planes that separate each Voronoi cell from its neighbor in 3D?

Or are you talking about a 2D Voronoi map? In either case, a single

bounding cell vertex will typically be used by more than two edges; most

algotithms will generate three edges per vertex, but a totally "proper"

Voronoi diagram could have more (consider a rectangular array of control

points; each boundary polygon vertex should have 4 edges).

Sincerely,

jw

-------------------------------------------------------------------------

This SF.Net email is sponsored by the Moblin Your Move Developer's challenge

Build the coolest Linux based applications with Moblin SDK & win great prizes

Grand prize is a trip for two to an Open Source event anywhere in the world

http://moblin-contest.org/redirect.php?banner_id=100&url=/

_______________________________________________

GDAlgorithms-list mailing list

GDAlgorithms-list@lists.sourceforge.net

https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list

Archives:

http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list