VORONOI_PLOT
Plot Voronoi Neighborhoods

VORONOI_PLOT is a FORTRAN90 program which plots a set of Voronoi neighborhoods.

The user must specify the name of a file containing the X and Y coordinates of the pointset to be analyzed. The points must lie in the unit square.

The program allows the user to choose the LP norm in which distances are calculated, with P any positive real value. In particular

• L1: distance = sum of absolute values of differences;
• L2: distance = square root of sum of squares of differences;
• Lp: distance = P-th root of sum of absolute values of P-th powers of differences;
• Linfinity: distance = maximum of absolute values of differences;

Usage:

voronoi_plot file_name p

• file_name is the name of a file containing the points;
• p chooses the P-norm, with the special value of 0 for L-infinity.

Licensing:

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

Languages:

VORONOI_PLOT is available in a FORTRAN90 version and a MATLAB version and a Python version.

Related Data and Programs:

GEOMPACK, a FORTRAN90 library which can compute the Voronoi diagram associated with a set of points.

PPMA, a file format which is used for the output graphics files created by VORONOI_PLOT.

PPMA_IO, a FORTRAN90 library which can write out an ASCII PPM file. These routines are used by VORONOI_PLOT.

QVORONOI, a C program which can compute the Voronoi diagram associated with a set of points.

TABLE_VORONOI, a FORTRAN90 program which can compute the Voronoi diagram associated with a set of points.

TRIANGLE, a C program which can compute and display the Voronoi diagram associated with a set of points.

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. Herbert Edelsbrunner,
   Geometry and Topology for Mesh Generation,
   Cambridge, 2001,
   QA377.E36,
   ISBN 0-521-79309-2.
3. Joseph O'Rourke,
   Computational Geometry,
   Cambridge University Press,
   Second Edition, 1998,
   QA448.D38.

Source Code:

• voronoi_plot.f90, the source code.

Examples and Tests:

DIAMOND_02_00009 is a set of 9 points whose Voronoi diagram includes a "diamond" shaped region. Test files you may copy include:

• diamond_02_00009.txt, the 9 points.
• diamond_02_00009_l0.25.png, a PNG image of the L0.25 neighborhoods.
• diamond_02_00009_l0.5.png, a PNG image of the L0.5 neighborhoods.
• diamond_02_00009_l1.png, a PNG image of the L1 neighborhoods.
• diamond_02_00009_l2.png, a PNG image of the L2 neighborhoods.
• diamond_02_00009_l3.png, a PNG image of the L3 neighborhoods.
• diamond_02_00009_li.png, a PNG image of the LInfinity neighborhoods.

UNIFORM_02_00010 is a set of 10 points chosen "randomly". Test files you may copy include:

• uniform_02_00010.txt, 10 "random" points in the unit square.
• uniform_02_00010_l1.png, a PNG image of the L1 neighborhoods.
• uniform_02_00010_l2.png, a PNG image of the L2 neighborhoods.
• uniform_02_00010_l3.png, a PNG image of the L3 neighborhoods.
• uniform_02_00010_l4.png, a PNG image of the L4 neighborhoods.
• uniform_02_00010_li.png, a PNG image of the LInfinity neighborhoods.

List of Routines:

• MAIN is the main program for VORONOI_PLOT.
• ANGLE_TO_RGB returns a color on the perimeter of the color hexagon.
• CH_CAP capitalizes a single character.
• CH_EQI is a case insensitive comparison of two characters for equality.
• CH_LOW lowercases a single character.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• DATA_READ reads generator coordinate data from a file.
• DIGIT_TO_CH returns the character representation of a decimal digit.
• FILE_COLUMN_COUNT counts the number of columns in the first line of a file.
• FILE_NAME_EXT_GET determines the "extension" of a file name.
• FILE_ROW_COUNT counts the number of row records in a file.
• FIND_CLOSEST_NORM finds the generator closest to a point X in a given norm.
• GET_UNIT returns a free FORTRAN unit number.
• I4_LOG_2 returns the integer part of the logarithm base 2 of |I|.
• I4_TO_ANGLE maps integers to points on a circle.
• I4_TO_RGB maps integers to RGB colors.
• I4_TO_S_LEFT converts an integer to a left-justified string.
• PPMA_WRITE writes an ASCII portable pixel map file.
• PPMA_WRITE_DATA writes the data of a PPMA file.
• PPMA_WRITE_HEADER writes the header of a PPMA file.
• R82VEC_DIST_L2 returns the L2 distance between a pair of R82VEC's.
• R8MAT_TRANSPOSE_PRINT prints an R8MAT, transposed.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT, transposed.
• REGION_PLOT_PPMA makes a ASCII PPM plot of the CVT regions in the LP norm.
• S_INDEX_LAST finds the LAST occurrence of a given substring.
• S_LOW replaces all uppercase letters by lowercase ones.
• S_TO_I4 reads an I4 from a string.
• S_TO_R8 reads an R8 from a string.
• S_TO_R8VEC reads an R8VEC from a string.
• S_WORD_COUNT counts the number of "words" in a string.
• TIMESTAMP prints the current YMDHMS date as a time stamp.

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