ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
394 
G) left sub-edge triangles ( 9 ) : 
L(T(U)),R(T(U)), T(L(U)),L(L(U)), T(R(U)),R(R(U)), T(L(T(U))) 
• R(R(T(U))), R(T(L(U))). 
H) right sub-edge triangles ( 9 ) : 
L(T(U)),R(T(U)), T(L(U)),L(L(U)), T(R(U)),R(R(U)),L(L(T(U))) 
,T(R(T(U))),R(T(L(U))) o 
I) sub-corner triangles ( 9 ) : 
L(T(U)),R(T(U)), T(L(U)),L(L(U)), T(R(U)),R(R(U)), T(L(T(U))) 
,T(R(T(U))),R(T(L(U)))o 
5 ALGORITHM FOR GENERATION OF VORONOI DIAGRAM 
BASED ON QTM 
5.1 Principle 
Algorithm for generation of Voronoi diagram in spherical 
surface is based on the definition of Voronoi diagram and dilation 
principle of spherical triangles. In the QTM, a point is represented 
by address code of a triangle, an arc is represented by a series 
of points and a region is represented by its boundary trace. 
Dilation of a line or region can be simply by dilation of all the 
points describing the line or borderline of a region. So the 
principle of generating Voronoi diagram is as follows: First, 
determining the direct and indirect triangles surround the points, 
arcs and areas by finding algorithm of neighbor triangles. 
Secondly, remove all duplicate triangles, and generate dilation 
trace of object (such as point, or arc, or area). The dilation trace 
has approximate spherical distance to the boundary of the object. 
Next, repeats the dilation and stops when the dilation trace is 
intersected with the other dilation trace. The intersecting trace is 
just the Voronoi edge between two objects. 
5.2 Algorithm 
input: partition level N and data sets in sphere: r 
~{Ai,A2,A3, ,A n } 
output: Voronoi diagram of sets r, and store in data file 
VoronoiData. 
CsphVoronoiView::OnCaculateVoronoi() 
{ 
stepl: LongLatitude_to_QTMcode(V); // 
step2: For every objects A, in r 
{ step2.1: For every QTMcode Q, in A,; 
{ Adjact12(Qy); 
if Adjact12(Q y ) are copy code 
Delete_copyQTMcode( Qy); 
Else Diatation_A[/] <- 
Adjact12(Qy) 
} 
step2.2: For every Diatation_A[/] 
{ For every QTMcode Q im in A[i\ and 
every QTMcode Q jk in A[/], ¡¿j 
{ if (Qim ~ Qjk) 
VoronoiData<-Qy* : 
} 
} 
} 
step3: QTMcode_to_LongLutitude(VoronoiData); 
step4: Output(); 
}over 
6 EXPERIMENT AND ANALYSIS 
Based on the principle described as above, we have developed 
calculated program in platform OpenGL with VC ++ language. 
Voronoi diagrams of spherical objects are generated by QTM 
cells dilation. The distortion in distance between great circle 
distance and QTM cells distance, especially; the relationship 
between distortion in distance and different locations will be 
analyzed in this section. 
6.1 Experiment and results 
Based on the principle described as above, we have developed 
calculated program in platform OpenGL with VC ++ language. 
Voronoi diagrams of point sets, arc sets, area sets and any sets 
are generated by QTM addresses. The results are as Figure 7. 
The experiment shows the complex of generating Voronoi 
diagram of point sets is as same as arc sets or is sets by QTM 
addresses. 
(a) (b) (c) (d) 
Fig 7 Voronoi diagram of spherical objects : (a) point sets ; (b) arc sets ; (c) area sets ; (d) mix sets 
6.2 Errors influence to dynamic model and control methods 
In planar mode, it is realized that the maximum difference 
between Euclidean distance and raster distance is a linear 
function of the distance itself ()• The distortion resulting from the 
dynamic distance transformation (C. Li et al. 1999) is consistent 
with the maximum distortion about 1 pixel, but spend more time. 
It is different to sphere QTM cells. In this case we select 7 points 
on different location in one octant unit (shown as Fig.8) to 
illustrate the relation between the distortion and distance. 
Fig.8 Points on different location in one octant unit 
Each point need to dilation 64 times when its dilations cover the 
whole globe. The distortion values of points are selected every 4 
times dilation and calculated as following: 
(6.1) 
where Sxoxi is the great circle distance between the center of 
origin triangle X 0 and the center of dilation triangle X,. K is the 
number of the dilation steps and n is the number of dilation 
triangles in Ksteps. A diagrammatic representation is given in 
figure 9: s is shown in horizontal axis and dilation times k 
0 
(one indicates four times dilation) is shown in vertical axis.