delaunay_tree_2d

delaunay_tree_2d, a C++ code which reads a file of point coordinates in 2D and produces a PostScript file containing an image of the Delaunay triangulation of the points, by Olivier Devillers.

Warning: A limitation of the program is that it assumes that the user's input coordinates are "reasonable" PostScript coordinates! Reasonable results will be achieved then if both X and Y coordinates are positive and range from 0 to 1000 or so, say. On the other hand, a user whose data is in the unit square will get a PostScript file which actually plots the entire image in a near infinitesimal and useless box! A reasonable fix is to rescale data so that it lies between 0 and 612. (The PostScript coordinates, by default, are in units of 1/72 inch, so 8.5 inches wide = 612.)

It would not be hard to correct the code so that the user can input data with any scaling whatsoever, while the program would (simple) just rescale it, or (better) insert the appropriate PostScript scaling commands in the plot file.

In any case, the program is more interesting for being a fairly clean embodiment of a Delaunay triangulation algorithm, and the author himself suggests that a user might profitably and easily modify the code to write out the information defining the triangulation.

Usage:

delaunay_tree_2d < data.txt > data.ps

reads the point coordinates from data.txt and writes a PostScript image of the Delaunay triangulation to data.ps.

Licensing:

The computer code and data files made available on this web page are distributed under the MIT license

Languages:

delaunay_tree_2d is available in a C++ version.

Related Data and Programs:

delaunay_tree_2d_test

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

Author:

Olivier Devillers

Reference:

1. https://www-sop.inria.fr/prisme/logiciel/index.html.en a software download site at INRIA.
2. Franz Aurenhammer,
   Voronoi diagrams - a study of a fundamental geometric data structure,
   ACM Computing Surveys,
   Volume 23, Number 3, pages 345-405, September 1991.
3. Jean-Daniel Boissonnat, Monique Teillaud,
   On the randomized construction of the Delaunay tree,
   Theoretetical Computer Science,
   Volume 112, pages 339-354, 1993.
4. Olivier Devillers, Stefan Meiser, Monique Teillaud,
   Fully dynamic Delaunay triangulation in logarithmic expected time per operation,
   Computational Geometry: Theory and Applications,
   Volume 2, Number 2, pages 55-80, 1992.
5. Olivier Devillers, Robust and efficient implementation of the Delaunay tree,
   INRIA Research Report 1619, 1992.

Source Code:

• delaunay_tree_2d.cpp, the source code;
• delaunay_tree_2d.sh, compiles the source code;