VORONOI_PLOT
Plot Voronoi Neighborhoods

VORONOI_PLOT is an executable FORTRAN90 program, using double precision arithmetic, that can plot 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;

Related Data and Programs:

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

MATLAB includes the command voronoi which can compute and display the Voronoi diagram associated with a set of points.

PPMA is the format which is used for the output graphics files created by VORONOI_PLOT. These files can be displayed by programs such as GIMP, the GNU Image Manipulation Program or XV.

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

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

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

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

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.

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,
   ../../pdf/aurenhammer.pdf
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.
• voronoi_plot.csh, commands to compile 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.