ISPRS, Vol.34, Part 2W2, “Dynamic and Multi-Dimensional GIS”, Bangkok, May 23-25, 2001
21
riAL OBJECTS 1
¡rsity,
ing
I relation often use
id to determine the
of objects' abstract
qualitative direction
econd one with line
ded into two stages,
3tion and reasoning
ner. So the cardinal
and described in a
inference direction
iy cannot consider
:tor in determining
3n extended spatial
is an improved
ssed method and
into nine direction
utheast (SE), south
JW), and same (O).
get object falls, the
target is described
station of the target
but there still exist
distinguished with
ction-relation matrix
bor code for empty
are empty or not. In
ptures intersections
ghboring boundary
the value of the
bits1-8 capture the
i, bottom-right, right,
spectively. Every bit
mber: 69833010
records a 0 if the corresponding boundary part does not
intersect with the target object and a 1 if the target object
intersects with the boundary. Bits have values multiple by the
powers of 2, from 2° to 2 8 . The neighbor code is the sum of nine
bit numbers. It ranges from 0 to 510. Nine of these neighbor
codes are arranged in the same topological organization as the
direction-relation matrix. This structure yields the deep
direction-relation matrix (Goyal, 2000). However neighbor codes
method is not cognitively plausible to describe detailed
directions and the computation process of neighbor codes is not
necessary so complicated between all six pair of objects (area
and area, area and line, area and point, line and line, line and
point, point and point). Such as point and point object, we need
not to record the tiles' boundary by calculating their neighbor
codes at all. Because of the different need in small-scale space
and large-scale space, spatial objects may change their
dimensional representation from a polygon to a point; direction
relations between two objects need to describe at different levels
of detail.
infinite. If the object is finite and its boundary is well defined
within the data window, then this is a closed object (Shekhar,
1999). We can use open object to model the directions between
extended objects by converting the calculation of directional
relationships to the calculation of topological relationships
between objects.
In order to test the direction of object B related to object A, we
use 4I matrix to test into which direction tile B falls (Equ.1-9).
The union of all the nine tiles overlapping with target object B is
the direction region where B is located with reference object A.
In fact, the eight open rectangles can be transformed into close
ones according to the maximum and minimum X, Y coordinates
of target object, as shown in Fig. 1a.
ôNW A Ç\dB ôNW a Ç]B°
NW/V\dB NW/[\B°
(1)
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 distance relation
of objects and topological relation between object and direction
tile’s boundary as a refiner. In our primary direction description,
direction relation is converted into topological model; such a
representation is based on n intersection model. First we use
projection-based method to obtain the MBR of reference object
and partition the space around it into nine direction tiles. We
present each direction tile as a spatial object, then we get eight
open rectangles N, NE, E, SE, S, SW, W, NW, and one close
rectangle O based on the MBR of reference object. In each
direction tiles, we use 4I topological matrix to calculate the
direction relation. The union of all the nine tiles that overlap with
target object is the direction region where the target object is
located with reference object. So we can describe direction with
a unified topological model. For the object meeting with direction
tiles boundary, we use extended detailed boundary
topological-relation matrixes to record every sixteen-boundary
element. And by integrating object’s distance relation in our
detailed reasoning model, we can inference direction relation
more accurately.
The rest of the paper is organized as follows: Section 2 uses 4I
topological matrix to define our primary direction description
model. Section 3 discusses direction relation inference and
gives an example to show the effect of object's distance relation
in direction reasoning. In order to distinguish more different
direction relations, Section 4 presents our detailed direction
relation matrix to record the topological relation between object
and direction tile’s boundary. Section 5 outlines a framework for
direction relation description using line object as a reference
object. Section 6 describes the direction relation description
model with point object as a reference. Section 7 concludes with
comments.
2. MODELING DIRECTION BETWEEN EXTENDED OBJECTS
USING 4I TOPOLOGICAL MATRIX
R H A, B
dN A V\ 5B 3N a Ç\B°
N/ f] dB N a °C\B°
(2)
dNE A f]3B 8NE a D B"
NE À ° D dB NE/f}B°
(3)
R Wa,B
dW A Ç\dB 3W A Ç]B°
w/^dB w/ïïb°
(4)
^A.B
dO A f) dB
0/ f]8B
dO A (T B°
o A °CiB°
(5)
R Ea,B
8E a Ç)dB
E/PiÔB
dE A fl B°
E A °CiB°
(6)
ôsw a r\ôB ôsw a n b"
sw/ftdB sw A °f]B°
dS A f] dB dS A C\B°
S A °C\dB S/C\B°
(7)
(8)
r se a ,b
dSE A fl dB dSE A f)B°
SE/ f| dB SE/f]B°
(9)
nw a
Na^|
Ëlf A
nw a
N A
ne a
•
nw a
N A
ne a
W A
if > '
No a |
W A
wêq ;
E A
W A
ss
Ea
05 ,
>
S A
SE a
SW A
S A
se a
swv
^S A
se a
(a) (b) (c)
For the direction relations between spatial objects with area
object as a reference, we use projection-based models with
neutral zone modeling direction relation (Fig 1). Given two
objects A and B, we want to decide the direction of target object
B related to the reference object A. First we obtain the MBR of
object A and partition the plane around it into nine direction tiles
based on the MBR of object A. We represent each direction tile
as a spatial object. Eight of nine direction tiles (NW A , N A , NE A , E A ,
SE a , S a , SW a , W a ) are open rectangles. 0 A is close object. Here
open objects mean those geometries whose boundaries are
partially defined, or extending beyond the data window, or
Fig. 1 the 8-directions model with area object as reference
From the 4I topological matrix, we have tree rules:
Rule 1. For one direction region, If there are no none-empty
intersections or only ana is not empty in the 4I matrix, then the
target object is not in this direction region.
For example, B is not in the direction region NW A (Fig 1a).
Rule 2. For one direction region, If the intersection of ° na