Click here to Skip to main content
11,490,003 members (57,478 online)
Click here to Skip to main content

Delaunay's TIN - Triangulated Irregular Network

, 18 Apr 2004 129.8K 11.4K 60
Rate this:
Please Sign up or sign in to vote.
Delaunay's TIN - Triangulated Irregular Network

Sample Image - maximum width is 600 pixels

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.

License

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

Share

About the Author

Kazumi Sato

United States United States
No Biography provided

Comments and Discussions

 
QuestionThank's Pin
Member 1153902320-Mar-15 4:20
memberMember 1153902320-Mar-15 4:20 
QuestionSome questions about 3D Pin
Member 1081660213-May-14 17:37
memberMember 1081660213-May-14 17:37 
QuestionSome questions Pin
dickobe29-Mar-14 3:23
memberdickobe29-Mar-14 3:23 
QuestionHi Pin
opium_2100210018-Nov-11 7:45
memberopium_2100210018-Nov-11 7:45 
GeneralNeed volume calculation code Pin
aser34trw345-Jul-11 2:40
memberaser34trw345-Jul-11 2:40 
GeneralRe: Need volume calculation code Pin
sajmon446-Jan-13 7:14
membersajmon446-Jan-13 7:14 
Generalnew member Pin
lily_white28-Mar-11 5:14
memberlily_white28-Mar-11 5:14 
GeneralTriangle_net Question Pin
meast110-Oct-10 5:24
membermeast110-Oct-10 5:24 
Generalsimilar data set, but different results Pin
jin_chen589-Jan-10 21:34
memberjin_chen589-Jan-10 21:34 
Generallicense Pin
dan ilie17-Sep-09 19:54
memberdan ilie17-Sep-09 19:54 
Generalquestion about using delaunay trangulation to construct 3D terrain Pin
dlzhanglei22-May-09 2:14
memberdlzhanglei22-May-09 2:14 
QuestionSome question about the three-dimensional object! [modified] Pin
tonio ann16-Feb-09 3:50
membertonio ann16-Feb-09 3:50 
Generalabout the 3D! Pin
farid_colombia24-Oct-08 12:26
memberfarid_colombia24-Oct-08 12:26 
GeneralCube Pin
henry110328-Apr-08 22:39
memberhenry110328-Apr-08 22:39 
Generalgood Pin
Marco Magi5-Jun-07 0:32
memberMarco Magi5-Jun-07 0:32 
GeneralHigh Complexity Pin
sagido8-Dec-06 7:59
membersagido8-Dec-06 7:59 
It apears that the algorythm is O(N*N).On my computer I could'nt even triangulte 10,000 points.
Beware !

Questionremove points with identical X and Y coordinates Pin
kastoraki3-Aug-06 3:48
memberkastoraki3-Aug-06 3:48 
Generalvery good code, but i have a question Pin
kastoraki24-Jul-06 0:27
memberkastoraki24-Jul-06 0:27 
GeneralVery good Pin
tasv23-Feb-06 6:15
membertasv23-Feb-06 6:15 
GeneralOut of memory Pin
zindines27-Oct-05 11:56
memberzindines27-Oct-05 11:56 
General3D surface code Pin
Jacques Lemaire26-Apr-05 5:50
memberJacques Lemaire26-Apr-05 5:50 
GeneralRe: 3D surface code Pin
farid_colombia26-Oct-08 7:49
memberfarid_colombia26-Oct-08 7:49 
GeneralRe: 3D surface code Pin
lily_white28-Mar-11 5:17
memberlily_white28-Mar-11 5:17 
Questione-mail address of Mr. Kaumi Sao? Pin
durgut18-Jan-05 22:50
memberdurgut18-Jan-05 22:50 
GeneralTriangles Pin
Yves23-Sep-04 17:06
memberYves23-Sep-04 17:06 

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

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

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.150520.1 | Last Updated 19 Apr 2004
Article Copyright 2004 by Kazumi Sato
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid