# 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;
The program then implicitly multiplies each point (X,Y) by A and computes the Delaunay triangulation of the transformed points (AX,AY). It then writes out
• 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
where
• node_file contains the coordinates of the nodes;
• matrix_file contains the 2x2 matrix;
creating the files
• node_file.delaunay.txt, with the triangulation information;
• node_file.delaunay.eps, with an image.

### 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,
Volume 13, Number 5, 1991, pages 325-331.
4. Joseph ORourke,
Computational Geometry,
Second Edition,
Cambridge, 1998,
ISBN: 0521649765,
LC: QA448.D38.

### Examples and Tests:

Test matrices you can copy include:

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

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

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:

### 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_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.

Last revised on 08 June 2010.