ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS", Bangkok, May 23-25, 2001 
206 
AN ENHANCED TIN GENERATION METHOD FOR USING CONTOUR LINE AS CONSTRAINS 
Wei LU, Takeshi DOIHARA 
Research Institute 
Asia Air Survey Co., Ltd. 
3F Asahi-Seimei Bldg. 8-6 Tamura-cho, Atsugi-shi, Kanagawa-ken, 243-0016, JAPAN 
Tel:+81-462-95-1886 Fax:+81-462-95-1934 E-mail: luwei@aiiko.co.jp 
Key Words: TIN, DEM, 3D-GIS, Elevation Interpolation 
Abstract 
TIN (Triangulated Irregular Network) is a fundamental elevation model for analyzing data of 3 dimensional random points and 
break-lines. In the field of 3 dimensional GIS, where height data are usually sampled at random location together with 3 dimensional 
break-lines, elevation data are interpolated with TIN model, with break-line as constrains. When contour lines are used as break-line 
during TIN generation, flat triangles will be formed at the locations where contour line turns sharply and where there are no random 
points. Flat triangles formed under such conditions lead to unnatural presentation of the original elevation model, which will 
consequently cause incorrect analysis result when used in subsequent consulting activities. 
While some researchers have proposed several algorithms to solve flat triangle problems in TIN generation, none of them gives a 
systematical way to generation natural TIN when using contour lines as constrains. 
In this paper, we propose a series of methods which include identification of the flat TIN, modification of the input break-line data and 
finally generation TIN with the modified break-lines. 
Experimental results with real world data show that the proposed method is easy to implement and generate more natural TIN. 
Exceptions and solutions of our proposed methods are also discussed. 
). Introduction 
In the recent years, since elevation data can be obtained at 
lower cost and higher precision with the rapid progress of 
devices such as laser range finder and SAR (Simulated Aperture 
Radar), the demand for 3 dimensional GIS becomes higher and 
higher, hence the need for better elevation analysis algorithms. 
TIN (Triangulated Irregular Network) has been widely used in 
numerical computing, and is especially effective in interpolation 
of elevation data only available at random positions. The output 
of a TIN generation module is a set of connected triangles, which, 
when the vertex are the known elevation points, can be used to 
interpolate any points within the triangles by either treating each 
triangle as a plain or using non-linear algorithms such as the one 
proposed by Akima [1]. Nowadays, there are many public 
resources offering TIN generation solutions, the most popular 
one is written by Shewchuk [2]. 
One problem with using TIN for elevation interpolation is when 
using contour line as constrains, triangles with all three vertex 
belonging to the same contour can be generated. As a result, 
any points that falls within such triangles will be treated as a 
plain, or close to plain even using non-linear interpolation 
methods. This will generate unnatural interpolation result. 
Some researches have studied this problem and given several 
solutions. The most representative solution is presented in 
Wang's paper [3], which gives a specific definition of flat TIN and 
proposes to add 3 dimensional points in the flat TIN related area. 
Yet, while it gives several methods of determining the horizontal 
position of the added points, the method of determining the 
height value of is not clear. 
In this paper, we propose an enhanced TIN generation method 
that is effective when using contour lines as constrains. Our 
method solves the problem of flat TIN by dividing the flat area 
into two groups and applies two different approaches for each 
group. The effectiveness of our proposed method has been 
confirmed with experimental results using real world data. 
2. Description of the Proposed Method 
The proposed method makes use of the result of popular TIN 
generation method [2] with line segments as constrains. It 
consists of the following phases: 
a. Generation of TIN with contour lines as constrains by 
conventional method 
b. Identification of the primal invalid triangle (flat TIN formed 
by the same contour line) 
c. Tracing of the related invalid triangles 
d. Generation of new break-lines 
e. Regeneration of TIN with modified break-lines 
f. Partial reconstruction of TIN 
2.1 Identification of the primal invalid triangle 
This phase locates the most fundamental triangle (hereafter 
called primal invalid triangle) that will always appear in the invalid 
triangles. With this primal invalid TIN, all the related invalid 
triangles can be efficiently located. 
A primal invalid triangle is defined as a triangle that has two 
edges belonging to the same contour line. Since in real world 
data, a contour line is not always consisted of a consecutive 
point string, a preprocessing must be performed to connect 
polylines that belong to the same contour line but divided into 
different data group during data generation. 
Fig. 1 shows an example of primal invalid triangle. 
110 
Fig. 1 An example of primal invalid triangle and flat triangles 
2.2 Tracing of the related invalid triangles 
This phase locates all the connected invalid TINs, so that 
modification of them will become possible.