QVORONOI
Voronoi Diagram
for M-Dimensional Pointsets

QVORONOI is a C program which constructs the Voronoi diagram for a set of points in M dimensions.

The standard Voronoi diagram organizes space by grouping regions with the nearest element of the pointset. An unusual feature of QVORONOI allows the user to request that the grouping be done, instead, so that a region is associated with the furthest element of the pointset.

Test pointsets can be generated by the accompanying program RBOX.

QVORONOI is invoked as a one-line command, with an extensive list of arguments, separated by spaces. An input data file must be supplied containing the coordinates of the points to be analyzed. A few typical usages include:

qvoronoi points.txt s

displays a summary of the Voronoi information;

qvoronoi points.txt p TO output.txt

writes the Voronoi vertices to the file output.txt;

qvoronoi points.txt Fn TO output.txt

for each Voronoi vertex, lists the neighboring Voronoi vertices; the first line of output is the number of vertices; subsequent lines start with the number of neighbors and then list the neighbors. A negative vertice indicates a vertex outside of the Voronoi diagram.

qvoronoi points.txt FN TO output.txt

for each Voronoi region, list the Voronoi vertices. The first line of output is the number of regions; remaining lines correspond to regions, and each begins with the number of vertices, followed by a list, with negative values indicated vertices outside the diagram;

qvoronoi points.txt Fv TO output.txt

writes the Voronoi diagram as a set of "ridges". The first line of output is the number of ridges. Remaining lines correspond to ridges, beginning with a value that is 2 more than the number of vertices in the ridge; then a pair of adjacent points, and then the sequence of Voronoi vertices that form the ridge. A '0' indicates the vertex at infinity.

qvoronoi points.txt o TO output.txt

writes a graphics file in OFF format containing the dimension, Voronoi vertices and Voronoi regions;

qvoronoi points.txt i TO output.txt

lists the indices of points that form the Delaunay triangles;

The input file describes the set of points whose Voronoi diagram is desired. The format of this file is as follows:

• Line 1: the spatial dimension, and a comment, which is the command used to generate the file;
• Line 2: the number of points;
• Line 3: the x and y coordinates of the first point;

The QHULL package includes QVORONOI and many other programs.

Languages:

QVORONOI is available in a C version.

Related Data and Programs:

RBOX, a C program which can be used to generate a random set of points for analysis by QVORONOI.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, September 1991, pages 345-405.
2. Bradford Barber, David Dobkin, Hannu Huhdanpaa,
   The Quickhull algorithm for convex hulls,
   ACM Transactions on Mathematical Software,
   Volume 22, Number 4, December 1996, pages 469-483.

Source Code:

• qvoronoi.sh commands to compile, link and load the source code;
• geom2.c;
• geom.c;
• geom.h;
• global.c;
• io.c;
• io.h;
• mem.c;
• mem.h;
• merge.c;
• merge.h;
• poly2.c;
• poly.c;
• poly.h;
• qhull_a.h;
• qhull.c;
• qhull.h;
• qset.c;
• qset.h;
• qvoronoi.c;
• stat.c;
• stat.h;
• user.c;
• user.h;

Examples and Tests:

• diamond_02_00009.qxy, an input file specifying the locations of 9 points in 2D.
• diamond_fn_output.txt, the output from the command

              qvoronoi < diamond_02_00009.qxy FN
            

• diamond_fn2_output.txt, the output from the command

              qvoronoi < diamond_02_00009.qxy Fn
            

• diamond_fv_output.txt, the output from the command

              qvoronoi < diamond_02_00009.qxy Fv
            

• diamond_i_output.txt, the output from the command

              qvoronoi < diamond_02_00009.qxy i
            

• diamond_o_output.txt, the output from the command

              qvoronoi < diamond_02_00009.qxy o
            

• diamond_p_output.txt, the output from the command

              qvoronoi < diamond_02_00009.qxy p
            

• diamond_s_output.txt, the summary output from the command

              qvoronoi < diamond_02_00009.qxy s
            

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