ul 2004 
ingle of 
of root 
the leaf 
it, is the 
or. Leaf 
riangles 
resents, 
nship in 
cent leaf 
ir own 
Lis easy 
ip after 
ITHM 
‚een the 
division 
Ice from 
(5) 
1gth (see 
2003 for 
v) 
v) 
) 
) 
Fi) 
y;) 
(6) 
between 
idgment 
ration’ is 
count of 
On, while 
ment ‘*x/ 
asure the 
1 the two 
mplexity 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004 
  
of calculating Qi(x;,y;) is 100(n) less than that of 
calculating distance d,(x;, y; J. 
  
Implementation times 
  
  
  
  
  
Basic operation 
dix; y.) Qi(x;. y;) 
Judgement 0 3 
[vr 6 2 
X/+ 9 1 
Jx 1 0 
|x] 1 0 
  
  
Table.1 Comparison of basic operation between d; (xi. v;) and 
Qi(x;, y;) 
7. CONCLUSION 
It is very necessary to improve the efficiency of the algorithm 
for mass data processing. This paper discusses the theory and 
method of restrained edge mosaic in constructed TIN and 
describes our algorithm, the radial spatial division algorithm, in 
detail. The following conclusions can be obtained. 
(1) This paper proposes radial spatial division method and 
relative Formulates based on Qi(x;, y; ), and proves that 
this division method can assure that expanded triangle is 
in the independent sub-zone theoretically; 
(2) Relative algorithm of restrained edge mosaic in 
constructed TIN with radial spatial division method based 
on Qi(x;, y;) is proposed. The analysis shows that the 
frequency count of executing this algorithm’s basic 
operation , ‘x/+?, is just one tenth of that of spatial 
division algorithm based on distance; 
(3) The conception of spatial division tree is also proposed in 
this paper. It is shown that this tree will be great benefit 
for the reconstruction of triangles and their topology in 
region affected by restrained edge after spatial division. 
REFERENCE 
M. Renslow, 2001. White paper: technology assessment of 
remote sensing applications: LIDAR, U. S. Department of 
Transportation - National Consortia on Remote Sensing in 
Transportation. 
httpZ/riker.unm.edu/DASH new/pdf/White?o20Papers/LIDAR. 
pdf (accessed 31 Dec. 2002) 
Zhu Q. and Chen C., 1998. Quick generation of TIN and is 
dynamic updating, Journal of Wuhan Technical University of 
Surveying and Mapping, 23(1), pp. 204-207. 
Lu Z., Wu C. and Lu X., 1994. A generalized algorithm of 
optimal triangulation of simple polygon, ACAT 
ELECTRONICA SINCA, Vol. 221 No. 1, pp. 86-89. 
Lu C. and Wu C., 1997. Optimal Triangulation of Data Points 
Scattered in arbitrary Polygon With Characteristic Constrained, 
J. CAD & CG, Vol. 9, No. 4, pp. 302-308. 
Li L. and Tan J, 1999. Multiple Diagonal Exchanging 
Algorithm for Inserting Constrained Boundary in Constrained 
Delaunay Triangulation. CHINESE J. COMPUTERS, Vol. 22, 
No. 10, pp. 1114-1118. 
Wang J., 2001. Principles for Spatial Information System. 
Publishing House of Science, Beijing, pp. 246-248. 
Zhou X. and Liu S., 1996. A robust algorithm for constrained 
Delaunay triangulation [J], CHINESE J. COMPUTERS, Vol. 
19:)No. 8, pp. 615-624. 
L. D. Floriani and E. Puppo, 1988. Constrained Delaunay 
Triangulation for Multiresolution Surface Description. 9th Inter. 
Conf. On Pattern Recognition, Rome, Nov., pp. 566-569. 
Qi H. and Liu W., 1996. Qi algorithm for arc-arc topological 
relationship built on nodes. ACTA GEODAETICA et 
CARTOGRAPHICA SINICA, 25(3), pp. 233-235. 
Qi H., 1997. Optimization and improvement for the algorithm 
to automatically establish polygon topological relationship. 
ACTA GEODAETICA et CARTOGRAPHICA SINICA, 26(3), pp. 
254-260. 
Qi H., Li D. and Zhu Q., 2003. Time complexity analysis for 
two non-angle algorithms to determine the radial spatial 
adjacent relationship, Advances in Spatial Analysis and 
Decision Making (Zhilin Li, Qiming Zhou and Wolfgang Kainz, 
Editors), A.A. Balkema Publishers, Lisse, pp. 45-52. 
Guo R., 2001. Spatial Analysis, Higher Education Publishing 
House, Beijing.