loki@NAZGUL.PHYSICS.MCGILL.CA (Loki Jorgenson Rm421) (01/23/91)
Thanks to all of the contributors below. There are a quite a large
number of Voronoi-based pieces of code around. Not suprising since one
should never think that one is the first to consider a given idea.
Those interested in Voronoi-polygon surfaces should probably take a
closer look at some to the references.
We have snared a couple and are exmining them right now. I can't
recommend any given piece/source at this time.
Regards,
__ __
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
======================================================================
From: "David R. Blythe" <drb@eecg.toronto.edu>
Date: Sat, 19 Jan 91 02:28:11 EST
you can get voronoi software from netlib.
try sending mail netlib!h@research.att.com with the message (or subject
line)
send index from voronoi
to get a list of the available software
david blythe
ontario centre for large scale computation
drb@clsc.utoronto.ca
Date: Sat, 19 Jan 91 15:19:54 GMT
From: bam%rudedog.asd.sgi.com@SGI.COM (Brian McClendon)
There is a demo hanging around somewhere at SGI that
displays graphically Varonoi sets. I don't know where
the src code would reside, but I'll look.
I just checked: the src code is here at SGI in
usr/src/demos/src/voronoi. I have no idea if its
in the demo tape or not, but if its not, your
sales rep ought to be able to get you a copy (unless
we got it from someone who didn't want it given out).
The above src path is only meaningful to SGI internal, but
will give you something to tell the sales rep.
Another option might be to mention this to gavin@sgi.com
since he was the one who checked it into our tree, he might
be able to give you a copy thru email.
--
----------------------------------------------------------------------------
Brian McClendon bam@rudedog.SGI.COM ...!uunet!sgi!rudedog!bam 415-335-1110
----------------------------------------------------------------------------
Date: Sat, 19 Jan 91 08:41:52 -0800
From: Alex Woo RAC <woo@pioneer.arc.nasa.gov>
Subject: 2D Delaunay Triangularization
Look at geom.umn.edu. Several "C" Voronoi program. Also one is
available from netlib.
Alex
Date: Sat, 19 Jan 91 10:11:18 PST
From: seth@miro.Berkeley.EDU (Seth Teller)
Subject: voronoi
there's an interactive voronoi program 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.
s.j. fortune, "a sweepline algorithm for voronoi diagrams,"
algorithmica 2 (1987), 153-174.
for those who don't want thousands of pounds of gl and ui code,
there's a c library version in vregion.tar.Z.
seth
Date: 19 Jan 91 18:29:25 GMT
From: Seth Teller <pasteur!miro.Berkeley.EDU!seth@ucbvax.berkeley.edu>
Organization: University of California at Berkeley
Subject: Re: generating Voronoi polygons
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
Date: Sat, 19 Jan 91 22:55 EST
From: "Bob Bruccoleri (609) 683-6165" <BRUC@dino.squibb.com>
Subject: Re: generating Voronoi polygons
Professor Fred Richards in the Biophysics department at Yale University
has written a program for this in three dimensions. It was written for
finding Voronoi polyhedra around the atoms in proteins, and the work
is around 10 years old. As far as I know, the source code (in Fortran) is free
and is likely to be in the public domain.
I suggest that you call Yale to get his correct U.S. mail address,
and write him a letter. He would be happy to help.
+-----------------------------------------+----------------------------+
| Robert E. Bruccoleri, Ph.D. | Macromolecular Modeling |
+-----------------------------------------+----------------------------+
Date: Mon, 21 Jan 91 18:28:29 PST
From: farestam@orion.cerfacs.fr (Stefan Farestam)
I am currently working on an automatic mesh generator in which
voronoi tesselations play a part. I have implemented a voronoi
tesselator, but can for various reasons not give away the code.
One reason being that I'm trying to make the tesselation
boundary conforming why the code is somewhat messy.
I saw the response on info-iris referring to the public
domain code available (some 10k lines of C) that used a sweep
line algorithm. I have not used this approach myself, and to
be fair does not know too much about it. I choosed to use the
algorithm due to Bowyer, which is easily implemented in a few
days using in the vicinity of 100-150 lines of code. It has the
advantage of being incremental, i.e. the vertices are added one
by one, and after each insertion of a new point you have the
complete tesselation in memory. Most sweep line algorithms do
just what that say, i.e. sweep the area so I would presume that
the sweep line algorithm referred to would have to redo the whole
tesselation after each insertion, which is an obvious drawback if
you try to do something fast and interactive. I leave you some
useful references (which you probably already have):
A. Bowyer, "Generating Dirichlet Tesselations", The Computer
Journal, Vol. 24, No 2, 1981
D.F. Watson, "Computing the n-Dimensional Delaunay tesselation
with application to Voronoi polytopes", The Computer Journal,
Vol. 24, No 2, 1981
P.J. Green and R. Sibson, "Computing Dirichlet tesselations in
the plane", The computer Journal, Vol 21, No 2
R. Riedinger et al, "About the Delaunay-Voronoi Tesselation",
Journal of Computational Physics, Vol 74, pp 61-72, 1988
/Stefan Farestam
Date: Tue, 22 Jan 91 08:18:58 EST
From: blue@azure.cam.nist.gov (Jim Blue)
Message-Id: <9101221318.AA25922@azure>
To: loki@physics.mcgill.ca
I have successfully used Robert Renka's programs in Fortran, ACM
Algorithm 624. Reference is ACM trans. Math. Software, vol 10, pp 440-442, 1984.
This should be available by e-mail from netlib.
Jim Blue
Center for Computing and Applied Mathematics
National Institute of Standards and Technology
__ __
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