VORONOI_DISPLAY
Compute and Display a Voronoi Diagram

VORONOI_DISPLAY is a MATLAB program which reads a file of 2D points, computes the Voronoi diagram, and displays an image of it.

A related program, table_voronoi(), computes the same information returns it as output arguments, and prints it out. This function is provided partially simply to verify that the information returned by table_voronoi() is correct, and can be used to construct the diagram.

You should be aware that MATLAB includes functions voronoi() and voronoin() which already compute the Voronoi diagram accurately and efficiently.

However, these functions do not seem to return information about the semi-infinite Voronoi cells that is necessary for certain applications, such as computing the areas of the cells of a Voronoi diagram that is confined to a box. In such a case, we expect the semi-infinite regions to lie partially inside and outside the box, and it is not too difficult to determine the (finite) portion of such regions that lies within the box.

VORONOI_DISPLAY computes the Voronoi diagram by calling the GEOMPACK library of Barry Joe.

The program then analyzes the Delaunay information returned from GEOMPACK to work out the location of the Voronoi vertices, their specific arrangement around each of the original data nodes, and the handling of the semi-infinite rays.

Finally, the program displays the Voronoi diagram, drawing the semi-infinite edges each with an arbitrary length of one unit.

For the analysis, 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, and in fact, we will generally end up with two "vertices at infinity" associated with each semi-infinite region.

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:

voronoi_display ( 'filename' )

• 'filename' is a file containing the (x,y) coordinates of points.

Licensing:

The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.

Languages:

VORONOI_DISPLAY is available in a MATLAB version.

Related Data and Programs:

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

TABLE_VORONOI, a program which reads a file of point coordinates, calls geompack to get Delaunay triangulation information, and then determines and prints the Voronoi diagram information;

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,
   Advances in Engineering Software,
   Volume 13, pages 325-331, 1991.

Source Code:

• voronoi_display.m, the source code.

Examples and Tests:

• diamond.txt, a simple data file of 9 points.
• diamond.png, a PNG image of the Voronoi diagram.

You can go up one level to the MATLAB source codes.