Toward Heterogeneous Cardinal Direction Calculus
Yohei Kurata and Hui Shi
SFB/TR 8 Spatial Cognition, Universität Bremen
Postfach 330 440, 28334 Bremen, Germany{ykurata,shi}@informatik.uni-bremen.de

Abstract. Cardinal direction relations are binary spatial relations determined
under an extrinsically-defined direction system (e.g., north of). We already havepoint-based and region-based cardinal direction calculi, but for the relations
between other combinations of objects we have only a model. We are,therefore, developing heterogeneous cardinal direction calculus, which allows
reasoning on cardinal direction relations without regard to object types. In thisinitial report, we reformulate the definition of cardinal direction relations,
identify the sets of relations between various pairs of objects, and develop the
methods for deriving upper approximation of converse and composition.
Keywords: cardinal direction relations, heterogeneous spatial calculi, converse,
composition

1.

Introduction

Imagine that you are at the peak of Mt. Fuji. You can see Fuji-gawa river flowing
from the northwest to the southwest, and also the city of Tokyo spreading out in thenorth-east. Then, what can you say about the relation between Fuji-gawa and Tokyo?
This question concerns cardinal direction relations [1], which are determined underan extrinsically-defined direction system. In addition to compass directions like northand south, these relations are applicable to capture such relations as above and left-of
in shelves and storages. Cardinal direction calculi are the mechanisms that realize
spatial reasoning on such cardinal direction relations. So far cardinal direction calculi
have been developed for the relations between points [1, 2] and those between regions[3-6]. In our example question, however, Mt. Fuji’s peak, Fuji-gawa, and Tokyo aremodeled as a point, a line, and a region, respectively. Accordingly, their arrangement
may not be deduced properly in the previous calculi, even though we can treat themas regions and conduct spatial reasoning at the cost of reliability.
Actually, most spatial calculi have targeted spatial relations between single-type
objects. Kurata [7], therefore, insisted on the necessity of heterogeneous spatial
calculi, which allow spatial reasoning beyond the difference of object types. As a firststep, he developed 9-intersection calculi that realize topology-based reasoning on
multi-type objects [7]. Following this effort, we are currently developing
heterogeneous cardinal relation calculus, since cardinal direction relations are one of
the most basic sets of spatial relations. This article is the first report of this work.

2 Yohei Kurata and Hui Shi

The remainder of this paper is structured as follows: Section 2 reviews existing
work on cardinal direction relations. Section 3 reformulates the model of cardinal
direction relations, under which Section 4 identifies the sets of cardinal direction
relations between various pairs of objects. Section 5 introduces the methods forderiving upper approximation of converse and composition of these directional
relations. Finally, Section 6 concludes the discussion.
In this paper, we consider a 2D Euclidean spacewith a coordinate system inwhich the x- and y-axes are aligned with the north and east, respectively. Simple
regions and non-branching line segments are called regions and lines for short, andlines parallel to x-axis, those parallel to y-axis, and other lines are called HLines,
VLines, and GLines (or horizontal, vertical, and generic lines), respectively.

2.

Related WorkIn general, directional relations concern the orientation of the target object (referent)with respect to the reference object (relatum). Frank [1] introduced cone-based andprojection-based frames for distinguishing directional relations between two points.
The frames are placed such that the relatum comes to the center of the frames. In a
spatio-linguistic viewpoint, these frames are sorts of extrinsic frames of spatialreference whose direction is fixed in the environment [8]. Frank [1] assessed theconverse and composition of his directional relations and identified the presence ofsome indeterminate compositions (for instance, the composition of north-of andsouth-of yields north-of, south-of, and equal). Together with the converse andcomposition operations, Frank’s model forms (Point-Based) Cardinal Direction
Calculus. Ligozat [2] applied this calculus to constraint-based reasoning, identifying
maximum tractable subsets of the relations. Star Calculus [9] generalizes cardinal
direction calculus, such that it captures directional relations in arbitrary granularity.
Papadias and Sellis [3] studied the cardinal direction relations between two regions
making use of their minimum bounding rectangles (MBRs). Regions are mapped tointervals on each axis. Thus, by applying MBRs, 13×13 directional relations weredistinguished, as well as the converse and composition of those relations were
determined based on Allen’s [10] interval calculus,.
Goyal and Egenhofer [4] introduced a directional-relation matrix, whose 3×3
elements correspond to the intersections between the referent and the 3×3 tiles. The
tiles are determined by four lines l1: x = infx(B), l2: x = supx(B), l3: y = infy(B), andl4: y = supy(B), where infx/y(B) and supx/y(B) are the greatest lower bound and the least
upper bound of the projection of the relatum B on x/y-axis. This approach isapplicable to any pair of objects, but depending on the relatum’s shape some tiles may
be collapsed to a line or a point. In the simplest approach, directional relations are
distinguished by the presence or absence of the 3×3 referent-tile intersections. Basedon this framework, calculus aspects of region-based cardinal directions were studied
in [5, 6]. Cicerone and Felice [6] identified all realizable pairs of the cardinal
directional relation between A and B and that between B and A. Skiadopoulos andKoubrakis [5] identified a method for deriving (weak) compositions of cardinal
direction relations between two regions.

Toward Heterogeneous Cardinal Direction Calculus 33.

Our Model of Cardinal Direction Relations

We introduce four iconic representations of spatial arrangements of two objects,
namely CD pattern, CD+ pattern, PCD pattern, and PCD+ pattern (Fig. 1a). The CD
pattern captures how the referent A intersects with the 3×3 tiles determined by the
relatum B, namely NWB, NCB, NEB, MWB, MCB, MEB, SWB, SCB, and SEB. The CD
pattern has 3×3 black-and-white cells, each of which is marked if the corresponding
element in

is non-empty. This follows the direction

matrix in [4], but in our model the tiles are defined as a set of jointly-exclusive andpairwise-disjoint partitions of the space (by this we avoid strange situations where apoint-like referent intersects with two tiles at the same time). First, two sets of JEPD
partitions, {WB, CB, EB} and {SB, MB, NB}, are defined as Eqs. 1-2. Then, the tiles are. Notedefined as the intersections of these two partition sets, likethat NCB, MWB, MCB, MEB, and SCB may be collapsed depending on the type of therelatum (Fig. 2).
2

,

|

2

,

inf
|

2

,

inf

2

,

CD pattern

[

,

|
|

sup

2

(1)

sup

2

(2)

][

PCD pattern

,

90°

90°

CD+ pattern][

PCD + pattern

,

(a)

]

[

,

]

(b)

SC

MW MC MC

SW

SC

(a)

EW

MC EW
MC

SE

MW

NW

NC

NC

NE

NC

NC

NC

NE

ME

MW MC MC MC ME

SE

SW

MC
SW

SC

(b)

SC

(c)

SC

MC

NW

SC

MC

MW

NE

MC EW
MC

MC

NC

MW MC MC

SC

NW

NC

Fig. 1. (a) Four types of iconic representations of a spatial arrangement featuring cardinal
directions and (b) converse between these four representations

SE

NW

NC

MW

MC

NE
EW

MW

MC

ME

MW

MC

EW

SW

SC

SE

(d)

Fig. 2. Tiles determined by the relatum, which is (a) a simple region or a GLine, (b) a point, (c)a HLine, and (d) a VLine, respectively

The CD+ pattern is a refinement of the CD pattern, which captures how the referent
intersects with n×m fields. The CD+ pattern has n×m black-and-white cells, among
which the ith left and jth bottom cell is marked if A intersects with the ith left and jthbottom field. The fields are determined by four lines l1: x = infx(B), l2: x = supx(B),l3: y = infy(B), and l4: y = supy(B), such that not only 2D blocks separated by theselines, but also 1D boundaries between two blocks and 0D boundary points between
four blocks are all considered independent fields. Naturally, 5×5, 3×3, 5×3, and 3×5

4 Yohei Kurata and Hui Shi

fields are identified when the relatum is a region or a GLine, a point, a HLine, and a
VLine, respectively.
The PCD pattern consists of two sub-patterns, called PCDx and PCDy patterns.
They have three black-and-white cells, each marked if the corresponding element in[A∩WB A∩CB A∩EB] and [A∩SB A∩MB A∩NB] is non-empty, respectively.
Essentially, PCDx/y patterns are the projection of the CD pattern onto x-/y-axis.
Finally, the PCD+ pattern is a counterpart of PCD pattern for the CD+ pattern.
In this paper, directional relations refer to the spatial arrangements distinguishedby CD patterns, while fine-grained directional relations refer to the spatial
arrangements distinguished by the CD+ patterns. We primarily use CD patterns
because they allow the unified representation of directional relations by 3×3 binary
patterns without regard to object types. Another practical reason is that CD+ patterns
may distinguish an overwhelming number of spatial arrangements (up to 25×5).

4.

Identification of Directional Relations

Even though the CD pattern icon distinguishes 23×3 patterns, not all of them are
effective as the representation of directional relations (i.e., some patterns have nogeometric instance). We, therefore, identify the sets of all effective CD patterns when
the referent and relatum are points, H/V/GLines, simple regions, and their
combinations (in total 5×5 cases). Suppose A be the referent and B be the relatum thatdefines n×m fields. First, we consider 2n×m CD+ patterns, from which we remove
geometrically-impossible CD+ patterns by the following constraints:• if A is a point, it intersects with exactly one field;• if A is a H/V/GLine, it intersects with at least one non-0D field, and all fields withwhich A intersects must be connected; in addition,• if A is an HLine/VLine, all fields with which A intersects must be
horizontally/vertically aligned;• if A is a GLine, letting C be the set of connected components formed by non-0D
fields with which A intersects, and P be the set of 0D fields with which A
intersects and which connect to more than one connected component in C, there
are at most two connected components in C that are connected to exactly one
field in P (otherwise A is branching; compare Figs. 3a-3a'); and• if A is a simple region, it intersects with at least one 2D field, and all fields withwhich A intersects must be connected, even if all 0D fields are excluded (otherwise
A has a spike or disconnected interior; compare Figs. 3b-3b').
Then, the remaining CD+ patterns are converted to CD patterns as shown in Fig. 1b.
We confirmed that these CD patterns are all effective (i.e., we succeeded to draw an
instance for every CD pattern). Thus, these CD patterns represent the complete set of
directional relations. For instance, we identified 222 directional region-region
relations (four more than the relations listed in [6], due to the slightly different
definition of relations). Table 1 shows the number of the directional relations we haveidentified for 5×5 cases, while Table 2 summarizes their patterns.

Toward Heterogeneous Cardinal Direction Calculus 5

C1

C1

P

C2 C

C2

P

C 2 C3

3

C2

(a)

C2

C2

C4

(a')

(b)

(b')

+

Fig. 3. Examples of CD patterns when the referent is a simple or non-simple object
Table 1. Numbers of cardinal direction relations distinguished by our framework

Referent

Point
HLine
VLine
GLine
Region

Point
9
15
15
254
106

Relatum
VLine
9
15
18
300
146

HLine
9
18
15
300
146

GLine
9
18
18
308
222

Region
9
18
18
308
222

Table 2. Cardinal direction relations distinguished by our framework (icons with “×4”/“×2”
also represent the CD patterns derived by rotating {90,180,270}/180 degree)

Referent

GLine

HLine VLine Point

Point

Relatum
HLine

RegionGLine orRegion

×4
×4

×2

×4

×2

×2

×4

×2

×2

×4

any

90°

×2

5.

VLine

×4

×4

Projection-Based Spatial Inference

Given the directional relation between two regions A and B as
, what are possible
relations between B and A? Similarly, given the relation between a GLine C and apoint D and that between D and a region E asand, respectively, what are
possible relations between C and E? Figs. 4a-b show one possible solution for eachquestion, but what else? The answers to these questions are derived by converse andcomposition operations. In general, given the relation r1 between the objects O1 andO2 and r2 between O2 and O3, the converse of r1 returns the relation(s) that may holdbetween O2 and O1, while the (weak) composition of r1 and r2 returns the relation(s)that may hold between O1 and O3. The converse and composition operations arefundamentals of qualitative spatial calculi [11].

6 Yohei Kurata and Hui Shi

We introduce methods for deriving upper approximations of converse andcomposition of cardinal directional relations. These methods project spatial objects
onto x- and y-axes, conduct converse/composition on each axis, and synthesize theresults to derive the candidates for the converse/composition. The basic idea comesfrom MBR-based spatial inference in [3], but our target is not limited to regions.
By projection onto an axis each object is mapped to an interval or a point. First,
suppose that the referent A and the relatum B correspond to two intervals iA and iB on
the x-axis. Then, the PCD+x-pattern for A and B corresponds to the interval relation
between iA and iB. Naturally, the converse of this PCD+x-pattern is determined by theconverse of this interval relation (Fig. 5a). Similarly, if A and B correspond to twointervals on the y-axis, the converse of their PCD+y-pattern is determined by theconverse of the corresponding interval relation. This mapping from PCD+x/y patterns totheir converse is coarsened based on the correspondence between PCD+x/y and PCDx/ypatterns in Fig. 6. Fig. 7a summarizes the result. By combining the converse of a
PCDx pattern and that of a PCDy pattern determined by Fig. 7a, we can determine theconverse of a PCD pattern. Making use of this projection-based converse, thecandidates for the converse of the given directional relation can be derived. For
instance, imagine that A and B are regions whose directional relation is(Fig. 4a).
The PCD pattern for A and B is [ , ]. The converse of this PCD pattern is { [ , ] ,
[
,
], [
,
], [
,
]}, since’s converse is { , } and’s converse is { ,} (Fig. 7a). From these four PCD patterns, we can derive ten CD patterns { , ,, , , , , , , }, but
is removed because it does not represent any
directional region-region relation (Table 2). As a result, we obtain nine directional
region-region relations as the candidates for the converse of the given relation.
When both the referent and relatum correspond to a point on x/y axis, we canderive the mapping from PCDx/y patterns to their converse (Fig. 7b), making use of thecorrespondence between PCD+x/y patterns and point-order relations (Fig. 5b).
Similarly, when the referent and relatum correspond to a point and an interval, we canderive the mapping from PCDx/y patterns to their converse (Figs. 7c-d), making use of
the correspondence between PCD+x/y patterns and point-interval relations (Fig. 5c).
In a similar way, we consider projection-based compositions. Suppose that threeobjects A, B, and C correspond to the intervals iA, iB, and iC on the x-axis. Then, thePCD+x pattern representing A-B relation and that representing B-C relation correspondto the interval relation between iA and iB and that between iB and iC, respectively.
Naturally, the composition of these two PCD+x patterns is determined by thecomposition of these interval relations. Thus, from Allen’s composition table [10], we
can derive the composition table of PCD+x/y patterns. By coarsening this table basedon the correspondence between PCD+x/y and PCDx/y patterns (Fig. 6), the composition
table of PCDx/y patterns was developed (Table 3). We skip the detail, but this table canbe used even when the referent, relatum, or both correspond to points (instead ofregions), taking the realizability of PCDx/y patterns into account (see * in Table 3).
Consequently, using Table 3, we can determine the compositions of two PCD
patterns, from which the candidates for the composition of the given directional
relations can be derived. For instance, the projection-based composition of a GLinepoint relation
and a point-region relation(Fig. 4b) is derived from thecomposition ofandand that ofand—the result is { , , } (thiscorresponds to the Fuji-gawa–Tokyo relation in Section 1).

Toward Heterogeneous Cardinal Direction Calculus 7AC

dir(A,B) =dir(C,D) =E

dir(D,E) =D

dir(B,A) =B

dir(C,E) =

(a)

(b)

Fig. 4. Examples of projection-based converse and composition

before

meet

after

met-bybeforeoverlap overlapped-by

duringcontains

after

finishes

started-by

startsafter

started-by

duringfinishes

after

equal

equal
startsbeforecontains finished-by

beforefinished-by

(a)

(b)

(c)

PCD+x/yFig. 5. Mapping frompatterns to their converse, when the referent and relatum
correspond to (a) two intervals, (b) two points, and (c) a point and an interval, respectively
PDC+x /PDC+y

PDCx /PDCy

Fig. 6. Correspondence between PCD+x/y and PCDx/y patterns when the PCD+x/y patterns havehigher granularity (otherwise PCD+x/y and PCDx/y patterns are equivalent)

(a)

(b)

(c)

(d)

Fig. 7. Converse of PCDx/y patterns when the referent and relatum correspond to (a) twointervals, (b) two points (c) a point and an interval, and (d) an interval and a point on an axis
Table 3. Composition table of PCDx/y patterns

*

,
, and
in
the composition results
are removed when
they correspond topoint-point or pointinterval relations, andis removed when
they correspond tointerval-point relations

8 Yohei Kurata and Hui Shi

6.

Conclusions and Future WorkIn this paper, we developed the basis of heterogeneous cardinal relation calculus,
which aims at the support of direction-featured spatial reasoning without regard to
object types. We captured cardinal direction relations with bitmap-like icons with 3×3
cells and identified sets of relations between points, lines, regions, and their
combinations. Then, we developed methods for deriving upper approximation of
converse and composition of these relations. Actually, these approximations agreewith the precise converse and composition when the source relations are convex (i.e.,
the icon’s black cells form a single rectangle); otherwise, the results of projectionbased converse or composition may include unnecessary patterns and, therefore, othermethods are necessary for deriving more precise converse and composition. Thesemethods, as well as the proof of the above fact, will be reported in our next report.
Acknowledgment
This work is supported by DFG (Deutsche Forschungsgemeinschaft) through the
Collaborative Research Center SFB/TR 8 Spatial Cognition—Strategic Project“Spatial Calculi for Heterogeneous Objects” and Project I3-[SharC]

References
1. Frank, A.: Qualitative Spatial Reasoning about Cardinal Directions. In: Mark, D., White, D.
(eds.): AutoCarto 10. ACSM/ASPRS (1990)
2. Ligozat, G.: Reasoning about Cardinal Directions. Journal of Visual Language andComputing 9(1), 23-44 (1998)
3. Papadias, D., Sellis, T.: Qualitative Representation of Spatial Knowledge in TwoDimensional Space. VLDB Journal 3(4), 479-516 (1994)
4. Goyal, R., Egenhofer, M.: Consistent Queries over Cardinal Directions across Different
Levels of Detail. In: Tjoa, A.M., Wagner, R., Al-Zobaidie, A. (eds.): 11th International
Workshop on Database and Expert Systems Applications, pp. 876-880 (2000)
5. Skiadopoulos, S., Koubarakis, M.: Composing Cardinal Direction Relations. Artificial
Intelligence 152(2), 143-171 (2004)
6. Cicerone, S., Felice, P.: Cardinal Directions between Spatial Objects: The PairwiseConsistency Problem. Information Science 164(1-4), 165-188 (2004)
7. Kurata, Y.: 9-Intersection Calculi for Spatial Reasoning on the Topological Relations
between Multi-Domain Objects. In: Guesgen, H., Bhatt, M. (eds.): IJCAI Workshop on
Spatial and Temporal Reasoning. (2009)
8. Levinson, S.: Frame of Reference. In: Space in Language and Cognition: Explorations in
Cognitive Diversity. Cambridge University Press, Cambridge, UK (2003) 24-61
9. Renz, J., Mitra, D.: Qualitative Direction Calculi with Arbitrary Granularity. In: Zhang, C.,
Guesgen, H., Yeap, W. (eds.): PRICAI 2004, LNAI 3157, pp. 65-74. Springer, (2004)
10.Allen, J.: Maintaining Knowledge about Temporal Intervals. Communications of the ACM
26(11), 832-843 (1983)
11.Ligozat, G., Renz, J.: What Is a Qualitative Calculus? A General Framework. In: Zhang, C.,
Guesgen, H., Yeap, W. (eds.): PRICAI 2004, LNAI 3157, pp. 53-64. Springer, (2004)