Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!samsung!uakari.primate.wisc.edu!sdd.hp.com!elroy.jpl.nasa.gov!ames!pasteur!miro.Berkeley.EDU!seth
From: seth@miro.Berkeley.EDU (Seth Teller)
Newsgroups: comp.sys.sgi
Subject: Re: generating Voronoi polygons
Summary: pd interactive, non-interactive code available
Message-ID: <10331@pasteur.Berkeley.EDU>
Date: 19 Jan 91 18:29:25 GMT
References: <9101190311.AA08355@nazgul.physics.mcgill.ca>
Sender: news@pasteur.Berkeley.EDU
Reply-To: seth@miro.Berkeley.EDU (Seth Teller)
Organization: University of California at Berkeley
Lines: 28

In article <9101190311.AA08355@nazgul.physics.mcgill.ca> loki@NAZGUL.PHYSICS.MCGILL.CA (Loki Jorgenson Rm421) writes:
>> looking for software to generate Voronoi polygons (also known as
>> Dirichlet tesselations) from a set of generating points in two dimensions.
>> any portion of the required algorithms would be appreciated.

an interactive voronoi program for sgi boxes is available through
anonymous ftp from the new ftp.brl.mil (internet 128.63.16.158) 
in pub/voronoi.tar.Z.

the program is about 10K lines of c code, fully interactive,
etc. it's based on steve fortune's sweepline algorithm and
non-interactive implementation.  the interactive version
displays voronoi diagrams, delaunay triangulations, convex
hulls, and the connection between d-dimensional voronoi
diagrams and (d+1)-dimensional convex hulls of co-spherical 
points (where d=2). some references:

        s.j. fortune, "a sweepline algorithm for voronoi diagrams,"
algorithmica 2 (1987), 153-174.

	f.p. preparata & m.i. shamos, _computational geometry: an
introduction_, springer-verlag, 1985, pp. 246-248.

for those who don't want thousands of pounds of gl and ui code,
there's a c library version in vregion.tar.Z that supports queries
for voronoi regions and delaunay triangles.

seth