International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B3. Istanbul 2004 
4. RADIAL SPATIAL DIVISION WITH RESTRAINED 
EDGE AS EXPANDING EDGE AND RESTRAINED 
EDGE MOSAIC 
4.1 Confirmation of region affected by restrained edge 
4.1.1 Confirmation of the first triangle 
The algorithm steps of confirmation of the first triangle in the 
region affected by restrained edge is the following: 
€ Record the starting point of restrained edge into left edge 
queue Q and right edge stack 5; 
€ Calculate Qi(x;, y;) of every triangular edge with the 
the starting point of restrained edge as a center; 
€ Use Oi as a key word to get two edges each adjacent 
with left and right of restrained edge. Starting points of 
restrained edge are one end of the two edges respectively. 
The triangle which contains the two edges is the first 
triangle in the region affected by restrained edge; 
€ Record the /D of the other point of the left adjacent edge 
and AQi for the left adjacent edge and the restrained 
edge into the left edge queue Q of the affected region; 
€ Record the ID of the other point of the right adjacent edge 
and AQi for the edge and the restrained edge into the 
right edge stack S of the affected region; 
€ Record the /D of the triangle. 
In the process mentioned above, if restrained edge has the 
same value of Qi as that of either edge of triangle, which 
means that restrained edge coincide with either edge of triangle, 
then the mosaic of the next restrained edge of restrained edge 
string can be performed directly. Because a triangle associated 
with the starting point of the next restrained edge has been 
gained, all other triangles which make starting point as vertex 
can be gained through the triangular adjacent relationship, and 
the first triangle can be get in the same way mentioned above. 
4.1.2 Confirmation of the middle and the last triangle 
The middle and the last triangle can be confirmed by analysis 
of spatial relationship between diagonal vertex and restrained 
edge. If the diagonal vertex lies to the left (or right) of the 
restrained edge, right adjacent edge (or left adjacent edge) of 
the diagonal vertex is certain to be the cross edge, and AB is 
certain to be middle triangle; if the diagonal vertex happen to 
be situated in the restrained edge, AB is certain to be the last 
triangle in the region affected by restrained edge. So the middle 
or the last triangle in region affected by restrained edge can be 
acheieved through analysing the spatial relationship between 
the diagonal vertex of the first triangle and restrained edge in 
the region affected by restrained edge. Such analysis should be 
continued till find the last triangle ,when the whole region 
affected by restrained edge can be confirmed. 
The spatial relationship analysis mentioned above can be 
acheieved by constructing radial with starting point and 
diagonal vertex and applying Formula (3) and (4). The step go 
as : 
® If AQi>4, the diagonal vertex of A4 must lie in the 
left of restrained edge. Record AQi into left edge queue 
Q of the affected region; 
® If AQi<4, the diagonal vertex of A4 must lie in the 
right of restrained edge. Record AQi into right edge 
stack S of the affected region; 
e If AQi 2 0 or 4, the diagonal vertex coincide with the 
restrained edge; 
€ Record the ID of AB. 
Repeat the process mentioned above till the diagonal vertex of 
TA coincided with restrained edge. Record the end point of the 
restrained edge into the left edge queue Q and right edge stack 
S, respectively. 
The sequence of the triangular /D recorded by radial spatial 
division process is the affected region of the restrained edge. 
4.2 Restrained edge mosaic 
In fact the process of confirming affected region of restrained 
edge is the first step of radial spatial division of the region 
affected by restrained edge. Being found from Q as an edge 
point which meets the condition of AQi = MAX , the edge 
point separate Q into two parts, the radial wherein the point lies 
is the left adjacent of the restrained edge. Then connecting this 
point with the two ends of restrained edge can form a triangle. 
Similarly in S to find an edge point that satisfies the condition 
of AQi= MIN and separate S into two parts, the radial 
wherein the point lies is the right adjacent of the restrained edge. 
And then connecting the edge point with the two ends of 
restrained edge can form a triangle. The region affected by 
restrained edge is divided into two triangles that have a 
restrained edge as common line and four independent sub-zones. 
In Figure 1, pops is the restrained edge. Two triangles, 
Apopa4ps and Apspgpo, and four independent sub-zone, 
( Do» Bi , PA UC as P5 Y-C Ps, De ) and ( po; P5. Pg» Po). 
can be obtained after restrained edge mosaic process. Figure 
1(b) shows the results. 
For example, the whole division process shows in figure 2 (a), 
(b). 
If the affected region is composed of two triangles, 
implementing diagonal processing of convex quadrangle 
exchange directly can do restrained edge mosaic. 
   
Po 
(a) (b) 
Figure 1 Affecting area of restrained edge 
PoPs PsPo 
PoPa PaPs PsP6 P6Po 
(a) (b) 
Figure 2 Spatial division trees 
    
   
   
   
   
  
   
   
    
  
   
  
    
   
   
   
   
   
   
    
    
    
   
  
   
   
   
  
  
  
   
  
  
   
    
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   
  
  
   
  
   
    
Co 
(Li 
201 
res 
als 
rel: 
set 
div 
Pq 
tra 
ed; 
Th 
of 
inc 
aff 
Cot 
Co 
col 
Fig 
op 
PC 
to t 
of, 
tha 
the