TABLE_VORONOI
Voronoi Diagram Data
TABLE_VORONOI
is a C++ program which
reads in a dataset
describing a 2D pointset, and prints out information defining
the Voronoi diagram of the pointset.
The information describing the 2D pointset is in the simple
TABLE format.
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
semiinfinite region, which we will persist in calling a polygon).
A typical vertex of the polygon is called V. For the semiinfinite
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 semiinfinite 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 semiinfinite 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

reads the data in file_name.xy, computes and prints out
the Voronoi information.
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 C++ library which
computes the Delaunay triangulation
or Voronoi diagram.
TABLE,
a file format which
is used for the input files.
TABLE_BORDER,
a C++ program which
can read a TABLE file
and add zero entries corresponding to a single layer of
boundary data.
TABLE_DELAUNAY,
a C++ program which
reads a
file of 2d point coordinates and computes the Delaunay triangulation.
TABLE_IO,
a C++ library which
can read or write
a TABLE file.
TABLE_LATINIZE,
a C++ program which
can read a TABLE file
and write out a "latinized" version.
TABLE_QUALITY,
a C++ program which
can read a TABLE file
and print out measures of the quality of dispersion of the points.
TABLE_UNBORDER,
a C++ program which
can be used to remove the
border from a table file.
Reference:

Franz Aurenhammer,
Voronoi diagrams 
a study of a fundamental geometric data structure,
ACM Computing Surveys,
Volume 23, Number 3, pages 345405, September 1991.

Barry Joe,
GEOMPACK  a software package for the generation of meshes
using geometric algorithms,
Advances in Engineering Software,
Volume 13, pages 325331, 1991.
Source Code:
Examples and Tests:
List of Routines:

MAIN is the main program for TABLE_VORONOI.

CH_CAP capitalizes a single character.

CH_EQI is true if two characters are equal, disregarding case.

CH_TO_DIGIT returns the integer value of a base 10 digit.

DIAEDG chooses a diagonal edge.

DTABLE_DATA_READ reads the data from a real TABLE file.

DTABLE_HEADER_READ reads the header from a real TABLE file.

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.

HANDLE_FILE handles a single file.

I4_MAX returns the maximum of two integers.

I4_MIN returns the smaller of two integers.

I4_MODP returns the nonnegative remainder of integer division.

I4_SIGN returns the sign of an integer.

I4_WRAP forces an integer to lie between given limits by wrapping.

I4MAT_TRANSPOSE_PRINT prints an integer matrix, transposed.

I4MAT_TRANSPOSE_PRINT_SOME prints some of an integer matrix, transposed.

I4VEC_INDICATOR sets an integer vector to the indicator vector.

I4VEC_PRINT prints an integer vector.

LINE_EXP_NORMAL_2D computes the unit normal vector to a line in 2D.

LRLINE determines where a point lies in relation to a directed line.

PERM_CHECK checks that a vector represents a permutation.

PERM_INV inverts a permutation "in place".

R8_EPSILON returns the round off unit for double precision arithmetic.

R8_MAX returns the maximum of two real values.

R8_MIN returns the minimum of two real values.

R82VEC_PERMUTE permutes an R2 vector in place.

R82VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an R2 vector.

R8MAT_TRANSPOSE_PRINT prints a real matrix, transposed.

R8MAT_TRANSPOSE_PRINT_SOME prints some of a real matrix, transposed.

S_LEN_TRIM returns the length of a string to the last nonblank.

S_TO_R8 reads a real number from a string.

S_TO_R8VEC reads a real vector 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.

TIMESTRING returns the current YMDHMS date as a string.

TRI_AUGMENT augments the triangle data using vertices at infinity.

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 C++ source codes.
Last revised on 12 November 2006.