a reply from Paul Chew

Subject :

Re: voronoi diagram

Date :

Thu, 15 May 2003 17:40:49 -0400 (EDT)

This sounds about right. You can simplify it by creating the entire

diagram inside a very large triangle (i.e., the triangle's vertices

are used to initialize the Delaunay triangulation). This way you

don't have to worry about the convex hull.

- Paul Chew

>hi

>if you dont mind to help

>i'm trying to construct a flowchart to create voronoi diagram

>i dont understand how to define the largest triangle

>Here's what i got so far.

>BEGIN

>Get Voronoi vertices from points (get a circle where three points are on =

>its surface) [do loop until all points participate in getting all =

>voronoi vertices]

>Check if Voronoi polygon is unbounded (create a convex hull for all =

>present points)

>Triangulate

>Check if min. angle of all triangles =3D max over all triangulations [if =

>yes, Delaunay created correctly]

>Get Voronoi from delaunay [straight dual of it]

>Check diagram with Euler's relation

>Print

>END

>******

>insert new site

>******

>BEGIN

>check all triangles (start with most recently created) [find which =

>triangle contains new site]

>eliminate this triangle and other triangle in the circumcircle that =

>contains the new site

>triangulate the resulting empty spot

>print

>END

Subject :

Re: voronoi diagram

Date :

Thu, 15 May 2003 17:40:49 -0400 (EDT)

This sounds about right. You can simplify it by creating the entire

diagram inside a very large triangle (i.e., the triangle's vertices

are used to initialize the Delaunay triangulation). This way you

don't have to worry about the convex hull.

- Paul Chew

>hi

>if you dont mind to help

>i'm trying to construct a flowchart to create voronoi diagram

>i dont understand how to define the largest triangle

>Here's what i got so far.

>BEGIN

>Get Voronoi vertices from points (get a circle where three points are on =

>its surface) [do loop until all points participate in getting all =

>voronoi vertices]

>Check if Voronoi polygon is unbounded (create a convex hull for all =

>present points)

>Triangulate

>Check if min. angle of all triangles =3D max over all triangulations [if =

>yes, Delaunay created correctly]

>Get Voronoi from delaunay [straight dual of it]

>Check diagram with Euler's relation

>END

>******

>insert new site

>******

>BEGIN

>check all triangles (start with most recently created) [find which =

>triangle contains new site]

>eliminate this triangle and other triangle in the circumcircle that =

>contains the new site

>triangulate the resulting empty spot

>END

<< Home