US LS 
nem ii 
MÀ — — LÁ LL I d 
Table 5 
Indexing the Vector Data by Quadtree 
Qing—huai Gao, Qing—yun Shi, Min—de Cheng 
Information Science Center, Peking University, 
100871, Beijing, P. R. China 
Abstract 
In the study of GIS/LIS, two kinds of data structure 
are studied, raster data structure and vector data struc- 
ture. It is proved by experience and theory that the vector 
data has a higher compression rate and a well —organized 
logical structure ( that is, an object is represented by its 
boundary polygons , and a polygon is a series of vectors 
V1, 02, ...,Uw , Where v; and s, have a same end 
point), and some basic image operations , such as scal- 
ing, rotating, calculating the area and perimeter , can be 
easily done on the vector data structure. But the spatial 
organization of the vector data is very loose , which leads 
to low efficiency when querying the objects near or at a 
given position. So, a good spatial index is needed to speed 
up the response of the system. 
In this paper, it is suggested that the vector data can be 
organized by a quadtree — like index structure — — — — 
QO (quadtree of objects). The definition of QO , the al- 
gorithm for creating QO of a image, the algorithms of op- 
eration on QO are given. By analysing the querying ef- 
fectiveness of QO, it is shown that the time consume of 
queries on the vector with QO — index is much more 
smaller than that on the "pure" vector data. 
Keywords ; GIS/LIS, Raster, Spatial , Data Base 
$1 Introduction 
The main task of the researcher on GIS is to speed up 
the implementation of variant queries on the data in some 
compressed form . In ordinary, the atom query of a GIS 
can be categorized into two classes ; one called attribute— 
based query, and the other called position—based query. 
The sophisticated queries are all composed by a series of 
atom queries, which makes, in the view of users, the 
GIS manage the spatial data (image data) and the at- 
tribute data consistently and flexibly. Obviously , the po- 
sition—based query has a more important position in the 
studies of GIS than the attribute— based query , and the 
speed of this kind query indicates the standard of a GIS. 
The class of the position—based query contains: to find 
the objects near or at a given position, to open a window 
83 
on a image , to judge the geometric relation of two objects 
( for example , whether one object contains or intersects 
with the other object) , to query the objects which have 
some special geometric relation with a given object, etc. 
In the study of GIS/LIS , two kinds of data structure 
are studied; raster data structure and vector data struc- 
ture. It is proved by experience and theory that the vector 
data has a higher compression rate and a well —organized 
logical structure ( that is, an object is represented by its 
boundary polygons , and a polygon is a series of vectors 
Dis Vas +. 
point), and some basic image operations , such as scal- 
ing, rotating, calculating the area and perimeter , can be 
easily done on the vector data structure. But the spatial 
organization of the vector data is very loose , which leads 
to low efficiency when querying the objects near or at a 
given position. So, a good spatial index is needed to speed 
up the response of the system. 
In this paper, it is suggested that the vector data can be 
organized by a quadtree —like index structure — — — — 
— — QO (quadtree of objects ). In a node of QO , a list 
of objects is stored. A object is stored in the node which 
correspondences to the smallest quad block that covers this 
UN , Where v; and v4; have a same end 
object. 
In the second section , the definition of QO and the al- 
gorithm for creating QO of a image , the algorithms of 
operation on QO are given. In the third section , the time 
consume of queries in the class of position — based query 
are analysed . In the last section a short conclusion is 
given. 
$2 The definition and operation on QO 
Organizing objects according their 2D position is the 
main idea of QO. 
2.1 The definition of QO 
Suppose that the image f is a function on region R with 
size 2* x 2* . Let set SO = {01,02,. . . yon} be the objects 
on the image , and R(o;) represents the region correspon- 
dences to oi . 
A QO is a tree whose every node has 4 or no sons, that