SAIC 
sing, it is 
ial spatial 
principle 
ied edges 
ruction of 
b-zone is 
npute the 
proposed 
area, and 
m! were 
e special 
thm’ fail 
issure the 
erms of 
between 
is (Wang, 
Igorithms 
| division 
iown that 
the ^mt? 
t affected 
‘estrained 
tance is 
;ub-zones 
d a point 
' baseline 
that point 
But, the 
lating the 
ed radial 
?;), and 
he region 
iscuss. In 
iod based 
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B5. Istanbul 2004 
  
on function Oi(x;, y; ) is presented. Section 4 and Section 5 
describe our algorithm in detail. A algorithm, the radial spatial 
division algorithm, for implementing restrained edge mosaic in 
constructed TIN based on the principle of radial spatial division 
method with function Qi(x;, y;) is proposed, and that the 
triangle created by radial spatial division algorithm proposed in 
this paper must be in the sub-zone is justified, and that an 
exceptional case is discussed, and that the spatial division tree 
which will be great benefit for the reconstruction of triangles 
and their topology in region affected by restrained edge after 
spatial division is proposed. Section 6 gives analysis about the 
time complexity of algorithms. Section 7 presents the 
conclusions. 
2. BASIC CONVENTION 
Some basic conventions are listed below for discuss: 
® no position coincide points in data set, or such points 
having been cleared off; 
€ supposing that vertexes of triangle numbered clockwise; 
€ restrained edge: defined as a vector,from the initial 
position to the end; 
€ cross edge: the edge of triangle intersected with restrained 
edge; 
® medium triangle: the triangle which have two cross edges; 
® region affected by restrained edge: region composed by 
triangles which have at least one cross edge; 
® diagonal vertex: two triangles, A4 and AB , are 
contiguity with cross edge. In the two triangles, the 
vertexs which are not on the cross edge are diagonal 
vertexs, and the diagonal vertex in AB is called the 
diagonal vertex of AA ; 
9 lett adjecent edge of diagonal vertex: edge is composed of 
diagonal vertex in AB and its previous vertex; 
€ right adjecent edge of diagonal vertex: edge is composed 
of diagonal vertex in AB and its next vertex; 
€ expanding edge: the standard for region spatial division, 
which is also an edge of divided triangle. 
See Figure l(a), for example, A4 is Ap,p;pg and AB is 
Api p» p; ; p5 is the diagonal vertex of AA ; p, p, is the left 
adjecent edge of diagonal vertex p», ; p,p3 is the right 
adjecent edge of diagonal vertex p,. 
3. RADIAL SPATIAL DIVISION METHOD BASED ON 
Qi(x;, y;) FUNCTION 
3.1 Radial spatial division theory based on Qi(x;,y;) 
function 
For the point set P in the plane, a radial cluster is composed of a 
point at random together with all other points. Every radial's 
azimuth angle a; is calculated and ascending sorted with o; 
as a key word, and then an ordered radial sequence in which 
radials with the same azimuth angle are counted as one radial is 
developed. 
At least there is one point besides the base point in every radial. 
Occasionally there are several points in the same radial. Here 
the spatial adjacent relation among the points at the same 
direction can be get as follow: 
When x = 0 : ascending sort with | as key word is down for 
the points; and 
When x # 0: ascending sort with E as key word is down for 
the points; 
In this case, this sequence's important property is that no point 
exists between any two adjacent radials. 
3.2 Spatial relation analysis methods between point at any 
radial and some other radial 
In order to analyse spatial relation between point p; on any 
radial / (azimuth @; ) and some radial k (azimuth a, ), Aa 
which start from radial / to radial k widdershins should be 
calculated, see Formula (1), and the spatial relationship 
between point p; and radial k can be deduced with Formula 
©). 
qu C. a;-a, 20 
Ag d (1) 
A; —a, +360 A «0 
if Aa <180°iijiii then pii righti ofii kiiiiii 
if ^a -0?£-6g0) then P;ii andij k:collinear (2) 
if Aa >180"jjiiii then p;ii lefiii ofii kiiiiiiii 
Usually arctan(x) is used to calculate azimuth «a; . In 
analyzing the spatial relationship between radials, the Qi 
algorithm turns the spatial adjacent relationship between radials 
into the adjacent relationship between the point of intersection 
of radials and side of the externally tangent rectangle of the unit 
circle. Then, the azimuth angle computation is shifted to the Qi 
length computation (Qi, Li and Zhu, 2003). So in practice for 
decreasing time complexity of algorithm arctan(x) could be 
replaced by Qi(x;,y;), see Formula (6), to calculate distance 
of Oi (Qi, 1996). All those analysis are implemented with 
function Qi(x;, y;) . Formula (3) and (4) correspond to 
Formula (1) and (2), respectively. 
AQ = o -0: Qj “0; 20 (3) 
: Qi; -Qa *8 Qi; -Qa «0 
if AQ; <4iiii then piii rightii ofii Kiiiiii 
if AQ; =0,f then  pjij andij k:collinear (4) 
if ^0Q;»4iiij then piii leftii ofii Kiiiiiiii 
3.3 Spatial analysis method of confirming adjacent radials 
of each radial in radial cluster 
According to Formula (3), AQ; can be worked out. 
When AQ; = MAX , corresponding radial is the left adjacent 
edge of the basic radials, and when AQ; = MIN | 
corresponding radial is the right adjacent edge of the basic 
radial.