×

You are using an outdated browser that does not fully support the intranda viewer.
As a result, some pages may not be displayed correctly.

We recommend you use one of the following browsers:

Full text

Title
The 3rd ISPRS Workshop on Dynamic and Multi-Dimensional GIS & the 10th Annual Conference of CPGIS on Geoinformatics
Author
Chen, Jun

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.