Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!pacbell.com!ucsd!ucbvax!NAZGUL.PHYSICS.MCGILL.CA!loki
From: loki@NAZGUL.PHYSICS.MCGILL.CA (Loki Jorgenson Rm421)
Newsgroups: comp.sys.sgi
Subject: generating Voronoi polygons
Message-ID: <9101190311.AA08355@nazgul.physics.mcgill.ca>
Date: 19 Jan 91 03:11:31 GMT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The Internet
Lines: 25


	I am looking for IRIS-users who have tackled a particular
problem already and can give me a leg up on it.  Specifically, I am
looking for software to generate Voronoi polygons (also known as 
Dirichlet tesselations) from a set of generating points in two dimensions.
Ideally, the code would be written in FORTRAN (although C would be fine) and
include graphics and some sort of interactive capability.  However, any
portion of the required algorithms would be appreciated.

Briefly, each Voronoi polygon represents the set of points in a plane which
are closer to one particular generating point than any other.  The generating
points are, in general, randomly positioned in the plane, although the case of
a regular lattice would be what is known as the Wigner-Seitz cell ( physic's 
terminology).  

	If anyone is aware of any code which has been written in
complete or partial form, please Email me the info.

	Thanks,

                             __          __
Loki Jorgenson              / /          \ \  node:  loki@Physics.McGill.CA
Grad, Systems Manager      / //////  \\\\\\ \ BITNET: PY29@MCGILLA
Physics, McGill University \ \\\\\\  ////// / fax:   (514) 398-8434
Montreal Quebec CANADA      \_\          /_/  phone: (514) 398-7027