The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences. Vol. XXXVII. Part B4. Beijing 2008 
triangles. A Delaunay triangulation DT(s) is a unique 
triangulation constructed on S such that a circum circle of any 
triangle does not contain any other point from S. This condition, 
frequently also considered as an empty circle property, 
optimizes triangulation according to the minimal inner angle of 
the triangles. Triangles from DT(s) considered as Delaunay 
triangles (or legal triangles) and their circum circles as 
Delaunay circles. Figure 1 shows an example of 
non-Delaunay and Delaunay triangulation. 
Figure 1. Non-Delaunay (a) and Delaunay (b) triangulation 
In 1977, Lawson (Lawson CL, 1977) showed that any 
triangulation T(s) can be transformed into DT(s) by applying 
the empty circle test on all pairs of triangles. If the empty circle 
property is violated, the common edges of the two triangles are 
swapped. The Delaunay triangulation is obtained when this 
procedure is recursively applied on all inner edges of the 
triangulation. This procedure is known as a Lawson’s local 
optimization shortly named also legalization or LOP (de Berg M, 
van Kreveld M, Overmars M, Schwarzkopf O, 1997). 
2.2 Algorithms 
There are many Delaunay triangulation algorithms. Su and 
Drysdale (Peter Su and Robert L. Scot Drysdale, 1995) 
classified the algorithms into five groups: incremental insertion 
algorithms, gift-wrapping algorithms, divide and conquer 
algorithms, convex hull based algorithms, and sweep-line 
algorithms. Some of these algorithms are surveyed and 
evaluated by Fortune (Ding-Zhu Du and Frank Hwang ,1992) 
and Su and Drysdale. Their results indicate a rough parity in 
speed among the incremental insertion algorithm of Lawson 
(Lawson CL, 1977)], the divide and conquer algorithm of Lee 
and Schachter, and the sweep-line algorithm of Fortune. 
Due to the Delaunay triangulation algorithms have reached 
maturity and the performance of these algorithms can satisfy the 
practical purpose, this paper adopts the following two 
algorithms for different purposes: the incremental insertion 
algorithm, the divide and conquer algorithm. 
When the points data haven’t been generated the TIN, the divide 
and conquer algorithm is used to construct the TIN. 
Dwyer (R.A.Dwyer, 1987) showed that a simple modification of 
this algorithm runs in O (Yl log log Yl) expected time on 
uniformly distributed points. Dwyer's algorithm splits the set of 
sites into vertical strips with yjYl / log Yl points per strip, 
constructs the DT of each strip by merging along horizontal 
lines, and then merges the strips together along vertical lines. 
His experiments indicate that in practice this algorithm runs in 
linear expected time. Another version of this algorithm, due to 
Katajainen and Koppinen (J. Katajainen and M. Koppinen, 
1987), merges square buckets together in a "quad-tree" order. 
They show that this algorithm runs in linear expected time for 
uniformly distributed sites. In fact, their experiments show that 
the performance of this algorithm is nearly identical to Dwyer's, 
in this paper we use the Dwyer’s divide and conquer algorithm. 
While there have been several generated local TINs to be 
integrated or new points to be added to the present network, 
incremental insertion algorithm is used. 
The incremental algorithm perhaps is simplest algorithm for 
constructing the Delaunay triangulation. The algorithm adds 
points to the network one by one and updates the network after 
each point is added. They have two basic steps. The first, Locate, 
finds the triangle containing the new point. (The algorithm is 
made simpler by assuming that the point is enclosed within 
large triangle.) The second, Update, updates the network 
The bottleneck of the algorithm is the Locate routine. All of the 
algorithms perform Update using an approach similar to that in 
Guibas and Stolfi (L. Guibas and J. Stolfi, 1985). They start at a 
random edge in the current network and walk across the 
network in the direction of the new point until the correct 
triangle is found. The basic step is to perform a CCW 
orientation step against an edge of a triangle to see if the point 
lies on the correct side of that edge. If not, the algorithm crosses 
to the other triangle that shares that edge. If so, it steps to the 
next edge around the triangle. When the point is on the correct 
side of all three edges in a triangle it has been located. 
2.3 Data structure 
A triangular mesh generator rests on the efficiency of its 
triangulation algorithms and data structures, so the following 
pseudo code algorithm illustrates the data structures of vertex, 
edge and triangle. 
Definition of vertex: 
Struct Vertex 
{ 
double x; 
double y; 
double z; 
}; 
Definition of Edge: 
Struct Edge 
{ 
int nEdgID; 
double startpoint; //the start vertex of the edge 
double endpoint; /the end vertex of the edge 
}; 
Definition of Triangle: 
Struct Triangle 
{ 
int nTrilD; //the ID of the triangle 
struct Vertex *mPtriangle; //three vertexes of the triangle 
}; 
//store the vertexes 
CTypedPtrList <Vertex> NewAddVertex; 
//store the edges 
CTypedPtrList <Edge> NewEdge: 
//store the triangles 
CTypedPtrList <Triangle> NewAddTriangle; • 
3 STORAGE STRATEGY 
How to store the huge seamless TIN-DEM data in the relational 
database management system (RDBMS in short) has a great 
impact on the efficiency of the index and the visualization. In 
//the coordinate of the vertex 
//the coordinate of the vertex 
//the coordinate of the vertex 
//the ID of the edge