# [vtkusers] Voronoi diagram ?

Randy Heiland heiland at ncsa.uiuc.edu
Wed Sep 13 10:23:34 EDT 2000

```In spite of the subject title, the original question asked about doing "Voronoi
triangulation".  There is no such thing.  Yes, a Voronoi diagram is the dual of
a Delaunay triangulation (but the diagram doesn't connect the "centers" of the
triangles - whatever that means).  A web search, or good ol' fashioned textbook
search, should turn up plenty of background.

I'm curious why a Voronoi diagram (polygons) would be any more useful than a
triangulation - esp. since graphics cards like triangles (strips).

--Randy
ps. rf. to earlier refs on this:
http://public.kitware.com/pipermail/vtkusers/2000-July/003850.html

pps. Voronoi = Dirichlet diagrams  (Dirichlet ~1850, Voronoi paper ~1908)

On Sep 13,  2:19pm, Tim Hutton wrote:
> Subject: RE: [vtkusers] Voronoi diagram ?
> Although I suspect VTK might have some difficulties rendering the polygons
> of infinite extent around the edge...
>
> I too am interested in voronoi diagrams (in 3d) - they would be useful for
> several surface reconstruction algorithms. I looked at how they might be
> computed from the delaunay but didn't get very far.
>
> Tim.
>
> At 09:13 13/09/00 -0400, you wrote:
> >I suspect vtkDelaunay2D or vtkDelaunay3D is what you're looking for. It's
> the same thing. (Well,
> >basically. A voronoi diagram is the dual of a delaunay triangulation. That
> is, if I recall correctly,
> >if you form a graph connecting the centers of adjacent triangles in a
> delaunay triangulation, the
> >result is a voronoi diagram.)
> >
> >Chris
> >
> >Christopher R. Volpe
> >Computer Scientist
> >Visual Information Program
> >Bldg KW, Room C215
> >P.O. Box 8, Schenectady, NY 12301
> >
> >(518) 387-7766, Dial Comm: 8*833-7766, Fax: (518) 387-6981
> >e-mail: volpecr at crd.ge.com    web: http://www.crd.ge.com/~volpecr
> >
> >
> >
> >> -----Original Message-----
> >> From: Sebastien BARRE [mailto:seb-ml-vtk at barre.nom.fr]
> >> Sent: Wednesday, September 13, 2000 8:43 AM
> >> To: vtkusers at public.kitware.com
> >> Subject: [vtkusers] Voronoi diagram ?
> >>
> >>
> >> Hi
> >>
> >> Has anyone worked on implementing Voronoi triangulation with VTK ?
> >>
> >> Thanks
> >>

```