Refining Topological Relations between Regions
Considering Their Shapes
Roland Billen 1 and Yohei Kurata 2
1

Geomatics Unit, University of Liege, 17 Allée du 6-Août,B-4000 Liege, Belgium
rbillen@ulg.ac.be2

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

Abstract. Topological relations are sometimes insufficient for differentiating
spatial configurations of two objects with critical difference in their connection
styles. In this paper, we present the projective 9+-intersection model, whichrefines topological relations into projective binary relations by considering
projective properties of the objects’ shapes. This is indeed a reformulation ofprojective concepts of the Dimensional Model within the framework of the 9+intersection. Thirty projective binary relations are established between two
regions in R2, one of which has a multi-order boundary (region+mob). These
relations are identified computationally by applying to all theoretical relations
the existing constraints for topological region-region relations and seven new
specific constraints. After defining the concept of continuous neighbours
between two projective binary relations, a conceptual neighbourhood graph ofthe 30 projective region+mob-region relations is developed.

1.

Introduction

Topological relations for categorising spatial configurations of objects have beenstudied extensively over the last two decades [1-15]. Especially, binary topologicalrelations between spatial objects (point, line, regions and, to a smaller extend, bodies)
are well-studied and frequently used. Several models of binary topological relations
have been proposed and some of them have been adopted as OGC standards [16].
Other types of relations have also been introduced [17-20] and lots of work has still to
be done to tackle the diversity and insufficiency of the representation of spatial
relations. Indeed, even binary topological relations can be pushed further; for instanceby considering dimension and number of topological intersections [7, 8]. However,
the existing approaches cannot differentiate some spatial configurations of two
objects, despite of their significant qualitative difference. For instance, Fig. 1a showsa set of spatial configurations between two bodies, which are all categorised into thesame topological relation “touch” with a two-dimensional intersection. Similarly,
Fig. 1b shows another set of configurations between a body and a line, which are allcategorised into the same topological relation “touch” with a zero-dimensional

2

Roland Billen and Yohei Kurata

intersection. Distinction of such configurations is useful to perform moresophisticated spatial analyses, to perform more specific consistency checks, and soon. Such distinction based on the difference of connection styles seems particularly
important when considering 3D large-scale applications; for example whencategorising the spatial configurations of indoor objects (object arrangements in aroom) or relationships between the components of objects (between the walls and roofof a building, between electronic components inside a computer, etc.). In such cases,
considering topology only is not enough. Such applications go beyond “traditional”
2D GIS domain and could be seen closer to 3D CAD world. However, with 3D urban
modelling and 3D urban GIS development, we strongly believe that the types ofspatial relationships currently modelled must be extended.
Categorising further binary spatial relations implies to consider anothermathematical framework. For instance, projective geometry has been adopted tocategorise spatial relations in a model called the Dimensional Model (DM) [21, 22].
The motivation behind DM was to identify spatial relations between 3D objects more
precisely. Although formally defined, DM suffers from a lack of standardisation andstrong algebra associated with the model. DM’s formal definition of spatial relations
differs from the standard definition of spatial relations (e.g., the 9-intersection [2] andRCC-calculus [3]), even though DM may distinguish the same set of relations as the
9-intersection and RCC-calculus do. Thus, it has been a hard step to adopt DM in
addition to other models. Furthermore, neither conceptual neighbourhood graphs nor
composition tables are currently available for DM relations. This is an obstacle toperforming qualitative spatial reasoning.
A recent development in the modelling methods of topological relations, the 9+intersection [15] has given an opportunity to reformulate DM projective concepts
within a well-standardized framework of topological relations. The new combinedmodel keeps all descriptive power of DM projective concepts and takes advantage ofexisting development in the 9-intersection [2] and the 9+-intersection [15], especiallyin terms of qualitative spatial reasoning.
In this article, we propose a new model of refined topological relations based on
projective properties of objects’ shapes. First, we explain fundamental concepts ofDM, such as the order of points of a spatial object (Section 2). Then, we reformulate
DM with the 9+-intersection (Section 3). We then identify all possible relations
between two regions embedded in R², one of which has a “projective” shape (Section
4). Then, we schematize these relations into a conceptual neighbourhood graph,
whose analysis reveals some interesting properties of the relations (Section 5). And
finally we conclude (Section 6).

(a)

(b)

Fig. 1. Topological equivalence of (a) spatial configurations of two bodies with twodimensional intersection and (b) those of a body and a line in zero-dimensional intersection.

Refining Topological Relations between Regions Considering Their Shapes

2.

3

Dimensional Model (DM)The Dimensional Model (DM) was formally defined according to affine geometry[21, 22]. It was shown later that its definition satisfies projective geometry rules [23].
This model introduced the concept of “order of each point of a convex set” to conduct
the segmentation of spatial objects. New binary spatial relations between two spatial
objects, called dimensional relations, were defined based on the connectivity of theobjects’ dimensional elements.
2.1.

Order of Point of a Spatial Object

Every point of a closed convex set has an order [24]. Let C be a convex set in ddimensional Euclidean space Rd. The order of a point x in C, denoted o(x,C), is thedimension of the intersection of all the supporting hyperplanes of C passing throughx. If there is no supporting hyperplane containing x, then x is of order d. One canprove that the set of points of order d correspond exactly to the points of C’s interior
in the sense of Euclidean topology (not equivalent to the interior in point-set
topology, as we will see later). For example, suppose a triangle in R². In R², an
infinite number of supporting hyperplanes (in this case, lines) can pass through avertex of the triangle (Fig. 2a). Their intersection is a subspace of dimension 0 (apoint corresponding to the given vertex). Thus, this vertex is of order 0. If we take apoint being located on the edge of the triangle, there is only one supporting
hyperplane. This subspace is of dimension 1 and thus the order of this point is 1 (likeall points of the edge other than the two vertices). Lastly, for an interior point of thetriangle, there is no supporting hyperplane and thus the order of this interior point is 2
(the dimension of the embedding space). Other examples (a drop-shaped region in R²
and a line segment in R²) are presented in Figs. 2b-c.

(a)

(b)

(c)

Fig. 2. Order of points of various spatial objects in R².

This order concept has been extended from convex sets to topological manifolds
with boundary1, such that we can consider a wide variety of spatial objects. The
1

Let n be a positive integer. We denote by Rn+ the subset of tuples (α1,...,αn) with
αn ≥ 0. A subset A of Rd is a topological n-manifold with boundary if each pointx∈A has neighbourhood which is homeomorphic to an open subset of Rn+.

4

Roland Billen and Yohei Kurata

definition of the extended concept is beyond the scope of this article; see [21] or [22]for a comprehensive development.
Strictly speaking, the object’s “interior” concept in Euclidean topology, on which
the original DM stands, is different from that in point-set topology [25], on which the
9-intersection stands. This difference appears when considering an n-dimensional
object embedded in Rd (n < d). In this case, Euclidean topology considers that theobject has only a boundary (Fig. 3a), while point-set topology considers that theobject consists of a boundary (the set of two endpoints) and an interior (Fig. 3b).

(a)

(b)

Fig. 3. Differences between Euclidean topology and point-set topology for n-dimensional
object embedded in Rd (n<d).

To make DM consistent with the models based on point-set topology, thedefinition of point order has been extended [21], such that the previous definition oforder is applied only to the points on the object’s boundary (in the sense of point-set
topology), while we consider that the points in object’s interior (in the sense of pointset topology) has the same order with the object’s dimension. In the previous
definition of point order, for example, points on a line can be of order 0 or 1 and thepoints of order 0 are not only line extremities (Fig. 4a). In the extended definition ofpoint order, the line’s “extremities” has order 0 while the line’s “interior” has order 1(Fig. 4b).

Æ

(a)

(b)

Fig. 4. The extension of point order concept for point-set objects.

Another issue occurs when applying the previous order definition to the inflexion
points. In this case, point’s order is higher than our intuition; i.e. equal to the order ofinterior points (Fig. 5a). Thus, in the extended definition of point order, if an object ofdimension d has a boundary point of order d, the order of this point is reduced to d-1(Fig. 5b).

Refining Topological Relations between Regions Considering Their Shapes

(a)

5

(b)

Fig. 5. Modification of inflexion points’ order.

This extended point order concept enables us to consider the segmentation of
object’s boundary and consequently to refine binary relationships between objects byconsidering the connectivity of objects “topological” primitives. It has given birth tothe DM model through the concepts of dimensional elements and dimensional
relationships.
2.2.

Dimensional Elements and Dimensional Relationships

Based on the point order concept, we can consider the subsets of spatial objects,
called dimensional elements. Dimensional elements are formally defined as follow:• The n-dimensional element (called nD-element) of a d-dimensional spatial object C(n ≤ d) corresponds to the set of all of C’s points (or parts) of order 0 to n.
• The nD-element of a spatial object C has an extension and may have a limit. The
extension is the subset of C formed by its points of order n, and the limit is thesubset of C formed by its points of order 0 to order (n-1).
Thus, if the nD-element has a limit, this limit corresponds to (n-1)D-element. The 0Delement does not have a limit by definition. For instance, let us consider a polygon in
Fig. 6a. This polygon is composed by points of order 0, 1, and 2. Thus, we canconsider 0D-, 1D-, and 2D-elements for this convex. The different extension andlimits are presented in the Figs. 6b-d. It should be noted that each object has one andonly one nD-element. Thus, nD-element may be disconnected (e.g., a polygon’s 0D
element)

(a)

(b)

(c)

(d)

Fig. 6. (a) Order of points and (b-d) dimensional elements of a polygon

Dimensional relationships between two spatial objects are spatial relationships
determined by the connectivity of their dimensional elements. We consider three6

Roland Billen and Yohei Kurata

connection styles, namely total relation, partial relation and no relation (nonexistent), instead of presence or absence of intersections (Fig. 7).
• A dimensional element is in total relation with another dimensional element if
their intersection is equal to the first element, and if the intersection between theirextensions is not empty.
• A dimensional element is in partial relation with another dimensional element if
their intersection is not equal to the first element, and if the intersection between
their extensions is not empty.
• A dimensional element is in no relation (non-existent) with another dimensional
element if the intersection between their extensions is empty.

Total relation

Partial relation

No relation (non-existent)

Fig. 7. Three types of connection styles between two 2D-elements (from black element to grey
element).

2.3.

Categorising Spatial Relationships Using Dimensional Relationships

The spatial relationship between two objects can be expressed by the set ofconnection styles between pairs of dimensional elements of these two objects. For
example, let us consider a triangle A (with 2D-, 1D-, and 0D-elements) and an ellipse
B (with 2D- and 1D-elements, but no 0D-element) (Fig. 8). The dimensional
relationships between two objects A and B are determined in the following sequence:
first, check the dimensional relationship between A’s 2D-element and each of B’s
dimensional elements; then, check the dimensional relationship between A’s 1Delement and each of B’s dimensional elements, and so on. The dimensional
relationships between B and A can be determined by the same approach. A
dimensional relationship is coded as RnDm, where R stands for relation, nD for thedimension of the element of the first object, and m for the dimension of the element of
the second object. For instance, R2D1 represents the dimensional relationships
between the 2D-element of the first object and the 1D-element of the second object.

R2D2=non-existent

R2D1=non-existent

R2D2=non-existent

R2D1=non-existent

R1D2=non-existent

R1D1=non-existent

R1D2=non-existent

R1D1=partial

R0D2=non-existent

R0D1=partial

R0D2=non-existent

R0D1=partial

Fig. 8. Two examples of categorization of spatial relationships using dimensional relationships.

Refining Topological Relations between Regions Considering Their Shapes

3.

7

Reformulating the Dimensional Model with the 9+-intersection

The Dimensional Model (DM) presented in the previous section has a strong
correspondence with the 9-intersection [2]. The 9-intersection and its extensions havebeen frequently adopted in the studies of topological relations (e.g., [2, 10-13, 15]).
Based on point-set topology [25], this model distinguishes the interior, boundary, andexterior of each spatial object, which are also called the object’s topological parts.
The topological relation between two spatial objects A and B is characterized by theintersections of A’s three topological parts and B’s three topological parts, which areconcisely represented by the 9-intersection matrix in Eqn. 1. A° , ∂A , and A− are A’s
interior, boundary, and exterior, while B° , ∂B , and B − are B’s interior, boundary, andexterior, respectively. Normally, topological relations are distinguished by thepresence or absence of these nine types of intersections.
⎛ A° ∩ B°⎜
M ( A, B ) = ⎜ ∂A ∩ B°⎜ −⎝ A ∩ B°A° ∩ ∂B∂A ∩ ∂B
A− ∩ ∂B

A° ∩ B − ⎞⎟∂A ∩ B − ⎟⎟A− ∩ B − ⎠(1)

In DM, as presented in Section 2, the points that form a spatial object are
distinguished by their orders. Among the points that form an n-dimensional spatial
object, the points of order n form the object’s interior, while the points of order 0 to n1 form the object’s boundary. This implies the presence of a certain correspondence
between DM and the 9-intersection. Meanwhile, if n ≥ 2, DM considers n subsets ofthe boundary, whereas the 9-intersection cannot distinguish these subsets of theboundary. Instead, the 9+-intersection [15] enables such distinction of boundary
subsets within the framework of the 9-intersection.
The 9+-intersection supports the subdivision of objects’ topological parts by
nesting the 9-intersection matrix. For instance, the topological relation between a
directed line segment D and a simple region R is captured by the 9+-intersection
matrix in Eqn. 2, as D’s boundary consists of two subparts (start point ∂ s D and end
point ∂ e D ). The support of such subdivision is useful when a certain topologicalparts consist of multiple subsets that are qualitatively different. In our case, theboundaries of two spatial objects A and B can be distinguished into multiple subsets,
each of which consists of the points of a specific order. Therefore, the relation
between two spatial objects A and B is captured by the 9+-intersection matrix in
Eqn. 3, where nA is A’s dimension, and nB is B’s dimension, ∂ i A is the set of points oforder i in A (0 ≤ i ≤ nA–1), and ∂ j B is the set of points of order j in B (0 ≤ j ≤ nB–1).
Similarly, if we distinguish A’s boundary subset, but not B’s boundary subset, thenthe relation between A and B is captured by the 9+-intersection in Eqn. 4.

8Roland Billen and Yohei Kurata⎛ D° ∩ R°
D° ∩ ∂R
D° ∩ R − ⎞⎟⎜⎜ ⎡∂ s D ∩ R°⎤ ⎡∂ s D ∩ ∂R ⎤ ⎡∂ s D ∩ R − ⎤ ⎟+M ( D, R ) = ⎜ ⎢
⎥
⎥ ⎢
⎥ ⎢
− ⎟
⎜ ⎣∂ e D ∩ R°⎦ ⎣∂ e D ∩ ∂R ⎦ ⎣⎢∂ e D ∩ R ⎦⎥ ⎟⎜ D − ∩ R°
D − ∩ ∂RD − ∩ R − ⎟⎠⎝M + ( A, B ) =⎛ A° ∩ B°⎜⎜ ⎡∂ n A −1 A ∩ B°⎤
⎜⎢
⎥
M
⎜⎢
⎥
⎜ ⎢⎣ ∂ 0 A ∩ B° ⎥⎦⎜⎜ A − ∩ B°⎝

[A° ∩ ∂nB −1

B L A° ∩ ∂ 0 B]⎡∂ n A −1 A ∩ ∂ nB −1 B L ∂ nA −1 A ∩ ∂ 0 B ⎤
⎥
⎢
M
O
M
⎥
⎢
⎢ ∂ 0 A ∩ ∂ n −1 B L ∂ 0 A ∩ ∂ 0 B ⎥B⎦⎣[A ∩ ∂−nB −1⎛ A° ∩ B°⎜⎜ ⎡∂ n−1 A ∩ B°⎤⎥+
M ( A, B ) = ⎜ ⎢⎢M⎥⎜
⎜ ⎢⎣ ∂ 0 A ∩ B° ⎥⎦⎜−⎝ A ∩ B°B L A− ∩ ∂ 0 B
A° ∩ ∂B⎡∂ n−1 A ∩ ∂B ⎤
⎢
⎥
M
⎢
⎥
⎢⎣ ∂ 0 A ∩ ∂B ⎥⎦A− ∩ ∂B

]

(2)

⎞
⎟
⎡∂ nA −1 A ∩ B ⎤ ⎟
⎥⎟
⎢
M
⎥⎟
⎢
⎢ ∂0 A ∩ B− ⎥ ⎟⎦⎟⎣−D1 ∩ B − ⎟⎠A° ∩ B −−A° ∩ B − ⎞⎟⎡∂ n−1 A ∩ B − ⎤ ⎟
⎢
⎥⎟
M
⎢
⎥⎟
⎢ ∂0 A ∩ B− ⎥ ⎟⎣⎦⎟−D1 ∩ B − ⎠

(3)

(4)

Precisely speaking, the captured relations are no longer topological relations whenn ≥ 2, but their refinements, because the order of a point is not invariant under
topological transformation. Therefore, the relations distinguished by the 9+intersection matrix in Eqn. 3 or 4 are named binary projective relations. In addition,
the model of spatial relations based on the 9+-intersection matrix in Eqn. 3 or 4 iscalled the projective 9+-intersection. As examples, Fig. 9 shows how the projective
9+-intersection captures projective relations between a triangle and an eclipse. We
also call an object whose boundary consists of points of different orders (e.g.,
polygons) the object with a multi-order boundary, or in short, objects+mob.

¬φ ⎞
φ
⎛ φ
⎜
⎟
⎜ ⎡φ ⎤ ⎡ φ ⎤ ⎡¬φ ⎤ ⎟⎜ ⎢⎣φ ⎥⎦ ⎢⎣¬φ ⎥⎦ ⎢⎣¬φ ⎥⎦ ⎟⎜ ¬φ ¬φ
¬φ ⎟⎠
⎝

¬φ ⎞
φ
⎛ φ
⎜
⎟
⎜ ⎡φ ⎤ ⎡¬φ ⎤ ⎡¬φ ⎤ ⎟⎜ ⎢⎣φ ⎥⎦ ⎢⎣¬φ ⎥⎦ ⎢⎣¬φ ⎥⎦ ⎟⎜ ¬φ ¬φ¬φ ⎟⎠⎝Fig. 9. Two examples of categorization of spatial relations using the projective 9+-intersection.

Refining Topological Relations between Regions Considering Their Shapes

9

The projective 9+-intersection is upward compatible with DM, because, given a 9+intersection matrix in Eqn. 3, we can uniquely determine the dimensional relation in
DM (i.e., a complete set of RnDm expressions) through the conversion formula in
Eqn. 5 (compare Figs. 8-9). Meanwhile, the new model and DM has the following
differences:• DM considers the intersections with respect to k-dimensional element (i.e., the setof points of order 1 to k), while the new model considers the intersections withrespect to the extension of k-dimensional element (i.e., the set of points of order k).
• The new model also considers the intersections with respect to the objects’
exteriors.
• DM distinguishes three styles of intersections (i.e., partial, total, and non-existent),
while the new model distinguishes only two styles (i.e., X intersects with Y or not).
This change does not reduce the model’s representation capability, because it
becomes possible to determine whether X overlaps with Y (partial relation), X is
included in Y (total relation), or else (no relation), considering the intersections
concerning the objects’ exteriors.
AO ( A ) = A°, Ai = ∂ i A (0 ≤ i < O( A) − 1)

BO ( B ) = B°, Bi = ∂ i B (0 ≤ i < O(B ) − 1)An ∩ Bm ≠ φ∧

An ∩ Bm ≠ φ∧

An ∩ Bm = φ⎛ O(B )⎞An ∩ ⎜ ∪ Bk ∪ B − ⎟ ≠ φ
k = n +1⎝⎠
⎛ O(B )−⎞An ∩ ⎜ ∪ Bk ∪ B ⎟ = φ⎝ k =n+1⎠→ RnDm = partial(5)→ RnDm = total→ RnDm = non - existent

The projective 9+-intersection serves as a refinement of the 9-intersection, as easily
expected from the shape of the underlying matrix. This means that spatial relations
under the new model can be systematically categorized based on the sets of
topological relations identified in the previous studies (e.g., [2]), as well as that the
spatial arrangement of two objects that falls into the same topological relations in theprevious relation set may be distinguished by the new model. The next sections
discuss such characteristics of the new model as a refinement of the 9-intersection.

4.

Projective Relations between a Region with Multi-Order
Boundary and a Region

There are in theory 24×3 = 4096 projective relations between a region with multi-orderboundary and a region in R2, because the relations are represented by the 9+intersection matrix with 4×3 two-valued elements (e.g., Fig. 9). However, only asmall subset of these relations can be realized in a particular space. As a refinement of
the 9-intersection, all the constraints of the 9-intersection for topological regionregion relations, identified in [2], can be applied to the projective 9+-intersection. In
addition, due to the subdivision of the region’s boundary, the following seven specific10

Roland Billen and Yohei Kurata

constraints are additionally applied, where the set of points of order n in the boundaryof a spatial object X is called X’s order n boundary:• Constraint 1: If A’s order 0 boundary intersects with B’s interior, then A’s order 1
boundary must intersect with B’s interior• Constraint 2: If A’s order 0 boundary intersects with B’s exterior, then A’s order 1
boundary must intersect with B’s exterior• Constraint 3: If A’s order 0 boundary intersects with B’s interior and B’s exterior,then A’s boundary must intersect with B’s boundary• Constraint 4: If A’s order 1 boundary intersects only with B’s exterior, then A’sorder 0 boundary must not intersect with B’s interior• Constraint 5: If A’s order 1 boundary intersects only with B’s interior, then A’sorder 0 boundary must not intersect with B’s exterior• Constraint 6: A’s order 1 boundary intersects with at least one part of B
• Constraint 7: A’s order 0 boundary intersects with at least one part of B
Fig. 10 illustrates these constraints using the 9+-intersection matrix.
⎛ −
⎜
⎡φ ⎤
M + ( A, B ) ≠ ⎜ ⎢ ⎥⎜ ⎣¬φ ⎦⎜ −⎝− ⎞⎟⎡− ⎤ ⎟⎢− ⎥ ⎟
⎣ ⎦
− ⎟⎠

⎛ −
−
− ⎞⎟
⎜
⎡− ⎤ ⎡ −⎤ ⎡ φ ⎤M + ( A, B) ≠ ⎜ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎟⎜ ⎣−⎦ ⎣−⎦ ⎣¬φ ⎦ ⎟
⎜ −
−
− ⎟⎠
⎝

⎛ −
−
− ⎞⎟
⎜
⎡ − ⎤ ⎡φ ⎤ ⎡ − ⎤
M + ( A, B) ≠ ⎜ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎟⎜ ⎣¬φ ⎦ ⎣φ ⎦ ⎣¬φ ⎦ ⎟
⎜ −
−
− ⎟⎠
⎝

Constraint 1

Constraint 2

Constraint 3

⎛ −
−
− ⎞⎟
⎜
⎡ φ ⎤ ⎡φ ⎤ ⎡¬φ ⎤M + ( A, B) ≠ ⎜ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎟⎜ ⎣¬φ ⎦ ⎣− ⎦ ⎣ − ⎦ ⎟
⎜ −
−
− ⎟⎠
⎝

⎛ −
−
− ⎞⎟
⎜
⎡¬φ ⎤ ⎡φ ⎤ ⎡ φ ⎤M + ( A, B) ≠ ⎜ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎟⎜ ⎣ − ⎦ ⎣− ⎦ ⎣¬φ ⎦ ⎟
⎜ −
−
− ⎟⎠
⎝

⎛ −
−
− ⎞⎟
⎜
⎡φ ⎤ ⎡φ ⎤ ⎡φ ⎤M + ( A, B) ≠ ⎜ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎟⎜ ⎣ − ⎦ ⎣ − ⎦ ⎣− ⎦ ⎟
⎜ −
−
− ⎟⎠
⎝

Constraint 4

Constraint 5

Constraint 6

−
⎡− ⎤
⎢− ⎥
⎣ ⎦
−

⎛ −
−
− ⎞⎟
⎜
⎡ − ⎤ ⎡ − ⎤ ⎡− ⎤M + ( A, B) ≠ ⎜ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎟⎜ ⎣φ ⎦ ⎣φ ⎦ ⎣φ ⎦ ⎟
⎜ −
−
− ⎟⎠
⎝

Constraint 7
Fig. 10. New constraints applied to the matrix of the projective 9+-intersection.

By applying these constraints, the number of relations is reduced from 4096 to 30(Figs. 11-12). All of these 30 relations normally have geometric realization in R2.
Exceptionally, when A’s order 0 boundary consist of three distinctive subparts (i.e.,
when A is a triangle), the relation “overlap-11” is impossible. These 30 relationships
are indeed a refinement of eight topological relations between regions. Consequently,
we have decided to keep the same names (i.e. overlap, contains, inside, covers,
coveredBy, equal, meet, and disjoint [4]) and just added a number to them whichreflects the number of refined cases.

Refining Topological Relations between Regions Considering Their Shapes

11

Fig. 11. Thirty possible projective relations between a region with a multi-order boundary and aregion in R² – Part 1.

12

Roland Billen and Yohei Kurata

Fig. 12. Thirty possible projective relations between a region with a multi-order boundary and aregion in R² – Part 2.

Refining Topological Relations between Regions Considering Their Shapes

5.

13Conceptual Neighbourhood Graph

The 30 projective relations derived in the previous section are organized into asimilarity-based schema, called a conceptual neighbourhood graph [26]. Conceptual
neighbourhood graphs are frequently used for schematizing, analyzing, andvisualizing a set of spatial relations [4, 9, 11, 14, 15, 19, 26-30]. In a conceptual
neighbourhood graph, each node corresponds to a spatial relation, and two nodes arelinked if their corresponding relations are conceptual neighbours. Different
definitions of conceptual neighbours lead to different graph shapes for the same set of
relations [26, 28]. This paper considers that two projective relations between a region
with a multi-order boundary (region+mob) A and a region B are conceptual neighbours
if there is a configuration of one relation that can switch to a configuration of anotherrelation by transforming A continuously, such that one vertex or edge loses/gains one
intersection with B’s interior, boundary, or exterior. Accordingly, the transformationin Fig. 13a establishes continuous neighbours, but that in Fig. 13b, which yields thegeneration of three intersections ( ∂ 0 A ∩ B° , ∂1 A ∩ B° , and ∂1 A ∩ ∂B ) and loss of
one intersection ( ∂ 0 A ∩ ∂B ), is not accepted. Acceptable continuous transformation
always results in the change of one of six elements in the middle two rows of thematrix (i.e., ∂ 0 A ∩ B° , ∂ 0 A ∩ ∂B , ∂ 0 A ∩ B − , ∂1 A ∩ B° , ∂1 A ∩ ∂B , and ∂1 A ∩ B − ).
Thus, all candidates for conceptual neighbours are derived computationally from thepatterns of the 9+-intersection matrix that correspond to the 30 projective relations.

⇔

⇔

φ
¬φ ⎞
⎛ φ
⎟
⎜
⎜ ⎡φ ⎤ ⎡¬φ ⎤ ⎡¬φ ⎤ ⎟⎜ ⎢⎣φ ⎥⎦ ⎢⎣¬φ ⎥⎦ ⎢⎣¬φ ⎥⎦ ⎟⎜ ¬φ ¬φ
¬φ ⎟⎠
⎝

φ
¬φ ⎞
⎛ φ
⎟
⎜
⎜ ⎡φ ⎤ ⎡ φ ⎤ ⎡¬φ ⎤ ⎟⎜ ⎢⎣φ ⎥⎦ ⎢⎣¬φ ⎥⎦ ⎢⎣¬φ ⎥⎦ ⎟⎜ ¬φ ¬φ
¬φ ⎟⎠
⎝

(a)

φ
¬φ ⎞
⎛ φ
⎟
⎜
⎜ ⎡ ¬ φ ⎤ ⎡ ¬φ ⎤ ⎡ ¬φ ⎤ ⎟⎜ ⎢⎣¬φ ⎥⎦ ⎢⎣ φ ⎥⎦ ⎢⎣¬φ ⎥⎦ ⎟
⎜ ¬φ
¬φ
¬φ ⎟⎠
⎝

φ
¬φ ⎞
⎛ φ
⎟
⎜
⎜ ⎡φ ⎤ ⎡ φ ⎤ ⎡¬φ ⎤ ⎟⎜ ⎢⎣φ ⎥⎦ ⎢⎣¬φ ⎥⎦ ⎢⎣¬φ ⎥⎦ ⎟⎜ ¬φ ¬φ
¬φ ⎟⎠
⎝

(b)

Fig. 13. (a) A continuous transformation that establishes conceptual neighbours and (b) anothercontinuous transformation that does not establish conceptual neighbours.

Based on the previous definition of conceptual neighbours, we developed theconceptual neighbourhood graph of the 30 projective region+mob-region relations(Fig. 14). Basically, the developed graph has both horizontal and vertical symmetry
axes, even though the upper-left part is missing and overlap-refinements do not follow
the horizontal symmetric axis. The spatial arrangement of the 30 projective
region+mob-region relations in this conceptual neighbourhood graph corresponds to thearrangement of topological region-region relations in their conceptual neighbourhood
graph [4] (Fig. 15a). This highlights the characteristics of these 30 projective
region+mob-region relations as the refinement of topological region-region relations.
The comparison of two graphs shows that the number of steps from one relation to14

Roland Billen and Yohei Kurata

another relation is larger in our graph, except those from disjoint to contains and viceversa (Fig. 15b).
overlap-3

meet-1meet-2

disjoint

1 1 1
1 0 1

0 0 1
0 1 0

0 0 1
0 1 1

0 0 1
0 0 1

overlap-5
1 1 1
1 1 1

overlap-11

meet-4meet-5meet-3

0 1 1
0 1 0

0 1 1
0 1 1

0 1 1
0 0 1

1 0 1
1 1 1

overlap-2

overlap-4

overlap-10

overlap-1

overlap-9

1 1 1
1 0 0

1 1 1
1 1 0

1 1 1
0 1 0

1 1 1
0 1 1

1 1 1
0 0 1

overlap-8

overlap-6

overlap-7

1 0 1
1 1 0

1 0 1
0 1 0

1 0 1
0 1 1

coverdBy-5

coverdBy-1

coverdBy-4

equal

covers-5

covers-1

covers-4

1 1 0
1 0 0

1 1 0
1 1 0

1 1 0
0 1 0

0 1 0
0 1 0

0 1 1
0 1 0

0 1 1
0 1 1

0 1 1
0 0 1

insidecoverdBy-3

coverdBy-2

covers-2

covers-3

contains

1 0 0
1 0 0

1 0 0
1 1 0

1 0 0
0 1 0

0 0 1
0 1 0

0 0 1
0 1 1

0 0 1
0 0 1

Fig. 14. Conceptual neighbourhood graphs of the 30 projective relations between a region witha multi-order boundary and a region in R², together with the six elements in the matrix’s middle
two rows.

disjoint
disjoint

4 stepsmeet
meet

overlap
overlap

coveredBy
coveredBy

insideinsidecover

covers

equal

equal

4 steps(a)containcontains

4 steps(b)

Fig. 15. (a) Conceptual neighbourhood graphs of eight topological region-region relations [4]and (b) numbers of steps between nodes in the corresponding conceptual neighbourhood graphof projective region+mob-region relations in Fig. 14.

Refining Topological Relations between Regions Considering Their Shapes

15

Through the analysis of the developed conceptual neighbourhood graph, we found
the following facts:• The pairs of relations with one difference in the matrices’ middle two rows, where
one has (¬φ φ ¬φ ) and another has (φ φ ¬φ ) or (¬φ φ φ ) withrespect to one of these two rows (e.g., overlap-3 and overlap-9), are not conceptual
neighbours, because the shift between these two relations require that one vertex or
one edge of the triangle skips over the region’s boundary (Fig. 16).
• The matrices’ middle two rows of the relations on the graph’s vertical centre line
(i.e., overlap-3, -5, -6, -10, -11, and equal) are left-right symmetric.
• In each pair of relations located symmetrically with respect to the graph’s verticalcentre line (e.g., inside and contain), the matrix of one relation is derived from thematrix of another relation by exchanging the matrix’s elements with respect to
B° and B − . This means that one relation is derived from another relation by
reversing B’s interior and exterior, assuming a spherical surface that embeds theconfigurations of the relations.
• Similarly, in each pair of relations located symmetrically with respect to thegraph’s horizontal centre line (e.g., disjoint and contain), the matrix of one relation
is derived from the matrix of another relation by exchanging the matrix’s elementswith respect to A° and A − . This means that one relation is derived from anotherrelation by reversing A’s interior and exterior, assuming a spherical surface thatembeds the configurations of the relations.
• Overlap-1 to overlap-11 follow the vertical symmetric axis only. We can consider
a virtual graph that is horizontally and vertically symmetric (Fig. 17), considering
the patterns of their projective 9+-intersection matrices. In this graph, however,overlap-1' to overlap-10' have no geometric realization.
From the third and fourth findings, we can expect that the upper-left empty part ofthe conceptual neighbourhood graph in Fig. 14 potentially domiciles the relations thatappear in a spherical surface, but not in a plane. This is analogous to Egenhofer’s [11]finding of three additional region-region relations on a spherical surface, namely
attaches, embraces, and entwined. Thus, it is expected that the relations at the graph’s
upper-left empty part neighbour should be the refinements of attaches, embraces, andentwined relations.

⇔

φ
¬φ ⎞
⎛ φ
⎟
⎜
⎜ ⎡¬φ ⎤ ⎡¬φ ⎤ ⎡¬φ ⎤ ⎟
⎢
⎥
⎢
⎥
⎢
⎥
⎜ ⎣ φ ⎦ ⎣ φ ⎦ ⎣¬φ ⎦ ⎟
⎜ ¬φ
¬φ
¬φ ⎟⎠
⎝

φ
¬φ ⎞
⎛ φ
⎟
⎜
⎜ ⎡ ¬ φ ⎤ ⎡ ¬φ ⎤ ⎡ ¬φ ⎤ ⎟
⎢
⎥
⎢
⎥
⎢
⎥
⎜ ⎣ ¬ φ ⎦ ⎣ φ ⎦ ⎣ ¬φ ⎦ ⎟
⎜ ¬φ
¬φ
¬φ ⎟⎠
⎝

Fig. 16. Non-continuous transformation, even though that yields only one change in the middle
two rows in the 9+-intersection matrix.

16

Roland Billen and Yohei Kurata
overlap-8'

overlap-6'

overlap-7'

1 0 1
1 1 0

1 0 1
0 1 0

1 0 1
0 1 1

overlap-2'

overlap-4'

overlap-10'

overlap-1'

overlap-9'

1 1 1
1 0 0

1 1 1
1 1 0

1 1 1
0 1 0

1 1 1
0 1 1

1 1 1
0 0 1

overlap-3
1 1 1
1 0 1

overlap-5
1 1 1
1 1 1
overlap-11
1 0 1
1 1 1

overlap-2

overlap-4

overlap-10

overlap-1

overlap-9

1 1 1
1 0 0

1 1 1
1 1 0

1 1 1
0 1 0

1 1 1
0 1 1

1 1 1
0 0 1

overlap-8

overlap-6

overlap-7

1 0 1
1 1 0

1 0 1
0 1 0

1 0 1
0 1 1

Fig. 17. Virtual symmetry of the conceptual neighbourhood graph in Fig. 3 with respect tooverlap refinements. Overlap-1' to overlap-10' have no geometric realization, however.

6.

Conclusions

This paper developed a new model of projective relations based on the Dimensional
Model [22] and the 9+-intersection [15]. As a first step, this paper identified 30
projective relations between a region with a multi-order boundary and a region (i.e.,
projective region+mob-region relations) in R2, and schematized these 30 relations into a
conceptual neighbourhood graph. Naturally, the next target is the relations between
two regions, both with a multi-order boundary (i.e., projective region+mob- region+mob
relations). By replacing regions by regions with multi-order boundaries, the numberof projective relations will increase, and the conceptual neighbourhood graph will
become more complicated (probably more high-dimensional). It is also expected thatthe shapes of regions with multi-order boundaries influence the realizability of someprojective relations. For instance, a triangle and a quadrilateral cannot have an equal
relation.
Another challenge is to identify and analyze projective relations in a three
dimensional space. Systematic analyses of three-dimensional topological relations
were conducted in [10, 21], identifying many relations that cannot be realized in R2.
Similar analysis should be possible for projective relations.
An interesting and promising topic is the composition of projective relations. The
composition of spatial relations is an operation that derives possible relations between
two spatial objects from the knowledge of the relations between each of these objects

Refining Topological Relations between Regions Considering Their Shapes

17

and the common third object. Such compositions of spatial relations have beenfrequently discussed as a foundation of qualitative spatial reasoning [6, 11, 14, 18, 2729, 31, 32]. It is an interesting question whether the compositions of projective
relations become crisper than those of topological relations, as the projective relations
consider the dimensional characteristics of the regions’ boundaries.

References
1. Egenhofer, M., Franzosa, R.: Point-Set Topological Spatial Relations. International Journalof Geographical Information Systems 5, 161-174 (1991)
2. Egenhofer, M., Herring, J.: Categorizing Binary Topological Relationships between
Regions, Lines and Points in Geographic Databases. In: Egenhofer, M., Herring, J., Smith,T., Park, K. (eds.): NCGIA Technical Reports 91-7. National Center for Geographic
Information and Analysis, Santa Barbara, CA, USA (1991)
3. Randell, D., Cui, Z., Cohn, A.: A Spatial Logic Based on Regions and Connection. In:
Nebel, B., Rich, C., Swarout, W. (eds.): 3rd International Conference on Knowledge
Representation and Reasoning, pp. 165-176. Morgan Kaufmann (1992)
4. Egenhofer, M., Al-Taha, K.: Reasoning about Gradual Changes of Topological
Relationships. In: Frank, A., Campari, I., Formentini, U. (eds.): Theories and methods ofspatio-temporal reasoning in geographic space, LNCS, vol. 639, pp. 196-219. Springer(1992)
5. Clementini, E., Di Felice, P., van Oosterom, P.: A Small Set of Formal Topological
Relationships Suitable for End-User Interaction. In: Abel, D., Ooi, B.C. (eds.): 3rdInternational Symposium on Advances in Spatial Databases, LNCS, vol. 692, pp. 277-295.
Springer (1993)
6. Egenhofer, M.: Deriving the Composition of Binary Topological Relations. Journal of
Visual Languages and Computing 5, 133-149 (1994)
7. Egenhofer, M., Franzosa, R.: On the Equivalence of Topological Relations International
Journal of Geographical Information Systems 9, 133-152 (1995)
8. Clementini, E., Di Felice, P.: Topological Invariants for Lines. IEEE Transactions on
Knowledge and Data Engineering 10, 38-54 (1998)
9. Hornsby, K., Egenhofer, M., Hayes, P.: Modeling Cyclic Change. In: Chen, P., Embley, D.,
Kouloumdjian, J., Liddle, S., Roddick, J. (eds.): Advances in Conceptual Modeling, LNCS,
vol. 1227, pp. 98-109. Springer (1999)
10.Zlatanova, S.: On 3D Topological Relationships. In: 11th International Workshop on
Database and Expert Systems Applications, pp. 913-924. IEEE Computer Society (2000)
11.Egenhofer, M.: Spherical Topological Relations. Journal on Data Semantics III, 25-49(2005)
12.Schneider, M., Behr, T.: Topological Relationships between Complex Spatial Objects. ACM
Transactions on Database Systems 31, 39-81 (2006)
13.Nedas, K., Egenhofer, M., Wilmsen, D.: Metric Details of Topological Line-Line Relations.
International Journal of Geographical Information Science 21, 21-48 (2007)
14.Kurata, Y., Egenhofer, M.: The Head-Body-Tail Intersection for Spatial Relations between
Directed Line Segments. In: Raubal, M., Miller, H., Frank, A., Goodchild, M. (eds.):
GIScience'06, LNCS, vol. 4197, pp. 269-286. Springer (2006)
15.Kurata, Y., Egenhofer, M.: The 9+-Intersection for Topological Relations between a
Directed Line Segment and a Region. In: Gottfried, B. (ed.): 1st International Symposiumfor Behavioral Monitoring and Interpretation, pp. 62-76 (2007)
16.OpenGIS Consortium: OpenGIS Simple Features Specification for SQL (1998)

18

Roland Billen and Yohei Kurata

17.Frank, A.: Qualitative Spatial Reasoning about Distances and Directions in Geographic
Space. Journal of Visual Languages and Computing 3, 343-371 (1992)
18.Freksa, C.: Using Orientation Information for Qualitative Spatial Reasoning. In: Frank, A.,
Campari, I., Formentini, U. (eds.): International Conference GIS - From Space to Territory:
Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, LNCS, vol.
639, pp. 162-178. Springer (1992)
19.Schlieder, C.: Reasoning about Ordering. In: Frank, A., Kuhn, W. (eds.): COSIT '95, LNCS,
vol. 988, pp. 341-349. Springer (1995)
20.Clementini, E., Billen, R.: Modeling and Computing Ternary Projective Relations between
Regions. IEEE Transactions on Knowledge and Data Engineering 18, 799-814 (2006)
21.Billen, R.: Nouvelle Perception De La Spatialité Des Objets Et De Leurs Relations.
Développment D'une Modélisation Tridimensionnelle De L'information Spatiale.
Department of Geography, Ph.D. Thesis. University of Liège, Liège, Belgium (2002)
22.Billen, R., Zlatanova, S., Mathonet, P., Boniver, F.: The Dimensional Model: A Framework
to Distinguish Spatial Relationships. In: Richardson, D., van Oosterom, P. (eds.): Advancesin spatial data handling: 10th International Symposium on Spatial Data Handling, pp. 285298. Springer (2002)
23.Billen, R., Clementini, E.: Etude Des Caractéristiques Projectives Des Objets Spatiaux Et
De Leurs Relations. Revue Internationale de Géomatique 14, 145-165 (2004)
24.Berger, M.: Géométrie 3 : Convexes Et Polytopes, Polyèdres Réguliers, Aires Et Volumes.
Cedic/Fernand Nathan, Paris (1978)
25.Alexandroff, P.: Elementary Concepts of Topology. Dover Publications, Mineola, NY(1961)
26.Freksa, C.: Temporal Reasoning Based on Semi-Intervals. Artificial Intelligence 54, 199227 (1992)
27.Galton, A.: Lines of Sight. In: AI and Cognitive Science '94, pp. 103-113. Dublin University
Press (1994)
28.Egenhofer, M., Mark, D.: Modeling Conceptual Neighborhoods of Topological Line-Region
Relations. International Journal of Geographical Information Systems 9, 555-565 (1995)
29.Gottfried, B.: Reasoning about Intervals in Two Dimensions. In: Thissenm, W., Pantic, M.,
Ludema, M. (eds.): IEEE International Conference on Systems, Man and Cybernetics, pp.
5324-5332 (2004)
30.Van de Weghe, N., De Maeyer, P.: Conceptual Neighbourhood Diagrams for Representing
Moving Objects. In: 2nd International Workshop on Conceptual Modeling for Geographic
Information Systems, LNCS, vol. 3770, pp. 228-238. Springer (2005)
31.Moratz, R., Renz, J., Wolter, D.: Qualitative Spatial Reasoning about Line Segments. In:
Horn, W. (ed.): 14th European Conference on Artificial Intelligence, pp. 234-238. IOS Press(2000)
32.Van de Weghe, N., Kuijpers, B., Bogaert, P., De Maeyer, P.: A Qualitative Trajectory
Calculus and the Composition of Its Relations. In: Rodriguez, A., Cruz, I., Egenhofer, M.,
Levashkin, S. (eds.): The 1st International. Conference on Geospatial Semantics, LNCS, vol.
3799, pp. 60-76. Springer (2005)