The 9+-Intersection for Topological Relations between
a Directed Line Segment and a Region
Yohei Kurata1 and Max J. Egenhofer2
1

SFB/TR8 Spatial Cognition, Universität Bremen
Postfach 330 440, 28334 Bremen, Germany
ykurata@informatik.uni-bremen.de2

National Center for Geographic Information and Analysis, andDepartment of Spatial Information Science and Engineering,
University of Maine
Boardman Hall, Orono, ME 04469-5711, USA
max@spatial.maine.edu

Abstract. This paper develops a formal model of topological relations between
a directed line segment (DLine) and a region in a two-dimensional space. Suchmodel forms a foundation for characterizing movement patterns of an agent
with respect to a region. The DLine-region relations are captured by the 9intersection for line-region relations with further distinction of the line’s
boundary into two subparts (starting and ending points). This 9+-intersection
distinguishes 26 topological DLine-region relations. The relations’ conceptual
neighborhood graph takes the shape of a V-shaped tube, whose upper and lower
halves are isomorphic to the conceptual neighborhood graph of 19 topologicalline-region relations. The conceptual neighborhood graph of the 26 DLineregion relations is applied to the iconic representation of movement patterns
that satisfy a qualitative condition. By manipulating such iconic representations,the movement patterns that satisfy complex conditions are easily deduced.

1.

Introduction

Movement of an agent with respect to an area, such as entering, leaving, and goingthrough, is modeled as a spatial relation between a directed line segment and a region.
For instance, Figs. 1a and 1b illustrate two scenarios, going abroad from Germany
and being blocked by the cell wall, by the combinations of a directed line segment anda region with different spatial relations. Similarly, how a person goes in and out of aroom, a hazardous district, or any area of interest, is captured as a spatial relation
between a directed line segment and a region. Among several types of spatial
relations, topological relations are particularly important, because the topologicalrelations capture how the agent moves between the inside and outside and how theagent crosses or touches the border, which are fundamental information when people
conceptualize the movement. A model of such topological relations is, therefore,
potentially useful for the information systems that concern spatio-dynamic behaviors,such as security monitoring systems, smart homes, mobile robots, and routenavigation systems, where computers have to communicate qualitative information
about spatial movement patterns with human users.

(a)

(b)

Fig. 1. (a) A directed line segment starts from the inside and ends at the outside of a Germanyshaped region, illustrating going abroad from Germany. (b) A directed line segment starts fromthe outside, touches the boundary, and ends at the outside of a cell-shaped region, illustrating
being blocked by the region.

The goal of this paper is to develop a formal model of topological relations
between a directed line segment and a region embedded in a two-dimensional space.
Spatial relations between a directed line segment and a region, including topologicalrelations, have not systematically studied, even though there are many studies on
spatial relations between two directed line segments (Schlieder 1995; Clementini and
Di Felice 1998; Moratz et al. 2000; Kurata and Egenhofer 2006) and those between anon-directed line segment and a region (Egenhofer and Herring 1991; Mark andEgenhofer 1994). Our model, which stands on these existing studies, distinguishes a
set of topological relations between a directed line segment and a region in a formal
way. This relation set forms a foundation for characterizing the movement patterns ofan agent with respect to a region.
A non-branching, non-directed line segment is often called a line for short(Egenhofer and Herring (1991), Hadzilacos and Tryfona (1992), Clementini (1993),
Paradias (1995), Schlieder (1995), Clementini (1998), Moratz (2000)). In contrast,
this paper calls a non-branching directed line segment a DLine (Kurata and Egenhofer2006). Accordingly, a spatial relation between a DLine and a region is called a DLineregion relation.
The remainder of this paper is structured as follows: Section 2 reviews related
work on topological relations. Section 3 develops a formal model of topological
DLine-region relations. Based on this model Section 4 identifies the complete set of
DLine-region relations in a two-dimensional space, which are then schematized by aconceptual neighborhood graph in Section 5. Section 6 applies the conceptual
neighborhood graph to the iconic representation of the movement patterns that satisfy
certain qualitative conditions and demonstrates some benefits of this representation.
Finally, Section 7 concludes with a discussion of future problems.

2.

Related Work

Topological relations are spatial relations that are invariant under topologicaltransformations, such as translation, rotation, and scaling (Egenhofer 1989).
Topological relations are considered highly influential for people’s conceptualizationsof space (Lynch 1960; Egenhofer and Mark 1995b). Topological relations between

two spatial objects (i.e., points, lines, and regions) and their lower-dimensionalcounterparts, time intervals, have been studied extensively, starting from Allen’s(1983) thirteen interval relations. Based on the point-set topology (Alexandroff 1961),
the 4-intersection (Egenhofer and Franzosa 1991) formally captures topologicalrelations between two spatial objects through the geometric intersections of theobjects’ interiors and boundaries. The 9-intersection (Egenhofer and Herring 1991)
further considers the intersections with respect to the objects’ exteriors. In this model,
topological relations between two spatial objects A and B are characterized by the 9intersection matrix (Eqn. 1), where Ao , ∂A , and A − are A’s interior, boundary, andexterior while B o , ∂B , and B − are B’s interior, boundary, and exterior, respectively.
Based on the presence or absence of the 3×3 types of geometric intersections, the 9intersection distinguishes 19 topological relations between a line and a region in R2(Egenhofer and Herring 1991) and 43 topological relations between a complex line
and a complex region in R2 (Schneider and Behr 2006).
 A° ∩ B° A° ∩ ∂B A° ∩ B − 
M ( A, B ) =  ∂A ∩ B° ∂A ∩ ∂B ∂A ∩ B − 
 −
−
−
−
 A ∩ B° A ∩ ∂B A ∩ B (1)Another variation of the 4-intersection distinguishes explicitly the disconnectedsubparts of the interval’s boundary or DLine’s boundary (i.e., its starting point andending point), distinguishing 16 relations between two intervals in a temporal cycle(Hornsby et al. 1999) and 68 relations between two DLines in R2 (Kurata andEgenhofer 2006).
A set of spatial relations is typically schematized by a conceptual neighborhood
graph (Egenhofer and Al-Taha 1992; Freksa 1992a; Egenhofer and Mark 1995b;
Papadias et al. 1995; Schlieder 1995; Hornsby et al. 1999; Egenhofer 2005; Van deWeghe and De Maeyer 2005; Kurata and Egenhofer 2006). In this graph, each nodecorresponds to a spatial relation and two nodes are linked if the corresponding
relations are conceptual neighbors (Freksa 1992a). Different definitions of conceptual
neighbors lead to different graphs. For instance, Egenhofer and Mark (1995a) derived
two different conceptual neighborhood graphs of the 19 line-region relations based on
the smooth-transition (Freksa 1992a), which requires the possibility of continuoustransformation between the neighboring relations, and the minimum topologicaldistance (Egenhofer and Al-Taha 1992), which requires minimum difference between
the 9-intersection matrices of the neighboring relations.
The conceptual neighborhood graph has been applied to the analysis of spatial
predicates in natural languages (Mark and Egenhofer 1994; Shariff et al. 1998). These
linguistic studies show that line-region relations are often associated with a spatial
predicate that assumes a spatial movement along the line, such as going into. Thisimplies that people may recognize a line segment by imposing a virtual movement onit, despite the lack of the line’s direction, just like such verbal expressions as “themountain range goes from Mexico to Canada” evokes fictive motion (Talmy 1996).

3.

The 9+-intersection for Topological DLine-Region Relations

This paper considers DLines that may curve, but have no loop. Such DLines are
simple lines with direction, which is obtained through a continuous one-to-one
mapping from [0, 1] to R2 (Schneider and Behr 2006). In the point-set topology(Alexandroff 1961), a simple line is considered a set of an infinite number of linearlyaligned points, among which two distinctive end-points form the boundary and theother points form the interior. The exterior is the complement of the union of theboundary and the interior. Naturally, the interior, boundary, and exterior of a DLine
are pairwise disjoint and jointly exhaustive in R2. A DLine categorizes its two endpoints into a starting point and an ending point, which are also called a tail and ahead, respectively (Kurata and Egenhofer 2006).
A single-component region is a connected, homogeneously two-dimensional 2-cellin R2 (Schneider and Behr 2006). A single-component region does not have two or
more disconnected interiors, spikes, puncturing points, cuts, but may have holes. A
multi-component region is the union of multiple disjoint single-component regions. In
this paper, a region refers to a single-component region or a multi-component region.
The interior, boundary, and exterior of a region are pairwise disjoint and jointly
exhaustive in R2.
Let D and R be a DLine and a region, respectively. Uppercase letters are usedbecause they are considered point sets. In the 9-intersection (Egenhofer and Herring1991) their topological relation is captured through the geometric intersections of D’s
three topological parts (i.e., interior D° , boundary ∂D , and exterior D − ) and R’s
three topological parts (i.e., interior R° , boundary ∂R , and exterior R − ). These 3×3
types of intersections are concisely represented by the 9-intersection matrix in Eqn. 2.
 D° ∩ R° D° ∩ ∂R D° ∩ R − 
M (D, R ) =  ∂D ∩ R° ∂D ∩ ∂R ∂D ∩ R − 
 D − ∩ R° D − ∩ ∂R D − ∩ R − 



(2)

In our model, the intersections with respect to D’s boundary ∂D are further
distinguished into the intersections with respect to D’s starting point ∂ s D and thosewith respect to D’s ending point ∂ e D . Accordingly, the 9-intersection matrix in
Eqn. 2 is extended to the matrix in Eqn. 3, which is called the 9+-intersection matrixof the topological relation between the DLine D and the region R.
 D° ∩ R°
D° ∩ ∂R

D
R
∂
∩
°
∂




s
s D ∩ ∂R 
M + ( D, R ) =   ∂ e D ∩ R° ∂ e D ∩ ∂R 
 D − ∩ R°
D − ∩ ∂R


D° ∩ R − ∂ s D ∩ R −  − ∂ e D ∩ R  
D − ∩ R − (3)

In general, the 9+-intersection captures topological relation between two spatial
objects A and B through the geometric intersections of all subparts of A’s interior,boundary, and exterior and all subparts of B’s interior, boundary, and exterior. The
subparts of the interior, boundary, and exterior are determined by theirdisconnections. For instance, a single-component region with n holes has n + 1
boundary subparts and n + 1 exterior subparts. On the other hand, we consider that aconnected interior, boundary, or exterior consists of a single subpart. Accordingly,
Eqn. 4 is the general form of the 9+-intersection matrix, where Ao , ∂ i A , and A − are
i

i

oj

the i-th subpart of A’s interior, boundary, and exterior while B , ∂ j B , and B

−j

are

the j-th subpart of B’s interior, boundary, and exterior, respectively.
  Ao i ∩ B o j 
 


oj 
+

M ( A, B ) =  ∂ i A ∩ B   A −i ∩ B o j 
 

 

 Ao i ∩ ∂ B j ∂ A ∩ ∂ B 
j 
 i

 A −i ∩ ∂ B 
j 



 Ao i ∩ B − j  
 


−
∂ A ∩ B j  
i

 
 A −i ∩ B − j  

 

(4)

For instance, the DLine-region relation in Fig. 2b and the DLine-DLine relation in
Fig. 2c are captured by the 9+-intersection matrix shown in each figure.
For simplification, the 9+-intersection matrices are represented by icons (Fig. 2b2c). These icons are based on the iconic representation of the 9-intersection matrix byMark and Egenhofer (1994) (Fig. 2b). Each icon has 3×3 cells, which correspond tothe matrix’s 3×3 elements. Each cell is marked out if the corresponding element is
non-empty (¬φ). In our iconic representation, the icon’s columns and rows are
partitioned if their corresponding topological parts have multiple subparts. For
instance, when visualizing the 9+-intersection matrix of a DLine-region relation, theicon’s second row is partitioned (Fig. 2b), such that the upper and lower halvescorrespond to the intersections with respect to the DLine’s starting point and ending
point, respectively. Similarly, for a DLine-DLine relation, both the second row andthe second column of the icon are partitioned (Fig. 2c).

 ¬φ

 ¬φ
 ¬φ


φ
¬φ
¬φ

φ 

φ 
¬φ 

(a)

φ
 ¬φ

 ¬φ   φ   φ  ¬φ 
 ¬φ
¬φ


φ 

φ  
φ  
 
¬φ 

(b)

 φ

 φ  φ 
 ¬φ


[φ

¬φ ] ¬φ 
φ φ  ¬φ  
φ φ  ¬φ    [¬φ φ ] ¬φ (c)Fig. 2. Sample configurations of (a) a line and a region, (b) a DLine and a region, and (c) two
DLines, together with (a) the 9-intersection and (b-c) the 9+-intersection matrices which capture
their topological relations. The icons visualize the pattern of these matrices.

4.

Set of Topological DL-Region Relations

From the 19 topological line-region relations distinguished by the 9-intersection(Egenhofer and Herring 1991) we can derive a set of topological DLine-region
relations through assigning directions to the lines. Among the 19 relations, twelve

relations (Figs. 3a-l) are invariant to the line’s direction, because the line’s two endpoints are located at the same part of the region, whereas seven relations (Fig. 3m-s)
are variant to the line’s direction. From each direction-variant relation we can derive
two DLine-region relations through assigning different directions to the line. As aresult, 12 + 7 × 2 = 26 topological DLine-region relations are obtained (Fig. 4).

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

(o)

(p)

(q)

(r)

(s)

Fig. 3. Sample configurations of 19 topological line-region relations (Egenhofer and Herring1991), together with the patterns of the corresponding 9-intersection matrices.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m1)

(n1)

(o1)

(p1)

(q1)

(r1)

(s1)

(m2)

(n2)

(o2)

(p2)

(q2)

(r2)

(s2)

Fig. 4. Sample configurations of 26 topological DLine-region relations, together with thepatterns of the corresponding 9+-intersection matrices.

These 26 relations correspond to different patterns of the 9+-intersection matrices(Fig. 4). This indicates that the 9+-intersection distinguishes at least 26 DLine-region
relations. Actually, there is no other DLine-region relation that the 9+-intersection
distinguishes. This is proven with the aid of the constraints on the 9+-intersection
matrix of DLine-region relations (Eqns. 6-14), which are derived systematically fromthe constraints on the 9-intersection matrix of line-region relations (Egenhofer andHerring 1991) considering the distinction of lines’ two end-points.
• D’s exterior and R’s exterior intersect with each other.
D − ∩ R − = ¬φ(5)

• If D’s interior is a subset of R’s closure then D’s both end-points must be a subsetof R’s closure as well.
D° ∩ R − = φ→ ∂s D ∩ R− = φ∧ ∂eD ∩ R− = φ(6)• D’s each end-point intersects at least one part of R.

{∃P, Q ∈ R°, ∂R, R −} ∂ D ∩ P = ¬ φ ∧ ∂ D ∩ Q = ¬φ
s

(7)

e

• If D’s interior and R’s interior are disjoint then neither of D’s end-points canintersect with R’s interior.
D° ∩ R° = φ→ ∂ s D ∩ R° = φ∧ ∂ e D ∩ R° = φ(8)• If D’s interior intersects with both R’s interior and exterior, then it must alsointersect with R’s boundary.
D ° ∩ R° = ¬φ

∧ D° ∩ R − = ¬φ

→ D° ∩ ∂R = ¬φ(9)

• D’s each end-point intersects one part of R.

{}{} ∂ D ∩ P = ¬φ ∧ ∂ D ∩ Q = φ∃ P ∈ {R°, ∂R, R }, ∀Q ∈ {R°, ∂R, R }\ P ∂ D ∩ P = ¬φ ∧ ∂ D ∩ Q = φ∃ P1 ∈ R°, ∂R, R − , ∀Q1 ∈ R°, ∂R, R − \ P1
−

2

2

−

2

1

s

e

1

s

2

e

(10)

2

• R’s interior always intersects with D’s exterior.
D − ∩ R ° = ¬φ(11)

• R’s boundary always intersects with D’s exterior.
D − ∩ ∂R = ¬φ(12)

• D’s interior must intersects with at least one part of R.

{∃P ∈ R°, ∂R, R −} D ° ∩ P = ¬φ

(13)

The 9+-intersection matrix may have 212 = 4096 patterns, since it has 12 elementswith two possible values (empty or non-empty). Among these 4096 patterns,
however, only 26 patterns satisfy the constraints in Eqns. 6-14. These 26 patterns areexactly same as the matrix patterns in Fig. 4. This indicates that the 26 patterns in
Fig. 4 are the complete set of topological DLine-region relations distinguished by the
9+-intersection.
In Fig. 4, the geometric configuration assigned to each DLine-region relation ismerely an example. It is possible that other configurations, which are topologicallydifferent from the illustrated example, may also correspond to the same topologicalrelation (Fig. 5). In this sense, the 26 topological relations categorize DLine-region
configurations based on some topological characteristics (the presence or absence of
12 types of intersections), but not on their topological equivalence.
To describe the topological detail of DLine-region configurations, this paper also
introduces an alternative notation by three-tuples, which trace the positions of avirtual agent moving along the DLine (Fig. 5a-c). The first and third element in each
three-tuple represents the agent’s starting and ending positions, while the second
element represents the sequence of the agent’s intermediate positions. I, B, E
represent the positions in the region’s interior, boundary, and exterior, respectively.

(a) (B, IBEBI, B)(b) (B, IBE, B)(c) (B, EBI, I)

Fig. 5. Three configurations that correspond to the same DLine-region relation in Fig. 4i.

With such three-tuple notations, Table 1 summarizes all DLine-region
configurations that belong to the 26 DLine-region relations. This table indicates that
17 DLine-region relations correspond to multiple configurations (i.e., they havemultiple topological interpretations).
Table 1. Sets of DLine-region configurations that belong to each DLine-region relations in Fig.
4. Each set of configurations is described using the three-tuple notation, where [X] is an empty
or X, Y* is an arbitrary number of Y, and Z|W is Z or W, but not both.
Direction-Invariant Relations
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
(j)
(k)
(l)

(I, I, I)(I, IB[IB]*I, I)(I, IB[IB|EB]*E[BI|BE]*BI, I)(E, EB[IB|EB]*I[BI|BE]*BE, E)(E, EB[EB]*E,E)(E, E, E)(B, I, B)(B, [B]IB[IB]*, B), (B, [BI]*BI[B], B)(B, [B][IB|EB]*(IBE|EBI)[BI|BE]*[B], B)(B, [B]EB[EB]*, B), (B, [BE]*BE[B], B)(B, E, B)(B, B, B)

Direction-Variant Relations
(m1)
(m2)
(n1)
(n2)
(o1)
(o2)
(p1)
(p2)
(q1)
(q2)
(r1)
(r2)
(s1)
(s2)

(I, I, B)(B, I, I)(I, IB[IB]*[I], B)(B, [I][BI]*BI, I)(I, IB[IB|EB]*E[BI|BE]*[B], B)(B, [B][IB|EB]*E[BI|EI]*BI, I)(I, IB[IB|EB]*E, E)(E, E[BI|BE]*BI, I)(B, [B][IB|EB]*I[BI|BE]*BE, E)(E, EB[IB|EB]*I[BI|BE]*[B], B)(B, [E][BE]*BE, E)(E, EB[EB]*[E], B)(B, E, E)(E, E, B)5.

Conceptual Neighborhood Graphs for DL-Region Relations

We schematize the 26 DLine-region relations graphically, using a conceptual
neighborhood graph (Freksa 1992a). In this graph, each node corresponds to a spatial
relation, and two nodes are linked if the corresponding relations are similar relations
called conceptual neighbors. This paper considers that two DLine-region relations areneighbors if one relation can be derived from another relation by moving either
starting point, interior, or ending point of the DLine while keeping the presence orabsence of the intersections with respect to the others (Fig. 6a). This transformation isa subset of the smooth transitions (Egenhofer and Mark 1995a), which also includes
the transformation by moving one part of the DLine without keeping the presence orabsence of the intersections with respect to the others (Fig. 6b).
Æ

Æ

(a)

(b)

Fig. 6. Smooth transitions between two DLine-region relations, derived by moving the DLine’s
ending point from the region’s boundary to (a) interior and (b) exterior, respectively. In (b), themovement of the DLine’s ending point generates the intersection of the DLine’s interior andthe region’s boundary.

We identified 46 pairs of conceptual neighbors among the 26 DLine-region
relations. By linking these neighbors, a conceptual neighborhood graph of the 26
topological DLine-region relations is developed (Fig. 7). The graph is non-planar anddrawn three-dimensionally on a V-shaped tube, such that links do not cross. Clearly,
this graph schematizes DLine-region relations based on their similarity.

Fig. 7. A conceptual neighborhood graph of the 26 topological DLine-regions.

Fig. 8 shows the upper and lower halves of the conceptual neighborhood graph inFig. 7. The relations with gray background in Fig. 8 correspond to the relations
located at the top and bottom of the V-shaped tube in Fig. 7, respectively.
Interestingly, the two subgraphs in Fig. 8 are isomorphic to the conceptual
neighborhood graph of the 19 line-region relations (Fig. 9). Actually, the twosubgraphs in Fig. 8 can be derived from the graph in Fig. 9 through assigning
directions to the line in each relation. Since the line-region relations with graybackground in Fig. 9 are variant to the line’s direction, different directions assigned to
the lines yield different conceptual neighborhood graphs.

Fig. 8. Upper and lower halves of the conceptual neighborhood graph in Fig. 7. The relations
with gray background correspond to the relation located at the top and bottom of the graph inFig. 7, respectively.

Fig. 9. The conceptual neighborhood graph of the 19 line-region relations, derived under thesame definition of conceptual neighbors. The relations with gray background are variant to theline’s direction.

The conceptual neighborhood graph of the 26 DLine-Region relations in Fig. 7 has
the following unique properties:• Pairs of vertically facing relations are derived from each other by exchanging
upper and lower halves of the second row of the 9+-intersection matrices(essentially reversing the DLine’s direction).
• Pairs of relations located symmetrically across the front-to-back line penetrating
the V-tube’s center are derived from each other by flipping the 9+-intersection
matrices horizontally (essentially reversing the region’s interior and exterior).
• The number of different elements in the 9+-intersection matrix, called the
topological distance (Egenhofer and Al-Taha 1992), is 1 between the horizontal
neighbors and 2 between the other neighbors. This implies that the conceptual
neighborhood graph in Fig. 7 cannot be obtained through linking all pairs ofrelations with minimum topological distance.

6.

Modeling Movement Patterns with Respect to a Region

Topological DLine-region relations categorize the patterns of an agent’s movementwith respect to a region. For instance, the DLine-region relation in Fig. 4p1
corresponds to movement patterns that start from the region’s interior, cross theregion’s boundary at least once, and end at the region’s exterior. Such categorization
is useful, because it highlights the topological characteristic of movement whichhighly influences people’s conceptualization of movement, while abstracts lessimportant detail. Another benefit of such categorization is that movement patterns thatsatisfy a certain qualitative condition, whose number is typically infinite, are captured
by a finite set of DLine-region relations. For instance, a set of movement patterns thatsatisfy the qualitative condition, starting from the region’s interior, is represented by
the set of seven DLine-region relations (Figs. 4a, 4b, 4c, 4m1, 4n1, 4o1, and 4p1). Suchsummarized expression makes it easy for computers to process people’scharacterization of movement patterns.
To visually represent a set of DLine-region relations, we introduce iconic
representations (Figs. 10a-h), which superimpose the two subgraphs in Fig. 8. The setof marked nodes indicates the set of DLine-region relations. Some nodes are
partitioned, such that their upper and lower halves correspond to the different
relations in the upper and lower subgraphs at the same position (i.e., the relations
located at the top and bottom of the V-shaped tube in Fig. 7). For instance, the icon in
Fig. 10a shows the set of seven relations in Fig. 4a, 4b, 4c, 4m1, 4n1, 4o1, and 4p1,
which corresponds to the previous condition, starting from the region’s interior. Herewe consider ten basic qualitative conditions: (a) starting from interior, (b) startingfrom boundary, (c) starting from exterior, (d) crossing boundary, (d) ending at
interior, (e) ending at boundary, (f) ending at exterior, and (g) crossing/touchingboundary. The icons in Figs. 10a-h show the sets of DLine-region relations that
represent all movement patterns satisfying each of these conditions.

starting from interior

starting from boundary

starting from exteriorcrossing boundary(I,*,*)(B,*,*)(E,*,*)(*,*(IBE|EBI)*,*)

(a)

(b)

(c)

(d)

ending at interior

ending at boundary

ending at exteriorcrossing/touchingboundary(*, *, I)(*, *, B)(*, *, E)(*,*B*,*)

(e)

(f)

(g)

(h)

Fig. 10. Marked nodes in each icon indicate the set of DLine-region relations that represent all
movement patterns satisfying each qualitative condition. Each condition is also described by
the three-tuple notation (Section 4) with a wildcard symbol *.

The ten icons in Fig. 10a-h have the following unique properties:• DLine-region relations that correspond to each qualitative condition form aconnected subgraph. This is because the movement patterns that satisfy eachcondition has certain topological similarity, while the conceptual neighborhood
graph schematizes the DLine-region relations based on their topologicalsimilarities.
• A non-directed condition, such as crossing boundary, yields a symmetric icon
(Figs. 10d and 10h).
• A pair of conditions, interchangeable by exchanging starting from and ending atyield a pair of icons with reversed partitions (Figs. 10a and 10e, Figs. 10b and 10f,
and Figs. 10c and 10g).
• A pair of conditions, interchangeable by exchanging interior and exterior, yields apair of horizontally flipped icons with reversed partitions (Figs. 10a and 10c, andFigs. 10e and 10g).
A merit of this iconic representation is that the set of movement patterns thatsatisfy a complex condition is derived through simple manipulations on the icons. For
instance, Fig. 11a shows the intersection of the icons in Figs. 10a and 10g, whose
result indicates that only one DLine-region relation corresponds to the movement
patterns satisfying starting from interior and end at exterior (Fig. 4p1). Similarly,
Figs. 11b-d show the union of two icons, the difference of two icons, and thecomplement of an icon, whose result correspond to the movement patterns satisfying
starting from inside or ending at outside, starting from inside but not ending at
outside, and not starting from inside, respectively. Such computation is particularly
useful for integrating the qualitative characterizations of a movement pattern reported
by multiple observers (e.g., different sensors).

∩

∪

=

(b) starting from inside or ending at exterior(a) starting from inside and ending at exterior

\

=

¬

=

(c) starting from inside but not ending at exterior=(d) not starting from inside

Fig. 11. Set operations on the icons for representing a set of DLine-region relations.

The iconic representation is also applicable to the classification of the region’sboundary. For instance, the icon in Fig. 12a corresponds to an inapproachable
boundary, like a prison’s wall, which people normally cannot cross or even stand on.
Conversely, the icon in Fig. 12e corresponds to a freely crossable boundary, like theborder between a city square and roads around the square. In this way, the regions’boundaries can be graphically classified in terms of the movement patterns they
accept (Fig. 12).

inapproachable

non-crossable

outward crossable

inward crossable

fully crossable

(a)

(b)

(c)

(d)

(e)

Fig. 12. Five types of regions’ boundaries in terms of the movement patterns they accept.

7.

Conclusion and Future Problems

This paper distinguished 26 topological DLine-region relations based on the 9+intersection. A conceptual neighborhood graph of these 26 relations took the shape ofa V-shaped tube except one node. The 26 DLine-region relations qualitatively
categorize the patterns of an agent’s movement with respect to a region. It is a future
question how to apply this model to the analysis of motional expressions in natural
language (i.e., how people describes a movement), as well as the computer systems
that communicate the information on spatial movement with human users, hopefully
in a qualitative way.
In the current model, we can tell whether an agent crosses or touches the boundary,but cannot describe how many times the agent crosses or touches the boundary, or
whether the agent crosses or touches the boundary instantly or stepwise. Also, we
cannot describe, if the DLine and the region are disjoint, whether the agent goes leftof, right of, toward, or against the region, even though people often emphasize suchinformation when describing movement. It is, therefore, a future question to extend
the current model in a meaningful way, incorporating other topological properties ofDLine-region relations, such as the number and dimension (point or interval) ofintersections, as well as non-topological properties such as distance and direction
between the DLine and the region.

This paper did not discuss the composition of two DLine-region relations (Freksa
1992b; Egenhofer 1994). We can consider two types of compositions: thecomposition of two DLine-regions relations with a common DLine (i.e., all possible
relations between two regions R1 and R2 when the relation between a DLine D and R1
and the relation between D and R2 are known) or that with a common region (i.e., allpossible relations between two DLines D1 and D2 when the relation between D1 and aregion R and the relation between D2 and R are known). The compositions of all pairsof 26 DLine-region relations yield two 26×26 composition tables, which will enrich
the foundation of qualitative spatial reasoning.
The 9+-intersection introduced in this paper provides a flexible and systematic
framework for capturing topological relations between various spatial objects,
including DLines, branching lines, regions with holes, and multi-component regions.
The application of the 9+-intersections for other spatial relations is highly potential forenriching the formal model of space configurations and the foundation of qualitative
spatial reasoning.

Acknowledgments
This work was partially supported by the National Geospatial-Intelligence Agency in
USA under grant number NMA201-01-1-2003 and NMA401-02-1-2009.

References
Alexandroff, P. (1961) Elementary Concepts of Topology. Dover, Mineola, NY.
Clementini, E. and Di Felice, P. (1998) Topological Invariants for Lines. IEEE Transactions on
Knowledge and Data Engineering, 10(1): 38-54.
Clementini, E., Di Felice, P., and van Oosterom, P. (1993) A Small Set of Formal Topological
Relationships Suitable for End-User Interaction. in: Abel, D. and Ooi, B. C. (Eds.) 3rd
International Symposium on Advances in Spatial Databases, Singapore, Lecture Notes in
Computer Science, 692, 277-295, Springer.
Egenhofer, M. (1989) A Formal Definition of Binary Topological Relationships. in: Litwin, W.
and Schek, H.-J. (Eds.) 3rd International Conference on Foundations of Data Organization
and Algorithms (FODO), Paris, France, Lecture Notes in Computer Science, 367, 457-472,
Springer.
Egenhofer, M. (1994) Deriving the Composition of Binary Topological Relations. Journal of
Visual Languages and Computing, 5(2): 133-149.
Egenhofer, M. (2005) Spherical Topological Relations. Journal on Data Semantics III: 25-49.
Egenhofer, M. and Al-Taha, K. (1992) Reasoning About Gradual Changes of Topological
Relationships. in: Frank, A., Campari, I., and Formentini, U. (Eds.) Theories and methods ofspatio-temporal reasoning in geographic space, Pisa, Italy, Lecture Notes in Computer
Science, 639, 196-219, Springer.
Egenhofer, M. and Franzosa, R. (1991) Point-Set Topological Spatial Relations. International
Journal of Geographical Information Systems, 5(2): 161-174.
Egenhofer, M. and Herring, J. (1991) Categorizing Binary Topological Relationships between
Regions, Lines and Points in Geographic Databases. in: Egenhofer, M., Herring, J., Smith,T., and Park, K. (Eds.) A Framework for the Definitions of Topological Relationships andan Algebraic Approach to Spatial Reasoning within This Framework, NCGIA Technical
Reports 91-7. National Center for Geographic Information and Analysis, Santa Barbara, CA.
Egenhofer, M. and Mark, D. (1995a) Modeling Conceptual Neighborhoods of TopologicalLine-Region Relations. International Journal of Geographical Information Systems, 9(5):555-565.
Egenhofer, M. and Mark, D. (1995b) Naive Geography. in: Frank, A. and Kuhn, W. (Eds.)
COSIT '95, Semmering, Austria, Lecture Notes in Computer Science, 988, 1-15, Springer.
Freksa, C. (1992a) Temporal Reasoning Based on Semi-Intervals. Artificial Intelligence, 54:
199-227.
Freksa, C. (1992b) Using Orientation Information for Qualitative Spatial Reasoning. in: Frank,
A., Campari, I., and Formentini, U. (Eds.) The International Conference GIS - From Space
to Territory: Theories and Methods of Spatio-Temporal Reasoning in Geographic Space,
New York, NY, Lecture Notes in Computer Science, 639, 162-178, Springer.
Hadzilacos, T. and Tryfona, N. (1992) Model for Expressing Topological Integrity Constraints
in Geographic Databases. in: Frank, A., Campari, I., and Formentini, U. (Eds.) The
International Conference GIS—From Space to Territory: Theories and Methods of SpatioTemporal Reasoning in Geographic Space, New York, NY, Lecture Notes in Computer
Science, 639, 252-268, Springer.
Hornsby, K., Egenhofer, M., and Hayes, P. (1999) Modeling Cyclic Change. in: Chen, P.,
Embley, D., Kouloumdjian, J., Liddle, S., and Roddick, J. (Eds.) Advances in Conceptual
Modeling, Paris, France, Lecture Notes in Computer Science, 1227, 98-109, Springer.
Kurata, Y. and Egenhofer, M. (2006) The Head-Body-Tail Intersection for Spatial Relation
between Directed Line Segments. in: GIScience2006, Münster, Germany, Lecture Notes in
Computer Science, 4197, 269-286, Springer.
Kuratowski, K. (1930) Sur Le Probleme Des Courbes Gauches En Topologie. Fundamenta
Mathematicae, 16: 271-283.
Lynch, K. (1960) The Image of the City. MIT Press, Cambridge, MA.
Mark, D. and Egenhofer, M. (1994) Modeling Spatial Relations between Lines and Regions:
Combining Formal Mathematical Models and Human Subjects Testing. Cartography andGeographical Information Systems, 21(3): 195-212.
Moratz, R., Renz, J., and Wolter, D. (2000) Qualitative Spatial Reasoning About Line
Segments. in: Horn, W. (Ed.) 14th European Conference on Artificial Intelligence, Berlin,
Germany, 234-238, IOS Press.
Papadias, D., Theodoridis, Y., Sellis, T., and Egenhofer, M. (1995) Topological Relations in
the World of Minimum Bounding Rectangles: A Study with R-Trees. in: Carey, M. andSchneider, D. (Eds.), SIGMOD RECORD, 24(2), 92-103.
Schlieder, C. (1995) Reasoning About Ordering. in: Frank, A. and Kuhn, W. (Eds.) COSIT '95,
Lecture Notes in Computer Science, 988, 341-349, Springer.
Schneider, M. and Behr, T. (2006) Topological Relationships between Complex Spatial
Objects. ACM Transactions on Database Systems, 31(1): 39-81.
Shariff, A., Egenhofer, M., and Mark, D. (1998) Natural-Language Spatial Relations between
Linear and Areal Objects: The Topology and Metric of English-Language Terms.
International Journal of Geographical Information Science, 12(3): 215-246.
Talmy, L. (1996) Fictive Motion in Language and ''Ception''. in: Bloom, P., Peterson, M.,
Nadel, L., and Garrett, M. (Eds.) Language and Space. MIT Press, Cambridge, MA, 211276.
Van de Weghe, N. and De Maeyer, P. (2005) Conceptual Neighbourhood Diagrams for
Representing Moving Objects. in: 2nd International Workshop on Conceptual Modeling for
Geographic Information Systems (CoMoGIS), Klagenfurt, Austria, Lecture Notes in
Computer Science, 3770, 228-238, Springer.