Click here to Skip to main content
14,865,827 members
Articles / Programming Languages / C++
Posted 18 Apr 2004


66 bookmarked

Delaunay's TIN - Triangulated Irregular Network

Rate me:
Please Sign up or sign in to vote.
4.36/5 (28 votes)
18 Apr 20043 min read
Delaunay's TIN - Triangulated Irregular Network

Sample Image - maximum width is 600 pixels


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:




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:


For example, the first triangle(A) consists of the first, sixth and seventh vertices in the input file.
Image 2 Image 3
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.

Image 4 Image 5

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.
Image 6 Image 7
Image 8 Image 9
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.


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.


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


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

Kazumi Sato
United States United States
No Biography provided

Comments and Discussions

QuestionCompete Source code Pin
Member 134676595-Nov-17 23:22
MemberMember 134676595-Nov-17 23:22 
QuestionTriNet source code Pin
Member 132932624-Jul-17 17:06
MemberMember 132932624-Jul-17 17:06 
Questionmọi người có thể tìm hiểu giúp mình về ưu điểm và nhược điểm cảu mạng lưới delaunay đc k ạ... mình cảm ơn nhiều ạ Pin
Member 1241339023-Mar-16 20:47
MemberMember 1241339023-Mar-16 20:47 
QuestionThank's Pin
Puppy Boo20-Mar-15 3:20
MemberPuppy Boo20-Mar-15 3:20 
QuestionSome questions about 3D Pin
Member 1081660213-May-14 16:37
MemberMember 1081660213-May-14 16:37 
QuestionSome questions Pin
dickobe29-Mar-14 2:23
Memberdickobe29-Mar-14 2:23 
QuestionHi Pin
opium_2100210018-Nov-11 6:45
Memberopium_2100210018-Nov-11 6:45 
GeneralNeed volume calculation code Pin
Parvathaneni Mamatha5-Jul-11 1:40
professionalParvathaneni Mamatha5-Jul-11 1:40 
GeneralRe: Need volume calculation code Pin
sajmon446-Jan-13 6:14
Membersajmon446-Jan-13 6:14 
Generalnew member Pin
lily_white28-Mar-11 4:14
Memberlily_white28-Mar-11 4:14 
GeneralTriangle_net Question Pin
meast110-Oct-10 4:24
Membermeast110-Oct-10 4:24 
Generalsimilar data set, but different results Pin
jin_chen589-Jan-10 20:34
Memberjin_chen589-Jan-10 20:34 
Generallicense Pin
dan ilie17-Sep-09 18:54
Memberdan ilie17-Sep-09 18:54 
Generalquestion about using delaunay trangulation to construct 3D terrain Pin
dlzhanglei22-May-09 1:14
Memberdlzhanglei22-May-09 1:14 
QuestionSome question about the three-dimensional object! [modified] Pin
tonio ann16-Feb-09 2:50
Membertonio ann16-Feb-09 2:50 
Generalabout the 3D! Pin
farid_colombia24-Oct-08 11:26
Memberfarid_colombia24-Oct-08 11:26 
GeneralCube Pin
henry110328-Apr-08 21:39
Memberhenry110328-Apr-08 21:39 
Generalgood Pin
Marco Magi4-Jun-07 23:32
MemberMarco Magi4-Jun-07 23:32 
GeneralHigh Complexity Pin
sagido8-Dec-06 6:59
Membersagido8-Dec-06 6:59 
Questionremove points with identical X and Y coordinates Pin
kastoraki3-Aug-06 2:48
Memberkastoraki3-Aug-06 2:48 
Generalvery good code, but i have a question Pin
kastoraki23-Jul-06 23:27
Memberkastoraki23-Jul-06 23:27 
GeneralVery good Pin
tasv23-Feb-06 5:15
Membertasv23-Feb-06 5:15 
GeneralOut of memory Pin
zindines27-Oct-05 10:56
Memberzindines27-Oct-05 10:56 
General3D surface code Pin
Jacques Lemaire26-Apr-05 4:50
MemberJacques Lemaire26-Apr-05 4:50 
GeneralRe: 3D surface code Pin
farid_colombia26-Oct-08 6:49
Memberfarid_colombia26-Oct-08 6:49 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.