9+-Intersection Calculi for Spatial Reasoning on
the Topological Relations between Heterogeneous Objects
We developed
p a series of qualitativeqspatialpcalculi that targetsg
topological relations between mixed-type objects
Q.What are topological relations?
A. They are spatial relations thatconcern how two spatial objects
connect and/or overlap

Q.Why do we consider mixed-type objects?
A. Existing qualitative spatial calculi target
only single-type object relations

e.g., What relations are possible between A and C?

goes intoi t+
A is in BB and C overlap

Region Connection
Calculus (RCC)

Q. Can we solve such problems
if there are many objects?
A. By preparing the following elements, we
can solve the problems computationally:

Such topological relations are
distinguished systematicallyby 9+-intersection [1, 2]

What is 9+-Intersection?

’s’sinterior
boundary
exterior

exterior

in a 2D Euclidian space R2, for instance, we candistinguish[2]:80 line-line relations

djPP
eqLL

eq'LL

djLL

mtsx/sxLL

mtxe/xeLL

mtse/seLL

es/es

mtix/ixLL

mtxi/xiLL

mtsi/siLLmtie/ieLL

mtii/iiLL

mtdjPL

djLP

bobxPL bbbxLP

boxbPL bbxbLP

inPL

djPR

djRP

boPR

inPL

bbRP

LL

ctLP

3 point-region relations
ctLP

mtex/xsLL mtxs/exLL mtii/xxLL mtxx/iiLL

mtix/xiLL mtxi/ixLL

mtei/isLL mtis/eiLL

mtix/xxLL mtxx/ixLL mtxi/xxLL mtxx/ixLL mtsx/siLL mtsi/sxLL

mtex/isLL mtis/exLL

mtxe/ieLL mtie/xeLL mtxs/eiLL mtei/xsLL mtix/iiLL mtii/ixLL

mtxi/iiLL mtii/xiLL

26 line-region relations
djLR

djRL

mtxb+LR mtxb+RL

mtbxLR mtbxRL

mtxxLR mtxxRL

mtxbLR mtxbRL

mtbbLR mtbbRL

mtbx+LR mtbx+RL

ovxbLR ovxbRL

ovixLR ovixRL

ovxiLR ovxiRL

ovbiLR ovbiRL

ovibLR ovibRL

ovxxLR ovxxRLovbbLR ovbbRL

oviiLR oviiRL

boLR

cbbiLR cvbiRLcbibLR cvibRL

cbbb+LR cvbb+RL

cbib+LR cvib+RL

cbiiLR

cbbbLR cvbbRL

cbbi+LR cvbi+RL

inLRbbRL

cviiRL

ovxx/xxLLovsx/sxLL

ovxe/xeLL

ovse/seLL

oves/esLL

ovix/ixLL

ovxi/xiLL

ovsi/siLL

ovie/ieLL

ovii/iiLL

mtbb+LR mtbb+RL

ovbxLR ovbxRL

ctRL

ovex/xsLL ovxs/exLL ovix/xxLL ovxx/ixLL ovxi/xxLL ovxx/ixLL

ovii/xxLL ovxx/iiLL

ovsx/siLL ovsi/sxLL

ovex/isLL ovis/exLL ovix/xiLL ovxi/ixLL

ovxe/ieLL ovie/xeLL

ovxs/eiLL ovei/xsLL

ovei/isLL ovis/eiLL

ovix/iiLL ovii/ixLL

ovxi/iiLL ovii/xiLL

cbie/xeLL cvxe/ieLLcbsi/sxLL cvsx/siLL

cbis/exLL cvex/isLL

cbei/xsLL cvxs/eiLL

8 region-region relations
inLL

eqRR

cbRR

djRR

mtRR

cvRR

inRR

ovRR

ctRR

ctLL

ovxiLR ovxiRL

I‐90EComposition
U d thUnder
the 9+-intersection,i tti
compositions of two arbitrary
relations can be determined
systematically by only fourconstraints (see our paper)

Urban
12̵

Integration
In order to conduct spatial reasoning within
the existing framework of QSC, we consider
a generalized object domain D* and generalizedbase relations * between two objects in D*e.g., in the case of a 2D Euclidian space R2
D* = R ∪ L ∪ P⋃ 1, 2∈, ,1 22

∪

P6P8

This is an advantageof 9+-intersection
over 9-intersection

Let the composition table of relations inand relations inbe CT ̵2 3
1 2 3̵

∗I‐95S

P3 I‐495S

Dowwntown’sInterior
start point
end point

2 point-line relations

gyFor instance,, let’s consider Boson’s highway
network, which consists of I-90, I-95, I-93,and I-495.
Imagine we have driven I-90, I-95, and I-495
and have the following knowledge:

Let the list of converse of all
relations in
be CL ̵1 2
1 2̵’seqPP

An Example Application
Our spatial knowledge grows by everyday
experience. From such imperfect knowledge,
what spatial model we can build?

Let D1 and D2 be two object domains(e.g., R: regions, L: Lines, and P: Points)
andbe a set of topological relations
1 2̵
between an object in D1 and an object in D2,
both embedded in a space S
Converse
Converse of a relation in
1 2̵
is a relation in
who has2 1̵a transposed icon pattern.

Double Cross
Calculus

Dipole CalculusStar Calculus

9+-Intersection Calculus

9+-intersection [1, 2] is a spatial model by which
topological relations between two objects are
distinguished by the black-and-white patterns oficons with 3×3 or more cells
This model is a refined version of the famous
9-intersection model[3]Cardinal Direction
Calculus

But in geographic contexts, we often deal
with mixture of regions, lines, and points- an object domain D- a set of base relations between two objects in D
- a list of converse relations for- a composition table for2 point-point relations

Tokyo Metropolitan University
ykurata@tmu.ac.jp∗Then, the list of converse pairs in * is derived
by concatenating all relevant lists of converserelations CL ̵
D1, D2 ∈ R,R L,
L P and adding
1 2
an item that indicates the converse of eq* is eq*
Similarly, the composition table for * is derived
by adjoining all relevant composition tables
D1, D2, D3 ∈ R, L, P and adding aCT ̵
1 2 3̵
line/column for eq*
Now that we have prepared all of the above
four elements of ordinary QSC, we can conduct
qualitative spatial reasoning computationally byan existing QSC solver (say, SparQ[4])Conclusions• We have identified the composition tables of 9+-intersection-based relations using simple rules• We developed a series of qualitative spatial calculi based on the 9+-intersection, making use of
the existing framework of ordinary binary spatial calculi• The developed calculi allow more finer reasoning than the previous 9-intersection calculi[5]I‐495S

I‐95S

P5P6

P7

I‐93S
I‐495S

I‐495S

P1UrbanoverlaplYohei Kurata

Urban

iin

Q.What are qualitative spatial calculi?
A. They are computational mechanisms
for qualitative spatial reasoning

TOKYO METROPOLITAN UNIVERSITY

I‐93S

P1

I‐95S

P2

I‐93S

P3

I‐90E

P4

I‐95S

I‐90E
I‐93S

P4

From this knowledge,
can we build a unique modelof the highway network, justlike the actual one?

P1

P2
P5
P3

P6

I‐90E P
8P7P4

If we use the 9+-intersection
intersection calculi,
calculi we candeduce that the I-93 goes through bothBoston’s downtown
and urban areaand there is no other solution
Similarly, when we consider the imaginary
drive on three of the four highways, we candeduce the possible relations between
unvisited highway and two areas as follows:
Unvisited
Candidates for the relation pairhighway x [(x, downtown ), (x, urban)]
I-90E
I-93S

[ovxiLR, ovxiLR][ovxxLR, ovxxLR]

I-95S[djLR, ovxxLR] [mtxxLR, ovxxLR][ovxxLR, ovxxLR]

I-495S[djLR, djLR] [djLR, mtxxLR][djLR, ovxxLR] [mtxxLR, mtxxLR][mtxxLR, ovxxLR] [ovxxLR, ovxxLR]

References[1] Yohei Kurata and Max J. Egenhofer (2007) The 9+-Intersection for Topological Relations between
a Directed Line Segment and a Region. in: 1st Workshop on Behaviour Monitoring andInterpretation (BMI'07), Universität Bremen TZI Technical Report 42, 62-76.
[2] Kurata, Y. (2008) The 9+-Intersection: A Universal Framework for Modeling Topological Relations.
In: GIScience 2008, LNCS 5266, 181-198[3] Max J. Egenhofer and John R. Herring (1991) Categorizing Binary Topological Relationshipsbetween Regions, Lines and Points in Geographic Databases. In: NCGIA Technical Reports 91-7
[4] Jan Oliver Wallgrün, Lutz Frommberger, Diedrich Wolter, Frank Dylla, and Christian Freksa(2006) Qualitative Spatial Representation and Reasoning in the SparQ-Toolbox. In: Spatial
Cognition V. LNAI 4387.
[5] Yohei Kurata (2009) 9-Intersection Calculi for Spatial Reasoning on the Topological Relations
between Multi-Domain Objects. In: IJCAI Workshop on Spatial and Temporal Reasoning.