International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004 
5.3 An exceptional case 
See figure 6(a), p, arises several times in left edge queue QO 
(Po: Pı>P2>Pı: 3; Pa: Ps) which obtained by the 
algorithm mentioned above (see 4.1 in this paper). Practically 
edge p,p3i€ps; p, are one borderline, but logically they are 
two edges called *logic edge'. Their left adjacent space is a line 
space without left adjacent triangle. So it is troubled for 
recording adjacent relationship of triangles after dividing 
because of no record of adjacent triangle in the record of edge 
adjacent relationship. 
  
Ps 
Da 
V7 p 
See 
Ps 
Po 
(a) (b) 
Figure 6 Affecting area of restrained edge 
The spatial trees showed in figure 7 (a), (b) are gained from 
figure 6(a) by spatial division according to the method proposed 
in this paper. The leaf nodes extend from left to right are the 
borderline of the adjacent sub-zone in the division tree, see 
figure 7(a), and the next leaf node of pip», is p3 p, . So by 
searching the triangles of the two adjacent special leaf nodes 
(no record of adjacent triangle) are the two triangles adjacent 
with the special edge as the public edge. Figure 6(b) show the 
divided results. 
PoPs 
sa NS 
^ 
4 PoPa™ Paps 
4 
2 AN N it NN 
7 PyMA PD». DP pars PsPo 
ir Cd 
= 
# P2P3SN. P3P4 PsP7 PP. 
N 
/ AN > 
/ poni P1P3 X P5sPo: PoP7 P3 Ps Ps Po 
Nune m unl umi uem em - 
1 
x 
(a) (b) 
Figure 7 Spatial division trees 
5.4 The property of spatial division tree 
The properties of spatial division tree go as: 
€ Father node together with its two child-nodes construct a 
triangle. The triangle of root node includes restrained 
edge; 
€ All nodes except leaf node represent either the 
independent sub-zone which have those nodes as 
expanded edge, as well as the public edges of divided 
triangle in the affected region, in which the triangle of 
root node of tree (a) is adjacent with the triangle of root 
node of tree (b); 
€ Leal nodes array, which formed by traversing on the leaf 
nodes of the tree (a) and tree (b) from left to right, is the 
clockwise sequence affecting the region border. Leaf 
nodes record the adjacent relationship with other triangles 
out of the affected region. When logic edge presents, 
there will be no any record of the adjacent relationship in 
the leaf node, so the two triangles of the two adjacent leaf 
nodes are of contiguity each other with their own 
corresponding physical edge as public edge. 
According to the important property mentioned above, it is easy 
to get the triangles and their spatial adjacent relationship after 
region being divided in the spatial division tree. 
6. TIME COMPLEXITY ANALYSIS OF ALGORITHM 
Here gives the comparison of time complexity between the 
radial spatial division algorithm and the spatial division 
algorithm based on distance. 
Formula (5) is the function used to calculate the distance from 
the point to the line. 
  
  
dix, viles, + By, +C (5) 
where: 
de Ja VI 
(y: d nr +(x, = #) 
Bon X Xi 
  
  
  
  
Formula (6) is the function used to calculate the Qi length (sce 
Qi and Liu, 1996, Qi, 1997 and Qi, Li and Zhu, 2003 for 
details). 
Ay; / Ax; (Ax; » 0) ^ (Ay; Z O) ^ (Ax; > Ay;) 
2-Ax;/Ay, (Ax; 2 0) ^ (Av; » O) ACA; S Ay) 
2-Ax/Ay, (Ax; £0) ^ (Av; » 0) ^ (Ay; 5 —Ax,) 
4+Ay,/Ax; (Ax; <0)A (Ar; > 0) a (Ay; $ —Ax;) 
4+Ap,/Ax; (Ax; <O)A (Ay; € 0) À (Ax; € Ay;) 
6-Axj/Ay; (Ax; S0) A (Ay; « O) ^ (Ax; » Ay,) 
6-Ax,/Ay; (Ax 2 0)A(Ay, «O^ (Ax, S Ay) 
84 Ay;/Ax; (Ax; 2 0) ^ (Av, « O)A(Ax, 5 -Ayi) 
Qi vy (6) 
Table 1 shows the comparison of the basic operation between 
dix. y; and Qi(x;, y;). 
Seen from Table 1, when the problem scale is n, if ‘judgment’ 
is taken as the same level as ‘+/-’, and ‘evolution operation’ is 
taken as the same level as ‘x/+* , the frequency count of 
calculating distance d; (x; v;) to implement *x/+’ is 10n, while 
the frequency count of calculating Qi(x;, y;) to implement 'x/ 
+’ is n. Take ‘x/+° as the basic operation to measure the 
difference of the progressive time complexity between the two 
algorithms. The result is that the progressive time complexity 
     
   
  
  
  
   
   
  
   
  
  
   
   
  
  
   
   
   
  
  
  
  
  
  
   
  
   
  
  
  
  
  
  
   
   
   
  
   
   
     
    
  
     
  
   
   
  
   
    
     
   
     
    
of 
cal 
  
Tal 
Iti 
for 
me 
de: 
det 
(1) 
M. 
rer 
Tr. 
Tr 
htt 
Zh 
dy 
Su