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:

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

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.


delaunay_lmap_2d node_file matrix_file
where creating the files


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


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.


  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:

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:

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

Last revised on 08 June 2010.