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 ymaxindicating 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.
npoints xmin xmax ymin ymaxindicating the number of points and their range. This option is for efficiency, since it allows the program to skip the sorting step.
SWEEP2 is available in a C version.
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.
Steve Fortune
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.