ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001 
ISPRS, Vol.34,1 
20 
THREE LEVEL HIERARCHICAL QUALITATIVE DESCRIPTIONS FOR DIRECTIONS OF SPATIAL OBJECTS 
Han CAO 1 Jun CHEN 2 Daosheng Du 3 
( 1 Department of Computer Science, Shaanxi Normal University, 710062, Xi'an, P. R. China 
caohan2000@263.net 
2 National Geomatics Center of China,Zizhuyuan 100044,Beijing,P. R. China; 
chenjun@nsdi.gov.cn 
3 National Lab for Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, 
430070,Wuhan, P. R. China) 
Keywords geographic information systems, spatial relations, direction relations, topological relations, spatial reasoning 
Abstract 
Because of the complexity and uncertainty inherent in spatial space, the description and reasoning of spatial relation often use 
qualitative method in accordance with spatial cognition. Direction is a kind of important spatial relation; it is used to determine the 
direction of spatial object. Current models for cardinal directions often use quite crude approximations in the form of objects’ abstract 
generalization points or their minimum bounding rectangles. In this paper we propose a three level hierarchical qualitative direction 
description model of spatial objects. The first one is the direction description with point object as a reference, the second one with line 
object as a reference, and the third one with area object as a reference. In each level, direction models is again divided into two stages, 
the first one is the primary direction description and reasoning model, and the second one is the detailed description and reasoning 
model with topological relation between object and direction tile’s boundary and distance relation of objects as a refiner. So the cardinal 
directions description is enlarged. In our direction description, direction relation is converted into topological model and described in a 
unified topological model. And By integrating object’s distance relation in our detailed reasoning model, we can inference direction 
relation more accurately. 
1. INTRODUCTION 
Direction relation is a special class of spatial relations that 
describe order in space (e.g., south, east, etc). It is a common 
and important spatial relation that is used in many fields such as 
GIS, robot, navigation, and image interpretation. It is frequently 
used as a selection criteria in spatial queries or for assessing 
similarities for spatial scenes, and it is also widely used 
everywhere in our daily life when people communicate about 
geographic space and determine the direction of spatial object. 
Current models for directions often use quite crude 
approximations in the form of objects’ abstract generalization 
points (i.e., point-based model) or their minimum bounding 
rectangles (MBR). Point-based model require each object to be 
represented by a single point, such as the object’s geometric 
center (Peuquet, 1987; Frank, 1992, 1996); While MBR 
approach approximate objects by their minimum bounding 
rectangles, the direction between two objects are determined 
according to their MBR’s intersections, which often leads to 
erroneous query results (Papadias, 1995, 1997). Due to the 
approximations of these two models, they cannot consider 
object’ shapes, which is an important factor in determining 
direction. How to describe directions between extended spatial 
objects? The direction-relation matrix is an improved 
representation. It uses the projection-based method and 
partitions space around a reference object into nine direction 
tiles: north (N), northeast (NE), east (E), southeast (SE), south 
(S), southwest (SW), west (W), northwest (NW), and same (O). 
By recording into which direction tiles a target object falls, the 
direction from the reference object to a target is described 
(Goyal, 1999). It considers the exact representation of the target 
object with respect to the reference frame, but there still exist 
some direction relations that cannot be distinguished with 
direction-relation matrix. So the deep direction-relation matrix 
was proposed. It records additionally neighbor code for empty 
tiles to capture whether the tiles’ boundaries are empty or not. In 
deep direction-relation matrix an element captures intersections 
with the direction partition and the neighboring boundary 
partitions using nine bits. Bit 0 records the value of the 
intersection with the direction partition, while bits1-8 capture the 
intersections with the left, bottom-left, bottom, bottom-right, right, 
top-right, top, and top-left boundary parts respectively. Every bit 
Ihis work was supported by the National Natural Science Foundation of China under grant number: 69833010 
records a 0 if 
intersect with tl 
intersects with t 
powers of 2, fror 
bit numbers. It 
codes are arran 
direction-relatior 
direction-relatior 
method is not 
directions and tf 
necessary so cc 
and area, area ; 
point, point and 
not to record th 
codes at all. Be< 
and large-scale 
dimensional rep 
relations betwee 
of detail. 
In this paper w< 
direction descrip 
direction descrip 
one with line obj 
object as a refe 
divided into two 
description and 
detailed descript 
of objects and tc 
tile’s boundary a 
direction relatior 
representation ii 
projection-based 
and partition the 
present each dir 
open rectangles 
rectangle O bas 
direction tiles, v 
direction relation 
target object is 
located with refe 
a unified topolog 
tile’s boundary 
topological-relatii 
element. And b 
detailed reasoni 
more accurately. 
The rest of the p 
topological matr 
model. Section 
gives an example 
in direction reai 
direction relatior 
relation matrix tc 
and direction tile 
direction relation 
object. Section 
model with point 
comments. 
2. MODELING C 
USING 41 TOI 
For the directior 
object as a refe 
neutral zone mi 
objects A and B, 
B related to the 
object A and pari 
based on the ME 
as a spatial objec 
SE a , S a , SW a , W 
open objects mi 
partially defined,