TABLE_VORONOI
Voronoi Diagram Data

TABLE_VORONOI is a FORTRAN90 program which reads in a dataset describing a 2D pointset, and prints out information defining the Voronoi diagram of the pointset.

TABLE_VORONOI is based on the GEOMPACK library of Barry Joe, which computes the Delaunay triangulation. The main work that TABLE_VORONOI does is to analyze that Delaunay information and work out the location of the Voronoi vertices, and their specific arrangement around each of the original data nodes.

TABLE_VORONOI is a work in progress; the output is currently simply printed, which is not very useful except for toy problems; printed output is of very little use for big problems. To handle big, interesting problems, I have to think about how to store this information in a useful and accessible data structure.

Moreover, I haven't thought enough about how to deal with the inevitable "infinite" Voronoi cells.

The program begins with the pointset, of which a typical element is a point G. Each G generates a Voronoi polygon (or semi-infinite region, which we will persist in calling a polygon). A typical vertex of the polygon is called V. For the semi-infinite regions, we have a vertex at infinity, but it's really not helpful to store a vertex (Inf,Inf), since we have lost information about the direction from which we reach that infinite vertex. We will have to treat these special regions with a little extra care.

We are interested in computing the following quantities:

• G_DEGREE, for generator G, the degree (number of vertices) of the Voronoi polygon;
• G_START, for generator G, the index of the first Voronoi vertex in a traversal of the sides of the Voronoi polygon;
• G_FACE, for all generators G, the sequence of Voronoi vertices in a traversal of the sides of the Voronoi polygon. A traversal of a semi-infinite polygon begins at an "infinite" vertex, lists the finite vertices, and then ends with a (different) infinite vertex. Infinite vertices are given negative indexes.
• V_NUM, the number of (finite) Voronoi vertices V;
• V_XY, for each finite Voronoi vertex V, the XY coordinates.
• I_NUM, the number of Voronoi vertices at infinity;
• I_XY, the "direction" associated with each Voronoi vertex at infinity.

So if we have to draw a semi-infinite region, we start at infinity. We then need to draw a line from infinity to vertex #2. We do so by drawing a line in the appropriate direction, stored in I_XY. Having safely reached finite vertex #2, we can connect the finite vertices, until it is time to draw another line to infinity, this time in another direction, also stored in I_XY.

Usage:

table_voronoi file_name.xy

• file_name.xy is a file containing the (x,y) coordinates of points.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

TABLE_VORONOI is available in a C++ version and a FORTRAN90 version and a MATLAB version.

Related Data and Programs:

GEOMPACK, a FORTRAN90 library which supplies the routines used to compute the Voronoi information.

TABLE_BARPLOT_PPMA, a FORTRAN90 program which reads a table file and creates a PPMA bargraph of the data.

TABLE_BORDER, a FORTRAN90 program which can be used to add a border (of zero values) to a table file.

TABLE_COLUMNS, a FORTRAN90 program which can extract specific columns of data from a table file.

TABLE_COLUMNS_PERMUTE, a FORTRAN90 program which permutes the columns of a table file.

TABLE_DELAUNAY, a FORTRAN90 program which computes the Delaunay triangulation of a set of points.

TABLE_HISTOGRAM, a FORTRAN90 program which can make a histogram of a set of points stored in a table file.

TABLE_IO, a FORTRAN90 library which supplies the routines used to read the TABLE file.

TABLE_LATINIZE, a FORTRAN90 program which reads a file of points and creates a "latinized" version by adjusting the data.

TABLE_MERGE, a FORTRAN90 program which reads a file of points, and removes duplicates, and points that are close to each other.

TABLE_ORTHONORMALIZE, a FORTRAN90 program which reads a file of points and orthonormalizes the columns.

TABLE_QUALITY, a FORTRAN90 program which reads a file of points and computes the quality of dispersion.

TABLE_READ, a MATLAB program which can read in a TABLE file.

TABLE_RECORD_MATCH, a FORTRAN90 program which can be used to find close records in a table file.

TABLE_SCALE, a FORTRAN90 program which can be used to multiply the entries of a table file by a scale vector.

TABLE_SHIFT, a FORTRAN90 program which can be used to shift the entries of a table file by a shift vector.

TABLE_STATS, a FORTRAN90 program which can read a table file and compute certain statistics.

TABLE_TET_MESH, a FORTRAN90 program which can read a table file of 3D data, and compute a tetrahedral mesh.

TABLE_TOP, a FORTRAN90 program which can read a table file of M-dimensional data and make a table of plots of all pairs of coordinates.

TABLE_UNBORDER, a FORTRAN90 program which can be used to remove the border from a table file.

TABLE_UNIFORM_NOISE, a FORTRAN90 program which can be used to add a uniform noise term to the data in a table file.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, pages 345-405, September 1991.
2. Jacob Goodman, Joseph ORourke, editors,
   Handbook of Discrete and Computational Geometry,
   Second Edition,
   CRC/Chapman and Hall, 2004,
   ISBN: 1-58488-301-4,
   LC: QA167.H36.
3. Barry Joe,
   GEOMPACK - a software package for the generation of meshes using geometric algorithms,
   Advances in Engineering Software,
   Volume 13, pages 325-331, 1991.

Source Code:

• table_voronoi.f90, the source code.

Examples and Tests:

• diamond_02_00009.xy, a simple data file of 9 points.
• diamond_02_00009_output.txt, the output from the program.

List of Routines:

• MAIN is the main program for TABLE_VORONOI.
• CH_CAP capitalizes a single character.
• CH_EQI is a case insensitive comparison of two characters for equality.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• DIAEDG chooses a diagonal edge.
• DTRIS2 constructs a Delaunay triangulation of 2D vertices.
• FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
• FILE_ROW_COUNT counts the number of row records in a file.
• GET_UNIT returns a free FORTRAN unit number.
• HANDLE_FILE computes Voronoi information for a given set of data.
• I4_MODP returns the nonnegative remainder of I4 division.
• I4_WRAP forces an I4 to lie between given limits by wrapping.
• I4MAT_TRANSPOSE_PRINT prints an I4MAT, transposed.
• I4MAT_TRANSPOSE_PRINT_SOME prints some of the transpose of an I4MAT.
• I4VEC_INDICATOR sets an I4VEC to the indicator vector.
• I4VEC_PRINT prints an I4VEC.
• LINE_EXP_NORMAL_2D computes the unit normal vector to a line in 2D.
• LRLINE determines if a point is left of, right or, or on a directed line.
• PERM_INV inverts a permutation "in place".
• R82VEC_PERMUTE permutes an R82VEC in place.
• R82VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an R82VEC.
• R8MAT_DATA_READ reads data from an R8MAT file.
• R8MAT_HEADER_READ reads the header from an R8MAT file.
• R8MAT_TRANSPOSE_PRINT prints an R8MAT, transposed.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
• S_TO_R8 reads an R8 from a string.
• S_TO_R8VEC reads an R8VEC from a string.
• S_WORD_COUNT counts the number of "words" in a string.
• SWAPEC swaps diagonal edges until all triangles are Delaunay.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TRI_AUGMENT augments the triangle data using vertices at infinity.
• TRIANGLE_AREA_2D computes the area of a triangle in 2D.
• TRIANGLE_CIRCUMCENTER_2D computes the circumcenter of a triangle in 2D.
• VBEDG determines which boundary edges are visible to a point.
• VORONOI_DATA returns data defining the Voronoi diagram.

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