loki@NAZGUL.PHYSICS.MCGILL.CA (Loki Jorgenson Rm421) (01/19/91)
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-7027seth@miro.Berkeley.EDU (Seth Teller) (01/20/91)
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