Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!usc!ucselx!bionet!agate!ucbvax!NAZGUL.PHYSICS.MCGILL.CA!loki From: loki@NAZGUL.PHYSICS.MCGILL.CA (Loki Jorgenson Rm421) Newsgroups: comp.sys.sgi Subject: Voronoi SUMMARY Message-ID: <9101231529.AA10157@nazgul.physics.mcgill.ca> Date: 23 Jan 91 15:29:59 GMT Sender: daemon@ucbvax.BERKELEY.EDU Organization: The Internet Lines: 193 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" 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 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 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" 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