Delaunay's TIN - Triangulated Irregular Network

• Download source - 49 Kb
• Download demo project (requires GDI+ and MFC71.dll) - 1123 Kb

Introduction

This program generates Triangulated Irregular Network, or TIN from scattered points on two-dimensional plane based on Delaunay's triangulation. This data structure allows data to be displayed as three-dimensional surface, or to be used for terrain analysis including contouring and visibility mapping.

Using the code

The source codes, if successfully compiled will generate a simple console program which only takes two arguments. The first argument should be a name of the points file. Points are read from this simple text file with a list of X-Y, or X-Y-Z coordinates separated by comma. Although z coordinates are not used in the calculation, data with altitude information can be used for perspective viewing in demo program, TriNET. Below is example of input file for data shown in the figure:

200,790
370,760
60,670
360,890
280,620
30,880
230,960

or,

200,790,100
370,760,110
60,670,115
360,890,92
280,620,125
30,880,95
230,960,110

The list of triangles is saved to triangle file. Triangle file is generated in the same directory as the input file with extension "tri". The output file will look like this. In this example, six triangles are generated and in the resulting "tri" file, sequential numbers of generated triangle vertices are listed as below:

1,6,7
1,3,6
2,7,4
1,2,5
1,7,2
1,5,3

For example, the first triangle(A) consists of the first, sixth and seventh vertices in the input file.

Two point files, Davis.nod and test32.nod are included in this distribution file as examples.

Notes on algorithm

The second argument to this program decides whether the convex hull is used or not. If this is set to N, or no second argument is given, in order to generate triangles beyond the area boundary, a set of pseudo points are generated around the extents of the points.
Contrarily, if 'Y' is given to this parameter, the convex hull is generated and is used as a boundary of the input area. Convex hull (in 2D) is a smallest convex polygon, which include all input points. As shown in the example below, as compared to the network in the left, all parts in the convex hull are triangulated in the right figure, but it tends to create triangles of irregular shape(blue triangles in the right figure), which do not fulfill the condition that the largest inner angles of all generated triangles must be minimized.

Demo Program

I added Windows program, TriNET to interactively run and display the results of triangulation. To construct TIN from a set of scattered points, select from a menu, "Terrain" -> "Construct TIN" or "Construct TIN - Convex Hull" and select points file from dialog. Check the menu item, "Terrain" -> "Display Monitor" to observe the process of triangulation real time. This has no effect in the result of calculation except that it makes it significantly slower. It is just for fun! Input points and generated triangles can be displayed in TriNET. If the points have z coordinates, generated TIN can be used for perspective viewing. Select each function from "Draw" menu.


In three-dimensional display, use left and right arrows to rotate horizontally, and up and down key to change the depression angle. F1 and F2 keys widen and narrow the field of view.

TriNET requires GDI+ library. The runtime module can be obtained at the website of the Microsoft. Copy gdiplus.dll to windows system directory. TriNET also requires MFC71.dll and msvcr71.dll.

References

This program uses Delaunay's triangulation method. There are a number of documents published or available on the net about this algorithm. I used a book written by John C. Davis, "Statistics and Data Analysis in Geology, Third Edition", John Wiley and Sons(2002), which included very plane but thorough description on this algorithm.

History

• First upload, 14/4/2004 - Only hoping people don't have to vomit after reading my English.