International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004 
  
raster data but can be used for indexing of any geographic 
features around the globe. The disadvantage is singularity at the 
poles and need for projecting all the data before actual 
indexing. 
There are other applications of quad division, e.g., dividing 
faces of cube or two sides of plane, which generate global grids. 
Some of them are used in commercial applications. 
2. GEOGRAPHIC INDEX 
This section presents an original indexing method for spatial 
data based on a global grid. The primary focus is on explanation 
of the concepts behind the tessellation itself, ie, on 
construction and geometry of the grid. 
2.1 Basic Division Scheme Properties 
The main concept of geographic index (geoindex) is a 
tessellation of the sphere into cells of similar size. This is 
achieved using Voronoi diagrams on the sphere. While 
(Lukatela, 1987) assumes an arbitrary constellation of cells, 
typically derived from the spatial distribution of the data, in 
geoindex the constellation of the cells is fixed. If the fixed 
constellation can be described by reasonable simple algorithm 
then it can be introduced as a general indexing method that 
could be applied globally. Another interesting implication 
would be a possibility to index at different resolutions of the 
division scheme. This is in general impossible with Voronoi 
diagrams because the cells cannot be divided recursively. The 
recursion however, can be replaced by an additional parameter 
that specifies the resolution of the tessellation. 
The grid used by geoindex can be presented as a set of specific 
instances of Voronoi on the sphere; where the instances are 
given by a distribution rule. The distribution rule is used in 
order to set a convenient density of the grid that would 
correspond to the nature of the data or to needs of an 
application. 
Although the division scheme is convenient to depict as a 
tessellation of the 
qct ae | oc2 Surface of sphere, based 
| on radial proximity the 
\ | / grid actually divides 
C el completely the whole 
Ao | int 3D space around the 
e. | / origin. This twofold 
approach to the 
tessellation is convenient 
because many 
\ | / geographic data and 
applications do not need 
Cl d three spatial dimensions. 
Ur For such applications 
AY range from the origin is 
y omitted which results in 
a two dimensional space 
given by sphere surface. 
Still however, the sphere 
itself ^ is ^ obviously 
defined in 3D space, which provides a good basis for fully 3D 
geographic applications. 
\| / 
V ORIGIN 
Figure 1. Radial distances 
670 
2.2 Cells 
The spatial unit in geoindex is a cell. Cell is an essential entity 
of the method that is directly used in the process of indexing. 
In order to define a cell, significant vectors called centroids 
have to be known for each cell. In general, a centroid can be 
any non-zero vector in 3D. The cell is then given by a set of 
points with radial distance to a given centroid smaller than to 
any other centroid as depicted. The situation is depicted in 
Figure 1 and 2. Cell is identified by spherical latitude and 
longitude of the centroid. This definition for cell is valid for any 
point in 3D space. 
Cell definition, however, can be interpreted in an analogous 
manner on the surface of the unit sphere using distance along 
the surface instead of radial proximity. It is important to note 
that in the first, more general, definition cells have no metric 
extents, only radial. 
As depicted in Figure 2 and 3 cells have vertices and edges. 
Edges are given by vectors from the origin with the same radial 
distance to two centroids. Vertices are then vectors with the 
same radial distance to, at least, three centroids. 
eo 
z^ 
X c2 
dd X 2 
p Nin UT 
) \ 
j NA 14 
o | P X 
1 but \E 
| rt n ^ 
} c 
? C1 
& > 
es 
9 o 
Figure 2. Cell definition 
The main task behind the indexing process is to classify a given 
3D point to its cell, e.g., to find its proximate centroid. In order 
to identify the proximate centroid it is necessary to know 
complete set of the centroids from which the closest one can be 
selected. The very idea in geoindex is that the minimum set of 
candidate centroids can be obtained computationally. 
The selection of the candidates is closely bound with the 
distribution rule for the centroids. The centroids are distributed 
through points given in spherical coordinates. The points are 
distributed semi-regularly around the sphere along parallels as 
follows: Interval between parallels is given by a division 
coefficient. This evenly marks off the specified number of 
points between poles along the prime meridian as depicted in 
Figure 4. Parallel at each marked point is then divided using as 
many points so that the interval along the parallel fits best to the 
interval along the meridian. Centroids then are defined as set of 
vectors from the origin to each point marked on the sphere. 
Obtaining candidate centroids is based on the following 
predicate; there are four candidate centroids for an arbitrary 3D 
point that does not define a centroid. Given such 3D point, its 
candidate centroids are from the 2 closest parallels---onc 
northern from the point and one to the south. Northern parallel 
is taken when the point occurs exactly on one of the parallels. 
Inte 
Fro 
sph 
can 
can 
eas 
St 
i 
A 
res 
app 
use 
the 
coe 
ind 
dep 
For 
bec 
The 
wh 
ho 
hie 
pro 
of { 
pro 
con 
In 
spe 
The 
twc 
eac 
kilc 
Use 
unc