rww@esl.ESL.COM (Rich Webb) (03/12/90)
Source is available from "netlib@ornl.gov" for FREE. Send "help" for help.
Sending "send index from voronoi" produces:
Caveat receptor. (Jack) dongarra@cs.utk.edu, (Eric Grosse) research!ehg
Careful! Anything free comes with no guarantee.
*Please note that netlib has moved, the new address is netlib@ornl.gov.
*The old address, netlib@mcs.anl.gov, will be turned off soon.
*** from netlib, Fri Feb 23 21:41:15 EST 1990 ***
====== VORONOI ======
sweep2 Fortune's Voronoi diagram / Delaunay triangulation
sweepline algorithm for 2d
Sending "send sweep2 from voronoi" returns C code, makefile, and manual page:
NAME
voronoi - compute Voronoi diagram or Delaunay triangulation
SYNOPSIS
voronoi [ -s -t -p ]
DESCRIPTION
Voronoi reads the standard input for a set of points in the
plane and writes either the Voronoi diagram or the Delaunay
triangulation to the standard output. Each input line
should consist of two real numbers, separated by white
space.
If option -t is present, the Delaunay triangulation is pro-
duced. Each output line is a triple i j k, which are the
indices of the three points in a Delaunay triangle. Points
are numbered starting at 0.
If option -t is not present, the Voronoi diagram is pro-
duced. There are four output record types.
s a b
indicates that an input point at coordinates a b was
seen.
l a b c
indicates a line with equation ax + by = c.
v a b
indicates a vertex at a b.
e l v1 v2
indicates a Voronoi segment which is a subsegment of
line number l with endpoints numbered v1 and v2. If v1
or v2 is -1, the line extends to infinity.
The other options are:
s The input is sorted by y coordinate (the second number
in the pair). The first input line should be npoints
xmin xmax ymin ymax. This describes the number of
points and the range of the points. This line is used
to determine internal hash table size; it need not be
exact but performance suffers if it is grossly wrong.
p Produce output suitable for input to plot (1), rather
than the forms described above.
On unsorted data uniformly distributed in the unit square,
voronoi uses about 20n+140n bytes of storage. On sorted
data, voronoi uses about 160n bytes.
DIAGNOSTICS
Insufficient memory.
BUGS
The sort used by voronoi is much faster than sort(1). Also
sort(1) does not correctly sort real data with embedded
exponent fields. Very strange output results if -s is used
on unsorted data. Binary input-output would probably halve
execution time.
Good Luck!
--
Richard W. Webb
ESL Inc. MS/302
495 Java Drive (408) 738-2888 x5729
Sunnyvale, CA 94088 EMAIL: rww@esl.ESL.COM, ames!esl!rww