# A Hybrid Reasoning Model for “Whole and Part” Cardinal Direction Relations

Authors: Ah-Lian Kor; Brandon Bennett
Journal: Advances in Artificial Intelligence
 (2013)

---

## Abstract

We have shown how the ninetiles in the projection-based model for cardinal directions can be partitioned into sets based on horizontal and vertical constraints (called Horizontal and Vertical Constraints Model) in our previous papers (Kor and Bennett, 2003 and 2010). In order to come up with an expressive hybrid model for direction relations between two-dimensional single-piece regions (without holes), we integrate the well-known RCC-8 model with the above-mentioned model. From this expressive hybrid model, we derive 8 basic binary relations and 13 feasible as well as jointly exhaustive relations for the x- and y-directions, respectively. Based on these basic binary relations, we derive two separate 8×8 composition tables for both the expressive and weak direction relations. We introduce a formula that can be used for the computation of the composition of expressive and weak direction relations between “whole or part” regions. Lastly, we also show how the expressive hybrid model can be used to make several existential inferences that are not possible for existing models.


---

## Body

## 1. Introduction

Relative positions of regions in large-scale spaces, and particularly in the geographic domain, are often described by relations referring to cardinal directions. These relations specify the direction from one region to another in terms of the familiar compass bearings: north, south, east, and west. The intermediate directions northwest, northeast, southwest, and southeast are also often used. Some models for reasoning with cardinal directions are the cone-shaped [1, 2], projection-based models (ibid), and direction matrix [3–5].Papadias and Theodoridis [6] describe topological and direction relations between regions using their minimum bounding rectangles (MBRs). However, the language used is not expressive enough to describe direction relations. Additionally, the MBR technique yields erroneous outcome when involving regions that are not rectangular in shape [4] Some work has been done on hybrid direction models. Escrig and Toledo [7] and Clementini et al. [8] integrated qualitative orientation and distance to obtain positional information. Isli [9] combined Frank’s [1, 2] cardinal direction relations model and Freksa’s [10] orientation model to facilitate a more expressive reasoning mechanism. Sharma and Flewelling [11] infer spatial relations from integrated topological and cardinal direction relations. Liu and colleagues [12] have developed reasoning algorithms which combine RCC-8 [13] for topological relations (discussed in Section 4) and the cardinal direction calculus (CDC [3–5], discussed in Section 2) for direction relations. Li and colleagues’ work [14, 15] focuses on the development and evaluation of an efficient reasoning mechanism for RCC-8 and RA (Rectangle Algebra, and further explanation can be found in [16, 17]) which is employed to solve the satisfiability problem of these two joint constraint networks.Typically, composition tables are used to infer spatial relations between objects. They have been employed to make different inferences about cardinal directions relations [3, 19–24]. One of the advantages of composition tables is that they can lead to tractable computation of inferences [25]. In this paper, we have developed an expressive hybrid model for direction relations. We will describe the binary relations in the model and define “whole and part” relations. Based on this model, we derive two 8×8 composition tables for expressive and weak direction relations. This is followed by introducing a formula which could be used to compute both expressive and weak direction relations for “whole and part” regions. Finally, we will demonstrate how the model could be used to make several types of existential inferences.


## 2. Cardinal Direction Models

Frank [1, 2] defines cardinal directions as cones which are related to the angular direction between an observer’s position (in the form of a point) and a destination point. The cone-shaped cardinal direction model could have 4, 8, or more partitions (look at Figure 1).Figure 1
Cone-shaped direction model with 4 or 8 partitions (ibid).Frank defines the four major cardinal directions (north, south, east, and west) as pair-wise opposites and half planes. When the two sets of half planes are combined, it yields four intermediate cardinal directions (northeast, northwest, southeast, and southwest) which are depicted in Figure2. Ligozat [21] applies the model to points in a two-dimensional space. Thus, the referent object, Point B, will be given the four major directions. However, the relations between two objects will be denoted by one of the following basic relations: N, S, E, W, NE, NW, SE, SW, or EQ.Figure 2
Cardinal directions defined by half-planes.Frank [1, 2] extends the half-planes to tiles for regions (as shown in Figure 3). In this projection-based model, the plane of an arbitrary single-piece region a is partitioned into nine tiles, North-West, NW(a); North, N(a); North-East, NE(a); South-West, SW(a); South, S(a); South-East, SE(a); West, W(a); Neutral Zone, O(a); East, E(a). According to Frank, the O tile is considered a neutral zone, because in this tile, the relative cardinal direction between two regions cannot be determined due to their proximity.Figure 3
Cardinal directions defined by tiles for extended objects [1, 2].Frank compares and contrasts reasoning with the cone-shaped and the projection-based models for cardinal directions. The reasoning capability for both the systems is limited and weak though they do not differ substantially in their reasoning outcomes. In order to create a more expressive reasoning model, Isli [26] integrates the Frank’s cone-shaped and projection-based models to facilitate reasoning about relative position of points of the 2-dimensional space. This hybrid model is well suited for applications of large-scale high-level vision, such as, for example, satellite-like surveillance of a geographic area.The cardinal direction calculus (CDC) [3–5] is a very expressive qualitative calculus for directional information of extended objects. A direction relation matrix (DRM) in (1) is used to represent direction relations between connected plane regions. Liu and colleagues [27, 28] have shown that consistency checking of complete networks of basic CDC constraints is tractable, while reasoning with the CDC in general is NP hard. However, if some constraints are unspecified, then consistency checking of incomplete networks of basic CDC constraints is intractable.The cardinal direction of a target object (regionb) to a referent object (region a) as shown in Figure 4 is described by recording those tiles covered by the target object. According to Goyal and Egenhofer [4], a 3×3 matrix is employed to register the intersections between the target object and the tiles of the referent object (see (1)). The elements in the direction-relation matrix correspond to the tiles of the referent object, region a(in Figure 4).Figure 4
Nine tiles with regionsa (as the referent object) and b (as the target object) [4, 5].In (1), the symbol ∅ represents empty tile while ¬∅ represents nonempty tile. These are used to describe cardinal directions at a coarse granularity level. In Figure 4, region b occupies the N, NW, and E tiles of region a. Thus, these three tiles are considered nonempty while the rest are considered empty (as shown in (1)).Goyal and Egenhofer [5] extend the direction relation matrix, so that it will be more expressive. Instead of using the empty and nonempty notations, it registers how much (in terms of proportion) the target region occupies each tile (see (2)). The expressive direction relation matrix in (2) has 6 elements of zero and three nonzero elements which sum up to 1.0. If the matrix has only one nonzero element then it is known as a single element direction relation matrix while a matrix with more than one nonzero element is called a multielement direction relation matrix (ibid).Coarse direction relation matrix [4]:
(1)dirRR(a,b)=(NW(a)∩bN(a)∩bNE(a)∩bW(a)∩bO(a)∩bE(a)∩bSW(a)∩bS(a)∩bSE(a)∩b),dirRR(a,b)=(∅¬∅¬∅∅∅¬∅∅∅∅).Expressive direction relation matrix [5]:
(2)dirRR(a,b)=(area(NW(a)∩b)areaofbarea(N(a)∩b)areaofbarea(NE(a)∩b)areaofbarea(W(a)∩b)areaofbarea(O(a)∩b)areaofbarea(E(a)∩b)areaofbarea(SW(a)∩b)areaofbarea(S(a)∩b)areaofbarea(SE(a)∩b)areaofb),dirRR(a,b)=(00.050.45000.50000).


## 3. Horizontal and Vertical Constraints Model

Every region has a minimal bounding box with specific minimum and maximumx (and y) values. The boundaries of the minimal bounding box of a region a are depicted in Figure 5. The set of boundaries of the minimal bounding box for region a could be represented as {Xmin(a), Xmax(a), Ymin(a), Ymax(a)}, and these values will be employed to define each tile.Figure 5
Horizontal and vertical sets oftiles for a.The definition of the nine tiles in terms of the boundaries of the minimal bounding box is listed as below. Note, in this paper, all the tiles are regarded as mutually exclusive. Thus neighboring tiles cannot share common boundaries:(i)
N(a)≡{〈x,y〉∣Xmin(a)≤x<Xmax(a)∧y≥Ymax(a)},(ii)
NE(a)≡{〈x,y〉∣x≥Xmax(a)∧y≥Ymax(a)},(iii)
NW(a)≡{〈x,y〉∣x<Xmin(a)∧y≥Ymax(a)},(iv)
S(a)≡{〈x,y〉∣Xmin(a)≤x<Xmax(a)∧y<Ymin(a)},(v)
SE(a)≡{〈x,y〉∣x≥Xmax(a)∧y<Ymin(a)},(vi)
SW(a)≡{〈x,y〉∣x<Xmin(a)∧y<Ymin(a)},(vii)
E(a)≡{〈x,y〉∣x≥Xmax(a)∧Ymin(a)≤y<Ymax(a)},(viii)
W(a)≡{〈x,y〉∣x<Xmin(a)∧Ymin(a)≤y<Ymax(a)},(ix)
O(a)≡{〈x,y〉∣Xmin(a)≤x<Xmax(a)∧Ymin(a)≤y<Ymax(a)}.In our previous papers [29, 30], we have shown how to partition the nine tiles (in Figure 5) into sets based on horizontal and vertical constraints called the Horizontal and Vertical Constraints Model. However, in this paper, we shall rename the sets for easy comprehension purposes. The following are the definitions of the partitioned regions.(i)
WeakNorth(a) is the region that covers the tiles NW(a), N(a), and NE(a). WeakNorth(a) ≡ NW(a) ∪ N(a) ∪ NE(a).(ii)
Horizontal(a) is the region that covers the tiles W(a), O(a), and E(a). Horizontal(a) ≡ W(a) ∪ O(a) ∪ E(a).(iii)
WeakSouth(a) is the region that covers the tiles SW(a), S(a), and SE(a). WeakSouth(a) ≡ SW(a) ∪ S(a) ∪ SE(a).(iv)
WeakWest(a) is the region that covers the tiles SW(a), W(a), and NW(a). WeakWest(a) ≡ SW(a) ∪ W(a) ∪ NW(a).(v)
Vertical(a) is the region that covers the tiles S(a), O(a), and N(a). Vertical(a) ≡ S(a) ∪ O(a) ∪ N(a).(vi)
WeakEast(a) is the region that covers the tiles SE(a), E(a), and NE(a). WeakEast(a) ≡ SE(a) ∪ E(a) ∪ NE(a).


## 4. RCC Model

RCC stands for region connection calculus [13, 18, 31]. It is a first-order theory employed for qualitative spatial representation as well as reasoning and is based on Clarke’s logic of connection [32, 33]. The connection predicate, C(a,b), which means “region a is connected with region b”, is the only primitive predicate for RCC. This dyadic relation is both reflexive and symmetric and holds whenever regions a and b are “connected.” The two main axioms expressing reflexivity and symmetry [18] are as follows:
(3)∀a[C(a,a)](reflexive)∀a∀b[C(a,b)⟶C(b,a)](symmetric).
Based on this primitive, a basic set of dyadic relations are defined as shown in Table 1.Table 1
Spatial relations defined in terms of C(a,b) [18].
Relations
Semantics
Definition
DC(a,b)
a is disconnected from b
¬ C(a,b)
P(a,b)
a is part of b
∀
e
[
C
(
e
,
a
)
→
C
(
e
,
b
)
]
PP(a,b)
a is a proper part of b
P(a,b) ∧¬ P(b,a)
EQ(a,b)
a is identical with b
P(a,b) ∧ P(b,a)
O(a,b)
a overlaps b
∃
e
[P(e,a) ∧ P(e,b)]
DR(a,b)
a is discrete from b
¬ O(a,b)
PO(a,b)
a partially overlaps b
O(a,b)∧ ¬ P(a,b)∧ ¬ P(b,a)
EC(a,b)
a is externally connected to b
C(a,b)∧ ¬ O(a,b)
TPP(a,b)
a is a tangential proper part of b
PP(a,b)∧ ∃e[EC(e,a) ∧ EC(e,b)]
NTPP(a,b)
a is a nontangential proper part of b
PP(a,b)∧ ¬ ∃e[EC(e,a) ∧ EC(e,b)]The relations P, PP, TPP, and NTPP are nonsymmetrical and will have their respective inverses (Pi, PPi, TPPi, and NTPPi). Of all the listed relations, only 8 relations in the following set {DC, EC, PO, EQ, TPP, NTPP, TPPi, NTPPi} are provably jointly exhaustive and pairwise disjoint (JEPD—which means any two regions are related by exactly one of these eight relations [34, 35]). Randell and colleagues [13] refer this set of relations as RCC-8, and they are depicted in Figure 6.Figure 6
8 basic JEPD RCC binary relations [13].


## 5. Expressive Hybrid Model

In our expressive hybrid model, we have combined ourHorizontal and Vertical Constraints Model [29, 30] and RCC-8 [13].


### 5.1. Definitions

If there is a referent regiona and another arbitrary region b, the possible basic binary relations between them can be defined as below.In terms of weak relations,(i)
WeakNorth(b,a): b⊆ WeakNorth(a),(ii)
Horizontal(b,a): b⊆ Horizontal(a),(iii)
WeakSouth(b,a): b⊆ WeakSouth(a),(iv)
WeakEast(b,a): b⊆ WeakEast(a),(v)
Vertical(b,a): b⊆ Vertical(a),(vi)
WeakWest(b,a): b⊆ WeakWest(a).In terms of RCC-8 relations,(i)
DCy(a,b): y-dimension of a is disconnected from y-dimension of b,(ii)
EQy(a,b): y-dimension of a is identical with y-dimension of b,(iii)
POy(a,b): y-dimension of a partially overlaps y-dimension of b,(iv)
ECy(a,b): y-dimension of a is externally connected to y-dimension of b,(v)
TPPy(a,b): y-dimension of a is a tangential proper part of y-dimension of b,(vi)
NTPPy(a,b): y-dimension of a is a nontangential proper part of y-dimension of b,(vii)
TPPiy(a,b): y-dimension of b is a tangential proper part of y-dimension of a,(viii)
NTPPiy(a,b): y-dimension of b is a non-tangential proper part of y-dimension of a,(ix)
DCx(a,b): x-dimension of a is disconnected from x-dimension of b,(x)
EQx(a,b): x-dimension of a is identical with x-dimension of b,(xi)
POx(a,b): x-dimension of a partially overlaps x-dimension of b,(xii)
ECx(a,b): x-dimension of a is externally connected to x-dimension of b,(xiii)
TPPx(a,b): x-dimension of a is a tangential proper part of x-dimension of b,(xiv)
NTPPx(a,b): x-dimension of a is a non-tangential proper part of x-dimension of b,(xv)
TPPix(a,b): x-dimension of b is a tangential proper part of x-dimension of a,(xvi)
NTPPix(a,b): x-dimension of b is a non-tangential proper part of x-dimension of a.


### 5.2. Basic Binary Relations of the Hybrid Model

In this section, we shall demonstrate how we come up with all possible binary direction relations for the hybrid model. All the possible basic binary relations for each horizontal set are shown in Figure7. The notations that will be used in this section are as follows.(i)
RELy(b,Z) is any basic binary relation between b and the horizontally partitioned region, Z.(ii)
RELx(b,Z) is any basic binary relation between b and the vertically partitioned region, Z.Figure 7
Possible basic binary relations for each horizontally partitioned region (note: it will be similar for vertically partitioned region).Based on Figure7, the total number of possible binary relations for the hybrid model in the y-direction is [(2+4+2)+(2×4)+(2×2)+(4×2)+(2×4×2)] which equals 44 cases. However, due to the single-piece condition, the following rules apply.Rule 1.
¬(b⊆ WeakNorth(a) ∧b⊆ WeakSouth(a)).Rule 2.
AssumeU to be {WeakNorth(a), Horizontal(a), WeakSouth(a)}. If NTPPy(b,R) where R∈U then ¬(NTPPy(b,R) ∧ RELy(b,S)),whereS∈U-R, or ¬(NTPPy(b,R)∧ RELy(b,S) ∧ RELy(b,T)),whereT∈U-S.Rule 3.
AssumeU to be {WeakNorth(a), WeakSouth(a)}.
If (TPPy(b,Horizontal(a)) ∧ ECy(b,R)), where R∈U,
then¬(TPPy(b,Horizontal) ∧ ECy(b,R)∧ RELy(b,S)),
whereS∈U-R.Based on the rules above, the total number of feasible binary relations for single-piece regions in they-direction is (44-4-23-4) which equals 13 cases. The thirteen feasible and jointly exhaustive binary relations for the hybrid model are depicted in Figure 8. This means that, in the hybrid model, the number of jointly exhaustive binary relations (in both the x- and y-directions) that hold between two single-piece regions will be 13×13. This concurs with the 13×13 basic relations in the Rectangle Algebra Model [16, 17].Figure 8
Thirteen feasible and jointly exhaustive binary relations in they-direction for the hybrid model (note: this will be similar for x-direction for the model).


## 5.1. Definitions

If there is a referent regiona and another arbitrary region b, the possible basic binary relations between them can be defined as below.In terms of weak relations,(i)
WeakNorth(b,a): b⊆ WeakNorth(a),(ii)
Horizontal(b,a): b⊆ Horizontal(a),(iii)
WeakSouth(b,a): b⊆ WeakSouth(a),(iv)
WeakEast(b,a): b⊆ WeakEast(a),(v)
Vertical(b,a): b⊆ Vertical(a),(vi)
WeakWest(b,a): b⊆ WeakWest(a).In terms of RCC-8 relations,(i)
DCy(a,b): y-dimension of a is disconnected from y-dimension of b,(ii)
EQy(a,b): y-dimension of a is identical with y-dimension of b,(iii)
POy(a,b): y-dimension of a partially overlaps y-dimension of b,(iv)
ECy(a,b): y-dimension of a is externally connected to y-dimension of b,(v)
TPPy(a,b): y-dimension of a is a tangential proper part of y-dimension of b,(vi)
NTPPy(a,b): y-dimension of a is a nontangential proper part of y-dimension of b,(vii)
TPPiy(a,b): y-dimension of b is a tangential proper part of y-dimension of a,(viii)
NTPPiy(a,b): y-dimension of b is a non-tangential proper part of y-dimension of a,(ix)
DCx(a,b): x-dimension of a is disconnected from x-dimension of b,(x)
EQx(a,b): x-dimension of a is identical with x-dimension of b,(xi)
POx(a,b): x-dimension of a partially overlaps x-dimension of b,(xii)
ECx(a,b): x-dimension of a is externally connected to x-dimension of b,(xiii)
TPPx(a,b): x-dimension of a is a tangential proper part of x-dimension of b,(xiv)
NTPPx(a,b): x-dimension of a is a non-tangential proper part of x-dimension of b,(xv)
TPPix(a,b): x-dimension of b is a tangential proper part of x-dimension of a,(xvi)
NTPPix(a,b): x-dimension of b is a non-tangential proper part of x-dimension of a.


## 5.2. Basic Binary Relations of the Hybrid Model

In this section, we shall demonstrate how we come up with all possible binary direction relations for the hybrid model. All the possible basic binary relations for each horizontal set are shown in Figure7. The notations that will be used in this section are as follows.(i)
RELy(b,Z) is any basic binary relation between b and the horizontally partitioned region, Z.(ii)
RELx(b,Z) is any basic binary relation between b and the vertically partitioned region, Z.Figure 7
Possible basic binary relations for each horizontally partitioned region (note: it will be similar for vertically partitioned region).Based on Figure7, the total number of possible binary relations for the hybrid model in the y-direction is [(2+4+2)+(2×4)+(2×2)+(4×2)+(2×4×2)] which equals 44 cases. However, due to the single-piece condition, the following rules apply.Rule 1.
¬(b⊆ WeakNorth(a) ∧b⊆ WeakSouth(a)).Rule 2.
AssumeU to be {WeakNorth(a), Horizontal(a), WeakSouth(a)}. If NTPPy(b,R) where R∈U then ¬(NTPPy(b,R) ∧ RELy(b,S)),whereS∈U-R, or ¬(NTPPy(b,R)∧ RELy(b,S) ∧ RELy(b,T)),whereT∈U-S.Rule 3.
AssumeU to be {WeakNorth(a), WeakSouth(a)}.
If (TPPy(b,Horizontal(a)) ∧ ECy(b,R)), where R∈U,
then¬(TPPy(b,Horizontal) ∧ ECy(b,R)∧ RELy(b,S)),
whereS∈U-R.Based on the rules above, the total number of feasible binary relations for single-piece regions in they-direction is (44-4-23-4) which equals 13 cases. The thirteen feasible and jointly exhaustive binary relations for the hybrid model are depicted in Figure 8. This means that, in the hybrid model, the number of jointly exhaustive binary relations (in both the x- and y-directions) that hold between two single-piece regions will be 13×13. This concurs with the 13×13 basic relations in the Rectangle Algebra Model [16, 17].Figure 8
Thirteen feasible and jointly exhaustive binary relations in they-direction for the hybrid model (note: this will be similar for x-direction for the model).


## 6. Combined Mereological, Topological, and Cardinal Direction Relations

Mereology (from the Greekμερος, “part”) is the theory of parthood relations: of the relations of part to whole and the relations, of part to part within a whole [36]. In this section, we shall make two distinctions: “whole and part” cardinal directions, as well as “weak and expressive” relations. We shall rewrite the notations used in our previous paper [29]. PR(b,a)means that only part of the destination extended region, b, is in tile R(a). The direction relation AR(b,a)means that whole destination extended region, b, is in the tile R(a). As an example, when b is completely in the South-East tile of a, this direction relation can be represented as shown below:
(4)ASE(b,a)=¬PN(b,a)∧¬PNE(b,a)∧¬PNW(b,a)∧¬PS(b,a)∧PSE(b,a)∧¬PSW(b,a)∧¬PW(b,a)∧¬PE(b,a)∧¬PO(b,a).The “whole and weak” direction relations are defined in terms of horizontal and vertical sets:(i)
AN(b,a)≡ WeakNorth(b,a) ∧ Vertical(b,a),(ii)
ANE(b,a)≡ WeakNorth(b,a) ∧ WeakEast(b,a),(iii)
ANW(b,a)≡ WeakNorth(b,a) ∧ WeakWest(b,a),(iv)
AS(b,a)≡ WeakSouth(b,a) ∧ Vertical(b,a),(v)
ASE(b,a)≡ WeakSouth(b,a) ∧ WeakEast(b,a),(vi)
ASW(b,a)≡ WeakSouth(b,a) ∧ WeakWest(b,a),(vii)
AE(b,a)≡ Horizontal(b,a) ∧ WeakEast(b,a),(viii)
AW(b,a)≡ Horizontal(b,a) ∧ WeakWest(b,a),(ix)
AO(b,a)≡ Horizontal(b,a) ∧ Vertical(b,a).The “whole and expressive” direction relations are defined in terms of expressive horizontal and vertical sets. A general form of such direction relation can be represented as follows:
(5)[AR(b,a)]RELx(b,V(a))RELy(b,H(a))≡RELy(b,H(a))∧RELx(b,V(a)),
where H(a) and V(a) are horizontally and vertically partitioned regions for a, respectively, where b⊆R(a) and R(a) ⊆ (H(a) ∩ V(a)).


## 7. Composition Table

Composition is a common inference mechanism for a wide range of relations and has been exploited for automated reasoning. It has been employed for reasoning about temporal descriptions of events based on intervals [37], topological relations [5, 38–42], direction relations [1, 24, 29, 30], and combined topological relations with cardinal direction relations [19]. To reiterate, one of the main advantages of using composition tables is that they can lead to tractable computation of significant classes of inference [25].Given the relation betweena and b and the relation between b and c, a composition table allows for concluding the relation between a and c. Bennett [41] defines the concept of the composition of two binary relations as follows.  Given a theory Θ which is used to define a setβ of mutually exhaustive and pairwise disjoint dyadic relations (i.e., a basis set), the composition, Comp(R1, R2), of two relations R1 and R2 which are taken from ß is defined to be the disjunction of all relations R3 in ß, such that, for arbitrary constants a, b, and c, the formula R1(a,b)∧R2(b,c)∧R3(a,c) is consistent with Θ.


### 7.1. Composition of Regions with Parts

In our previous paper [29], the method for computing the composition of cardinal direction relations for part regions is not robust enough, because it does not hold for all cases. In order to address this problem, we introduce a formula (obtained through case analyses) for computing the composition of cardinal direction relations. The basis of the formula is to consider the direction relation between a and each individual part of b followed by the direction relation between each individual part of b and c.Assume that the region covers one or moretiles of region a while region c covers one or more tiles of b.The direction relation between a and b is R(b,a) while the direction relation between b and c is S(c,b). The composition of direction relations could be written as follows:
(6)R(b,a)∧S(c,b).
Firstly, establish the direction relation between a and each individual part of b:
(7)R(b,a)∧S(c,b)≡[R1(b1,a)∧R2(b2,a)⋯∧Rk(bk,a)]∧[S(c,b)],
where  1≤k≤9.Consider the direction relation of each individual part ofb and c. Equation (7) becomes
(8)[[R1(b1,a)∧S11(c1,b1)]∨[R1(b1,a)∧S12(c2,b1)]⋯∨[R1(b1,a)∧S1m(c1m,b1)]]∧[[R2(b2,a)∧S21(c1,b2)]∨[R2(b2,a)∧S22(c2,b2)]⋯∨[R2(b2,a)∧S2m(c2m,b2)]]∧⋯[[Rk(bk,a)∧Sk1(c1,bk)]∨[Rk(bk,a)∧Sk2(c2,bk)]⋯∨[Rk(bk,a)∧Skm(ckm,bk)]],
where 1≤k,m≤9.


### 7.2. Composition of Weak Direction Relations

Firstly, we shall demonstrate how to apply the formula for the composition of weak direction relations followed by more expressive direction relations.Type 1.
A
R(b,a)∧AR(c,b).
Find the composition ofAO(b,a)∧ASW(c,b).
Use (8) with k=1 and m=1:
(9)R1(b1,a)∧S11(c1,b1)≡AO(b,a)∧ASW(c,b)≡[Horizontal(b,a)∧Vertical(b,a)]∧[WeakSouth(c,b)∧WeakWest(c,b)]≡[Horizontal(b,a)∧WeakSouth(c,b)]∧[Vertical(b,a)∧WeakWest(c,b)].
The outcome of the composition is(10)[Horizontal(c,a)∨WeakSouth(c,a)]∧[Vertical(c,a)∨WeakWest(c,a)].
This means that the regionc⊆ O(a) ∨ W(a) ∨ S(a) ∨ SW(a).Type 2.
A
R(b,a)∧PR(c,b).
Find the composition ofAE(b,a)∧[PNW(c,b)∧PN(c,b)].
Use (8) with k=1, and 1≤m≤2:
(11)[[R1(b1,a)∧S11(c1,b1)]∨[R1(b1,a)∧S12(c2,b1)]]≡[[AE(b,a)∧ANW(c1,b)]∨[AE(b,a)∧AN(c2,b)]]≡[[Horizontal(b,a)∧WeakEast(b,a)]∧[WeakNorth(c1,b)∧WeakWest(c1,b)]]∨[[Horizontal(b,a)∧WeakEast(b,a)]∧[WeakNorth(c2,b)∧Vertical(c2,b)]]≡[[Horizontal(b,a)∧WeakNorth(c1,b)]∧[WeakEast(b,a)∧WeakWest(c1,b)]]∨[[Horizontal(b,a)∧WeakNorth(c2,b)]∧[WeakEast(b,a)∧Vertical(c2,b)]].
The outcome of the composition is(12)[[Horizontal(c1,a)∨WeakNorth(c1,a)]∧[WeakEast(c1,a)∨Vertical(c1,a)∨WeakWest(c1,a)]]∨[[Horizontal(c2,a)∨WeakNorth(c2,a)]∧[WeakEast(c2,a)]].
Viewing the fact thatc1⊂c and c2⊂c, the above outcome can be written as
(13)[[Horizontal(c,a)∨WeakNorth(c,a)]∧[WeakEast(c,a)∨Vertical(c,a)∨WeakWest(c,a)]].
This means that the regionc⊆ E(a) ∨ O(a) ∨ W(a) ∨ NE(a) ∨ N(a) ∨ NW(a).Type 3.
P
R(b,a) ∧AR(c,b).
Find the composition of[PO(b1,a)∧PN(b2,a)]∧ANE(c,b). Establish the relationship between c and each individual part of b. In this case, ANE(c,b), PNE(c,b1) and PNE(c,b2) holds (this is not necessarily true for all cases).
Use (8) with 1≤k≤2 and m=1. 									(14)[[PR1(b1,a)]∧[PR11(c1,b1)]]∧[[PR2(b2,a)]∧[PR21(c1,b2)]]≡[[PO(b1,a)]∧[PNE(c,b)]]∧[[PN(b2,a)]∧[PNE(c,b)]].
Therefore, the above composition can be rewritten as(15)[[PO(b1,a)]∧[PNE(c,b1)]]∧[[PN(b2,a)]∧[PNE(c,b2)]]≡[[Horizontal(b1,a)∧Vertical(b1,a)]∧[WeakNorth(c,b1)∧WeakEast(c,b1)]]∧[[WeakNorth(b2,a)∧Vertical(b2,a)]∧[WeakNorth(c,b2)∧WeakEast(c,b2)]]≡[[Horizontal(b1,a)∧WeakNorth(c,b1)]∧[Vertical(b1,a)∧WeakEast(c,b1)]]∧[[WeakNorth(b2,a)∧WeakNorth(c,b2)]∧[Vertical(b2,a)∧WeakEast(c,b2)]].
The outcome of the composition is(16)[[Horizontal(c,a)∨WeakNorth(c,a)]∧[WeakEast(c,a)∨Vertical(c,a)]]∧[[NTPPy(c,WeakNorth(a))]∧[WeakEast(c,a)∨Vertical(c,a)](a)2]=[[NTPPy(c,WeakNorth(a))]∧[WeakEast(c,a)∨Vertical(c,a)](a)2].
This means that theYmin(c) of the minimal bounding box for region c is greater than Ymax(a) of the minimal bounding box for region a and c⊆NE(a)∨N(a).Type 4.
P
R(b,a)∧PR(c,b).
Find the composition of(17)[PO(b1,a)∧PNE(b2,a)]∧[PO(c,b)∧PW(c,b)∧PSW(c,b)].
Figure9 has been drawn for this example. Establish the direction relation between each individual part of b and c.
Use (8) with 1≤k≤2; the value of m1 for b1 is 1≤m1≤4, while the value m2 for b2 is 1≤m2≤7:
(18)[[PR1(b1,a)∧PR11(c1,b1)]∨[PR1(b1,a)∧PR12(c2,b1)]∨[PR1(b1,a)∧PR13(c3,b1)]∨[PR1(b1,a)∧PR14(c4,b1)]]∧[[PR2(b2,a)∧PR21(c1,b2)]∨[PR2(b2,a)∧PR22(c2,b2)]∨[PR2(b2,a)∧PR25(c5,b2)]∨[PR2(b2,a)∧PR26(c6,b2)]∨[PR2(b2,a)∧PR27(c7,b2)]]≡[[PO(b1,a)∧PS(c1,b1)]∨[PO(b1,a)∧PSW(c2,b1)]∨[PO(b1,a)∧PW(c3,b1)]∨[PO(b1,a)∧PO(c4,b1)]]∧[[PNE(b2,a)∧PNE(c1,b2)]∨[PNE(b2,a)∧PN(c2,b2)]∨[PNE(b2,a)∧PNW(c3,b2)]∨[PNE(b2,a)∧PE(c4,b2)]∨[PNE(b2,a)∧PO(c5,b2)]∨[PNE(b2,a)∧PW(c6,b2)]∨[PNE(b2,a)∧PSW(c7,b2)]].Figure 9
An example.In part(1) of the above composition, c1,c2,c3,c4⊂c. To simplify the composition, we consider the combined horizontal and vertical sets of all the parts of c.Thus, we have the following:
(19)[WeakNorth(b1,a)∧WeakEast(b1,a)]∧[[Horizontal(c,b1)∨WeakSouth(c,b1)]∧[Vertical(c,b1)∨WeakWest(c,b1)]]≡[[WeakNorth(b1,a)]∧[Horizontal(c,b1)∨WeakSouth(c,b1)]]∧[[WeakEast(b1,a)]∧[Vertical(c,b1)∨WeakWest(c,b1)]]=[WeakNorth(c,a)∨Horizontal(c,a)∨WeakSouth(c,a)]∧[WeakEast(c,a)∨Vertical(c,a)∨WeakWest(c,a)].In part(2) of the above composition, c1, c2, c3, c4, c5, c6, c7⊂c. The simplified version of the composition is as follows:
(20)[Horizontal(b2,a)∧Vertical(b2,a)]∧[[WeakNorth(c,b2)∨Horizontal(c,b2)∨WeakSouth(c,b2)]∧[WeakEast(c,b2)∨Vertical(c,b2)∨WeakWest(c,b2)]]≡[[Horizontal(b2,a)]∧[WeakNorth(c,b2)∨Horizontal(c,b2)∨WeakSouth(c,b2)]]∧[[Vertical(b2,a)]∧[WeakEast(c,b2)∨Vertical(c,b2)∨WeakWest(c,b2)]]=[[WeakNorth(c,a)∨Horizontal(c,a)∨WeakSouth(c,a)]]∧[WeakEast(c,a)∨Vertical(c,a)∨WeakWest(c,a)]].The final outcome of the composition is part(1)∧ part (2) is equivalent to
(21)[WeakNorth(c,a)∨Horizontal(c,a)∨WeakSouth(c,a)]∧[WeakEast(c,a)∨Vertical(c,a)∨WeakWest(c,a)].This means that the regionc⊆Uwhich is the union of all the 9 tiles of region a. However, based on Figure 9, region c⊄SW(a).


### 7.3. Composition of Expressive Direction Relations

We shall use the following notations to represent the 13 binaryy-direction relations:(i)
REL1y(b,a)-NTPPy(b,WeakNorth(a)),(ii)
REL2y(b,a)-TPPy(b,WeakNorth(a)) ∧ ECy(b,Horizontal(a)),(iii)
REL3y(b,a)-TPPy(b,Horizontal(a)) ∧ ECy(b,WeakNorth(a)),(iv)
REL4y(b,a)-TPPy(b,Horizontal(a)) ∧ ECy(b,WeakSouth(a)),(v)
REL5y(b,a)-NTPPy(b,Horizontal(a)),(vi)
REL6y(b,a)-EQy(b,Horizontal(a)),(vii)
REL7y(b,a)-NTPPy(b,WeakSouth(a)),(viii)
REL8y(b,a)-TPPy(b,WeakSouth(a)) ∧ ECy(b,Horizontal(a)),(ix)
REL9y(b,a)-POy(b,WeakNorth(a)) ∧ POy(b,Horizontal(a)) ∧  DCy(b,WeakSouth(a)),(x)
REL10y(b,a)-POy(b,WeakNorth(a)) ∧ POy(b,Horizontal(a)) ∧  ECy(b,WeakSouth(a)),(xi)
REL11y(b,a)-POy(b,WeakNorth(a)) ∧ POy(b,WeakSouth(a)) ∧  NTPPiy(b,Horizontal(a)),(xii)
REL12y(b,a)-POy(b,WeakSouth(a)) ∧ POy(b,Horizontal(a)) ∧  DCy(b,WeakNorth(a)),(xiii)
REL13y(b,a)-POy(b,WeakSouth(a)) ∧ POy(b,Horizontal(a)) ∧  ECy(b,WeakNorth(a)).Similar notations will be used to represent the 13 binaryx-direction relations (WeakNorth is replaced by WeakEast, Horizontal with Vertical, and WeakSouth by WeakWest).Example 1.
Find the composition of the following:(22)[[REL3y(b1,a)[PO(b1,a)]REL3x(b1,a)]∧[REL2y(b2,a)[PNE(b2,a)]REL2x(b2,a)]]∧[REL1y(c,b)[AN(c,b)]REL5x(c,b)].
Establish the direction relation betweenc and each individual part of b. Use (8), with 1≤k≤2 and 1≤m1≤2, and 1≤m2≤2:
(23)[[PR1(b1,a)]∧[PR11(c1,b1)∨PR12(c2,b1)]]∧[[PR2(b2,a)]∧[PR21(c1,b2)∨PR22(c2,b2)]].
Use (5), and the above composition can be rewritten in the following expressive form:
(24)[[REL3y(b1,a)∧REL3x(b1,a)]]∧[[REL1y(c1,b1)∧REL3x(c1,b1)]∨[REL1y(c2,b1)∧REL2x(c2,b1)]]∧[[REL2y(b2,a)∧REL2x(b2,a)]]∧[[REL1y(c1,b2)∧REL8x(c1,b2)]∨[REL1y(c2,b2)∧REL4x(c2,b2)]]≡[REL3y(b1,a)∧[REL1y(c1,b1)∨REL1y(c2,b1)]]∧[REL3x(b1,a)∧[REL3x(c1,b1)∨REL2x(c2,b1)]]∧[REL2y(b2,a)∧[REL1y(c1,b2)∨REL1y(c2,b2)]]∧[REL2x(b2,a)∧[REL8x(c1,b2)∨REL4x(c2,b2)]].
Use Tables2 and 3, and c1⊂c and c2⊂c. Thus, the outcome of the composition can be written as follows:
(25)REL1y(c,a)∧[REL2x(c,a)∨REL3x(c,a)]∧REL1y(c,a)∧[REL2x(c,a)∨REL3x(c,a)∨REL6x(c,a)∨REL13x(c,a)]=REL1y(c,a)∧[REL2x(c,a)∨REL3x(c,a)].
The outcome of the composition is:(26)NTPPy(c,WeakNorth(a))∧[TPPx(c,WeakEast(a))∧ECy(c,Horizontal(a))∨TPPx(c,Vertical(a))∧ECy(c,Horizontal(a))].Table 2
(a) Composition of binary relations in they-direction for the hybrid model (composed relations of {WN} and {WN,H}). (b) Composition of binary relations in the y-direction for the hybrid model (composed relations of {H} and {WN,H}). (c) Composition of binary relations in the y-direction for the hybrid model (composed relations of {S} and {WN,H}). (d) Composition of binary relations in the y-direction for the hybrid model (composed relations of {WN,H,S} and {WS}).
(a)
Composed relations of  {WN} and {WN,H}
WN(c,b)
H(c,b)
NTPPy(c,WN(b))
TPPy(c,WN(b))∧ ECy(c,H(b))
TPPy(c,H(b))∧ ECy(c,WN(b))
TPPy(c,H(b))∧ ECy(c,WS(b))
NTPPy(c,H(b))
EQy(c,H(b))
NTPPy(b,WN(a))
NTPPy(c,WN(a))
NTPPy(c,WN(a))
NTPPy(c,WN(a))
NTPPy(c,WN(a))
NTPPy(c,WN(a))
NTPPy(c,WN(c))
WN(b,a)
TPPy(b,WN(a))∧ ECy(b,H(a))
NTPPy(c,WN(a))
NTPPy(c,WN(a))
NTPPy(c,WN(a))
TPPy(c,WN(a)) ∧ ECy(c,H(a))
NTPPy(c,WN(a))
TPPy(c,WN(a)) ∧ ECy(c,H(a))
WN(b,a)
NTPPy(c,WN(a))
WN(c,a)
Note: the data in bold are results of the composition of relations.
(b)
Composed relations of  {H} and {WN,H}
WN(c,b)
H(c,b)
NTPPy(c,WN(b))
TPPy(c,WN(b))∧ ECy(c,H(b))
TPPy(c,H(b))∧ ECy(c,WN(b))
TPPy(c,H(b))∧ ECy(c,WS(b))
NTPPy(c,H(b))
EQy(c,H(b))
H(b,a)
TPPy(b,H(a))∧ ECy(b,WN(a))
NTPPy(c,WN(a))
TPPy(c,WN(a)) ∧ ECy(c,H(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
NTPPy(c,H(a))
NTPPy(c,H(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
TPPy(b,H(a))∧ ECy(b,WS(a))
[
NTPPy(c,H(a))
]
∨ [TPPy(c,H(a)) ∧ ECy(c,WN(a))]∨ [TPPy(c,WN(a)) ∧ ECy(c,H(a))]∨ [NTPPy(c,WN(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ DCy(c,WS(a))]
[
NTPPy(c,H(a))
]
∨ [PPy(c,H(a)) ∧ ECy(c,WN(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ DCy(c,WS(a))]
NTPPy(c,H(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
NTPPy(c,H(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
NTPPy(b,H(a))
[
NTPPy(c,H(a))
]
∨ [TPPy(c,H(a)) ∧ ECy(c,WN(a))]∨ [TPPy(c,WN(a)) ∧ ECy(c,H(a))]∨ [NTPPy(c,WN(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ DCy(c,WS(a))]
[
NTPPy(c,H(a))
]
∨ [TPPy(c,H(a)) ∧ ECy(c,WN(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ DCy(c,WS(a))]
NTPPy(c,H(a))
NTPPy(c,H(a))
NTPPy(c,H(a))
NTPPy(c,H(a))
EQy(b,H(a))
NTPPy(c,WN(a))
TPPy(c,WN(a)) ∧ ECy(c,H(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
TPPy(c,H(a)) ∧ ECy(c,WS(a))
NTPPy(c,H(a))
EQy(c,H(a))
H(b,a)
WN(c,a)
∨
H(c,a)
H(c,a)
Note: the data in bold are the results of the composition of relations.
(c)
Composed relations of  {S} and {WN,H}
WN(c,b)
H(c,b)
NTPPy(c,WN(b))
TPPy(c,WN(b))∧ ECy(c,H(b))
TPPy(c,H(b))∧ ECy(c,WN(b))
TPPy(c,H(b))∧ ECy(c,WS(b))
NTPPy(c,H(b))
EQy(c,H(b))
S(b,a)
NTPPy(b,WS(a))
U-13 relations
[
NTPPy(c,WS(a))
]
∨ [TPPy(c,WS(a)) ∧ ECy(c,H(a))]∨ [POy(c,WS(a)) ∧ POy(c,H(a)) ∧ DCy(c,WN(a))]∨ [POy(c,WS(a)) ∧ POy(c,H(a)) ∧ ECy(c,WN(a))]∨ [POy(c,WS(a)) ∧ POy(c,WN(a)) ∧ NTPPiy(c,H(a))]
NTPPy(c,WS(a))
NTPPy(c,WS(a))
NTPPy(c,WS(a))
NTPPy(c,WS(a))
TPPy(b,WS(a))∧ ECy(b,H(a))
[
NTPPy(c,H(a))
]
∨ [TPPy(c,H(a)) ∧ ECy(c,WN(a))]∨ [TPPy(c,WN(a)) ∧ ECy(c,H(a))]∨ [NTPPy(c,WN(a))] ∨[POy(c,WN(a)) ∧ POy(c,H(a)) ∧ DCy(c,WS(a))]
[
TPPy(c,H(a)) ∧ ECy(c,WS(a))]∨ [EQy(c,H(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ ECy(c,WS(a))]
TPPy(c,WS(a)) ∧ ECy(c,H(a))
NTPPy(c,WS(a))
NTPPy(c,WS(a))
TPPy(c,WS(a)) ∧ ECy(c,H(a))
S(b,a)
WN(c,a) ∨ H(c,a) ∨ WS(c,a)
WS(c,a)
Note: the data in bold are the results of the composition of relations.
(d)
Composed relations of  {WN,H,S} and {WS}
WS(c,b)
WN(b,a)
NTPPy(b,WN(a))
NTPPy(c,WS(b))
TPPy(c,WS(b)) ∧ ECy(c,H(b))
TPPy(b,WN(a)) ∧ ECy(b,H(a))
U-13 relations
[
NTPPy(c,WN(a))
]
∨ [TPPy(c,WN(a)) ∧ ECy(c,H(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ DCy(c,WS(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ ECy(c,WS(a))]∨ [POy(c,WN(a)) ∧ POy(c,WS(a)) ∧ NTPPiy(c,H(a))]
WN(b,a)
WN(c,a) ∨ H(c,a) ∨ WS(c,a)
H(b,a)
TPPy(b,H(a)) ∧ ECy(b,WN(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
[
NTPPy(c,H(a))
]
∨ [TPPy(c,H(a)) ∧ ECy(c,WS(a))]∨ [TPPy(c,WS(a)) ∧ ECy(c,H(a))]∨ [NTPPy(c,WS(a))]∨ [POy(c,WS(a)) ∧ POy(c,H(a)) ∧ DCy(c,WN(a))]
TPPy(b,H(a)) ∧ ECy(b,WS(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
NTPPy(c,WS(a))
NTPPy(b,H(a))
[
NTPPy(c,H(a))] ∨ [TPPy(c,H(a)) ∧ ECy(c,WS(a))]∨ [TPPy(c,WS(a)) ∧ ECy(c,H(a))]∨ [NTPPy(c,WS(a))]∨ [POy(c,WS(a)) ∧ POy(c,H(a)) ∧ DCy(c,WN(a))]
[
NTPPy(c,H(a))
]
∨ [TPPy(c,H(a)) ∧ ECy(c,WS(a))]∨ [POy(c,WS(a)) ∧ POy(c,H(a)) ∧ DCy(c,WN(a))]
EQy(b,H(a))
NTPPy(c,WS(a))
TPPy(c,WS(a)) ∧ ECy(c,H(a))
H(b,a)
H(c,a) ∨ WS(c,a)
S(b,a)
NTPPy(b,WS(a))
NTPPy(c,WS(a))
NTPPy(c,WS(a))
TPPy(b,WS(a)) ∧ ECy(b,H(a))
NTPPy(c,WS(a))
NTPPy(c,WS(a))
S(b,a)
NTPPy(c,WS(a))
Note: the data in bold are the results of the composition of relations.Table 3
(a) Composition of binary relations in thex-direction for the hybrid model (composed relations of {WE} and {WE,V,WW}). (b) Composition of binary relations in the x-direction for the hybrid model (part 1: composed relations of {V} and {WE,V,WW}). (c) Composition of binary relations in the x-direction for the hybrid model (part 2: composed relations of {V} and {WE,V,WW}). (d) Composition of binary relations in the x-direction for the hybrid model (part 2: composed relations of {WW} and {WE,V,WW}).
(a)
Composed relations of  {WE} and {WE,V,WW}
WE(c,b)
V(c,b)
WW(c,b)
NTPPx(c,WE(b))
TPPx(c,WE(b))∧ECx(c,V(b))
TPPx(c,V(b))∧ECx(c,WE(b))
TPPx(c,V(b))∧ECx(c,WW(b))
NTPPx(c,V(b))
EQx(c,V(b))
NTPPx(c,WW(b))
TPPx(c,WW(b))∧ECx(c,V(b))
WE(b,a)
NTPPx(b,WE(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
U-13 relations
[
NTPPx(c,WE(a))
] ∨[TPPx(c,WE(a)) ∧ ECx(c,V(a))]∨ [POx(c,WE(a)) ∧ POx(c,V(a)) ∧ DCy(c,WW(a))]∨ [POx(c,WE(a)) ∧ POx(c,V(a)) ∧ ECx(c,WW(a))]∨ [POx(c,WE(a)) ∧ POx(c,WW(a)) ∧ NTPPix(c,V(a))]
TPPx(b,WE(a))∧ECx(b,V(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
TPPx(c,WE(a)) ∧ ECx(c,V(a))
NTPPx(c,WE(a))
TPPx(c,WE(a)) ∧ ECx(c,V(a))
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WW(a))]∨ [TPPx(c,WW(a))∧ ECx(c,V(a))]∨[NTPPx(c,WW(a))]∨[POx(c,WW(a))∧ POx(c,V(a)) ∧ DCy(c,WE(a))]
[
TPPx(c,V(a)) ∧ ECx(c,WE(a))]∨ [EQx(c,V(a))]∨ [POx(c,WW(a)) ∧ POx(c,V(a)) ∧ ECx(c,WE(a))]
WE(b,a)
NTPPx(c,WE(a))
WE(c,a)
WE(c,a) ∨ V(c,a) ∨ WW(c,a)
Note: the data in bold are the results of the composition of relations.
(b)
Part 1 of composed relations of  {V} and {WE,V,WW}
WE(c,b)
V(c,b)
WW(c,b)
NTPPx(c,WE(b))
TPPx(c,WE(b))∧ECx(c,V(b))
TPPx(c,V(b))∧ECx(c,WE(b))
TPPx(c,V(b))∧ECx(c,WW(b))
NTPPx(c,V(b))
EQx(c,V(b))
NTPPx(c,WW(b))
TPPx(c,WW(b))∧ECx(c,V(b))
V(b,a)
TPPx(b,V(a))∧ECx(b,WE(a))
NTPPx(c,WE(a))
TPPx(c,WE(a)) ∧ ECx(c,V(a))
TPPx(c,V(a)) ∧ ECx(c,WE(a))
NTPPx(c,V(a))
NTPPx(c,V(a))
TPPx(c,V(a)) ∧ ECx(c,WE(a))
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WW(a))]∨ [TPPx(c,WW(a)) ∧ ECx(c,V(a))]∨ [NTPPx(c,WW(a))] ∨[POx(c,WW(a)) ∧ POx(c,V(a)) ∧ DCy(c,WE(a))]
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WW(a))]∨ [POx(c,WW(a)) ∧ POx(c,V(a)) ∧ DCy(c,WE(a))]
TPPx(b,V(a))∧ECx(b,WW(a))
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WE(a))]∨ [TPPx(c,WE(a)) ∧ ECx(c,V(a))]∨ [NTPPx(c,WE(a))]∨[POx(c,WE(a)) ∧ POx(c,V(a)) ∧ DCy(c,WW(a))]
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WE(a))]∨ [POx(c,WE(a)) ∧ POx(c,V(a)) ∧ DCy(c,WW(a))]
NTPPx(c,V(a))
TPPx(c,V(a)) ∧ ECx(c,WE(a))
NTPPx(c,V(a))
TPPx(c,V(a)) ∧ ECx(c,WE(a))
NTPPx(c,WW(a))
TPPx(c,WW(a)) ∧ ECx(c,V(a))
Note: the data in bold are the results of the composition of relations.
(c)
Part 2 of composed relations of  {V} and {WE,V,WW}
WE(c,b)
V(c,b)
WW(c,b)
NTPPx(c,WE(b))
TPPx(c,WE(b))∧ECx(c,V(b))
TPPx(c,V(b))∧ECx(c,WE(b))
TPPx(c,V(b))∧ECx(c,WW(b))
NTPPx(c,V(b))
EQx(c,V(b))
NTPPx(c,WW(b))
TPPx(c,WW(b))∧ECx(c,V(b))
V(b,a)
NTPPx(b,V(a))
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WE(a))]∨ [TPPx(c,WE(a)) ∧ ECx(c,V(a))]∨ [NTPPx(c,WE(a))] ∨[POx(c,WE(a)) ∧ POx(c,V(a)) ∧ DCy(c,WW(a))]
[
NTPPx(c,V(a))
]
∨
[
TPPx(c,V(a)) ∧
ECx(c,WE(a))
]
∨
[
POx(c,WE(a)) ∧POx(c,V(a)) ∧DCy(c,WW(a))]
NTPPx(c,V(a))
NTPPx(c,V(a))
NTPPx(c,V(a))
NTPPx(c,V(a))
[
NTPPx(c,V(a))
]
∨
[
TPPx(c,V(a)) ∧
ECx(c,WW(a))
]
∨
[
TPPx(c,WW(a)) ∧
ECx(c,V(a))
]
∨
[
NTPPx(c,WW(a))
]
∨
[
POx(c,WW(a)) ∧
POx(c,V(a)) ∧
DCy(c,WE(a))
]
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WW(a))]∨ [POx(c,WW(a)) ∧ POx(c,V(a)) ∧ DCy(c,WE(a))]
EQx(b,V(a))
NTPPx(c,WE(a))
TPPx(c,WE(a)) ∧ ECx(c,V(a))
TPPx(c,V(a)) ∧ ECx(c,WE(a))
TPPx(c,V(a)) ∧ ECx(c,WW(a))
NTPPx(c,V(a))
EQx(c,V(a))
NTPPx(c,WW(a))
TPPx(c,WW(a)) ∧ ECx(c,V(a))
V(b,a)
WE(c,a) ∨ V(c,a)
V(c,a)
V(c,a) ∨ WW(c,a)
Note: the data in bold are the results of the composition of relations.
(d)
Composed relations of  {WW} and {WE,V,WW}
WE(c,b)
V(c,b)
WW(c,b)
NTPPx(c,WE(b))
TPPx(c,WE(b))∧ECx(c,V(b))
TPPx(c,V(b))∧ECx(c,WE(b))
TPPx(c,V(b))∧ECx(c,WW(b))
NTPPx(c,V(b))
EQx(c,V(b))
NTPPx(c,WW(b))
TPPx(c,WW(b)) ∧ECx(c,V(b))
WW(b,a)
NTPPx(b,WW(a))
U-13 relations
[
NTPPx(c,WW(a))
]
∨
[
TPPx(c,WW(a)) ∧ ECx(c,V(a))]∨ [POx(c,WW(a)) ∧ POx(c,V(a)) ∧ DCy(c,WE(a))]∨ [POx(c,WW(a)) ∧ POx(c,V(a)) ∧ ECx(c,WE(a))]∨ [POx(c,WW(a)) ∧ POx(c,WE(a)) ∧ NTPPix(c,V(a))]
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
TPPx(b,WW(a))∧ ECx(b,V(a))
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WE(a))]∨ [TPPx(c,WE(a)) ∧ ECx(c,V(a))]∨ [NTPPx(c,WE(a))]∨[POx(c,WE(a)) ∧ POx(c,V(a)) ∧ DCy(c,WW(a))]
[
TPPx(c,V(a)) ∧ ECx(c,WW(a))]∨ [EQx(c,V(a))]∨ [POx(c,WE(a)) ∧ POx(c,V(a)) ∧ ECx(c,WW(a))]
TPPx(c,WW(a))
∧ ECx(c,V(a))
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
TPPx(c,WW(a))
∧ ECx(c,V(a))
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
WW(b,a)
WE(c,a) ∨ V(c,a) ∨ WW(c,a)
WW(c,a)
NTPPx(c,WW(a))
Note: the data in bold are the results of the composition of relations.Example 2.
This example is similar to the fourth example in the previous section of this paper.
Find the composition of(27)[PO(b1,a)∧PNE(b2,a)]∧[PO(c,b)∧PW(c,b)∧PSW(c,b)].
Establish the direction relation betweenc and each individual part of b.Use (8), with 1≤k≤2 and 1≤m1≤4, and 1≤m2≤7.
The composition in expressive form will be as follows.For part
b
1,
(28)[[REL2y(b1,a)∧REL2x(b1,a)]]∧[[REL4y(c1,b1)∧REL4x(c1,b1)]∨[REL8y(c2,b1)∧REL4x(c2,b1)]∨[REL4y(c3,b1)∧REL8x(c3,b1)]∨[REL8y(c4,b1)∧REL8x(c4,b1)]].The regionsc1, c2, c3, c4⊂c; the above composition can be written as follows: (29a)[REL2y(b1,a)∧[REL4y(c,b1)∨REL8y(c,b1)∨REL4y(c,b1)∨REL8y(c,b1)]]∧[REL2x(b1,a)∧[REL4x(c,b1)∨REL4x(c,b1)∨REL8x(c,b1)∨REL8x(c,b1)]]=[REL2y(c,a)∨REL3y(c,a)∨REL6y(c,a)∨REL13y(c,a)]∧[REL2x(c,a)∨REL3x(c,a)∨REL6x(c,a)∨REL13x(c,a)].For part
b
2,
(29b)
[
[
REL
3
y
(
b
2
,
a
)
∧
REL
3
x
(
b
2
,
a
)
]
]
∧
[
[
REL
8
y
(
c
1
,
b
2
)
∧
REL
7
x
(
c
1
,
b
2
)
]
∨
[
REL
6
y
(
c
2
,
b
2
)
∧
REL
8
x
(
c
2
,
b
2
)
]
∨
[
REL
2
y
(
c
3
,
b
2
)
∧
REL
8
x
(
c
3
,
b
2
)
]
∨
[
REL
2
y
(
c
4
,
b
2
)
∧
REL
6
x
(
c
4
,
b
2
)
]
∨
[
REL
3
y
(
c
5
,
b
2
)
∧
REL
6
x
(
c
5
,
b
2
)
]
∨
[
REL
3
y
(
c
6
,
b
2
)
∧
REL
2
x
(
c
6
,
b
2
)
]
∨
[
REL
2
y
(
c
7
,
b
2
)
∧
REL
2
x
(
c
7
,
b
2
)
]
]
=
[
[
REL
2
y
(
c
,
a
)
∨
REL
3
y
(
c
,
a
)
∨
REL
5
y
(
c
,
a
)
∨
REL
12
y
(
c
,
a
)
]
∧
[
REL
2
x
(
c
,
a
)
∨
REL
3
x
(
c
,
a
)
∨
REL
4
x
(
c
,
a
)
∨
REL
5
x
(
c
,
a
)
∨
REL
7
x
(
c
,
a
)
∨
REL
8
x
(
c
,
a
)
∨
REL
12
x
(
c
,
a
)
]
]
.
The final outcome of the composition is the composition of part b1 (29a) ∧ part b2 (29b).Apply Rule3 from the earlier part of the paper, and we will get the following:
(30)[[REL2y(c,a)∨REL3y(c,a)∨REL6y(c,a)∨REL13y(c,a)]∧[REL2y(c,a)∨REL3y(c,a)∨REL12y(c,a)]∧[REL2x(c,a)∨REL3x(c,a)∨REL4x(c,a)∨REL8x(c,a)∨REL12x(c,a)]∧[REL2x(c,a)∨REL3x(c,a)∨REL6x(c,a)∨REL13x(c,a)][REL2y(c,a)∨REL3y(c,a)]].
We collapse some of the disjunction of relations:
(31)REL6y(c,a)∨REL13y(c,a)=REL13y(c,a)REL4x(c,a)∨REL8x(c,a)∨REL12x(c,a)=REL12y(c,a)REL6x(c,a)∨REL13x(c,a)=REL13x(c,a).
Equation (30) becomes (32)[REL2y(c,a)∨REL3y(c,a)∨REL13y(c,a)]∧[REL2y(c,a)∨REL3y(c,a)∨REL12y(c,a)]∧[REL2x(c,a)∨REL3x(c,a)∨REL12x(c,a)]∧[REL2x(c,a)∨REL3x(c,a)∨REL13x(c,a)].
Region c is single piece. Therefore, (32) becomes
(33)[POy(c,WeakNorth(a))∧POy(c,WeakSouth(a))∧NTPPiy(c,Horizontal(a))](34)∧[POx(c,WeakEast(a))∧POx(c,WeakWest(a))∧NTPPix(c,Vertical(a))].
This means that the region c⊆Uwhich is the union of all the 9 tiles of region a. As mentioned earlier, based on Figure 9, region c⊄SW(a). Thus, the outcome of the composition for weak relations (in the previous section) yields the same result as this composition. However, the computation for the latter is more tedious and complex when involving regions with many parts.


## 7.1. Composition of Regions with Parts

In our previous paper [29], the method for computing the composition of cardinal direction relations for part regions is not robust enough, because it does not hold for all cases. In order to address this problem, we introduce a formula (obtained through case analyses) for computing the composition of cardinal direction relations. The basis of the formula is to consider the direction relation between a and each individual part of b followed by the direction relation between each individual part of b and c.Assume that the region covers one or moretiles of region a while region c covers one or more tiles of b.The direction relation between a and b is R(b,a) while the direction relation between b and c is S(c,b). The composition of direction relations could be written as follows:
(6)R(b,a)∧S(c,b).
Firstly, establish the direction relation between a and each individual part of b:
(7)R(b,a)∧S(c,b)≡[R1(b1,a)∧R2(b2,a)⋯∧Rk(bk,a)]∧[S(c,b)],
where  1≤k≤9.Consider the direction relation of each individual part ofb and c. Equation (7) becomes
(8)[[R1(b1,a)∧S11(c1,b1)]∨[R1(b1,a)∧S12(c2,b1)]⋯∨[R1(b1,a)∧S1m(c1m,b1)]]∧[[R2(b2,a)∧S21(c1,b2)]∨[R2(b2,a)∧S22(c2,b2)]⋯∨[R2(b2,a)∧S2m(c2m,b2)]]∧⋯[[Rk(bk,a)∧Sk1(c1,bk)]∨[Rk(bk,a)∧Sk2(c2,bk)]⋯∨[Rk(bk,a)∧Skm(ckm,bk)]],
where 1≤k,m≤9.


## 7.2. Composition of Weak Direction Relations

Firstly, we shall demonstrate how to apply the formula for the composition of weak direction relations followed by more expressive direction relations.Type 1.
A
R(b,a)∧AR(c,b).
Find the composition ofAO(b,a)∧ASW(c,b).
Use (8) with k=1 and m=1:
(9)R1(b1,a)∧S11(c1,b1)≡AO(b,a)∧ASW(c,b)≡[Horizontal(b,a)∧Vertical(b,a)]∧[WeakSouth(c,b)∧WeakWest(c,b)]≡[Horizontal(b,a)∧WeakSouth(c,b)]∧[Vertical(b,a)∧WeakWest(c,b)].
The outcome of the composition is(10)[Horizontal(c,a)∨WeakSouth(c,a)]∧[Vertical(c,a)∨WeakWest(c,a)].
This means that the regionc⊆ O(a) ∨ W(a) ∨ S(a) ∨ SW(a).Type 2.
A
R(b,a)∧PR(c,b).
Find the composition ofAE(b,a)∧[PNW(c,b)∧PN(c,b)].
Use (8) with k=1, and 1≤m≤2:
(11)[[R1(b1,a)∧S11(c1,b1)]∨[R1(b1,a)∧S12(c2,b1)]]≡[[AE(b,a)∧ANW(c1,b)]∨[AE(b,a)∧AN(c2,b)]]≡[[Horizontal(b,a)∧WeakEast(b,a)]∧[WeakNorth(c1,b)∧WeakWest(c1,b)]]∨[[Horizontal(b,a)∧WeakEast(b,a)]∧[WeakNorth(c2,b)∧Vertical(c2,b)]]≡[[Horizontal(b,a)∧WeakNorth(c1,b)]∧[WeakEast(b,a)∧WeakWest(c1,b)]]∨[[Horizontal(b,a)∧WeakNorth(c2,b)]∧[WeakEast(b,a)∧Vertical(c2,b)]].
The outcome of the composition is(12)[[Horizontal(c1,a)∨WeakNorth(c1,a)]∧[WeakEast(c1,a)∨Vertical(c1,a)∨WeakWest(c1,a)]]∨[[Horizontal(c2,a)∨WeakNorth(c2,a)]∧[WeakEast(c2,a)]].
Viewing the fact thatc1⊂c and c2⊂c, the above outcome can be written as
(13)[[Horizontal(c,a)∨WeakNorth(c,a)]∧[WeakEast(c,a)∨Vertical(c,a)∨WeakWest(c,a)]].
This means that the regionc⊆ E(a) ∨ O(a) ∨ W(a) ∨ NE(a) ∨ N(a) ∨ NW(a).Type 3.
P
R(b,a) ∧AR(c,b).
Find the composition of[PO(b1,a)∧PN(b2,a)]∧ANE(c,b). Establish the relationship between c and each individual part of b. In this case, ANE(c,b), PNE(c,b1) and PNE(c,b2) holds (this is not necessarily true for all cases).
Use (8) with 1≤k≤2 and m=1. 									(14)[[PR1(b1,a)]∧[PR11(c1,b1)]]∧[[PR2(b2,a)]∧[PR21(c1,b2)]]≡[[PO(b1,a)]∧[PNE(c,b)]]∧[[PN(b2,a)]∧[PNE(c,b)]].
Therefore, the above composition can be rewritten as(15)[[PO(b1,a)]∧[PNE(c,b1)]]∧[[PN(b2,a)]∧[PNE(c,b2)]]≡[[Horizontal(b1,a)∧Vertical(b1,a)]∧[WeakNorth(c,b1)∧WeakEast(c,b1)]]∧[[WeakNorth(b2,a)∧Vertical(b2,a)]∧[WeakNorth(c,b2)∧WeakEast(c,b2)]]≡[[Horizontal(b1,a)∧WeakNorth(c,b1)]∧[Vertical(b1,a)∧WeakEast(c,b1)]]∧[[WeakNorth(b2,a)∧WeakNorth(c,b2)]∧[Vertical(b2,a)∧WeakEast(c,b2)]].
The outcome of the composition is(16)[[Horizontal(c,a)∨WeakNorth(c,a)]∧[WeakEast(c,a)∨Vertical(c,a)]]∧[[NTPPy(c,WeakNorth(a))]∧[WeakEast(c,a)∨Vertical(c,a)](a)2]=[[NTPPy(c,WeakNorth(a))]∧[WeakEast(c,a)∨Vertical(c,a)](a)2].
This means that theYmin(c) of the minimal bounding box for region c is greater than Ymax(a) of the minimal bounding box for region a and c⊆NE(a)∨N(a).Type 4.
P
R(b,a)∧PR(c,b).
Find the composition of(17)[PO(b1,a)∧PNE(b2,a)]∧[PO(c,b)∧PW(c,b)∧PSW(c,b)].
Figure9 has been drawn for this example. Establish the direction relation between each individual part of b and c.
Use (8) with 1≤k≤2; the value of m1 for b1 is 1≤m1≤4, while the value m2 for b2 is 1≤m2≤7:
(18)[[PR1(b1,a)∧PR11(c1,b1)]∨[PR1(b1,a)∧PR12(c2,b1)]∨[PR1(b1,a)∧PR13(c3,b1)]∨[PR1(b1,a)∧PR14(c4,b1)]]∧[[PR2(b2,a)∧PR21(c1,b2)]∨[PR2(b2,a)∧PR22(c2,b2)]∨[PR2(b2,a)∧PR25(c5,b2)]∨[PR2(b2,a)∧PR26(c6,b2)]∨[PR2(b2,a)∧PR27(c7,b2)]]≡[[PO(b1,a)∧PS(c1,b1)]∨[PO(b1,a)∧PSW(c2,b1)]∨[PO(b1,a)∧PW(c3,b1)]∨[PO(b1,a)∧PO(c4,b1)]]∧[[PNE(b2,a)∧PNE(c1,b2)]∨[PNE(b2,a)∧PN(c2,b2)]∨[PNE(b2,a)∧PNW(c3,b2)]∨[PNE(b2,a)∧PE(c4,b2)]∨[PNE(b2,a)∧PO(c5,b2)]∨[PNE(b2,a)∧PW(c6,b2)]∨[PNE(b2,a)∧PSW(c7,b2)]].Figure 9
An example.In part(1) of the above composition, c1,c2,c3,c4⊂c. To simplify the composition, we consider the combined horizontal and vertical sets of all the parts of c.Thus, we have the following:
(19)[WeakNorth(b1,a)∧WeakEast(b1,a)]∧[[Horizontal(c,b1)∨WeakSouth(c,b1)]∧[Vertical(c,b1)∨WeakWest(c,b1)]]≡[[WeakNorth(b1,a)]∧[Horizontal(c,b1)∨WeakSouth(c,b1)]]∧[[WeakEast(b1,a)]∧[Vertical(c,b1)∨WeakWest(c,b1)]]=[WeakNorth(c,a)∨Horizontal(c,a)∨WeakSouth(c,a)]∧[WeakEast(c,a)∨Vertical(c,a)∨WeakWest(c,a)].In part(2) of the above composition, c1, c2, c3, c4, c5, c6, c7⊂c. The simplified version of the composition is as follows:
(20)[Horizontal(b2,a)∧Vertical(b2,a)]∧[[WeakNorth(c,b2)∨Horizontal(c,b2)∨WeakSouth(c,b2)]∧[WeakEast(c,b2)∨Vertical(c,b2)∨WeakWest(c,b2)]]≡[[Horizontal(b2,a)]∧[WeakNorth(c,b2)∨Horizontal(c,b2)∨WeakSouth(c,b2)]]∧[[Vertical(b2,a)]∧[WeakEast(c,b2)∨Vertical(c,b2)∨WeakWest(c,b2)]]=[[WeakNorth(c,a)∨Horizontal(c,a)∨WeakSouth(c,a)]]∧[WeakEast(c,a)∨Vertical(c,a)∨WeakWest(c,a)]].The final outcome of the composition is part(1)∧ part (2) is equivalent to
(21)[WeakNorth(c,a)∨Horizontal(c,a)∨WeakSouth(c,a)]∧[WeakEast(c,a)∨Vertical(c,a)∨WeakWest(c,a)].This means that the regionc⊆Uwhich is the union of all the 9 tiles of region a. However, based on Figure 9, region c⊄SW(a).


## 7.3. Composition of Expressive Direction Relations

We shall use the following notations to represent the 13 binaryy-direction relations:(i)
REL1y(b,a)-NTPPy(b,WeakNorth(a)),(ii)
REL2y(b,a)-TPPy(b,WeakNorth(a)) ∧ ECy(b,Horizontal(a)),(iii)
REL3y(b,a)-TPPy(b,Horizontal(a)) ∧ ECy(b,WeakNorth(a)),(iv)
REL4y(b,a)-TPPy(b,Horizontal(a)) ∧ ECy(b,WeakSouth(a)),(v)
REL5y(b,a)-NTPPy(b,Horizontal(a)),(vi)
REL6y(b,a)-EQy(b,Horizontal(a)),(vii)
REL7y(b,a)-NTPPy(b,WeakSouth(a)),(viii)
REL8y(b,a)-TPPy(b,WeakSouth(a)) ∧ ECy(b,Horizontal(a)),(ix)
REL9y(b,a)-POy(b,WeakNorth(a)) ∧ POy(b,Horizontal(a)) ∧  DCy(b,WeakSouth(a)),(x)
REL10y(b,a)-POy(b,WeakNorth(a)) ∧ POy(b,Horizontal(a)) ∧  ECy(b,WeakSouth(a)),(xi)
REL11y(b,a)-POy(b,WeakNorth(a)) ∧ POy(b,WeakSouth(a)) ∧  NTPPiy(b,Horizontal(a)),(xii)
REL12y(b,a)-POy(b,WeakSouth(a)) ∧ POy(b,Horizontal(a)) ∧  DCy(b,WeakNorth(a)),(xiii)
REL13y(b,a)-POy(b,WeakSouth(a)) ∧ POy(b,Horizontal(a)) ∧  ECy(b,WeakNorth(a)).Similar notations will be used to represent the 13 binaryx-direction relations (WeakNorth is replaced by WeakEast, Horizontal with Vertical, and WeakSouth by WeakWest).Example 1.
Find the composition of the following:(22)[[REL3y(b1,a)[PO(b1,a)]REL3x(b1,a)]∧[REL2y(b2,a)[PNE(b2,a)]REL2x(b2,a)]]∧[REL1y(c,b)[AN(c,b)]REL5x(c,b)].
Establish the direction relation betweenc and each individual part of b. Use (8), with 1≤k≤2 and 1≤m1≤2, and 1≤m2≤2:
(23)[[PR1(b1,a)]∧[PR11(c1,b1)∨PR12(c2,b1)]]∧[[PR2(b2,a)]∧[PR21(c1,b2)∨PR22(c2,b2)]].
Use (5), and the above composition can be rewritten in the following expressive form:
(24)[[REL3y(b1,a)∧REL3x(b1,a)]]∧[[REL1y(c1,b1)∧REL3x(c1,b1)]∨[REL1y(c2,b1)∧REL2x(c2,b1)]]∧[[REL2y(b2,a)∧REL2x(b2,a)]]∧[[REL1y(c1,b2)∧REL8x(c1,b2)]∨[REL1y(c2,b2)∧REL4x(c2,b2)]]≡[REL3y(b1,a)∧[REL1y(c1,b1)∨REL1y(c2,b1)]]∧[REL3x(b1,a)∧[REL3x(c1,b1)∨REL2x(c2,b1)]]∧[REL2y(b2,a)∧[REL1y(c1,b2)∨REL1y(c2,b2)]]∧[REL2x(b2,a)∧[REL8x(c1,b2)∨REL4x(c2,b2)]].
Use Tables2 and 3, and c1⊂c and c2⊂c. Thus, the outcome of the composition can be written as follows:
(25)REL1y(c,a)∧[REL2x(c,a)∨REL3x(c,a)]∧REL1y(c,a)∧[REL2x(c,a)∨REL3x(c,a)∨REL6x(c,a)∨REL13x(c,a)]=REL1y(c,a)∧[REL2x(c,a)∨REL3x(c,a)].
The outcome of the composition is:(26)NTPPy(c,WeakNorth(a))∧[TPPx(c,WeakEast(a))∧ECy(c,Horizontal(a))∨TPPx(c,Vertical(a))∧ECy(c,Horizontal(a))].Table 2
(a) Composition of binary relations in they-direction for the hybrid model (composed relations of {WN} and {WN,H}). (b) Composition of binary relations in the y-direction for the hybrid model (composed relations of {H} and {WN,H}). (c) Composition of binary relations in the y-direction for the hybrid model (composed relations of {S} and {WN,H}). (d) Composition of binary relations in the y-direction for the hybrid model (composed relations of {WN,H,S} and {WS}).
(a)
Composed relations of  {WN} and {WN,H}
WN(c,b)
H(c,b)
NTPPy(c,WN(b))
TPPy(c,WN(b))∧ ECy(c,H(b))
TPPy(c,H(b))∧ ECy(c,WN(b))
TPPy(c,H(b))∧ ECy(c,WS(b))
NTPPy(c,H(b))
EQy(c,H(b))
NTPPy(b,WN(a))
NTPPy(c,WN(a))
NTPPy(c,WN(a))
NTPPy(c,WN(a))
NTPPy(c,WN(a))
NTPPy(c,WN(a))
NTPPy(c,WN(c))
WN(b,a)
TPPy(b,WN(a))∧ ECy(b,H(a))
NTPPy(c,WN(a))
NTPPy(c,WN(a))
NTPPy(c,WN(a))
TPPy(c,WN(a)) ∧ ECy(c,H(a))
NTPPy(c,WN(a))
TPPy(c,WN(a)) ∧ ECy(c,H(a))
WN(b,a)
NTPPy(c,WN(a))
WN(c,a)
Note: the data in bold are results of the composition of relations.
(b)
Composed relations of  {H} and {WN,H}
WN(c,b)
H(c,b)
NTPPy(c,WN(b))
TPPy(c,WN(b))∧ ECy(c,H(b))
TPPy(c,H(b))∧ ECy(c,WN(b))
TPPy(c,H(b))∧ ECy(c,WS(b))
NTPPy(c,H(b))
EQy(c,H(b))
H(b,a)
TPPy(b,H(a))∧ ECy(b,WN(a))
NTPPy(c,WN(a))
TPPy(c,WN(a)) ∧ ECy(c,H(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
NTPPy(c,H(a))
NTPPy(c,H(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
TPPy(b,H(a))∧ ECy(b,WS(a))
[
NTPPy(c,H(a))
]
∨ [TPPy(c,H(a)) ∧ ECy(c,WN(a))]∨ [TPPy(c,WN(a)) ∧ ECy(c,H(a))]∨ [NTPPy(c,WN(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ DCy(c,WS(a))]
[
NTPPy(c,H(a))
]
∨ [PPy(c,H(a)) ∧ ECy(c,WN(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ DCy(c,WS(a))]
NTPPy(c,H(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
NTPPy(c,H(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
NTPPy(b,H(a))
[
NTPPy(c,H(a))
]
∨ [TPPy(c,H(a)) ∧ ECy(c,WN(a))]∨ [TPPy(c,WN(a)) ∧ ECy(c,H(a))]∨ [NTPPy(c,WN(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ DCy(c,WS(a))]
[
NTPPy(c,H(a))
]
∨ [TPPy(c,H(a)) ∧ ECy(c,WN(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ DCy(c,WS(a))]
NTPPy(c,H(a))
NTPPy(c,H(a))
NTPPy(c,H(a))
NTPPy(c,H(a))
EQy(b,H(a))
NTPPy(c,WN(a))
TPPy(c,WN(a)) ∧ ECy(c,H(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
TPPy(c,H(a)) ∧ ECy(c,WS(a))
NTPPy(c,H(a))
EQy(c,H(a))
H(b,a)
WN(c,a)
∨
H(c,a)
H(c,a)
Note: the data in bold are the results of the composition of relations.
(c)
Composed relations of  {S} and {WN,H}
WN(c,b)
H(c,b)
NTPPy(c,WN(b))
TPPy(c,WN(b))∧ ECy(c,H(b))
TPPy(c,H(b))∧ ECy(c,WN(b))
TPPy(c,H(b))∧ ECy(c,WS(b))
NTPPy(c,H(b))
EQy(c,H(b))
S(b,a)
NTPPy(b,WS(a))
U-13 relations
[
NTPPy(c,WS(a))
]
∨ [TPPy(c,WS(a)) ∧ ECy(c,H(a))]∨ [POy(c,WS(a)) ∧ POy(c,H(a)) ∧ DCy(c,WN(a))]∨ [POy(c,WS(a)) ∧ POy(c,H(a)) ∧ ECy(c,WN(a))]∨ [POy(c,WS(a)) ∧ POy(c,WN(a)) ∧ NTPPiy(c,H(a))]
NTPPy(c,WS(a))
NTPPy(c,WS(a))
NTPPy(c,WS(a))
NTPPy(c,WS(a))
TPPy(b,WS(a))∧ ECy(b,H(a))
[
NTPPy(c,H(a))
]
∨ [TPPy(c,H(a)) ∧ ECy(c,WN(a))]∨ [TPPy(c,WN(a)) ∧ ECy(c,H(a))]∨ [NTPPy(c,WN(a))] ∨[POy(c,WN(a)) ∧ POy(c,H(a)) ∧ DCy(c,WS(a))]
[
TPPy(c,H(a)) ∧ ECy(c,WS(a))]∨ [EQy(c,H(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ ECy(c,WS(a))]
TPPy(c,WS(a)) ∧ ECy(c,H(a))
NTPPy(c,WS(a))
NTPPy(c,WS(a))
TPPy(c,WS(a)) ∧ ECy(c,H(a))
S(b,a)
WN(c,a) ∨ H(c,a) ∨ WS(c,a)
WS(c,a)
Note: the data in bold are the results of the composition of relations.
(d)
Composed relations of  {WN,H,S} and {WS}
WS(c,b)
WN(b,a)
NTPPy(b,WN(a))
NTPPy(c,WS(b))
TPPy(c,WS(b)) ∧ ECy(c,H(b))
TPPy(b,WN(a)) ∧ ECy(b,H(a))
U-13 relations
[
NTPPy(c,WN(a))
]
∨ [TPPy(c,WN(a)) ∧ ECy(c,H(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ DCy(c,WS(a))]∨ [POy(c,WN(a)) ∧ POy(c,H(a)) ∧ ECy(c,WS(a))]∨ [POy(c,WN(a)) ∧ POy(c,WS(a)) ∧ NTPPiy(c,H(a))]
WN(b,a)
WN(c,a) ∨ H(c,a) ∨ WS(c,a)
H(b,a)
TPPy(b,H(a)) ∧ ECy(b,WN(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
[
NTPPy(c,H(a))
]
∨ [TPPy(c,H(a)) ∧ ECy(c,WS(a))]∨ [TPPy(c,WS(a)) ∧ ECy(c,H(a))]∨ [NTPPy(c,WS(a))]∨ [POy(c,WS(a)) ∧ POy(c,H(a)) ∧ DCy(c,WN(a))]
TPPy(b,H(a)) ∧ ECy(b,WS(a))
TPPy(c,H(a)) ∧ ECy(c,WN(a))
NTPPy(c,WS(a))
NTPPy(b,H(a))
[
NTPPy(c,H(a))] ∨ [TPPy(c,H(a)) ∧ ECy(c,WS(a))]∨ [TPPy(c,WS(a)) ∧ ECy(c,H(a))]∨ [NTPPy(c,WS(a))]∨ [POy(c,WS(a)) ∧ POy(c,H(a)) ∧ DCy(c,WN(a))]
[
NTPPy(c,H(a))
]
∨ [TPPy(c,H(a)) ∧ ECy(c,WS(a))]∨ [POy(c,WS(a)) ∧ POy(c,H(a)) ∧ DCy(c,WN(a))]
EQy(b,H(a))
NTPPy(c,WS(a))
TPPy(c,WS(a)) ∧ ECy(c,H(a))
H(b,a)
H(c,a) ∨ WS(c,a)
S(b,a)
NTPPy(b,WS(a))
NTPPy(c,WS(a))
NTPPy(c,WS(a))
TPPy(b,WS(a)) ∧ ECy(b,H(a))
NTPPy(c,WS(a))
NTPPy(c,WS(a))
S(b,a)
NTPPy(c,WS(a))
Note: the data in bold are the results of the composition of relations.Table 3
(a) Composition of binary relations in thex-direction for the hybrid model (composed relations of {WE} and {WE,V,WW}). (b) Composition of binary relations in the x-direction for the hybrid model (part 1: composed relations of {V} and {WE,V,WW}). (c) Composition of binary relations in the x-direction for the hybrid model (part 2: composed relations of {V} and {WE,V,WW}). (d) Composition of binary relations in the x-direction for the hybrid model (part 2: composed relations of {WW} and {WE,V,WW}).
(a)
Composed relations of  {WE} and {WE,V,WW}
WE(c,b)
V(c,b)
WW(c,b)
NTPPx(c,WE(b))
TPPx(c,WE(b))∧ECx(c,V(b))
TPPx(c,V(b))∧ECx(c,WE(b))
TPPx(c,V(b))∧ECx(c,WW(b))
NTPPx(c,V(b))
EQx(c,V(b))
NTPPx(c,WW(b))
TPPx(c,WW(b))∧ECx(c,V(b))
WE(b,a)
NTPPx(b,WE(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
U-13 relations
[
NTPPx(c,WE(a))
] ∨[TPPx(c,WE(a)) ∧ ECx(c,V(a))]∨ [POx(c,WE(a)) ∧ POx(c,V(a)) ∧ DCy(c,WW(a))]∨ [POx(c,WE(a)) ∧ POx(c,V(a)) ∧ ECx(c,WW(a))]∨ [POx(c,WE(a)) ∧ POx(c,WW(a)) ∧ NTPPix(c,V(a))]
TPPx(b,WE(a))∧ECx(b,V(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
NTPPx(c,WE(a))
TPPx(c,WE(a)) ∧ ECx(c,V(a))
NTPPx(c,WE(a))
TPPx(c,WE(a)) ∧ ECx(c,V(a))
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WW(a))]∨ [TPPx(c,WW(a))∧ ECx(c,V(a))]∨[NTPPx(c,WW(a))]∨[POx(c,WW(a))∧ POx(c,V(a)) ∧ DCy(c,WE(a))]
[
TPPx(c,V(a)) ∧ ECx(c,WE(a))]∨ [EQx(c,V(a))]∨ [POx(c,WW(a)) ∧ POx(c,V(a)) ∧ ECx(c,WE(a))]
WE(b,a)
NTPPx(c,WE(a))
WE(c,a)
WE(c,a) ∨ V(c,a) ∨ WW(c,a)
Note: the data in bold are the results of the composition of relations.
(b)
Part 1 of composed relations of  {V} and {WE,V,WW}
WE(c,b)
V(c,b)
WW(c,b)
NTPPx(c,WE(b))
TPPx(c,WE(b))∧ECx(c,V(b))
TPPx(c,V(b))∧ECx(c,WE(b))
TPPx(c,V(b))∧ECx(c,WW(b))
NTPPx(c,V(b))
EQx(c,V(b))
NTPPx(c,WW(b))
TPPx(c,WW(b))∧ECx(c,V(b))
V(b,a)
TPPx(b,V(a))∧ECx(b,WE(a))
NTPPx(c,WE(a))
TPPx(c,WE(a)) ∧ ECx(c,V(a))
TPPx(c,V(a)) ∧ ECx(c,WE(a))
NTPPx(c,V(a))
NTPPx(c,V(a))
TPPx(c,V(a)) ∧ ECx(c,WE(a))
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WW(a))]∨ [TPPx(c,WW(a)) ∧ ECx(c,V(a))]∨ [NTPPx(c,WW(a))] ∨[POx(c,WW(a)) ∧ POx(c,V(a)) ∧ DCy(c,WE(a))]
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WW(a))]∨ [POx(c,WW(a)) ∧ POx(c,V(a)) ∧ DCy(c,WE(a))]
TPPx(b,V(a))∧ECx(b,WW(a))
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WE(a))]∨ [TPPx(c,WE(a)) ∧ ECx(c,V(a))]∨ [NTPPx(c,WE(a))]∨[POx(c,WE(a)) ∧ POx(c,V(a)) ∧ DCy(c,WW(a))]
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WE(a))]∨ [POx(c,WE(a)) ∧ POx(c,V(a)) ∧ DCy(c,WW(a))]
NTPPx(c,V(a))
TPPx(c,V(a)) ∧ ECx(c,WE(a))
NTPPx(c,V(a))
TPPx(c,V(a)) ∧ ECx(c,WE(a))
NTPPx(c,WW(a))
TPPx(c,WW(a)) ∧ ECx(c,V(a))
Note: the data in bold are the results of the composition of relations.
(c)
Part 2 of composed relations of  {V} and {WE,V,WW}
WE(c,b)
V(c,b)
WW(c,b)
NTPPx(c,WE(b))
TPPx(c,WE(b))∧ECx(c,V(b))
TPPx(c,V(b))∧ECx(c,WE(b))
TPPx(c,V(b))∧ECx(c,WW(b))
NTPPx(c,V(b))
EQx(c,V(b))
NTPPx(c,WW(b))
TPPx(c,WW(b))∧ECx(c,V(b))
V(b,a)
NTPPx(b,V(a))
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WE(a))]∨ [TPPx(c,WE(a)) ∧ ECx(c,V(a))]∨ [NTPPx(c,WE(a))] ∨[POx(c,WE(a)) ∧ POx(c,V(a)) ∧ DCy(c,WW(a))]
[
NTPPx(c,V(a))
]
∨
[
TPPx(c,V(a)) ∧
ECx(c,WE(a))
]
∨
[
POx(c,WE(a)) ∧POx(c,V(a)) ∧DCy(c,WW(a))]
NTPPx(c,V(a))
NTPPx(c,V(a))
NTPPx(c,V(a))
NTPPx(c,V(a))
[
NTPPx(c,V(a))
]
∨
[
TPPx(c,V(a)) ∧
ECx(c,WW(a))
]
∨
[
TPPx(c,WW(a)) ∧
ECx(c,V(a))
]
∨
[
NTPPx(c,WW(a))
]
∨
[
POx(c,WW(a)) ∧
POx(c,V(a)) ∧
DCy(c,WE(a))
]
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WW(a))]∨ [POx(c,WW(a)) ∧ POx(c,V(a)) ∧ DCy(c,WE(a))]
EQx(b,V(a))
NTPPx(c,WE(a))
TPPx(c,WE(a)) ∧ ECx(c,V(a))
TPPx(c,V(a)) ∧ ECx(c,WE(a))
TPPx(c,V(a)) ∧ ECx(c,WW(a))
NTPPx(c,V(a))
EQx(c,V(a))
NTPPx(c,WW(a))
TPPx(c,WW(a)) ∧ ECx(c,V(a))
V(b,a)
WE(c,a) ∨ V(c,a)
V(c,a)
V(c,a) ∨ WW(c,a)
Note: the data in bold are the results of the composition of relations.
(d)
Composed relations of  {WW} and {WE,V,WW}
WE(c,b)
V(c,b)
WW(c,b)
NTPPx(c,WE(b))
TPPx(c,WE(b))∧ECx(c,V(b))
TPPx(c,V(b))∧ECx(c,WE(b))
TPPx(c,V(b))∧ECx(c,WW(b))
NTPPx(c,V(b))
EQx(c,V(b))
NTPPx(c,WW(b))
TPPx(c,WW(b)) ∧ECx(c,V(b))
WW(b,a)
NTPPx(b,WW(a))
U-13 relations
[
NTPPx(c,WW(a))
]
∨
[
TPPx(c,WW(a)) ∧ ECx(c,V(a))]∨ [POx(c,WW(a)) ∧ POx(c,V(a)) ∧ DCy(c,WE(a))]∨ [POx(c,WW(a)) ∧ POx(c,V(a)) ∧ ECx(c,WE(a))]∨ [POx(c,WW(a)) ∧ POx(c,WE(a)) ∧ NTPPix(c,V(a))]
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
TPPx(b,WW(a))∧ ECx(b,V(a))
[
NTPPx(c,V(a))
]
∨ [TPPx(c,V(a)) ∧ ECx(c,WE(a))]∨ [TPPx(c,WE(a)) ∧ ECx(c,V(a))]∨ [NTPPx(c,WE(a))]∨[POx(c,WE(a)) ∧ POx(c,V(a)) ∧ DCy(c,WW(a))]
[
TPPx(c,V(a)) ∧ ECx(c,WW(a))]∨ [EQx(c,V(a))]∨ [POx(c,WE(a)) ∧ POx(c,V(a)) ∧ ECx(c,WW(a))]
TPPx(c,WW(a))
∧ ECx(c,V(a))
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
TPPx(c,WW(a))
∧ ECx(c,V(a))
NTPPx(c,
WW(a))
NTPPx(c,
WW(a))
WW(b,a)
WE(c,a) ∨ V(c,a) ∨ WW(c,a)
WW(c,a)
NTPPx(c,WW(a))
Note: the data in bold are the results of the composition of relations.Example 2.
This example is similar to the fourth example in the previous section of this paper.
Find the composition of(27)[PO(b1,a)∧PNE(b2,a)]∧[PO(c,b)∧PW(c,b)∧PSW(c,b)].
Establish the direction relation betweenc and each individual part of b.Use (8), with 1≤k≤2 and 1≤m1≤4, and 1≤m2≤7.
The composition in expressive form will be as follows.For part
b
1,
(28)[[REL2y(b1,a)∧REL2x(b1,a)]]∧[[REL4y(c1,b1)∧REL4x(c1,b1)]∨[REL8y(c2,b1)∧REL4x(c2,b1)]∨[REL4y(c3,b1)∧REL8x(c3,b1)]∨[REL8y(c4,b1)∧REL8x(c4,b1)]].The regionsc1, c2, c3, c4⊂c; the above composition can be written as follows: (29a)[REL2y(b1,a)∧[REL4y(c,b1)∨REL8y(c,b1)∨REL4y(c,b1)∨REL8y(c,b1)]]∧[REL2x(b1,a)∧[REL4x(c,b1)∨REL4x(c,b1)∨REL8x(c,b1)∨REL8x(c,b1)]]=[REL2y(c,a)∨REL3y(c,a)∨REL6y(c,a)∨REL13y(c,a)]∧[REL2x(c,a)∨REL3x(c,a)∨REL6x(c,a)∨REL13x(c,a)].For part
b
2,
(29b)
[
[
REL
3
y
(
b
2
,
a
)
∧
REL
3
x
(
b
2
,
a
)
]
]
∧
[
[
REL
8
y
(
c
1
,
b
2
)
∧
REL
7
x
(
c
1
,
b
2
)
]
∨
[
REL
6
y
(
c
2
,
b
2
)
∧
REL
8
x
(
c
2
,
b
2
)
]
∨
[
REL
2
y
(
c
3
,
b
2
)
∧
REL
8
x
(
c
3
,
b
2
)
]
∨
[
REL
2
y
(
c
4
,
b
2
)
∧
REL
6
x
(
c
4
,
b
2
)
]
∨
[
REL
3
y
(
c
5
,
b
2
)
∧
REL
6
x
(
c
5
,
b
2
)
]
∨
[
REL
3
y
(
c
6
,
b
2
)
∧
REL
2
x
(
c
6
,
b
2
)
]
∨
[
REL
2
y
(
c
7
,
b
2
)
∧
REL
2
x
(
c
7
,
b
2
)
]
]
=
[
[
REL
2
y
(
c
,
a
)
∨
REL
3
y
(
c
,
a
)
∨
REL
5
y
(
c
,
a
)
∨
REL
12
y
(
c
,
a
)
]
∧
[
REL
2
x
(
c
,
a
)
∨
REL
3
x
(
c
,
a
)
∨
REL
4
x
(
c
,
a
)
∨
REL
5
x
(
c
,
a
)
∨
REL
7
x
(
c
,
a
)
∨
REL
8
x
(
c
,
a
)
∨
REL
12
x
(
c
,
a
)
]
]
.
The final outcome of the composition is the composition of part b1 (29a) ∧ part b2 (29b).Apply Rule3 from the earlier part of the paper, and we will get the following:
(30)[[REL2y(c,a)∨REL3y(c,a)∨REL6y(c,a)∨REL13y(c,a)]∧[REL2y(c,a)∨REL3y(c,a)∨REL12y(c,a)]∧[REL2x(c,a)∨REL3x(c,a)∨REL4x(c,a)∨REL8x(c,a)∨REL12x(c,a)]∧[REL2x(c,a)∨REL3x(c,a)∨REL6x(c,a)∨REL13x(c,a)][REL2y(c,a)∨REL3y(c,a)]].
We collapse some of the disjunction of relations:
(31)REL6y(c,a)∨REL13y(c,a)=REL13y(c,a)REL4x(c,a)∨REL8x(c,a)∨REL12x(c,a)=REL12y(c,a)REL6x(c,a)∨REL13x(c,a)=REL13x(c,a).
Equation (30) becomes (32)[REL2y(c,a)∨REL3y(c,a)∨REL13y(c,a)]∧[REL2y(c,a)∨REL3y(c,a)∨REL12y(c,a)]∧[REL2x(c,a)∨REL3x(c,a)∨REL12x(c,a)]∧[REL2x(c,a)∨REL3x(c,a)∨REL13x(c,a)].
Region c is single piece. Therefore, (32) becomes
(33)[POy(c,WeakNorth(a))∧POy(c,WeakSouth(a))∧NTPPiy(c,Horizontal(a))](34)∧[POx(c,WeakEast(a))∧POx(c,WeakWest(a))∧NTPPix(c,Vertical(a))].
This means that the region c⊆Uwhich is the union of all the 9 tiles of region a. As mentioned earlier, based on Figure 9, region c⊄SW(a). Thus, the outcome of the composition for weak relations (in the previous section) yields the same result as this composition. However, the computation for the latter is more tedious and complex when involving regions with many parts.


## 8. Existential Inference

The composition table in Table2 is the result of transitive inferences made about regions a and c, given the hybrid cardinal direction relations for regions a and b as well as regions b and c. In the context of this paper, an existential inference is the inference made about the spatial relation between a and b, given the relations between c and a or/and the given relations between c and b. We shall demonstrate how our expressive hybrid cardinal direction model could be used to make several existential inferences which are not possible in existing models.Example 3 (FindR(b,a) such that c⊂ WeakNorth(b) and c⊂ WeakNorth(a)).
To answer this query, we must first specify the expressive relation betweena and c.
There are two possible relations: TPPy(c,WeakNorth(a)) or WeakNorth(c,a). If it is the former then composition is WeakNorth(b,a)∧ WeakNorth(c,b) which means R(b,a) is WeakNorth(b,a).If it is the latter, there are several combinations: (i)
WeakNorth(b,a) ∧ Horizontal(c,b)(ii)
WeakNorth(b,a) ∧ WeakSouth(c,b)(iii)
Horizontal(b,a) ∧ WeakNorth(c,b)(iv)
WeakSouth(b,a) ∧ WeakNorth(c,b).
This meansR(b,a) are Horizontal(b,a) or WeakSouth(b,a) when c⊂ WeakNorth(b) and c⊂ WeakNorth(a).Example 4 (FindR(b,a) and S(c,b) such that T(a,c) is ¬[TPPy(c,Horizontal(a)) ∧ ECy(c,WeakSouth(a))]).
Based on Table2, 9 different compositions will yield the following outcome:
TPPy(c,Horizontal(a)) ∧ ECy(c,WeakSouth(a))
The set of possible compositions,Q, is:
{REL1y(b,a) ∧ REL7y(c,b), REL2y(b,a) ∧ REL7y(c,b),
REL3y(b,a) ∧ REL7y(c,b), REL3y(b,a) ∧ REL8y(c,b),
REL5y(b,a) ∧ REL7y(c,b), REL5y(b,a) ∧ REL8y(c,b),
REL6y(b,a) ∧ REL4y(c,b), REL7y(b,a) ∧ REL1y(c,b),
REL8y(b,a) ∧ REL12(c,b)}.
IfU equals 8 × 8 basic binary direction relations, then the set of all possible ordered pairs of R and S which satisfy the above query will be U–Q.Example 5 (FindR(b,a) and S(c,b) such that T(a,c) is POy(c,WeakSouth(a)) ∧ POy(c,Horizontal(a)) ∧ ECy(c,WeakNorth(a))).
Based on Table2, we have 4 pairs of R and S which satisfy T. They are: REL1y(b,a)∧REL7y(c,b),REL2y(b,a)∧  REL8y(c,b),REL7y(b,a)∧ REL1y(c,b), REL7y(b,a) ∧ REL2y(c,b).


## 9. Conclusion

In this paper, we have shown how topological and direction relations can be integrated to produce a more expressive hybrid model for cardinal directions. The composition table derived from this model could be used to infer bothweak and expressive direction relations between regions. We have also introduced and demonstrated how to use a formula to compute the composition of weak or expressive relations between “whole and part” regions. We have also demonstrated how the composition table with expressive direction relations could be used to make several difficult existential inferences.



---

*Source: 205261-2013-02-28.xml*