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:
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.
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
TABLE_VORONOI is available in a C++ version and a FORTRAN90 version and a MATLAB version.
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.
You can go up one level to the FORTRAN90 source codes.