and
is
uld
ton
it
lO
f
f
structure of the borders is similar to that of
lines, while the cells are constructed by two-
dimensional run-encoding(Figure 9). An overlay is
represented by a 2DRE file. Because the 2DRE of
an overlay can occupy a large file, an index file
is necessary.
Figure 9. Structure of surface
In the 2DRE file, each "leaf node" uses a record,
which contains only one Morton key M1, and a
cycle pointer instead of the attribute/value of
the "leaf node" in figure 4c. A purpose to set up
pointers is to build the object-oriented data
models. All leaves that belong to a surface
feature are linked by the chain pointers, and
connected with the data file of the surface
features.
The data structure of surface features should
contain both the border information and the cell
information. A surface feature uses a record
which contains a surface identifier SURFACE ID,
some ARC IDs of the boundary arcs and a pointer
to point at the first "leaf node" record of the
feature in the 2DRE file.
4.4 Data Structure of
the Complex Features
A feature consisting of several features is
called a complex feature. The data structure of
complex feature contains a complex feature
identifier COMPLEX_ID and some identifiers of its
component features, which may be different types
of features.
4.5 Data Model Based on
the Unified Data Structure
The concepts of object-orientation can be
employed to build the geometric data models. In
geometry, there are only three types of basic
features and several primitive elements such as
node, arc and "leaf node" in 2DRE. A feature
consists of one or more primitive elements, more
than one features may compose a more complex
objects. Some underlying data are propagated from
the components to the composite object in terms
of the identifiers or the pointers. On the other
hand, aggregation would be helpful to share the
common objects, which could establish the
771
topological relationships among objects. The data
models including the primitive elements, the
simple and the complex features are shown in the
following diagram.
p
| Complex feature |
E
simple feature
T P
(‘Point toate}
oy
Fig. 10. Data model based
on unified data structure
The arrows in the diagram express the identifier
linking or the pointers in the data files, the
ellipses contain the most primitive data in GIS.
The diagram shows that the vector structures and
the raster structures do not have any obvious
distinctions because they use the same primitive
data format--Morton key, which can guarantee the
unified data structure serve the two kinds of
data.
5. CONCLUSION
This paper has discussed the linear quadtree and
two-dimensional run-encoding, fine-divided grids
for improving the representation precision of
raster and rough grids for indexing 2DRE file. A
modeling of an unified data structure and a data
model based on the structure has been proposed
for future GIS. The data structures based on
linear quadtree has been formed by using the
object-oriented programming language C'*. The
data models according to Fig. 10 have been built
by using the same language. It has illustrated
that the structures are powerful for analysing
and processing the geoinformation. Some
algorithms based on the data structure, such as
spatial querying, automatically establishing
topological relations among features, directly
converting vector data into linear quadtree and
the linear quadtree into vector data, are
developed. Here are some examples for statial
analysing and data processing: figure 11 is an
example for querying all susfaces neighbouring
the the Surface A; figure 12 is an example for
querying all surfaces relating to the Line A;
figure 13 is a result of an intersection set
operation; figure 14 is an example converting
vector into linear quadtree; and figure 15 is a
vector map from linear quadtree. The database
with the unified data structure may need more
storage space than the single vector structure,
but with the development of the hardware it is
not a crucial issue.
