3.2 Rough Grids for Indexing 2DRE File
It is often necessary to access only a part of
the spatial database, that is, to index into the
database and retrieve only data pertaining to a
particular area. B'* tree is a popular approach
in a general database. However, B** trees do not
map directly into the quadtree structure, that
is, there is no logical correspondence between
the two structures. Accordingly, a block of the
B-tree covers an irregular varying unit of space
Within the quadtree.
To overcome this problem, a quadtree indexing
method is proposed, where the index corresponds
to some higher (non-leaf node) level of the
quadtree and so gives a regular division of
space, which is termed rough grid and is also
encoded in Morton key(MO). A limitation when
generating 2DRE is that a "leaf node" can not
exceed a rough grid. The index is also stored as
a linear list in Morton key. The sequences of the
records in the index file implicitly represent
Morton keys(MO) so MO can be not written in the
index file. Each record of the index contains
only the number of bytes from the start of the
file (Figure 6).
M1 | Value
ee 0 Pl
(MO)Pointed | |
0 o e uci 256 | L4
t res "e
Eddie TI
2 12406 | =k Bi
3 130942 — 768 | LA
3320| P2
Figure 6. Rough grid index for 2DRE
The index readily provides random access into a
"leaf node” of 2DRE. to retrieve data at
particular point, the Morton key(M1) of the point
in the basic grid is divided by the rough grid
size, and a Morton key(MO0) in rough grid is
obtained. This gives the number of the relevant
index record, from which the number of bytes can
be used to retrieve the relevant point portion of
the 2DRE. This portion is then searched linear
until the required point is found.
4. UNIFIED DATA STRUCTURES OF FEATURES
There are three types of features including
points, lines, and surfaces. Several files may
exist, each of them contains information on a
primitive element or a kind of feature.
4.1 Data Structure of the Point Features
A point feature may simultaneously be an
intersection of several lines. Therefore we treat
the point features and the intersections of lines
as the same objects, which are called nodes and
Stored in the same data file.
A node can be geometrically described only by its
location. Node data would be held as files in
Which each node was represented by two Morton
keys M1 and M2 of the node, M1 and M2 represent
770
respectively the Morton key of the basic grid and
that of the fine-grid in which the node is
located. Each record in the node file would
contain a node identifier NODE ID, two Morton
keys M1 and M2 (see figure 7).
m [3
o
c
a
a E
FI
Figure 7. Structure of points
4.2 Data Structure of the Line Features
A line feature has a shape and should be
described by the whole route of the line. It is
suitable that line features are treated as vector
structures. But in order to interface raster
data, the vector structures are also represented
by linear quadtree address keys. The coordinates
X, y are converted into Morton keys M1 and M2. It
is noted that the converted coordinates not only
are those of the original sampling points but
also include those of the intersection points
between the line and each basic grid side(Figure
8).
Figure 8. Structure of ARC
To consider a line feature may be divided into
several arcs, an arc file should first be first
created. Each arc uses a record in the arc file,
which contains an arc identifier ARC_ID, two
NODE_IDs of the start-node and the end-node of
the arc, a string of Morton keys M1 and M2 of
medium points.
A line feature consists of arcs. Its data
structure is linked with the file of the arcs.
The structure contains a line identifier LINE ID
and some ARC IDs of arcs composing the line
feature.
4.3 Data Structure of
the Surface Features
A surface feature involves its borders and all
the cells bound by its borders. The data
The
emp
geo
fea
nod
con
tha
obj
the
of
hant
comi
