# TABLE_VORONOI Voronoi Diagram Data

TABLE_VORONOI is a MATLAB 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' )
where
• 'file_name.xy' is a file containing the (x,y) coordinates of points.

### Languages:

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

### Related Data and Programs:

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

VORONOI_DISPLAY, a MATLAB program which computes the exact Voronoi diagram using geompack, and displays it.

VORONOI_NEIGHBORS, a MATLAB program which is given a set of points in the plane and determines the Voronoi adjacency structure, that is, which points share an edge of the Voronoi diagram.

### 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,