## NAME

s.sweep - computes Voronoi diagram or Delaunay triangulation (used by s.voronoi and s.delaunay)

## SYNOPSIS

s.sweep [-dstp]

## DESCRIPTION

s.sweep 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. The program is used by s.voronoi and s.delaunay and is not meant to be useful as a standalone program. If option -t is present, the Delaunay triangulation is produced. 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 produced. 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, s.sweep uses about 20n+140/n bytes of storage. On sorted data, s.sweep uses about 160/n bytes.

## REFERENCES

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

## SEE ALSO

v.autocorr, v.spag, v.support, s.delaunay, s.sweep

## AUTHOR

James Darrell McCauley,
GRASS 5 update, improvements: Andrea Aime, Modena, Italy

Last changed: $Date: 2002/01/25 05:45:35 $