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,