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:
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.
table_voronoi ( 'file_name.xy' )where
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 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.
You can go up one level to the MATLAB source codes.