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.
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:

Franz Aurenhammer,
Voronoi diagrams 
a study of a fundamental geometric data structure,
ACM Computing Surveys,
Volume 23, Number 3, September 1991, pages 345405.

Marc deBerg, Marc Krevald, Mark Overmars,
Otfried Schwarzkopf,
Computational Geometry,
Springer, 2000,
ISBN: 3540656200.

Barry Joe,
GEOMPACK  a software package for the generation of meshes
using geometric algorithms,
Advances in Engineering Software,
Volume 13, Number 5, 1991, pages 325331.

Joseph ORourke,
Computational Geometry,
Second Edition,
Cambridge, 1998,
ISBN: 0521649765,
LC: QA448.D38.
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:
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_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.
Last revised on 08 June 2010.