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