VORONOI(7)          UNIX Programmer's Manual           VORONOI(7)



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+140v/n bytes of storage.  On sorted
     data, voronoi uses about 160v/n bytes.

AUTHOR
     Steve J. Fortune (1987) A Sweepline Algorithm for Voronoi
     Diagrams, Algorithmica 2, 153-174.

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.