Abstract: Reasoning about the inverse of cardinal direction relation is a fundamental problem in qualitative spatial reasoning and plays an important role in reasoning with cardinal direction relation and consistency checking. In order to fullfill reasoning about the inverse of the basic cardinal direction relations between regions themselves defined in the model of Goyal, after deeply researching on reasoning about the inverse of cardinal direction relation in MBR model, we propose the concept of original relation of rectangular cardinal direction relation, propose an algorithm to computer it and then develop an algorithm to reason about the inverse of basic cardinal direction relation between regions defined in the model of Goyal. The results of both analyzing in theory and verifying through comparing the result of the algorithm with the actual situation for each of basic cardinal direction relations demonstrate that the algorithm is correct and complete.
INTRODUCTION
Research in the field of Qualitative spatial reasoning is very active from more than a decade. Qualitative spatial reasoning has received a lot of attention in the areas of Geographic Information Systems (Papadias and Egenhofer, 1997), Artificial Intelligence (Gerevini and Renz, 2002; Liu et al., 2008), Databases (Skiadopoulos and Koubarakis, 2001; Hao and Li, 2009) and Multimedia (Huang et al., 2008; Punitha and Guru, 2006). Several kinds of useful spatial relations have been studied so far, e.g., topological relations (Gerevini and Renz, 2002; Schneider and Behr, 2006), cardinal direction relations (Frank, 1996; Skiadopoulos and Koubarakis, 2001, 2004) and qualitative distance relations (Clementini et al., 1997; Frank, 1992).
The present study, concentrates on reasoning about the inverse of cardinal direction relations which allows the inference of the cardinal direction relation of b with respect to a, given the cardinal direction relation of object a with respect to object b. It is a fundamental problem in qualitative spatial reasoning and plays an important role in reasoning and consistence checking with cardinal direction relations. In the last few years several research contributions have appeared on the topic. Frank (1996) introduced a system for reasoning about the inverse of cardinal direction relations between points from an algebraic point of view. Papadias and Egenhofer (1997) applied the inverse operation for cardinal direction relations between points in hierarchical reasoning about direction relations, but do not address the problem of reasoning about the inverse of cardinal direction relation between regions. Liu and Hao (2006) use Interval Algebra and Rectangle Algebra to reason about the inverse of basic cardinal direction relations defined in MBR model. Wang et al. (2008) provide a method to reason with the inverse of basic cardinal direction relations defined in MBR model on the basis of reasoning about the inverse of direction relation between points. From the previous study presented above, regions are modeled either in terms of their Minimum Bounding Rectangle (MBR) or as a point in the previous work, to a certain extent, which reduces the complexity of reasoning, but sharply lowers the precision of representation and reasoning at the same time.
To the best of our knowledge, there has not been a method to reason about the inverse of cardinal direction relation between general regions. In this study, we take effort to solve this problem. Until now, the model presented by Goyal and Egenhofer (2001) is currently one of the most expressive models for qualitative representation and reasoning with cardinal directions because it is formally defined and can be applied to a wide set of regions (e.g., disconnected regions and regions with holes). After deeply studying reasoning about the inverse of the cardinal direction relations between rectangles, we employ the aforementioned model and then propose an algorithm to reason about the inverse of the basic cardinal direction relations between regions. The results of analyzing in theory demonstrate that this algorithm is correct and complete which is also confirmed by comparing the result of this algorithm with the actual situation for any basic cardinal direction relation defined in the aforementioned model.
The major contribution of this study is that an algorithm is developed to reason about the inverse of basic cardinal direction relation between general regions. Compared with the previous methods, our algorithm can be applied to a wide set of objects (not restricted to two particular classes of objects, points and rectangles) and improves the precision of reasoning. Therefore, our algorithm better meets the demand of practical application of spatial reasoning.
A FORMAL MODEL FOR CARDINAL DIRECTION RELATION
The model presented in Goyal and Egenhofer (2001) and Skiadopoulos and Koubarakis (2004) is currently one of the most expressive models for qualitative representation and reasoning with cardinal directions. Now, we show this model by means of related definitions. Throughout this study, we will consider regions that are closed, connected and have connected boundaries. The set of these regions will be denoted by REG.
Definition 1: Let a ∈REG. The greatest lower bound of the projection of a on the x-axis (respectively y-axis) is denoted by infx(a) (respectively infy(a)). The least upper bound or the supremum of the projection of a on the x-axis (respectively y-axis) is denoted by supx(a) (respectively supy(a)). The minimum bounding rectangle of a region a, denoted by mbr(a), is the rectangle formed by the straight lines x=infx(a), x=supx(a), y=infy(a) and y=supy(a).
Definition 2: Let a ∈REG and a be reference object. The straight lines x=infx(a), x=supx(a), y=infy(a) and y=supy(a) forming the minimum bounding rectangle of the reference region a divide the space into 9 areas which we call tiles of a (Fig. 1). These tiles will be denoted by NW(a), N(a), NE(a), W(a), B(a), E(a), SW(a), S(a) and SE(a), respectively, where NW(a) ={(x,y)|- ∞<x ≤infx(a) supy (a) ≤y<+ ∞}, N(a)={(x,y)| infx(a) ≤x ≤supx(a) ≤supy(a) ≤y+ ∞}, NE(a)={(x,y)| supx(a) ≤x<+ ∞ ∧ supy(a) ≤y<+ ∞}, W(a)={(x, y)|- ∞<x ≤infx(a) ∧infy(a) ≤y ≤supy(a)}, B(a)={(x,y)|infx(a) ≤x ≤supx(a) ∧infy(a) ≤y ≤supy(a))}, E(a)={(x,y)|supx(a) ≤x<+ ∞vinfy(a) ≤y ≤supy(a)}, SW(a)={(x,y)|- ∞<x ≤infx(a) ∧- ∞<y ≤infy(a)}, S(a)={(x,y)|=infx(a) ≤x ≤supx(a) ∧- ∞<y ≤infy(a)}, SE(a)= {(x, y)| supx(a) ≤x<+ ∞v- ∞<y ≤ infy(a)}.
| Fig. 1: | Space division |
Definition 3: Let a, b ∈REG where a is the reference region and b is the primary region. If b is included in tile NW(a) of a then we say that b is northwest of a and we write b NW a. Similarly, we can define North (N), Northeast (NE), West (W), bounding rectangle (B), Southwest (SW), East (E) and Southeast (SE) relations.
Definition 4: A basic cardinal direction relation is an expression R1: ... :Rk where R1, …,Rk ∈{B, S, SW, W, NW, N, NE, E, SE},1 ≤k ≤9 and Ri ≠Rj for every i, j such that 1 ≤i, j ≤k and i ≠j and there exist regions a1, …,ak ∈REG such that a1 ∈R1(b), …, ak ∈Rk(b) and a1 ∪þcak ∈REG for any reference region b ∈REG. A cardinal direction relation R1: þ:Rk is called single-tile if k = 1, otherwise it is called multi-tile. The set of basic cardinal direction relations in this model that contains 218 elements is denoted by D. For instance, b lies partly in the tile N(a) and partly in the tile NE(a) of a (Fig. 1) then, a N:NE b and we say that b is partly North and partly Northeast of a.
Using the 218 relations of D as our basis, we can define the powerset 2D of D which contains 2218 relations. Elements of 2D are called cardinal direction relations and can be used to represent not only definite but also indefinite information about cardinal directions, e.g., a {N, S} b denotes that region a is north or south of region b.
Definition 5: Let R ∈2D. The inverse of relation R, denoted by inv(R), is another cardinal direction relation which satisfies the following. For arbitrary regions a, b ∈ REG, a inv(R) b holds, iff b R a holds.
Definition 6: A basic cardinal direction relation R is called rectangular iff there exist two rectangles (with sides parallel to the x- and y-axes) a and b such that a R b is satisfied; otherwise it is called non-rectangular. The set of these relations that contains 36 elements is denoted by Drec.
Definition 7: Let R1 = R11: ...:R1k and R2 = R21:...:R2l be two cardinal direction relations. R1 includes R2 iff {R21, . . ., R2l} ⊆ {R11, . . ., R1k} holds.
Definition 8: Let R be a basic cardinal direction relation. The bounding relation of R, denoted by Br(R) is the smallest rectangular relation (with respect to the number of tiles) that includes R.
REASONING ABOUT THE INVERSE OF DIRECTION RELATION BETWEEN RECTANGLES
MBR model (Skiadopoulos and Koubarakis, 2001) is essentially that the actual target object is taken into account instead of approximating it with its minimum bounding rectangle in the model presented by Goyal and Egenhofer (2001). The set of basic cardinal direction relations in MBR model contains 36 elements. Liu and Hao (2006) researched on reasoning about the inverse of basic cardinal direction relations in MBR model by means of Interval Algebra and Rectangle Algebra. Allen ’s Interval Algebra (Allen, 1983) models the relative position between any two intervals as a set of thirteen basic relations, namely before, meets, overlaps, starts, during, finishes (b, m, o, s, d, f) together with theirs inverses (bi, mi, oi, si, di, fi) and the basic relation equal(eq).The set {p, m, o, s, d, f, pi, mi, oi, si, di, fi, eq} is denoted by Aint. Similarly, the domain considered in the rectangle algebra introduced by Balbiani et al. (1998) is the set of rectangles. A basic relation between two rectangles is a pair (Rx, Ry) of basic IA-relations: the x-axis relation and the y-axis relation. The set of basic RA-relations that contains 169 elements is denoted by Arec.
Liu and Hao (2006) reveal that there exists a natural connection between basic relations in MBR model and basic RA-relations. This connection is shown in Table 1 where any basic relation in MBR model corresponds to a Cartesian product ( x) of the power set of the interval relations.
Theorem 1: Let R, S ∈2Aint. The inverse operation for RA-relations (IA-relations) is denoted by -1. Then (R xS) -1=R -1 xS -1 (Balbiani et al., 1998).
According to Theorem1 and the correspondence between a basic cardinal direction relation in MBR model and a basic relation in rectangle algebra, the algorithm for reasoning about the inverse of basic cardinal direction relations in MBR model is shown as follows:
| Algorithm: | Invmbr (R) |
REASONING ABOUT THE INVERSE OF DIRECTION RELATION BETWEEN REGIONS
This study proposes an algorithm to reason about the inverse relation of basic cardinal direction relation defined in the model presented by Goyal and Egenhofer (2001). The main idea of this algorithm is reasoning about the inverse of cardinal direction relation between the primary object and the reference object from the inverse of cardinal direction between the minimum bounding rectangle of the primary object and the minimum bounding rectangle of the reference object. We first give the related definitions and theorems, before the algorithm is presented.
Definition 9: Let R ∈Drec, r ∈D. If Br(r)=R holds, then we say that r is the original relation of R. The set of the original relations of R is denoted by ORG(R).
Next, we will focus on computing ORG(R) of a basic rectangular cardinal direction relation R. We first introduce many symbols as fallows. A rectangle is denoted by rec(p, q) where p and q are the endpoints of a diagonal of the rectangle. The number of single tiles included in a basic cardinal direction relation R is denoted by Rnum.
Theorem 2: Let R ∈Drec. If Rnum=1 or Rnum=2 or Rnum=3, then ORG(R) ={R}.
Proof: If Rnum=1, then R is a single-tile. Then there exists only one r (r=R) such that Br(r) =R holds. Therefore ORG(R) ={R} holds when Rnum=1.
If Rnum=2, assume that R is r1:r2 where r1, r2 are single-tile cardinal direction relations, then Br(r1)=r1 ≠R,Br(r2)=r2 ≠R and Br(r1:r2)=R hold. According to definition 9, r1, r2 ∉ORG(R) and R ∈ORG(R) hold. So Br(r)=R holds iff r=R holds. Therefore ORG(R)={R} holds when Rnum=2.
| Table 1: | The mapping between basic relations in MBR model and basic RA-relations |
If Rnum=3, assume that R is r1:r2: r3, similarly, we have r1, r2, r3, r1: r2, r2: r3 ∉ORG(R) and R ∈ORG(R). It is easy to see that r1: r3 is not a basic cardinal direction relation. So, there exists only one r=R such that Br(r) =R holds. Therefore ORG(R)={R} when Rnum=3 and thus the theorem holds.
Theorem 3: Let R ∈Drec and Rnum=4. Assume that R is r1: r2: r3: r4. Then, ORG(R) can be computed using the formula:
| (1) |
Proof: If R ∈Drec and Rnum=4, then R will be in one of the following relations: W:B:SW:S, B:E:S:SE, NW:N:W:B, N:NE:B:E.
Let us first consider that R=W:B:SW:S. It is easy to see that W:S and B:SW are not basic cardinal relations and Br(r)=R holds for any r ∈{W:B:SW, W:B:S, W:SW:S, B:SW:S, W:B:SW:S}. Then, according to Definition 9, ORG(R)={W:B:SW, W:B:S, W:SW:S,B:SW:S, W:B:SW:S} holds, that is to say, Eq. 1 holds.
The cases where, R=B:E:S:SE, R=NW:N:W:B and R= N:NE:B:E can be proved similarly and thus the theorem holds.
Theorem 4: Let R ∈Drec, Rnum=6, S ∈Drec, T ∈Drec, Snum=3 and Tnum=3. Assume that S is s1: s2: s3 and T is t1: t2: t3. Then there exists only one pair (S, T) such that R= s1: s2: s3:t1: t2: t3 holds. Then, the correspondence between this R and this pair(S, T) is shown in Table 2.
Proof: The theorem can be proved easily from 36 basic rectangular cardinal direction relations.
Theorem 5: Let R ∈Drec and Rnum = 6. Assume that there exist S=s1: s2: s3 and T= t1: t2: t3 where S and T are in Drec such that R= s1: s2: s3:t1: t2: t3 holds. Then, ORG(R) can be computed using the formula:
| (2) |
Proof: If R ∈Drec and Rnum=6, then R will be in one of the following relations: NW:N:NE:W:B:E, W:B:E:SW:S:SE, N:NE:B:E:S:SE, NW:N:W:B:SW:S. We can prove that Eq. 2 holds for each of these cases above similarly with Theorem 3 and thus the theorem holds.
Theorem 6: Let R be NW:N:NE:W:B:E:SW:S:SE. Then, ORG(R) can be computed using the formula:
| (3) |
Proof: According to the definition of original relation (Definition 9) and the set of basic cardinal direction relations, it is easy to see that:
holds and if r ≠s where r and s are in Drec, then ORG(r) ∩ORG(s)= ø holds. Therefore, Eq. 3 holds and thus the theorem holds.
According to the theorems above, an algorithm is proposed to compute the ORG(R) of any basic rectangular cardinal direction relation R which is shown as follows:
| Algorithm: | ORG (R) |
Theorem 7: Algorithm ORG( ) for computing the set of original relations of basic rectangular cardinal direction relations is correct and complete.
Proof: ∀R ∈Drec, Rnum may be every value in {1,2,3,4,6,9}. Theorem 2-6 offer methods to compute ORG (R) and prove themselves when Rnum=1 or Rnum=2 or Rnum=3, when Rnum=4, when Rnum=6 and when Rnum=9, respectively. The algorithm fulfills the methods offered by these theorems.
| Table 2: | The correspondence between the aforementioned relation R and pair (S, T) |
Therefore the algorithm can correctly compute ORG (R) for any R in Drec. Thus the algorithm is correct and complete.
Definition 10: Let R1 and R2 be basic cardinal direction relation. The bounding relation of R1 and R2, denoted by Br (R1, R2) is the smallest rectangular relation (with respect to the number of tiles) that includes R1 and R2 simultaneously.
Theorem 8: Let a and b be regions in REG and b be a rectangle. Assume that p and q are bottom-left point and top-right point of b, respectively. If p R1 a and q R2 a hold, then b Br(R1, R2) a holds.
Proof: Since, p is bottom-left point of b and q is top-right point of b, we have the follows: if R1=SW, then R2 ∈{N,NE,E,SE,S,SW,W,NW,B}; if R1=S, then R2 ∈{N, B, S, NE,E,SE}; if R1=SE, then R2 ∈{NE,E,SE}; if R1=W, then R2 ∈{W,B,E,NW,N,NE}; if R1= B, then R2 ∈{B,E,N,NE}; if R1=E, then R2 ∈{E,NE}; if R1=NW, then R2 ∈{NW, N,NE}; if R1=N, then R2 ∈{N,NE}; if R1=NE, then R2 =NE.
Let us first consider the case that R1=SW and R2= B. Assume that rectangle b is formed by the straight lines x =l, x =r, y =d and y =t. Since, R1=SW ∧R2= B ∧ p R1 a ∧q R2 a holds, l<infx(a) ∧infx(a)<r<supx(a) ∧d<infy(a) ∧infy(a) <t<supy(a) holds. Thus, rec((l,d), (infx(a),infy(a))) SWa ∧ rec((infx(a), d), (r,infy(a)) S a ∧rec((l, infy(a)), (infx(a), t)) Wa ∧rec((infx(a), infy(a), (r,t)) Ba ∧rec((l,d), (infx(a), infy(a)) ∪ rec((infx(a),d), (r,infy(a)) ∪rec((l,infy(a)), (infx(a),t)) ∪rec ((infx (a), infy(a), (r,t))=b holds. Then, according to Definition 4, b SW:S:W:B a holds. Since, Br (SW, B) is equal to SW:S: W:B, b Br(SW, B) a holds, that is to say, b Br(R1, R2) a holds. Thus the theorem holds in the case.
All the other cases can be proved similarly and thus the theorem holds.
Theorem 9: Let a, b be regions in REG. If b R a holds where R is a basic cardinal direction relation, then mbr(b) Br(R) a holds.
Proof: Let us first consider that R=W:SW:S. Assume that mbr(b) is formed by the straight lines x =l, x =r, y =d and y=t. Since, R=W:SW:S holds, l<infx(a) ∧infx(a)< r<supx(a) ∧d<infy(a) ∧ infy(a) <t<supy(a) holds. Therefore, for (l,d) the bottom-left point of mbr(b), (l,d) SW a holds; for (r,t) the top-right point of mbr(b), (r,t) B a holds. Then, according to Theorem 8, mbr(b) Br(SW,B) a holds, that is to say, mbr(b) SW:S:W: B a holds. Since Br(R) is SW:S:W: B, b Br(R)a holds and thus the theorem holds in the case.
Similarly, we can prove that the theorem holds for any other basic cardinal direction relations and thus the theorem holds.
Theorem 10: Let R ∈D. Then the inverse of relation R can be computed using the formula:
| (4) |
Proof: ∀r ∈inv(R), there exist a, b ∈REG such that a r b and b R a hold. Then a r mbr(b) and b R mbr(a) hold. According to Theorem 9, mbr(a)Br(r)mbr(b) and mbr(b) Br(R) mbr(a) hold. Then, according to Definition 4, Br(r) ∈invmbr(Br(R)) holds. Since, a r mbr(b) ∧mbr(a) Br(r) mbr(b) holds, according to Definition 9, r ∈ORG(Br(r)) holds. Therefore, ∀r ∈inv(R),
Conversely, ∀t ∈invmbr(Br(R)), there exist rectangle a and rectangle b such that a t b and b Br(R) a hold. Then a r mbr(b) and b R mbr(a) hold. ∀r ∈ ORG(t), assume that r is r1: ... :rk, assume also that R is R1: ... : Rj, let us form region b0=b ∩ (R1 (a) ∪ … ∪Rj (a)) and region a0=a ∩(r1(b) ∪ … ∪rk (b)), it is easy to see that b0 R a0 and a0 r b0 hold and thus, r ∈inv(R) holds. Therefore,
r ∈inv(R) holds and thus the theorem holds.
Using Algorithm invmbr( ), Algorithm ORG( ) and Theorem 10 as our basis, we propose an algorithm to reason the inverse of basic cardinal direction relations which is shown as follow.
| Algorithm: | inv (r) |
Theorem 11: Algorithm inv( ) for reasoning about the inverse of basic cardinal direction relation is correct and complete.
Proof: ∀r ∈D, there exists only one R ∈Drec such that Br(r)=R holds. ∀t ∈ invmbr(R), t ∈Drec holds. Theorem 7 proves that Algorithm ORG( ) can correctly compute ORG(t ) for any t in Drec.
| Fig. 2: | All the possible spatial configurations between regions a
and b. (a) bBa, (b) bW:Ba, (c) bB:Sa, (d) bB: bW:S:SW:Sa, (e) bW:B:Sa, (f)
bS:S:SWa, (g) bW:SW:Sa and (h) bW:B:SWa |
Theorem 10 offers a method proved to be correct which uses Algorithm invmbr ( ) and Algorithm ORG( ) to reason about the inverse of r. Therefore the algorithm can correctly compute the inverse of r for any r in D. Thus the algorithm is correct and complete.
CONFIRMATION
The purpose of this section is to confirm that our algorithm is correct by comparing the result of our algorithm with the actual situation.
Let us first verify whether our algorithm holds or not for cardinal direction relation N:NE:E.
Let us consider two regions a and b and assume that a N:NE:E b. If a N:NE:E b, then it is possible that b B a or b B:S a or b W:B a or b W:B:SW:S a or b W:B:S a or b B:S:SW a or b W:SW:S a or b W:B:SW a (Fig. 2a-h). Therefore, inv(N:NE:E)={B, B:S, W:B, W:B:SW:S, W:B:S, B:S:SW, W:SW:S, W:B:SW}.
Next, let us adopt our algorithm to reason about the inverse of relation N:NE:E. It is easy to see that Br(N:NE:E)=N:NE:B:E. Then we have that N:NE:B:E corresponds to rectangle algebra {si,oi} x{si,oi} from Table 1. Next, we have that ({si,oi} x{si, oi}) -1= {s,o} x{s, o} = {(s, s), (s, o), (o, s), (o, o)}, according to Theorem 1. Therefore, invmbr(N:NE:B:E)={B, B:S, W:B, W:B:SW:S}. Then, we have inv(N:NE:E) = ORG(B) ∪ORG(B:S) ∪ORG (W:B) ∪ORG (W:B:SW:S) = {B,B:S, W:B, W:B:SW:S, W:B:S, B:S:SW, W:SW:S,W:B:SW}, according to Theorem 10.
We can see that the result of our algorithm is consistent with the actual situation in the case. Therefore our algorithm holds true for cardinal direction relation N:NE:E.
Furthermore, we compare the result of our algorithm with the actual situation for each of the other basic cardinal direction relations, respectively. We find that the result of our algorithm is consistent with the actual situation for any basic cardinal direction relation. Therefore our algorithm can correctly computer the inverse of any basic cardinal direction relation.
CONCLUSIONS
In this study we developed an algorithm to solve the problem of reasoning about the inverse of the basic cardinal direction relations defined in the model of Goyal and Egenhofer (2001). We move a step forward and solve the problem of reasoning about the inverse of cardinal direction relation between regions in a more direct way that does not approximate regions too coarsely either in terms of their minimum bounding rectangle or as a point. The contribution is original and useful in itself; additionally, it will be helpful to enrich and improve the powers of spatial reasoning and spatial analysis.
ACKNOWLEDGMENTS
The authors would like to thank National Natural Science Foundation of China and National Science Foundation of Heilongjiang Province of China, under Grant No. 60673136 and No. F200601, for funding this research. The authors also gratefully acknowledge the helpful comments and suggestions of the reviewers, which have improved the presentation.