VORONOI_DISPLAY, 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:
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.
voronoi_display ( 'filename' )where
The computer code and data files described and made available on this web page are distributed under the GNU LGPL license.
VORONOI_DISPLAY is available in a MATLAB version.
GEOMPACK, a MATLAB library which supplies the routines used to compute the Voronoi information.
VORONOI_CITY, a MATLAB program which displays the steps involved in computing the Voronoi diagram of 3 points, which we think of as cities connected by roads.
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.