ul 2004
al entity
Xing.
entroids
| can be
a set of
than to
icted in
ude and
| for any
1alogous
ce along
. to note
o metric
d edges.
ne radial
with the
/ a given
In order
to know
ie can be
m set of
with the
stributed
jyints are
'allels as
division
mber of
picted in
using as
est to the
as set of
ere.
ollowing
trary 3D
point, its
els---one
parallel
parallels.
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol XXXV, Part B4. Istanbul 2004
From each parallel are taken two centroids with values of
spherical longitude closest to the point. From the four
candidates the proximate centroid is found. If two or more
candidates have the same distance to the point the most north
east centroid is selected. Note that next to the poles only three
candidates are available.
An example of full
tessellation of geoindex
projected on the sphere is
shown in Figure 3. The
tessellation — generates a
semi-regular global grid.
The geometry of the cells is
not unified but it is possible
to claim that cells tend to
have a shape of hexagons.
Fig. 3. Geoindex tesselation.
2.3 Levels
In order to use Voronoi based grid for data with various
resolutions | geoindex introduces concept of levels. In
applications of geoindex an arbitrary number of levels can be
used. Each level tessellates the space into cells as introduced in
the previous section. Each level has different division
coefficient (see Section 2.2). The levels are accessed directly as
independent layers rather than hierarchy. In Figure 4 are
depicted cells from levels with division coefficients 10 and 50.
For sake of clarity only cells along the prime meridian have
been rendered.
There is a straightforward way of constructing an acyclic graph
when traversing from the coarsest level to a finer level;
however this option has not been elaborated. Building a
hierarchical structure across the levels is not necessary since the
proximate cell can be accessed directly regardless the resolution
of the grid at the particular level. Using independent levels also
provides flexibility in decision about which levels are needed or
convenient to use.
Level Number of cells —width [m]
2 6 10 000 000
3 12 6 680 000
4 22 5 010 000
5 34 4 010 000
10 128 2 000 000
100 12 732 200 000
1000 1 273 248 20 000
10 000 127.323 974 2 000
100 000 12.732 395 370 200
Table 1. Number of cells in selected levels.
In Table 1 are given number of cells in selected levels. Number
specifying the level directly refers to the division coefficient.
The coarsest available level is with division coefficient being
two. This generates a tessellation of the space through six cells,
€.g., a cube projected on the sphere. For this case the width of
each cell on the Earth's surface would be approximately 10 000
kilometers.
Use of levels has direct use for dealing with level of detail in
underlying applications. Levels with higher division coefficient
671
are accessed when more detailed geographic data from smaller
spatial range are necessary, while lower division coetficient is
used when larger areas need to be available in their spatial
context.
Figure 4. Cells distributed along the prime meridian with
division coefficient ten and fifty.
2.4 Applications
In this section is presented how geoindex can be used for
management of geographic data in practice. Also reasoning
about applications that could exploit the concepts of geoindex is
presented.
[n order to apply geoindex it is necessary to maintain a search
tree and for each record assign an address referencing its
physical position in a file or memory. This mechanism,
however, is implemented tested and optimized for many years
by numerous available database management systems. There
are solutions for indexing one-dimensional sets, e.g., B+-tree,
which can be used immediately when unique identifiers are
assigned to cach cell. Similar approach has been proposed in
(Oosterom, 1996).
Geoindex has been devised to aid visual applications in 3D.
That is one of the main reasons why proximity features of
Voronoi diagram have been picked over hierarchical structures
as used in QTM or quad division based global grids. Typical
query when navigating visually through geographic 3D model
can be in a form “give me the nearest data with highest level of
detail and distant locations with less detail and from certain
distance nothing at all”. This closely expresses the concept used
by geoindex and any application that can elaborate on this
approach can use geoindex.
Regarding geometric data representation that can be indexed
using this method; any geometric data structures representing
spatial features can be used as long as the data representation
