DELAUNAY_LMAP_2D
Delaunay Triangulations Under Linear Maps

DELAUNAY_LMAP_2D is a FORTRAN90 program which computes the Delaunay triangulation of a set of points in the plane that have been transformed by a linear map A.

Specifically, DELAUNAY_LMAP_2D reads two input files:

• a node file containing (many) point coordinates (X,Y);
• a map file containing the entries of the 2x2 matrix A that describes the linear distortion of the geometry;

• an order 3 triangulation file, listing the indices of the 3 nodes that form each Delaunay triangle,
• an Encapsulated PostScript file containing an image of the triangulation.

In a sense, there's no reason to do all this fancy stuff. You can simply multiply your data by A yourself, get the Delaunay triangulation of the transformed data, and then recover your original data.

The main reason for setting up this code is to prepare for cases that are a generalization of this one, in which the matrix A actually varies spatially.

Usage:

delaunay_lmap_2d node_file matrix_file

• node_file contains the coordinates of the nodes;
• matrix_file contains the 2x2 matrix;

• node_file.delaunay.txt, with the triangulation information;
• node_file.delaunay.eps, with an image.

Licensing:

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

Languages:

DELAUNAY_LMAP_2D is available in a FORTRAN90 version.

Related Data and Programs:

GEOMPACK, a FORTRAN90 library which computes Delaunay triangulations, written by Barry Joe.

STRIPACK, a FORTRAN90 library which computes the Delaunay triangulation or Voronoi diagram of points on a sphere.

TABLE_DELAUNAY, a FORTRAN90 program which reads a file of point coordinates in the TABLE format and writes out the Delaunay triangulation.

TRIANGULATION_DISPLAY_OPENGL, a C++ program which reads files defining a triangulation and displays an image using Open GL.

TRIANGULATION_ORDER3, an data directory which contains a description and examples of the information needed to describe an order 3 triangulation of a set of nodes..

TRIANGULATION_PLOT, a FORTRAN90 program which may be used to make a PostScript image of the triangulation of the points.

TRIPACK, a FORTRAN90 library which computes the Delaunay triangulation of points in the plane.

Reference:

1. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, September 1991, pages 345-405.
2. Marc deBerg, Marc Krevald, Mark Overmars, Otfried Schwarzkopf,
   Computational Geometry,
   Springer, 2000,
   ISBN: 3-540-65620-0.
3. Barry Joe,
   GEOMPACK - a software package for the generation of meshes using geometric algorithms,
   Advances in Engineering Software,
   Volume 13, Number 5, 1991, pages 325-331.
4. Joseph ORourke,
   Computational Geometry,
   Second Edition,
   Cambridge, 1998,
   ISBN: 0521649765,
   LC: QA448.D38.

Source Code:

• delaunay_lmap_2d.f90, the source code.

Examples and Tests:

Test matrices you can copy include:

• matrix_identity.txt, the identity matrix.
• matrix_d21.txt, the (2,1) dilation.
• matrix_d41.txt, the (4,1) dilation.
• matrix_d81.txt, the (8,1) dilation.
• matrix_d15.txt, the (1,5) dilation.
• matrix_r30.txt, the 30 degree rotation (should have no effect on Delaunay).
• matrix_r30d21.txt, the (2,1) dilation and 30 degree rotation.
• matrix_r30d41.txt, the (4,1) dilation and 30 degree rotation.
• matrix_r30d81.txt, the (8,1) dilation and 30 degree rotation.

POINTS is a set of 10 "random" points in the unit square. Test files you may copy include:

• points.txt, a (real) TABLE file describing the coordinates of the points.
• points.identity.delaunay.txt, the (integer) TABLE file, describing the Delaunay triangulation of the points under the identity map.
• points.identity.delaunay.png, a PNG image of the triangulated data.
• points.d21.delaunay.png, a PNG image of the triangulated data under the D21 matrix.
• points.d41.delaunay.png, a PNG image of the triangulated data under the D41 matrix.
• points.d81.delaunay.png, a PNG image of the triangulated data under the D81 matrix.
• points.rot30.delaunay.png, a PNG image of the triangulated data under the R30 matrix.
• points.r30d21.delaunay.png, a PNG image of the triangulated data under the R30D21 matrix.
• points.r30d41.delaunay.png, a PNG image of the triangulated data under the R30D41 matrix.
• points.r30d81.delaunay.png, a PNG image of the triangulated data under the R30D81 matrix.

DOUBLE_HEX2_CVT is a set of 139 points in the unit square with two hexagonal holes. Test files you may copy include:

• double_hex2_cvt.txt, a (real) TABLE file containing the point coordinates.
• double_hex2_cvt.identity.delaunay.txt, the Delaunay triangulation under the identity matrix.
• double_hex2_cvt.identity.delaunay.png, a PNG image of the Delaunay triangulation under the identity matrix.
• double_hex2_cvt.d21.delaunay.png, a PNG image of the Delaunay triangulation under the D21 matrix.
• double_hex2_cvt.d41.delaunay.png, a PNG image of the Delaunay triangulation under the D41 matrix.
• double_hex2_cvt.d81.delaunay.png, a PNG image of the Delaunay triangulation under the D81 matrix.

GRID105 is a set of 105 points in the unit square, arranged into 5 columns of 21 points each. The points were originally evenly spaced in the X direction, and evenly spaced in the Y direction, but a uniform random perturbation of scale 0.03 was applied to both coordinates of every point. Because the data has been compressed by a factor of 5 in the Y direction, we get some "ugly" triangles if we do a Delaunay triangulation directly on the data. However, if we use a (1,5) dilation matrix to uncompress the Y direction, the triangles look much nicer (except along the boundary, where we are powerless to help). Test files you may copy include:

• grid105.txt, a (real) TABLE file containing the point coordinates.
• grid105.png, a PNG image of the points.
• grid105.identity.delaunay.png, a PNG image of the Delaunay triangulation under the identity matrix.
• grid105.d15.delaunay.png, a PNG image of the Delaunay triangulation under the D15 matrix.

List of Routines:

• MAIN is the main program for DELAUNAY_LMAP_2D.
• CH_CAP capitalizes a single character.
• CH_EQI is a case insensitive comparison of two characters for equality.
• CH_TO_DIGIT returns the integer value of a base 10 digit.
• DIAEDG_LMAP chooses a diagonal edge under a linear map.
• DTRIS2_LMAP constructs a Delaunay triangulation of 2D linear mapped vertices.
• 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_NAME_EXT_SWAP replaces the current "extension" of a file name.
• FILE_ROW_COUNT counts the number of row records in a file.
• GET_UNIT returns a free FORTRAN unit number.
• I4_MODP returns the nonnegative remainder of I4 division.
• I4_WRAP forces an I4 to lie between given limits by wrapping.
• I4MAT_TRANSPOSE_PRINT_SOME prints some of the transpose of an I4MAT.
• I4MAT_WRITE writes an I4MAT file.
• I4VEC_INDICATOR sets an I4VEC to the indicator vector.
• I4VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an I4VEC.
• LRLINE determines if a point is left of, right or, or on a directed line.
• PERM_INV inverts a permutation "in place".
• R82VEC_PERMUTE permutes an R82VEC in place.
• R82VEC_SORT_HEAP_INDEX_A does an indexed heap ascending sort of an R82VEC.
• R8MAT_DATA_READ reads data from an R8MAT file.
• R8MAT_HEADER_READ reads the header from an R8MAT file.
• R8MAT_PRINT prints an R8MAT.
• R8MAT_PRINT_SOME prints some of an R8MAT.
• R8MAT_TRANSPOSE_PRINT_SOME prints some of an R8MAT transposed.
• S_BLANK_DELETE removes blanks from a string, left justifying the remainder.
• S_INDEX_LAST finds the LAST occurrence of a given substring.
• 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.
• SWAPEC_LMAP swaps diagonal edges until all triangles are Delaunay.
• TIMESTAMP prints the current YMDHMS date as a time stamp.
• TRANSFORM_LMAP applies a transformation matrix to a vector.
• TRIANGULATION_PLOT_EPS creates an EPS file image of a triangulation.
• VBEDG determines which boundary edges are visible to a point.

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