d 2004 
ith the 
rtex of 
t of the 
e stack 
spatial 
lge. 
trained 
region 
n edge 
e edge 
int lies 
ng this 
rangle. 
ndition 
radial 
:d edge. 
nds of 
ted by 
have a 
I-ZONÉS. 
angles, 
b-zone, 
8» Po ) 
Figure 
e 2 (a), 
iangles, 
drangle 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXX\ 
   
/. Part BS. Istanbul 2004 
  
4.3 Discussion 
Compared with the method that calculates the triangular area 
(Lu and Wu, 1997) or the point of intersection of radials (Wang, 
2001), applying Formula (3), (4) to confirm affected region of 
restrained edge can improve time efficiency. The process can 
also be implemented by judging AxB , which is the 
relationship between point and directed line. Utilizing Ax B can 
set up the binary tree, see figure 3. The ordered radial spatial 
division sequence Q, (PoP2> PoP3» PoP1i> PoP4 > PoP5s 
PoP6 » PoPs » PoP7 ), can be established by inorder 
traversing of that binary tree (see Figure 3). The left adjacent 
edge of pops is popa4and its right adjacent edge is po pg . 
The time efficiency of Ax B is almost the same order with that 
of Formula (3), (4), but the time complexity of this method will 
increase nonlinearly with the increase of the edge points in 
affected region, while using the value of AQ; the time 
complexity increase linearly (Qi, Li and Zhu, 2003). 
Consequently method proposed in this paper with lower time 
complexity than that of judging Ax B method. 
PoPs 
p 
PoP PoPs 
PoP2 PoP3 PoP6 PoP7 
> 
PoP3 
Figure 3 Binary sort trees 
S. SPATIAL DIVISION OF INDEPENDENT SUB-ZONE 
5.1 Spatial division method of independent sub-zone 
Figure l(b), radial spatial division based on Qi(x;,y;) are 
operated in independent sub-zone (55: po^. pa) with 
PoP4 as expanded edge, which is formed from the first point 
to the last point in the sub-zone to search the left adjacent radial 
of Po P4 - Edge point p, meets the condition. If there are more 
than one edge points in that radial, the edge point adjacent to 
the base point meets the condition. Then that point can be 
connected with expanded edge pop, to construct triangle, see 
figure 4(a), and Apo p, p, including expanded edge pop, 
separates (Do: P1>À , P4) into Apop,P4 and independent 
sub-zone (po, p, ) and (pi P2 P3 DA). 
Next (pg, pi) and (Di, P2> P3, D.) , the two independent 
sub-zones, are divided with pop, and p, p, as expanded edge 
repeatedly according the process mentioned above till there is 
only two edge points in the sub-zone. 
Similarly the other independent sub-zones can adopt the same 
radial division method as in the (po SPA JP, ). 
In practice, division operation have to be done only when the 
number of edge points in the sub-zone more than 3 otherwise 
the edge points can be connected to be a triangle directly. 
For radial division process in region affected by restrained edge, 
sce spatial division trees in Figure 5(a), (b). Figure 4(b) show 
the results. 
   
Po 
(a) (b) 
Figure 4 Spatial division of independent area 
o 
X £7 « 
^T PPS. f 
X \ S 
^ fp p pap 4 IN 
d UIN a a (PsPs PDA 
4 LA mA -- —_— \ 
4 pap T M SN \ 
X Poi LA UDVPRYN 4(PSP8 N— peo Y 
— "x ans 
A d 4 
^ 
4 ms \ PsPa 4 (ss P; 
4 qmm mas” 
\ 
d PP» P3P3 4 
(a) (b) 
Figure 5 Spatial division trees 
5.2 Justification that triangle including expanded edge 
must be in an independent sub-zone 
It is provability that the triangles formed by the spatial division 
based on Qi(x;, y;) and restrained edge mosaic must be in 
each independent sub-zone. In the independent sub-zone 
(Bos P^ pa, with base point p, and expanded edge 
Po P4 search a triangle including expanded edge by radial 
spatial division theory based on Qi(x;,v;) function, for 
example. 
Supposed that Apo p, p4 does not in the independent sub-zone 
(Pos P1>À ‚Pa at least Vp, e(p., pi) belong to 
Apo pips, because Ap, py py have included expanded edge, 
which means that at least there are one point in (p; , pi) lie in 
the right of radial po p, . 
But pgp; is the left adjacent radial line of pops through 
radial division. According to the important property of the 
radial spatial division (see section 3.1 in this paper), there is not 
any other edge point exist among pop, and pops. 
So the hypothesis above does not tenable. And App, pa 
being in (50; Dr A pa) can be justified. 
By the same token other processes of sub-zone division and 
restrained edge mosaic can be authenticated.