RADIAL SPATIAL DIVISION BASED ON Qix,. y, ) AND RESTRAINED EDGE MOSAIC 
IN CONSTRUCTED TIN 
Hua QI **5, Deren LI * 
* The State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, 
Wuhan University, Wuhan, Hubei, China, 430079 
? Dept. of Surveying Engineering, School of Civil Engineering, 
Southwest Jiaotong University, Chengdu, Sichuan, China, 610031 
Email: qi-3dgis@sohu.com 
Commission PS, WG V/2 
KEY WORDS: TIN, Algorithm, Time complexity 
ABSTRACT: 
To insert restrained edges into TIN is of great necessity in many fields. At present, for the need of mass data processing, it is 
expected that the time efficiency of the algorithm be higher and higher. As a result, the paper proposes the method of radial spatial 
division based on Qi(x;, y;) to realize the restrained edges mosaic in constructed TIN. First of all, it introduces the basic principle 
of radial spatial division based on Qi(x;,y;). After that, on the basis of the principle the algorithm to realize restrained edges 
mosaic is given in detail. A spatial division tree is proposed as an efficient implementation method in the aspect of reconstruction of 
triangles and their spatial relationship after the division. And then, the triangle obtained with this method is sure in the sub-zone is 
proved. The analysis of time complexity shows that the time complexity to execute Qi(x;, y;) is lower than that to compute the 
126531 
distance from a point to a line. Finally, the conclusions are presented. It is shown that the radial spatial division algorithm proposed 
in this paper has more advantages in time efficiency than the spatial division algorithm based on distance. 
1. INTRODUCTION 
Triangulated Irregular Network plays great role in many fields 
such as finite element analysis, curved face approaching, 
computer vision, digital elevation model and mapping, three- 
dimensional simulation, which need to conduct a restrained 
edge (feature linc) mosaic into TIN. For example, in the 
application of DEM and mapping, it is necessary to inset terrain 
feature line into TIN in order to enhance the approach degree 
between TIN and the actual terrain. In high accuracy mapping 
with the LIDAR data for highway corridor mapping projects 
requiring 0.6 meter contours at 1:1200 scale, beyond hard 
surface corridor, photogrammetry support (terrain breaklines) is 
required to maintain the true shape of the terrain (Renslow, 
2001). There are two approaches: (1) combine restrained edge 
with TIN construction, or judge whether the triangle intersect 
with restrained edge when construct TIN (Zhu and Chen, 1998): 
(2) mosaic the restrained edge in constructed TIN (Lu, Wu and 
Lu, 1994). This paper mainly refers to the relative method of 
the second approach. 
Lu and etc. introduced an algorithm, ‘m+2 borders cater corner 
exchange' (Lu, Wu and Lu, 1994), which is a typical algorithm 
among the second approach mentioned above for it can resolve 
all complex cases. But this algorithm needs to compare the 
distances from points to line which resulted in redundant code 
and hard to record adjacent relation among triangles, etc (Li 
and Tan, 1999; Wang, 2001). Therefore with analysis of 'track 
creation’ algorithm (Zhou and Liu, 1996), Li and Tan found 
that ‘track creation’ algorithm might fail when affected area is a 
concave polygon. And they proposed that transform concave 
affected area to convex polygon before apply ‘track creation’ 
algorithm to mosaic restrained edge in any affected area, and 
then ‘descending algorithm’ and ‘looping algorithm’ were 
proposed (Li and Tan, 1999). Wang provided some special 
graphic patterns which may make ‘descending algorithm’ fail 
and suggested that ‘looping algorithm’ can be used to assure the 
validity of exchange in any situations. In terms of 
implementation method, there are lots of differences between 
the algorithm given by Lu and the follow-up algorithms (Wang, 
2001). 
This paper does not discuss the diversity of the algorithms 
mentioned above but probe into the method of spatial division 
in order to provide a more effective approach. It is shown that 
‘spatial division based on distance’ is the basis of the ‘m+2 
borders cater corner exchange’ algorithm. It means that affected 
region are divided into two independent sub-zone by restrained 
edge before spatial segmentation based on distance is 
conducted on the two sub-zone repeatedly till all sub-zones 
emerge as a triangle. According to the method, to find a point 
among the boundary point which is the nearest to any baseline 
(such as restrained edge), the triangle constructed by that point 
and the baseline must be in the sub-zone. But, the 
disadvantageous of this approach is the cost of calculating the 
distance. Therefore, this paper proposes a so-called radial 
spatial division method based on function Qi(x;,»;) , and 
apply the method to construct initial triangulation in the region 
affected by restrained edge for restrained edge mosaic. 
In Section 2 some basic conventions are given for discuss. In 
~ 
Section 3 the principle of radial spatial division method based 
  
    
   
    
   
  
  
  
  
  
  
  
  
  
     
    
   
  
  
  
  
  
  
  
  
   
    
   
   
   
   
   
   
   
   
    
    
    
   
   
    
    
   
   
   
   
   
   
    
Inter 
on 1 
desc 
divi: 
cons 
metl 
triar 
this 
exce 
whic 
and 
spat 
time 
conc 
Som 
e 
See 
Ap, 
adje 
adje 
3.1 
func 
For t 
poin 
azim 
as a 
radiz 
deve 
At le 
Occe