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:

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:

  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. 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:

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


Last revised on 12 November 2006.