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.

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

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:

• s x y
  indicates an input point (or "site") at (x,y);
• v x y
  indicates a Voronoi vertex at the point (x,y);
• l a b c
  indicates a line with the equation a*x+b*y=c. These lines are not actually drawn, but are used in the description of the next object;
• e l v1 v2
  indicates a Voronoi edge, which is the segment of the line with index l that extends from Voronoi vertex v1 to v2. If either vertex has the value -1, this indicates that the line segment is actually a semi-infinite ray, which extends to infinity on that side;

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.

Related Data and Programs:

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

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

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

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

VORONOI_NEW is a MATLAB function which can compute the Voronoi diagram of a set of points.

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:

• -p: indicates that the output file should be formatted for use with the UNIX plot command instead of the usual output format; (In my copy, this switch does nothing, because I don't have plot set up.)
• -s: indicates that the input file has been sorted by Y coordinate. In this case, an extra line should be inserted at the head of the input file containing the special information

  npoints xmin xmax ymin ymax

  indicating the number of points and their range. This option is for efficiency, since it allows the program to skip the sorting step.
• -t: indicates that the Delaunay triangulation is to be output. If this option is not specified, then the Voronoi diagram is output.

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:

• main.c, the main program.
• defs.h, an include file;
• edgelist.c;
• geometry.c;
• heap.c;
• memory.c.
• output.c, writes information about the Voronoi diagram or Delaunay triangulation to the output file.
• voronoi.c;
• sweep2.csh, commands to compile and load the 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:

• diamond.txt, the data file.
• diamond_vor.txt, the Voronoi diagram as computed by SWEEP2;
• diamond_del.txt the Delaunay triangulation as computed by SWEEP2;
• diamond_del.png a PNG image of the Delaunay triangulation;
• diamond_vor.png, a PNG image of the Voronoi diagram;

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

• test.txt, the data file.
• test_vor.txt, the Voronoi diagram as computed by SWEEP2;
• test_del.txt the Delaunay triangulation as computed by SWEEP2;
• test_del.png, a PNG image of the Delaunay triangulation;
• test_vor.png, a PNG image of the Voronoi diagram;

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