Content-Type: multipart/alternative; boundary="----=_Part_70751_18468582.1222886473388" ------=_Part_70751_18468582.1222886473388 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline 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 On Tue, Sep 30, 2008 at 3:29 PM, Jon Watte wrote: > Scott Macmillan wrote: > > 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. > > > > Each vertex in the Delaunay triangulation is exactly the Voronoi region > 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 > ------=_Part_70751_18468582.1222886473388 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Content-Disposition: inline
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

On Tue, Sep 30, 2008 at 3:29 PM, Jon Watte wrote:
Scott Macmillan wrote:
> 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.
>

Each vertex in the Delaunay triangulation is exactly the Voronoi region
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

------=_Part_70751_18468582.1222886473388--