r
a
QO ® 0 nn
30
ne OO:
woo oS 0
There are two methods for compacting raster data:
quadtree and run-length encoding. But here the
two-dimensional run-encoding is different from
the conventional run-length encoding. It is a
space-efficient form of linear quadtree, and
uses the same address keys as linear quadtree.
2.1 Linear Quadtree
The linear quadtree is a data structure which is
based on the regular decomposition of a square
into quadrants and sub-quadrants (see Mark 1989).
Such structure represents only leaf nodes, with
nodes identified by numeric keys. The form of
these keys permits topological and spatial
relations to be determined from the key values.
The data structure is conceptually then a list of
the leaf nodes in sequence by key. In general,
Morton keys are used as the numeric keys (Figure
2).
7| 22143 | h6| 47 [58 | 59 | 62 | 63
6| 40/41 | 54 | 45156 | 57 | 66/61
5| 35|35| a8| 39|58| 51| 5| 55
5| 32|33]| 36| 37 |n8 | n9 | 52] 53
3| 18| 11] 15| 15|26 | 27 | 38| 31
?| g|9]| 12] 13| 25] 25| 28| 29
1| 2| 83 18| 19| 22| 23
8| 8| 1 16 | 17] 28 21 |
9 1.2 3 a 5 6 7
Figure 2. Morton keys
There are several ways to obtain Morton keys,
while bit interleaving is the fast one (Gong
1991). Bit interleaving consists of taking the
bit representations of the row and the column
number, and forming a key consisting of
alternating bits from each number (Figure 3).
A ais mt ta go FA j
Pr /
Morton key-[ — ^ Toe|rp [o[slo] ifo]
Figure 3. Generation of Morton key
A "bottom-up" quadtree construction may be the
easier and faster than the "top-down"
construction (Gong 1991). Appropriate sets of
four mutually-adjacent cells can be examined and
combined into a node of level 1 if they all have
Linear quadtree
M1 | Value
; 2DHE
0 0 | M1 |Valu
4 D es
[ally
8 0 |
a 10/4
| 13| 0
i | 14] 1
14 | 1 |
Fig. 4a
15 1 Fig. 4c
Fig. 4b
Figure 4. Linear quadtree and 2DRE
769
the same value. Then, if four such level-1 nodes
have the same value, they are combined into a
level-2 node and so on (Figure 4b). This method
will lead to the same set of quadtree nodes as
the top-down approach.
2.2 Two-dimensional Run-encoding
Two-dimensional run-encoding (2DRE) is an
approach for the compact representation and
manipulation of linear quadtree (Lauzon 1983,
Mark and Lauzon 1989). A 2DRE file can be
constructed by run-encoding a linear quadtree,
that is, by combining runs of consecutive leaves
of the same value into a single data element. In
figure 4b, the three values of the former leaf
nodes are the same, and they are combined to form
a record (Figure 4c).
Two-dimensional run-encoding exhibits several
desirable features for a data structure for use
in geographical data processing; for example,
multiple attribute encoding, random access and
error recovery. This enhances the performance of
GIS procedures such as search and overlay, and
result in greater storage efficiency and
flexibility for processing of geographical
information than do other quadtree structures.
3. MULTI-GRIDS TECHNIQUE
The original cells of raster serve basic grids.
To improve the representation precision of
raster, some particular basic grids containing
points and lines are divided into many fine
grids, and to index the 2DRE file, basic grids
are grouped into rough grids as indexing blocks.
3.1 Fine-divided Grids for Improving
Representation Precision of Raster
A main disadvantage of raster structure is too
low accuracy. In this section, an approach by
using fine-dividing grids is presented. In figure
5, each basic grid is encoded in Morton key(M1).
In order to improve the geometric resolution of a
raster, those basic grids that contain points and
lines are redivided into 256*256 fine-grids,
which are also encoded in Morton key(M2). Thus, a
pair of coordinates x, y can be converted into
two Morton keys M1 and M2, and replaced by them.
In this way the represented precision of raster
data for points and lines will be increased by
about 256 times, however, the storage is
increased only by 2 bytes for each sampling point
and intersection point between a line and a basic
grid side.
Figure 5. Morton keys of basic grids
and fine-divided grids