SWEEP2
Voronoi and Delaunay Calculations


SWEEP2 is a C program which computes the Voronoi diagram or Delaunay triangulation of a set of points in the plane, by Steve Fortune.

Input to the program is a text file containing the coordinates of points in the plane. Each input line consists of two real values separated by spaces or tab characters. If the -s option is used, then the points should be sorted by Y coordinate, and an extra initial line should be inserted into the file, having the form

npoints xmin xmax ymin ymax
indicating the number of points and their range.

By default, the program outputs a description of the Voronoi diagram. The description of this structure is fairly complicated. There are four kinds of records in the output file:

If the -t command line option is specified, then the program outputs a description of the Delaunay triangulation. This is a simple item to describe. Each line of output lists the indices of three input points that are to be connected to form one of the triangles of the triangulation.

Usage:

sweep2 -p -s -t < data.txt
reads the file data.txt 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 consists of two real values separated by spaces or tab characters.
Command line options:

Languages:

SWEEP2 is available in a C version.

Related Data and Programs:

GEOMPACK, a C++ library which can compute the Delaunay triangulation or Voronoi diagram of a set of points.

SWEEP2_DELAUNAY_EPS, a FORTRAN90 program which can create an Encapsulated PostScript File containing an image of the Delaunay triangulation computed by SWEEP2.

SWEEP2_VORONOI_EPS, a FORTRAN90 program which can create an Encapsulated PostScript File containing an image of the Voronoi diagram computed by SWEEP2.

TABLE_DELAUNAY, a FORTRAN90 program which can compute the Delaunay triangulation of a set of points stored in a file.

Author:

Steve Fortune

Reference:

  1. Franz Aurenhammer,
    Voronoi diagrams - a study of a fundamental geometric data structure,
    ACM Computing Surveys,
    Volume 23, pages 345-405, September 1991.
  2. Steve Fortune,
    A Sweepline Algorithm for Voronoi Diagrams,
    Algorithmica,
    Volume 2, pages 153-174, 1987.
  3. A copy of the original release of the SWEEP2 code is available through NETLIB at http://www.netlib.org/voronoi/sweep2

Source Code:

Examples and Tests:

DIAMOND is a simple test case of 9 points, for which the Voronoi diagram includes a diamond. Files you may copy include:

TEST.TXT is a test case with 100 points. Files you may copy include:

You can go up one level to the C source codes.


Last revised on 14 May 2006.