Computing the inverse of cardinal direction relations between regions

1 Introduction

Spatial direction relation as one of the basic concepts in spatial cognitive, is used to describe the position information with one object relative to another which reflects the ordering relations between spatial objects [1]. It is an indispensable part of spatial relation theory as well as topological relation and qualitative distance relation. With the further application of direction relations, people are no longer satisfied with simply describing and storing, but also need the ability of spatial reasoning to deal with the inference of the unknown information and the consistence checking of the existing information for direction relations. In recent years, qualitative spatial reasoning with direction relations has received a lot of attention in the areas of Geographic Information System [2,3,4], Spatial Database [5,6,7], and Artificial Intelligence [8,9,10]. Several problems in reasoning with direction relations have been studied so far, e.g., composition [10,11,12,13,14,15], inversion [16,17,18,19], and consistence checking [20,21,22,23] with cardinal direction relations, which play an important role in spatial query, spatial analysis, and planning decision.

In this work, we focus on the inversion operation for cardinal direction relations. The inverse operation for direction relations allows to infer the direction of object B with respect to A, given the direction of object A with respect to B, which plays an important role in saving storage and improving the efficiency of spatial queries and spatial reasoning [18]. For example, in an intelligent transportation system, the results of inverse operation for direction relations can be used as the constraints for path selection to reduce the search space and then improve the query efficiency, which can provide supports for choosing reasonable travel or rescue routes when traffic jams or accidents occur. Therefore, it is important to develop the automatic reasoning techniques for the inversion operation of direction relations.

In our work, we aim to solve the problem of automatically computing the inverse of cardinal direction relations in the model of Goyal and Egenhofer [24,25]. This model is currently one of the most expressive models for cardinal directions between regions because it is simple in calculation and it is easy to perform formal reasoning. The specific contributions of this work are summarized as follows.

• We introduce the operations of direction matrix to study the inversion operation for cardinal direction relations in the model of Goyal. We give the representation of the rectangular cardinal direction relations in the form of interval matrix. We get the results of the inversion operation of interval matrix by using the inference rules of interval algebra.

• Then, we give several important theorems which provide the solution for the target problem by using the operations of direction matrix, and their proofs to build up our theoretical framework.

• By our theoretical framework, we study the problem of deciding whether a Boolean matrix is geometrically realized or not and the problem of computing all possible original matrices of the given rectangular direction matrix. Then, we give the algorithmic solutions for the two problems.

• Then, we propose our algorithm to compute all possible results of the inverse of the basic cardinal direction relations directly. Several theorems are provided to prove that our algorithms are correct.

• We implement our algorithm in C programs. The results of running the programs show that our algorithm is correct and complete. In this work, we realized the automatic calculation of the inverse of the basic cardinal direction relations in the model of Goyal. Our study makes that model of Goyal has the power of automated reasoning for the inverse operation because our solution does not require the help of reference tables and any manual calculation.

This article is structured as follows. In Section 2, we survey related work. Section 3 presents the direction relation matrix model. In Sections 4 and 5, we introduce the rectangle algebra, and build the inference mechanism of the inverse operation for interval matrix and the correlations between interval matrix and rectangular direction matrix. Section 6 presents our algorithms for the inverse operation of basic cardinal direction relations and proves their correctness. Section 7 discusses the implementation of the proposed algorithms and presents the results of analysis and verification. Finally, Section 8 gives the conclusion and discusses future work.

2 Related work

As the basis of the spatial cognition and reasoning with directions, the formal description of spatial directions has received a lot of attention in recent years. Many models for cardinal directions have been proposed in the literature [2,5,24,25,26,27,28,29]. The model of Goyal and Egenhofer [24,25] is currently one of the most expressive models for cardinal directions in two dimensional space because it can more realistically express the direction relations between regions, and it is simple in calculation and easy to perform formal reasoning. This model is widely used in many fields related to the cognition of spatial direction. For example, the direction information represented by the model of Goyal can be used in the point of interest recommendation for more effective recommendation. To be specific, it is easy to get interested restaurants in a certain direction by means of this model. Research have been carried out on this interesting model. Goyal and Egenhofer [25] first studied the composition operation on this model and gave a method for computing the consistency-based composition. Skiadopoulos and Koubarakis [10] pointed out that the above composition method of Goyal cannot work correctly for some cases and revised this method, but the corrected method is relatively complicated and it requires the use of composition tables.

Spiros and Manolis [20] also studied the problem of checking the consistency of cardinal directions, and proposed the first algorithm for this problem on the model of Goyal which can be performed in O(n ⁵). Navarrete et al. [22] proposed an O(n ⁴) algorithm to check the consistency of the basic cardinal directions between regions in the model of Goyal. As a matter of fact, the consistency checking of a set of unrestricted cardinal directions is a NP-hard problem [23], which is difficult to be solved. Most methods solve this problem on the model of Goyal by using different composition methods based on the traditional path-consistency method, which are generally computationally expensive and inefficient.

In a previous line of work, Liu and Hao [21,30] proposed algorithms for the problems of composition, inversion, and consistency checking with cardinal directions involving only rectangular cardinal directions which is an important class of direction relations in the model of Goyal. The above works can only solve these problems with the condition regions should be rectangles or are approximately substituted by their minimum bounding box which may be too crude and thus reduces the precision of expression and reasoning. With the above problem in mind, Chen et al. [12] and Wang et al. [17] extended these methods presented in ref. [30] to deal with the composition and inversion operations for the general case based on the concepts of rectangular cardinal direction and its original relation. However, the above methods still require manual calculations or the use of reference tables in computing the possible original relations of rectangular cardinal directions.

In addition, several improved models [7,31,32,33] based on the model of Goyal have been proposed by researchers. In these models, the space is further subdivided on the basis of the model of Goyal in different ways. In summary, these models have a finer granularity of space division and can describe the spatial arrangements more accurately. Thus, directions in these models are clearly more expressive than the model of Goyal, but it is difficult to perform formal reasoning and calculation for these models.

In this work, we will focus on the inversion operation of directions which is a fundamental problem in qualitative spatial reasoning. In earlier studies on this problem, the concerned spatial objects mainly involve points, intervals [34], and rectangles [17,21,30]. Obviously, it is necessary to deal with the above problem for general regions. Summarizing, the model of Goyal is a more expressive model of qualitative reasoning with cardinal directions between regions. We will employ this model to handle the inversion operation for cardinal direction relations between regions. Although, there are several works [10,13,17,20] on qualitative reasoning with cardinal directions in this model, the ability of automated reasoning is still very poor. Especially for the inversion operation, the only published method presented in ref. [17] still needs to employ inference tables and manual calculations. In the following sections, we will present an algorithm that automatically performs the inversion operation for cardinal directions in the model of Goyal. This algorithm can be widely used in a lot of areas such as resource allocation, emergency rescue, disaster prevention and mitigation, and intelligent transportation. For example, in an intelligent transportation system, the results of inverse operation computed by our algorithm for direction relations can be used as the constraints for path selection to reduce the search space and then improve the query efficiency, which can provide supports for choosing reasonable travel or rescue routes when traffic jams or accidents occur.

3 Direction relation matrix model

In this work, we employ the model introduced by Goyal and Egenhofer [24,25] for cardinal direction relations which are used to describe how one region called primary region is placed relative to another called reference region. The concerned regions are homeomorphic to the closed unit disk ({(x, y) ∈ R ²|x ² + y ² ≤ 1}). Such a set of these regions will be denoted by REG. Briefly, regions in REG are closed, connected, and have connected boundaries. Let a be a region in REG. The projection of a on the x-axis (respectively y-axis) is denoted by a _x (respectively a _y ). The greatest lower bound or infimum of a _x (respectively a _y ) is denoted by inf _x (a) (respectively inf _y (a)). The least upper bound or the supremum of a _x (respectively a _y ) is denoted by sup _x (a) (respectively sup _y (a)). The minimum bounding box of region a, denoted by mbb(a), is the box formed by the straight lines x = inf _x (a), x = sup _x (a), y = inf _y (a), and y = sup _y (a).

The model of Goyal adopts a projection-based system placed around the reference region. Let region a in REG be the reference region. Such a system induced by the axes forming mbb(a), divides the plane into nine areas NW(a), N(a), NE(a), W(a), B(a), E(a), SW(a), S(a), and SE(a) which we call direction tiles of a (Figure 1).

Figure 1

Reference tiles.

If the primary region b in REG is included in tile N(a), then we say that b is north of a and we write b N a. Similarly, we can define northwest (NW), northeast (NE), west (W), bounding box (B), southwest (SW), east(E) and southeast (SE) relations. The above relations called single-tile cardinal direction relations are defined formally as following:

b NW a iff sup _x (b) ≤ inf _x (a) and sup _y (a) ≤ inf _y (b)

b N a iff sup _y (a) ≤ inf _y (b), inf _y (a) ≤ inf _x (b), and sup _x (b) ≤ sup _y (a)

b NE a iff sup _x (b) ≤ inf _x (a) and sup _y (a) ≤ inf _y (b)

b W a iff sup _x (b) ≤ inf _x (a), inf _y (a) ≤ inf _x (b), and sup _y (b) ≤ sup _y (a)

b B a iff inf _x (a) ≤ inf _x (b), sup _x (b) ≤ sup _x (a), inf _y (a) ≤ inf _y (b), and sup _y (b) ≤ sup _y (a)

b E a iff sup _x (a) ≤ inf _x (b), inf _y (a) ≤ inf _x (b), and sup _y (b) ≤ sup _y (a)

b SW a iff sup _x (b) ≤ inf _x (a) and sup _y (b) ≤ inf _y (a)

b S a iff sup _y (b) ≤ inf _y (a), inf _x (a) ≤ inf _x (b), and sup _x (b) ≤ sup _y (a)

b SE a iff sup _x (a) ≤ inf _x (b) and sup _y (b) ≤ inf _y (a)

However, the primary region b may fall into more than one tile. For instance the primary region b lies partly in the tile NW(a) and partly in the tile W(a) of a (Figure 1), then we say that b is partly northwest and partly east of a and we write a NW:W b.

Without loss of generality, the definition of basic cardinal direction relation is provided as following on the basis of the single-tile cardinal direction relations.

The set of basic cardinal direction relations that contains 218 elements is denoted by D. Then, a cardinal direction relation is defined as an element of the power set 2 ^D of D. A cardinal direction relation can be seen as the union of basic cardinal direction relations, which can be used to describe not only definite but also indefinite information about cardinal directions, e.g., b {NW,E} a means that b is northwest or east of a.

In this model, the cardinal direction relation of the primary region b relative to the reference region a is stored in a Boolean 3 × 3 matrix (equation (1)) called the direction relation matrix. Such matrix is generated by checking whether the intersection of the primary object and the tiles of the reference object is empty or not. For each tile, if such intersection is non-empty, it means that the primary object falls into this direction tile. In this work, for convenience, if such intersection is empty, it is recorded by 0, else recorded by 1 in such matrix. For instance, as shown in Figure 1, the direction c with respect to a can be represented by the direction matrix M ₁ and we write c P ₁ b.

By Definition 2, we have that there are 36 rectangular cardinal direction relations as follows: NW, N, NE, W, B, E, SW, S, SE, NW:N, N:NE, NW:W, N:B, NE:E, W:B, B:E, W:SW, B:S, E:SE, SW:S, S:SE, NW:N:NE, W:B:E, SW:S:SE, NW:W:SW, N:B:S, NE:E:SE, NW:N:W:B, N:NE:B:E, W:B:SW:S, B:E:S:SE, NW:N:NE:W:B:E, W:B:E:SW:S:SE, NW:W:SW:N:B:S, N:B:S:NE:E:SE, and NW:N:NE:W:B:E:SW:S:SE. The set of these rectangular cardinal direction relations is denoted by D _rec. By Definition 3, we can conclude that the direction relation matrix corresponding to each relation in D _rec is rectangular.

In Sections 4 and 5, we aim to solve the problem of computing the inverse of basic cardinal direction relations which is defined formally as following.

4 Rectangle algebra and rectangular cardinal direction relation

Interval algebra was introduced by Allen [34] for temporal reasoning. There are 13 basic relations between two temporal intervals which form a set of jointly exhaustive and pairwise disjoint relations (Table 1). The set of symbols A _{int =} {p,m,o,s,d,f,pi,mi,oi,si,di,fi,eq} is used to denote the 13 basic relations.

Table 1

Interval algebra relations

Similar to cardinal direction relation matrix, we can also use a Boolean matrix called interval relation matrix to describe the relations between the intervals. The one dimensional space is divided into three parts by the reference interval a (Figure 2). This matrix records into which parts the primary interval b falls by checking whether the intersection of the primary interval b and each part is empty or not. As shown in Figure 2, the relation of b with respect to a can be represented by interval relation matrix [1 1 0] and we write b[1 1 0]a.

Figure 2

Example of interval relation matrix.

There are six basic interval relation matrices defined as follows:

 b [1 0 0] a iff sup(b) ≤ inf(a).

 b [1 1 0] a iff inf(b) < inf(a) < sup(b) ≤ sup(a).

 b [1 1 1] a iff inf(b) < inf(a) and sup(a) < sup(b).

 b [0 1 0] a iff inf(a) ≤ inf(b) and sup(b) ≤ sup(a).

 b [0 1 1] a iff inf(a) ≤ inf(b) and sup(a) < sup(b).

 b [0 0 1] a iff sup(a) ≤ inf(b).

According to the definitions of interval relation matrix and interval algebra relations, there exists a mapping between interval relation matrix and interval algebra relations as shown in Table 2. For each pair of mapping, the corresponding interval relation matrix and interval algebra relation have the same spatial constraints between the intervals.

Rectangular algebra proposed by Balbiani et al. [35,36] is the extension of interval algebra to the bi-dimensional space. It describes the spatial configurations between rectangles whose sides are parallel to the axes of some orthogonal basis in a bi-dimensional Euclidean space. A basic rectangular algebra relation is defined as an element of the set A _rec = {(R _x ,R _y )|R _x ,R _y ∈ A _int}. For each relation (R _x ,R _y ) ∈ A _rec, there exist two rectangles a and b such that b (R _x ,R _y ) a holds iff b _x R _x a _x and b _y R _y a _y hold.

Figure 3

Illustration of Example 2.

Then, a rectangular algebra relation is defined as an element of the power set 2 ^Arec of A _rec. It can be used to describe not only definite but also indefinite information about spatial configurations between rectangles. If there exist rectangles a and b such that b R a is satisfied, where R is a rectangular algebra relation, if and only if one of the basic relation in R is satisfied, e.g., b{(pi,f), (d,e)} a denotes that b (pi,f) a or b (d,e) a for rectangles a and b.

Both rectangular cardinal direction relation and rectangular algebra can be used to describe the spatial configurations between rectangles in REG. Let us consider two rectangles a and b and assume that b R a, where R is a basic rectangular cardinal direction relation, then there exists a rectangular algebra relation r such that b r a holds, and vice versa. Thus, there must be a mapping between rectangular cardinal direction and rectangular algebra relations. Let us consider the basic rectangular cardinal direction relation SW:S and assume that there exist rectangles a and b such that b SW:S a holds. According to the definition of basic cardinal direction relation (Definition 1), we have b SW:S a if and only if inf _x (b) < inf _x (a) < sup _x (b) ≤ sup _x (a) and sup _y (b) ≤ inf _y (a), from which we have b _x {o, fi} a _x and b _y {p,m} a _y according to the definition of interval algebra relations presented in Table 1, namely, b {o, fi} × {p,m} a. Thus, rectangular cardinal direction relation SW:S and rectangular algebra relation {o, fi} × {p,m} are a pair of mapping. In similar way, we build a mapping between rectangular cardinal directions and rectangular algebra relations which is presented in the form of matrix as shown in Table 3.

5 Correlations between interval relation matrix and rectangular cardinal direction matrix

There exist equivalent correlations between interval relation matrix and interval algebra relations, so that we can get the inverse matrix by means of the inference rules of interval algebra for basic interval relation matrix. For interval relation matrix [1 0 0], we have its equivalent interval algebra relation {p,m} from Table 3. Thus, the interval algebra corresponding to INV([1 0 0]) is {p,m}⁻¹ which equals {pi,mi}. From Table 2, we have {pi,mi} is equivalent to [0 0 1], so we have INV([1 0 0]) = [0 0 1]. In the same way, we have the inverse of basic interval relation matrices presented in Table 4.

6 Computing the inverse of basic cardinal direction relations

In this Section, we will focus on the problem of computing the inverse of basic cardinal direction relations. We will need the following definitions and theorems.

Figure 4

Proving Lemma 3.

Therefore, we have t ∈ {p × q|p ∈ INV(P _y ) ∧ q ∈ INV(P _x )}.

Conversely, ∀t ∈ p × q|p ∈ INV(P _y ) ˄ q ∈ INV(P _x )}, according to Lemma 2, we have t = t _y × t _x , and since t ∈ {p × q|p ∈ INV(P _y ) ∧ q ∈ INV(P _x ), then, t _y ∈ INV(P _y ) ∧ t _x ∈ INV(P _x ), and then t _y × t _x ∈ INV _rec(P). Since t = t _y × t _x , then t ∈ INV _rec(P) and thus the theorem holds.

Conversely, ∀t ∈ INV _rec(Br(Q)), there exist rectangles a and b such that a t b ∧ b Br(Q) a holds. ∀q ∈ ORG(t), assume that r ₁:…: r _k is the cardinal direction corresponding to q, assume also that R ₁:…: R _j is the cardinal direction corresponding to Q, let us form region b ₀ = b ∩ (R ₁(a) ∪ … ∪ R _j (a)) and region a ₀ = a ∩ (r ₁(b) ∪ … ∪ r _k (b)). By the construction of regions a ₀ and b ₀, have mbb(a ₀) = a and mbb(b ₀) = b. Then, we have b ₀ R ₁:…: R _j a ₀ ∧ a ₀ r ₁:…: r _k b ₀ holds by the construction of regions a ₀ and b ₀ and the definition of basic cardinal direction relation (Definition 1), namely, b ₀ Q a ₀ ∧ a ₀ q b ₀ holds.

For instance, if aBr(N:NE:E)b ∧ bBr(W:SW:S) a holds (Figure 5(a)), then a ₀ N:NE:E b ₀ ∧ b ₀ W:SW:S a ₀ also holds, where a ₀ = a ∩ (N(b) ∪ NE(b) ∪ E(b)) and b ₀ = b ∩ (W(a) ∪ SW(a) ∪ S(a)) (Figure 5(b)).

Figure 5

Proving Theorem 2.

Since b ₀ Q a ₀ ∧ a ₀ q b ₀ holds, then we have q ∈ INV(Q) holds by Definition 4. Thus, INV(Q) = {ORG(t)|t ∈ INV _rec (Br(Q))} holds. We have INV _rec (Br(Q)) = {p × q|p ∈ INV(Br(Q) _y ) ∧ q ∈ INV(Br(Q) _x )} by Theorem 1, and thus the Theorem holds.

The above theorem offers a method to compute the inverse of basic cardinal direction relation. By this theorem, we have to get the set ORG(P) for a rectangular direction matrix P. The set ORG(P) can be obtained by manual reasoning and calculating. First, the invalid direction matrices are eliminated from the set of matrices included by P. Then, all the possible original matrices of P will be found by manual checking according to Definition 9.

We illustrate the above manual operation with the following example.

0 1 0 1 0 0 0 0 0 , 1 0 0 0 1 0 0 0 0 , 1 0 0 0 0 0 0 0 0 , 0 1 0 0 0 0 0 0 0 , 0 0 0 0 1 0 0 0 0 , 0 0 0 1 0 0 0 0 0 , 1 0 0 1 0 0 0 0 0 , 1 1 0 0 0 0 0 0 0 , 0 1 0 0 1 0 0 0 0 , 0 0 0 1 1 0 0 0 0 , 0 1 0 1 1 0 0 0 0 , 1 0 0 1 1 0 0 0 0 , 1 1 0 1 0 0 0 0 0 , 1 1 0 0 1 0 0 0 0 , 1 1 0 1 1 0 0 0 0

we cannot find out the two regions a,b in REG such that a M b holds, so that M is invalid by Definition 9. The other matrices are direction matrices.

∀ M ∈ 1 0 0 0 0 0 0 0 0 , 0 1 0 0 0 0 0 0 0 , 0 0 0 0 1 0 0 0 0 , 0 0 0 1 0 0 0 0 0 , 1 0 0 1 0 0 0 0 0 , 1 1 0 0 0 0 0 0 0 , 0 1 0 0 1 0 0 0 0 , 0 0 0 1 1 0 0 0 0 Br(M) = M, so that the eight direction matrices are not the original matrices of P.

O R G ( P ) = 0 1 0 1 1 0 0 0 0 , 1 0 0 1 1 0 0 0 0 , 1 1 0 1 0 0 0 0 0 , 1 1 0 0 1 0 0 0 0 , 1 1 0 1 1 0 0 0 0 , we have Br(M) = P. Then,

according to Definition 9, we have

Notice that the above process of manual reasoning is very complicated as it needs to check all the matrices included by the rectangular direction matrix P to find out the target matrices. By Definition 7, there are 2 ⁿ − 1 matrices included by a given rectangular direction matrix P with n(1 ≤ n ≤ 9) non-zero elements. Therefore, the amount of work on manual reasoning increases sharply as the number of non-zero elements in P grows. So, it is impractical to employ manual reasoning. Therefore, to solve above problem the following problem should be solved.

By Definition 9, if matrix M in the set of the Boolean 3 × 3 matrices is a valid direction matrix such that Br(M) = P holds, then M ∈ ORG(P) holds, for a rectangular direction matrix P. Thus, we can get ORG(P) by checking each matrix M in the set of the Boolean 3 × 3 matrices. Therefore, to solve problem 1, we first have to solve the following problem.

The following Lemma provides necessary and sufficient conditions to determine the validity of a given matrix.

We provide an approach to determine whether a given matrix is 4-connected or not by using auxiliary queue in the following way.

Initially, start with any non-zero element in matrix M, record its row and column number into the queue and then set it to be zero. Then, repeat the following process we call 4-neighbors, search when the queue is non-empty. Remove an element from the front of the queue and then, for each non-zero element in the four neighbors which are horizontally or vertically adjacent to the removed element, add its row and column number to the queue and set it to be zero. When the queue is empty, if there does not exist non-zero element in M, then M is 4-connected, else it is not.

By using the above approach and Lemma 4, we get the following algorithm to solve problem 2.

 Input: An arbitrary Boolean 3 × 3 matrix M

 Output: true or false

begin

 int row[4] = {0,0,-1,1};int col[4] = {1,-1,0,0};

 struct Point {int x,y;}; queue < Point > que;

 int cnt: = 0; bool flag: = false;

 for int i: = 1 to 3 do

  for int j: = 1 to 3 do

   if(M[i][j] = 1), then

    M[i][j] = 0; flag = true; cnt ++;

    que.push(Point{i,j});

    while(!que.empty()) do

     {Point q = que.front();}

      que.pop();

       for int k: = 0 to 3 do

          {int x = q.x + row[k]; int y = q.y + col[k];}

               if (x > = 1&&x < = 3&&y > = 1&&y < = 3&& M[x][y] = 1) then

               M[x][y]: = 0; que.push(Point{x,y});

               end if

  end if

 if (cnt > 1 or flag = false) then return false;

  else return true;

 end if

end

Otherwise, the for loop terminates when cnt > 1 ∨ flag = false holds and then this algorithm returns false. If flag = false, which implies M is empty, then M is invalid by Lemma 4. If cnt > 1 which indicates the non-zero elements of M cannot be found by once iterative four-neighbors search, then we can conclude that the primary object corresponding to M consists of at least two regions in REG, which contradicts with the definition of basic cardinal direction relation (Definition1). Therefore, the result of this algorithm is correct and thus this theorem holds

We give an example of Algorithm VALID-CDM in operation as following.

Figure 6

Illustration of Algorithm VALID-CDM in operation.

In the following, we will combine Algorithm VALID-CDM to solve Problem 1. We know that the set of Boolean 3 × 3 matrices can be represented by a full binary tree with depth 9. Thus, the original matrices of a rectangular direction matrix can be computed by implementing depth-first search in such binary tree. During this search, a Boolean 3 × 3 matrix is obtained whenever a leaf node is reached. For each obtained matrix, we check whether it is a direction matrix or not by calling algorithm VALID-CDM. If it is valid, then we check whether it is the original matrix of the given rectangular matrix or not. By the above method, an algorithm for computing all the original matrices of a given rectangular direction matrix is presented as follows.

In the remainder of this section, we will give an algorithm for computing the inverse of the basic cardinal direction relation.

By Theorem 2, the inverse of a basic direction matrix P can be computed by the following way. The rectangular matrix Br(P) is calculated first. Then, Br(P) is projected to the x-axis and y-axis, respectively. Furthermore, we take the inverse operation for the projection matrix of Br(P) on x-axis and y-axis, respectively. Then, we get the set INV(Br(P) _y ) × INV(Br(P) _x ). Finally, we employ algorithm COMPUTE-ORG to compute the original matrices for each matrix in INV(Br(P) _y ) × INV(Br(P) _x ). Notice that the set of the original matrices obtained is the result of the inversion operation of P. Based on the above discussion, we present our algorithm as following.

7 Algorithm analysis and discussion

In Section 6, we have presented algorithm COMPUTE-INV that computes the inverse of basic cardinal direction relations. In this section, we will verify the correctness and completeness of the proposed algorithm by comparing the result of this algorithm with that of manual reasoning for each basic cardinal direction relation.

We have implemented the Algorithm VALID-CDM, COMPUTE-ORG, and COMPUTE-INV in C programming language that runs on Visual C++ 6.0. We employ two dimensional arrays to store direction relation matrices. The queue used in Algorithm VALID-CDM with element <i,j> (i and j are two integers) is implemented by using the C++ Standard Template Library. Algorithm COMPUTE-ORG performs the depth-first search in the set of Boolean 3 × 3 matrices which is implemented by recursive programming. Although the set of Boolean 3 × 3 matrices can be seen as a full binary tree with depth 9, there is no need to use the data structure binary tree as such binary tree can be simulated by each element in the direction matrix set to be 0 or 1 randomly.

The inverse of each basic direction matrix has been generated by Algorithm COMPUTE-INV and manual reasoning, respectively. The results and the code are available from us. Then, we will check whether the result of Algorithm COMPUTE-INV is consistent with that of manual reasoning for each basic cardinal direction relation.

An example of the inverse of the basic direction matrix generated by Algorithm COMPUTE-INV is presented as follows.

For instance, we want to calculate the basic direction matrix M = 0 0 0 0 0 1 0 1 1 . Br(M) is calculated first. We have B r ( M ) = 0 0 0 0 1 1 0 1 1 .

So, the projection of Br(M) on the y-axis is 0 1 1 , and the projection of Br(M) on the x-axis is [0 1 1].

Then, we take the inverse operation for the projection matrix of Br(Q) on x-axis and y-axis, respectively.

We have I N V 0 1 1 = 0 1 0 , 1 1 0 and I N V 0 1 1 = 0 1 0 , 1 1 0 .

Therefore, we have

Equivalently, we have

We know that

O R G 0 0 0 0 1 0 0 0 0 = 0 0 0 0 1 0 0 0 0 , O R G 0 0 0 1 1 0 0 0 0 = 0 0 0 1 1 0 0 0 0 , O R G 0 1 0 0 1 0 0 0 0 = 0 1 0 0 1 0 0 0 0

Therefore, we have

Then, the inverse of the basic direction matrix is generated by manual reasoning, shown as follows.

Assume that a and b are regions in REG such that a 0 0 0 0 0 1 0 1 1 b holds (Figure 7). We have the possible spatial configurations of b with respect to a (also see Figure 7).

Figure 7

All possible spatial configurations of b with respect to a.

We have

b B a ∨ b W:B a ∨ b N:B a ∨ b N:W:B a ∨ b NW:W:B a ∨ b NW:N:W a ∨ b NW:N:B a ∨ b NW:N:W:B a holds.

Equivalently, we have

By Definition 4, we can conclude that the inverse of M generated by Algorithm COMPUTE-INV is consistent with that of manual reasoning. Therefore, the proposed algorithm can calculate INV(M) correctly. We compared the result of Algorithm COMPUTE-INV with that of manual reasoning for each basic cardinal direction relation. We find that the results of this algorithm are in good agreement with those of manual reasoning without exception. The results of comparison show that Algorithm COMPUTE-INV is correct and complete.

From the above example, we know that the manual reasoning has to find out all the possible spatial configurations between the primary region and reference region. It is easy to miss some possible case. There needs to make a lot of hypotheses and inferences with the spatial configurations between the primary region and reference region. To make sure there are no omissions, the results need to be checked completely and thoroughly. Obviously, the manual reasoning is a very complicated operation and requires a lot of work. The proposed algorithm COMPUTE-INV can calculate the inverse of any basic cardinal direction relation directly which does not need to use reference tables and any manual operation.

We know that the time cost of this algorithm depends on that of the depth-first search. The search space is a binary tree with depth 9 which only has 2⁹ = 512 elements. During this search, when a Boolean 3 × 3 matrix is obtained, Algorithm VALID-CDM is performed where at most 9 elements are processed by means of the queue. By Theorem 2, we know that the depth-first search is performed at most 16 times. The time complexity of algorithm COMPUTE-INV is constant. Therefore, it is unnecessary to concentrate on the time efficiency of Algorithm COMPUTE-INV.

In this section, the correctness and completeness of algorithm COMPUTE-INV has been verified. So far, the problem of computing the inverse of basic cardinal direction relations in the mode of Goyal is solved.

8 Conclusion and future work

In this work, we have addressed on the problem of automatically computing the inverse of cardinal direction relations in the model of Goyal. We first provided a solution by theorems for this problem. Then, we gave an algorithm for deciding whether a Boolean matrix is a valid direction matrix or not and an algorithm for computing the original matrices of the rectangular direction matrix. Finally, we provided our algorithm for computing the inverse of cardinal direction relations by means of the operations of direction matrix including the inverse operation of interval matrix, projection of direction matrix, and multiplication of matrix. Theorems were provided to prove formally that our algorithms are correct and complete. The verification was carried out by comparing the result of our algorithm with that of manual reasoning. The results of comparison also demonstrate that our algorithm can work correctly.

Notice that our solution does not need any manual reasoning and calculation, and the help of the reference tables. The proposed algorithm completely realized the automatic inference and calculation of the inverse of the basic cardinal direction relations in the model of Goyal, which improved the ability of intelligent reasoning and prediction of this model and then enhanced the usability of this model. This work is of great significance for improving the ability of spatial reasoning and spatial analysis of spatial database.

However, the real world is a three-dimensional space. In a recent paper [11], we provided a model for cardinal directions in three-dimensional space, which is the extension of the model of Goyal in the three-dimensional space. We found that this model has as many as 38,209,336 basic cardinal direction relations by programming calculation. For such a large number of direction relations, it is undoubtedly a huge challenge to perform spatial reasoning with cardinal directions in this model. We plan to extend our algorithms to solve the problem of computing the inverse of cardinal direction relations defined by the above three-dimensional model in a separate paper.