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
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
-
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 345-405, September 1991.
-
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:
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.