A UNIFIED DATA STRUCTURE TO REPRESENT
VECTOR AND RASTER DATA IN GIS
Li Deren
Gong Jianya
Department of Photogrammetry and Remote Sensing
Wuhan Technical University of Surveying and Mapping
Wuhan, China
ABSTRACT
In the literature a number of proposals have been made for an unified data structure to represent vector
and raster data. The unified data structure is based on linear quadtree encoding and multi-grids
technique, and it can combine the advantages of vector and raster structures and support an integrated
system to contain GIS, DTM and RS.
In this data structure, all geometric data are expressed by the address keys of linear quadtrees instead
of X and Y coordinates. In order to improve the representation precision of raster, an approach for fine-
dividing grids is proposed, on the other hand, in order to index database, an indexing file based on
linear quadtree is used. The location of a point is represented by two Morton keys, one of them indicates
its location in the basic grid, and the other one corresponds to the fine-divided grid. A line feature is
described with a set Morton keys, which contains not only the end points and sampling points but also
consists of the whole route that passes the basic grids. Similarly, a surface feature consists of the
borders similar to the line representation and the whole terrain area encircled by its borders. The
surface features as coverage data can be stored as a two-dimensional run-encoding file. These geometric
data can be considered as vector form or raster form or both.
Key Words: Linear quadtree, Raster, Vector, Unified data structure, Two-dimensional run-encoding.
1. INTRODUCTION
There are two kinds of data structures: vector-
based and raster-based, in the conventional
geographical information system. The storage of
data in a vector-based form is superior to the
storage of that in raster form for several
reasons. In the vector-based data structure the
information stored follows the original data and
the degree of approximation used in storing those
data is controllable; generally, one piece of
vector data may be used in representation of more
than one features (for instance, a wall may be
part of house and also the edge of a road), this
contrasts with raster data, where each pixel may
be shared by several features, whereas in a
raster data overlay, each pixel can represent
only one kind of feature; there are also problems
of resolution with raster data, a line of length
less than the pixel size being indistinguishable
from a point in the raster image; the vector data
are more compact than raster data, as the white
space of the map need not be represented; the
vector structure has the better topological
representation than the raster one.
A major disadvantage of vector data with respect
to raster data is that they do not contain
explicit two dimension relationships. To do an
operation such as ’ Finding all features near
this roadway in 5 kilometers’ can require a great
deal of work. To do the set operations
(intersection, union, subset) will be very
difficult in the vector data structure. The
raster data structure can just overcome the
disadvantages of the vector data structure. On
the other hand, the combination between remote
sensing and GIS is on the increase. In order to
do the geographical analysis by combining the
remote sensing data in raster-based form with
conventional GIS in the vector-based form, it is
necessary to convert the vector data in GIS into
raster data.
A multiple functions GIS is often required to do
convertion between vector data and raster data.
Thus, to find a data structure containing the
vector and raster data becomes increasingly
interesting. It can combine the advantages of the
vector and the raster data structures. Some
768
schemes for the integration of the two kinds of
data has been investigated (B. Sonne & B. Zillien
1990, M. Molenaar & D. Fritsch 1990).
In the geographic information system, a necessary
evolution is the integration of it with remote
sensing (Ehlers et al. 1989). There are three
kinds of integration strategies, which are
defined as "separate but equal", "seamless
integration", and "total integration". The total
integration is the highest level one and the
long-term goal. In this kind of system, a very
important thing is to design an unified data
structure to represent vector and raster data and
an integrated database to combine attribute,
geometry, DTM and RS.
| USER INTERFACE |
1
| Image / Carto /Database processing |
Unified data structure to represent vector and raster
Integrated database to combine GIS, DTM and RS
Figure 1 Total integration of GIS, DTM and RS
Currently, the quadtree has received considerable
attention as a data structure for GIS application
(Mark and Lauzon 1989, Yong Hongguang 1990,
Molenaar and Fritsch 1990). Quadtrees appear to
have many advantages for handling coherent
spatial data, and especially good for
geographical overlays.
This paper first introduces linear quadtree and
two-dimensional run-encoding. A strategy to
improve the representation precision of raster
and an indexing method based on linear quadtree
are presented in section 3. In the section 4, the
data structures of three typical features are
discussed. Finally section 5 draws some
conclusions.
2. LINEAR QUADTREE AND
TWO-DIMENSIONAL RUN-ENCODING
AG 4 $24 Q1 db 0. "8
O r0 0 >