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

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

ISPRS, Vol.34, Part 2W2, "Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001
Definition 1 (great circle distance on sphere surface)
If P= {pi, p 2 , .... p in }( 2 S, / and A x are vectors of pieS and p hi €S respectively. The
shortest distance between points p, and pj is defined as: the
distance of the shorter arcs in the biggest circle (its center point
is the center of sphere) via point p and p,. This distance is
expressed by formula as follow.
( , )= arccos ( )< n (3.1)
Definition 2(Voronoi diagram of spherical points sets)
If P= {pi, p 2 , ..., p n }(2 < n < oo)is points sets in spherical surface
S, giving a non-empty sets in S.
() = {|(,)<(, ) * , € , e } (3.2)
is called Voronoi polygon in sphere about p/. Figure 1 shows a
spherical voronoi diagram on point sets
Fig. 1 Spherical Voronoi diagram on point sets
Definition 3(dilation and erosion based on QTM cells)
If A is a region in QTM and B is an structure element, the
operations of dilation and erosion in QTM are as follows (Figure
2) :
© = u e
0 = n e
Fig.2 Dilation and erosion operation in QTM
4.1 Partition method of spherical facet based on QTM
Originally the concept of spherical facet partition was presented
by Fuller, a German cartographer, for studying the mapping
projection in 1940's, after then many researchers have
approached this problem to analyze and index the global data
(White, et.at., 1992). Many methods is based on inscribed
polyhedron (such as tetrahedron, cube, octahedron,
dodecahedron, icosahedron). Edges of polyhedron are projected
to the spherical surface and form the edges of spherical triangles.
This is a basis for global partition. In this paper, we choose an
octahedron as a basis for an O-QTM, the reason is that it can be
readily aligned with the conventional geographic grid of longitude
and latitude. When this is done, its vertices occupy cardinal
points and its edges assume cardinal directions, following the
equator, the prime meridian, and the 90 th , 180 ,h and 270 th
meridians, making it simple to determine which facet a point on
the planet occupied. Each facet is a right spherical triangle.
But if recursive partition for the spherical triangle is done, the
shape and length of triangles have to be varied, i.e. edges and
internal angles are not equal. There are some methods of
recursive partition to satisfy the different requires. Latitudes &
longitudes average method is selected in this paper. When a
facet is subdivided, the latitudes and longitudes of pairs of its
vertices are averaged to yield edge midpoint locations, and so on.
As a result, most of the triangles in the QTM network have
almost same shapes and area (Figure 3).
(c) 512
Fig.3 Hierarchical partition of spherical facet based on octahedron [Dutton, 1996]
4.2 Code character of QTM
A point on the earth is usually defined by its longitude X and
latitude .„ In the QTM triangular hierarchical data structure, the
position of a point is identified by the centriod of a decomposed
triangle. The accuracy of estimates of the locations of points
improves with increasing amounts of decomposition. A QTM
location address consists of an octant number (from 1 to 8)
followed by up to 30 quaternary digits (from 1 to 3) which name a
leaf node in a triangular quadtree rooted in the given octant. At
the k-th level of decomposition, the triangle address A is
represented by : A = aoaia 2 a 3 a k . where a r to a k are k
quaternary digits, while a 0 is an octal digit representing the initial
Fig.4 (a) Original partition of earth surface; (b) Code in 0
octant unit