3.1 Mereotopology

Mereotopology, the integration of mereology (the theory of parthood) and topology, is the most studied theory in QSR, concerning the invariant properties that are under continuous deformations of objects, including translating, rotating and scaling. As it can only make qualitative distinctions, this kind of relationship (also called topological relations) is perhaps the most fundamental spatial relationship. Although mathematical topology has influenced various qualitative spatial theories, the wholesale importation is undesirable for a number of reasons (Gotts et al., Reference Gotts, Gooday and Cohn1996). RCC (region connection calculus; Cohn et al., Reference Cohn, Bennett, Gooday and Gotts1997; Renz, Reference Renz2002) and n-intersections (Egenhofer & Franzosa, Reference Egenhofer and Franzosa1991, Reference Egenhofer and Franzosa1995; Egenhofer & Herring, Reference Egenhofer and Herring1991; Egenhofer & Sharma, Reference Egenhofer and Sharma1993; Egenhofer et al., Reference Egenhofer, Clementini and Felice1994a, Reference Egenhofer, Mark and Herring1994b; Egenhofer, Reference Egenhofer2005; Egenhofer & Vasardani, Reference Egenhofer and Vasardani2007) are the two best-known approaches for representing and reasoning with topological relations; most existing approaches are extensions or improvements of them.

RCC is based on a reflexive and symmetric primitive relationship between spatial regions C(x, y). The intended topological interpretation of C(x, y) is that two regions x and y are connected if and only if their topological closures share a common point where the spatial regions are non-empty regular subsets of some topological space. It does not require that the regions be simple ones, that is, they might consist of (multiple) disconnected pieces. Of the number of relations defined by C(x, y), some relations are of particular interest: DC(x, y), P(x, y), PP(x, y), EQ(x, y), O(x, y), PO(x, y), DR(x, y), EC(x, y), TPP(x, y), NTPP(x, y) and P⁻¹, PP⁻¹, TPP⁻¹ and NTPP⁻¹, the converse of non-symmetrical relation P, PP, TPP and NTPP, respectively. Their formal definitions and the meaning under the intended interpretations, denoted after the double slash, are the following (Randell et al., Reference Randell, Cui and Cohn1992b; Renz, Reference Renz2002):

$$\[--><$$l> {{\matrix \hskip -3.2pc{\rm{DC(}}x,\ y{\rm{)}} \quad {\equiv_{ def}\; \; \neg {\rm C}{\rm{(}}x,\ y{\rm{)} \qquad\qquad\ \qquad\ \qquad\qquad\qquad\qquad \ \ {{{//}} {\it x} \ {\rm{is}} \ {\rm{disconnected}} \ {\rm{from}} \ {\it y}}}}} \cr {{\rm{P(}}x,\ y{\rm{)}}} \hfill { \quad\equiv_{ def}\; \; \forall z({\rm{C(}}z, \ x{\rm{)}} \rightarrow {\rm{C(}}z,\ y{\rm{))}} \quad \ \qquad\ \,\quad \quad \quad \ \quad \quad //{x \ {\rm{is}} \ {\rm{a}} \ {\rm{part}} \ {\rm{of}} \ y}} \cr {{\rm{PP(}}x,\ y{\rm{)}}} \hfill { \quad \equiv_{ def}\; \; {\rm{P(}}x,\ y{\rm{)}}\wedge \neg \,{\rm{P(}}y,\ x{\rm{)}} \quad \quad \quad \quad \quad \quad \quad \quad \ \ \quad\ \,\ \ //{x \ {\rm{is}} \ {\rm{a}} \ {\rm{proper}} \ {\rm{part}} \ {\rm{of}} \ y}} \cr {{\rm{EQ(}}x, \ y{\rm{)}}} \hfill { \quad \equiv_{ def}\; \; {\rm{P(}}x,\ y{\rm{)}} \wedge {\rm{P(}}y,\ x{\rm{)}} \quad \quad \quad \quad \ \qquad\ \ \ \quad \quad \quad \ \ \ \ //{x \ {\rm{equals}} \ y}} \cr {{\rm{O(}}x, \ y{\rm{)}}} \hfill & { \quad \equiv_{ def}\; \; \exists \,z({\rm{P(}}z, \ x{\rm{)}}\wedge {\rm{P(}}z, \ y{\rm{))}} \quad \quad \quad \ \quad \quad \quad \ \qquad\ \ \ \, //{x \ {\rm{overlaps}} \ y}} \cr {{\rm{PO(}}x,\ y{\rm{)}}} \hfill & { \quad \equiv_{ def}\; \; {\rm{O(}}x,\ y{\rm{)}} \wedge \neg \,{\rm{P(}}x,\ y{\rm{)}}\, \wedge \neg \,{\rm{P(}}y, \ x{\rm{)}} \quad \quad \ \quad \ \ \quad //{x \ {\rm{partially}} \ {\rm{overlaps}} \ y}} \cr {{\rm{DR(}}x, \ y{\rm{)}}} \hfill & { \quad \equiv_{ def}\; \; \neg {\rm{O(}}x, \ y{\rm{)}} \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \ \qquad\ \,\quad \, \,\ //{x \ {\rm{is}} \ {\rm{discrete}} \ {\rm{from}} \ y}} \cr {{\rm{EC(}}x, \ y{\rm{)}}} \hfill & { \quad \equiv_{ def}\; \; {\rm{C(}}x, \ y{\rm{)}}\, \wedge \neg {\rm{O(}}x, \ y{\rm{)}} \quad \quad \quad \quad \quad \quad \quad \quad \ \,\ \ \quad\ \, //{x \ {\rm{is}} \ {\rm{externally}} \ {\rm{connected}} \ {\rm{with}} \ y}} \cr {{\rm{TPP(}}x, \ y{\rm{)}}} \hfill & { \quad \equiv_{ def}\; \; {\rm{PP(}}x, \ y{\rm{)}}\, \wedge \,\exists z{\rm{(EC(}}z, \ x{\rm{)}} \wedge {\rm{EC(}}z, \ y{\rm{))}} \ \ \quad \, \ \,\ //{x \ {\rm{is}} \ {\rm{a}} \ {\rm{tangential}} \ {\rm{proper}} \ {\rm{part}} \ {\rm{of}} \ y}} \cr {{\rm{NTPP(}}x, \ y{\rm{)}}} \hfill & { \quad\equiv_{ def}\; \; {\rm{PP(}}x, \ y{\rm{)}}\, \wedge \neg \,\exists z{\rm{(EC(}}z, \ x{\rm{)}} \wedge {\rm{EC(}}z, \ y{\rm{))}} \ \ \quad \ //{x \ {\rm{is}} \ {\rm{a}} \ {\rm{non{\hbox -} tangential}} \ {\rm{proper}} \ {\rm{part}} \ {\rm{of}} \ y}} \cr {{{{\rm{P}}}^{{\rm{ - 1}}}} (x,\ y)} \hfill & { \quad \equiv_ {def}\; \; {\rm{P(}}y, \ x{\rm{)}} \ \qquad \ \ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \ \, //{y \ {\rm{is}} \ {\rm{a}} \ {\rm{part}} \ {\rm{of}} \ x}} \cr {{\rm{P}}{{{\rm{P}}}^{{\rm{ - 1}}}} (x,\ y)} \hfill & { \quad \equiv_{ def}\; \; {\rm{PP(}}y, \ x{\rm{)}} \ \qquad \ \,\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \, \ \ \, //{y \ {\rm{is}} \ {\rm{a}} \ {\rm{proper}} \ {\rm{part}} \ {\rm{of}} \ x}} \cr {{\rm{TP}}{{{\rm{P}}}^{{\rm{ - 1}}}} (x,\ y)} \hfill & { \quad \equiv_{ def}\; \; {\rm{TPP(}}y, \ x{\rm{)}} \ \qquad \ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \ \ \ \,\ //{y \ {\rm{is}} \ {\rm{a}} \ {\rm{tangential}} \ {\rm{proper}} \ {\rm{part}} \ {\rm{of}} \ x}} \cr {{\rm{NTP}}{{{\rm{P}}}^{{\rm{ - 1}}}} (x,\ y)} \hfill & { \quad \equiv_{def}\; \; {\rm{NTPP(}}y, \ x{\rm{)}} \quad \quad \quad \quad \quad \ \qquad\,\quad \quad \quad \quad \quad \quad \,\ \,// {y \ {\rm{is}} \ {\rm{a}} \ {\rm{non {\hbox-} tangential}} \ {\rm{proper}} \ {\rm{part}} \ {\rm{of}} \ x{}} }\hfill \right $$

By adding new primitive relations and functions, a much larger number of different relations can be defined upon the C relation (Cohn & Hazarika, Reference Cohn and Hazarika2001). This paper only presents a small fraction of the relations that can be expressed by RCC theory. If some of the above relations can form a set of JEPD relations and are closed under composition, then they generate a relation algebra; thus, the reasoning about these relations can be done by the path-consistency algorithm mentioned in Section 2. DC, EC, PO, EQ, TPP, NTPP, TPP⁻¹ and NTPP⁻¹ are the eight JEPD relations of the constraint language RCC8,Footnote ¹ as shown in Figure 1. They are of particular interest, for they form the smallest set of base relations that allows topological distinctions rather than just mereological, that is, being expressed by part–whole relationship (Randell et al., Reference Randell, Cui and Cohn1992b; Renz, Reference Renz2002) RCC5 is the coarser edition of RCC8, containing five base relations DR, PO, EQ, PP and PP⁻¹, and does not take the boundary of a region into account.

Figure 1

The eight jointly exhaustive and pairwise disjoint relations of region connection calculus (RCC8). The arrows show which relation is the next relation a configuration would transit to, assuming the continuous movements or deformations. This structure has been called a continuity network (Cohn et al., Reference Cohn, Bennett, Gooday and Gotts1997: 295) or a conceptual neighborhood (Cohn & Hazarika, Reference Cohn and Hazarika2001: 7; Cohn & Renz, Reference Cohn and Renz2007: 564)

A series of extensions and completions of RCC theory have been made: the density axiom of the RCC has been shown to be redundant and each RCC model leads to a Boolean algebra (Düntsch et al., Reference Düntsch, Wang and McCloskey2001). Three maximal tractable subsets of RCC8: $$\[--><$> {{\hat{{\cal H}}}_8} <$><!--$$ , $$\[--><$> {{{\cal C}}_8} <$><!--$$ and $$\[--><$> {{{\cal Q}}_8} <$><!--$$ have been given in Renz (Reference Renz2002). Each RCC model is a consistent model of the RCC8 CT (the consistency-based composition table of RCC8) and no RCC model can be interpreted extensionally anyway, thus giving a negative answer to Bennett's conjecture, which is to remove the universal region from the domain of possible referents of the region constants (Li & Ying, Reference Li and Ying2003). A generalization of RCC (GRCC; Li & Ying, Reference Li and Ying2004) is introduced, which accommodates both discrete and continuous spatial information. Each countable RCC model (compared with the ‘standard RCC in continuous space’) can be constructed hierarchically from a sequence of finite GRCC models, and every finite GRCC model can be isomorphically embedded in any RCC model; this bridges the gap between qualitative and quantitative approaches for spatial information (Li et al., Reference Li, Ying and Li2005). Consistency w.r.t. RCC theory is equivalent to consistency w.r.t. topology, and an O(n ³) algorithm for generating a realization of any path-consistent network of RCC8 base relations has been proposed, proving that any consistent RCC8 network has a realization in the digital plane and in any RCC model (Li, Reference Li2006b). Any consistent RCC8 binary constraint network can be consistently extended (Li & Wang, Reference Li and Wang2006), which removes the doubts about the complexity analysis of RCC8, that is, whether the reduction method proposed in Renz and Nebel (Reference Renz and Nebel1999) works for all calculi using weak compositions, given that the composition table of RCC8 is a weak one.

N-intersections are an alternative representation framework of mereotopology based on point-set topological theory. An object can be seen as a point set embedded in a specified space. For example, a region is a homogeneous 2D point set x embedded in $$\[--><$> {{{\Bbb R}}^2} <$><!--$$ related to three point sets: the interior (x°) is the union of all open sets in x, the boundary ( $$\[--><$> \partial x <$><!--$$ ) is the intersection of the closure of x and the closure of the exterior of x, and the exterior (x ⁻) is the set of all points not contained in x. In the simplest case, only the interior (x°) and the boundary ( $$\[--><$> \partial x <$><!--$$ ) are considered. The relationship between any two (simply connected) 2D regions x and y can be characterized by a 2 × 2 matrix called the four-intersection matrix (4IM; Egenhofer & Franzosa, Reference Egenhofer and Franzosa1991):

$$ {{\rm{R}}(x,y)\, = \:\left[ {\matrix{{{x}^ \circ } \bigcap {{y}^ \circ} & {{{{x}^ \circ } \bigcap \partial y}} \cr {\partial x\bigcap {{y}^ \circ } } & {\partial x\bigcap \partial y}}}\right] $$

After taking into account the constraints imposed by the physical reality of planar space and some specific assumptions about the regions, it turns out that there are exactly eight valid matrices that correspond to the RCC8 and RCC5 relations, as shown in Figure 2. Egenhofer et al. (Reference Egenhofer, Clementini and Felice1994a) have shown that the topological relationship between regions with holes can be classified by not only the relationship between each pair of regions but also the relationship each hole of each region has w.r.t. the other region and each of its holes, where the topological relationships between basic elements (regions and holes) are the eight basic relationships discerned by 4IM. The shortcomings of this approach are that the resulting relations are dependent on the number of holes, as the number of holes increasing this approach will be inefficient and painstaking. A method independent of holes is proposed in Vasardani and Egenhofer (Reference Vasardani and Egenhofer2009), which is based on the 23 JEPD relations between a region and a region with a hole (Egenhofer & Vasardani, Reference Egenhofer and Vasardani2007). It shows that there are 152 basic topological relations (Vasardani & Egenhofer, Reference Vasardani and Egenhofer2008) between single-holed regions.

Figure 2

The corresponding basic relations of 4-intersection matrix (4IM), region connection calculus (RCC8) and RCC5

Considering the exterior (x ⁻), the 4IM is extended into 9IM; one can use this calculus to classify the relationship not only between pairs of regions but also between all combinations of lines, points and regions (Egenhofer & Herring, Reference Egenhofer and Herring1991; Egenhofer et al., Reference Egenhofer, Mark and Herring1994b). Dividing the exterior of a concave region into two parts, the inside and outside of the convex hull, the 9IM is extended to 16IM (Ouyang et al., Reference Ouyang, Fu and Liu2009b), which is a refinement of RCC23 (Cohn, Reference Cohn1995), a calculus discriminating the topological relationship between concave regions:

$${{\rm{R}}(x,\,y)\, = \left[ {\matrix{{{x}^ \circ} \,\bigcap \,{{y}^ \circ} & {{{x}^ \circ } \,\bigcap \,\partial y} & {{{x}^ \circ } \,\bigcap \,{{y}^{\rm{-}}}} \cr {\partial x\,\bigcap \,{{y}^ \circ}} & {\partial x\,\bigcap \,\partial y} & {\partial x\,\bigcap \,{{y}^{\rm{ - }}} } \cr {{{x}^{\rm{ - }}} \,\bigcap \,{{y}^ \circ } } & {{{x}^{\rm{ - }}} \,\bigcap \,\partial y} & {{{x}^{\rm{ - }}} \,\bigcap \,{{y}^{\rm{ -}}}}}}\right] $$

Different calculi with more JEPD relations can be derived by changing the assumptions about what kind of space the entities are in and what information the cells of the matrix represent. For example, three new relations can be identified between the regions on the spherical surface (Egenhofer, Reference Egenhofer2005). If the exterior of the entity is replaced by its voronoi-region in the 9IM, a more comprehensive calculus V9I (Voronoi-based 9-intersection; Chen et al., Reference Chen, ming Li, lin Li and Gold2001) is obtained. One can derive a calculus for representing and reasoning about regions in $$\[--><$> {{{\Bbb Z}}^2} <$><!--$$ rather than $$\[--><$> {{{\Bbb R}}^2} <$><!--$$ , in which case the base relations in $$\[--><$> {{{\Bbb R}}^2} <$><!--$$ is a strict subset of those in $$\[--><$> {{{\Bbb Z}}^2} <$><!--$$ because of the one-pixel extent the boundary of a raster region has (Egenhofer & Sharma, Reference Egenhofer and Sharma1993). Alternatively, one can extend the representation in each matrix cell by the dimension of the intersection rather than emptiness and non-emptiness, which is called the dimension entended method (DEM). To handle the large number of possible relationships identified by the DEM, the calculus-based method has been proposed to group all possible cases into five meaningful topological relationships: disjoint, touch, in, overlap and cross (Clementini et al., Reference Clementini, Felice and van Oosterom1993). Besides the dimension of the non-empty intersection, the types (touching, crossing and different refinements of crossings), the relationships w.r.t. the exterior neighborhoods and sequence can also be used to discriminate fine-grained relationships and evaluate the topological similarity between any two pairs of spatial objects, which have the same topological relation (Egenhofer & Franzosa, Reference Egenhofer and Franzosa1995).

It should be noticed that the above calculi are mostly concerned about topological relationships that are discernible between simple spatial objects such as points, lines or disk-like regions in 2D spaceFootnote ². However, in practice, spatial objects are the deformations or aggregations of these primary elements or entities in 3D space, such as complex points, compound regions or bodies. 9IM is the most popular calculus to reason the topological relationships between these objects. Compared with the eight possible 9IM matrices over simple regions, it has been proved that only 43 (out of 2⁹ = 512) matrices are identified as realizable over general regions, where a general region is a non-empty, proper, regular, closed subset of the Euclidean plane (Li, Reference Li2006a). According to 25 rules that encode the constraints imposed by physical space and assumptions relating to spatial objects in 3D space, only 69 valid 9IM matrices remain and can discriminate 279 different relationships between all types of combinations of objects (Zlatanova, Reference Zlatanova2000). Given the definitions of complex points (finite collections of single points), complex lines (finite collections of one-dimensional curves) and complex regions (multi-part regions possibly with holes), one can use 9IM to classify 248 exclusive relations for all type combinations (Schneider & Behr, Reference Schneider and Behr2006). A nested matrix, called the 9+-intersection matrix that extends each matrix cell by a sub matrix, gives a systematic way representing different topological relations in planar space, cubic space, circle and spherical surface (Kurata, Reference Kurata2008).

Ever since Allen (Reference Allen1983) gave the composition table for the Interval Algebra (he actually called it the transitivity table), building composition tables has become a major challenge for current QSR approaches (Randell et al., Reference Randell, Cohn and Cui1992a). El-Geresy and Abdelmoty (Reference El-Geresy and Abdelmoty2004) present a general method for automatic derivation of such tables between different types of objects according to the space division theory inside the 9IM.

3.2 Direction

Direction relations describe where a spatial entity is placed relative to one another, which is more constrained than topological information but less constrained than metrical information. It usually involves three primary elements: the target object, the reference object and the reference frame; thus, in contrast to the binary relationships usually found in mereotopological calculi, direction relations can be binary (if the reference frame is implicit), ternary or with even more arguments. Depending on the dimension of the objects involved, direction calculi can be divided into two categories: one based on the points and the other based on extended objects.

The two most common binary point-based calculi are cone-shaped direction (Frank, Reference Frank1991) and projection-based (Frank, Reference Frank1996) direction, shown in Figures 3 and 4, respectively. The basic relations of the cone-shaped calculus are based on the four or eight disjoint sectors of the space divided by the lines going through the reference point, whereas the basic relations of the projection-based calculus are decided by the horizontal and vertical lines across the reference point. Their combination with a coarser version of double-cross (Freksa, Reference Freksa1992) calculus leads to a more expressive calculus $$\[--><$> c{\cal C}{\cal O}{\cal A} <$><!--$$ (Isli et al., Reference Isli, Haarslev and Möller2003), which claims to integrate directions in geography and those of human perception. For oriented points (an abstraction of objects with an intrinsic direction), the Oriented Point Algebra ( $$\[--><$> {\cal O}{\cal P}{\cal R}{\cal A} <$><!--$$ ) (Moratz, Reference Moratz2006) can be used to describe the relative direction information, which can be seen as an extension of the cone-shaped calculus. Scalable granularity is used in $$\[--><$> {\cal O}{\cal P}{\cal R}{{{\cal A}}_m} <$><!--$$ (Mossakowski & Moratz, Reference Mossakowski and Moratz2012) dealing with information with different granularities in one frame, where m is the number of lines going through the points. As shown in Figure 5, $$\[--><$> {{x}_4}\angle _{{13}}^{3} y <$><!--$$ denotes that oriented point x lies on the third part of the space divided by the lines going through oriented point y, whereas y lies on the 13th part decided by x, where 4 means that there are four lines going through points and divide the space around the points equally.

Figure 3

Cone-shaped direction relations (Isli et al., Reference Isli, Haarslev and Möller2003: 7)

Figure 4

Projection-based direction relations (Isli et al., Reference Isli, Haarslev and Möller2003: 7)

Figure 5

A basic relation $$\[--><$> {{x}_4}\angle _{{13}}^{3} y <$><!--$$ in $$\[--><$> {\cal O}{\cal P}{\cal R}{{{\cal A}}_4} <$><!--$$ (Mossakowski & Moratz, Reference Mossakowski and Moratz2012: 37)

The CYCORD (short for CYClic ORDering) system is a ternary relation calculus based on the cyclic ordering relation CYCORD (x, y, z), which is true when x, y and z are clockwise in 2D space. It shows that a number of qualitative calculi can be translated into the CYCORD system, but reasoning in it is NP complete (Röhrig, Reference Röhrig1994, Reference Röhrig1997). $$\[--><$> {\cal C}{\cal Y}{{{\cal C}}_t} <$><!--$$ is a refinement of CYCORD system, which leads to a ternary relation algebra containing 24 basic relations, as shown in Figure 6. A basic relation expresses for triples of orientationsFootnote ³ whether each of the three orientations is equal to, to the left of, opposite to or to the right of each of the other two orientations. The constraint propagation procedure is proved to be polynomial and complete for a subset including all atoms; it also delineates those situations when the consistency checking problem is tractable or NP complete (Isli & Cohn, Reference Isli and Cohn2000).

Figure 6

Pictorial examples of the 24 $$\[--><$> {\cal C}{\cal Y}{{{\cal S}}_t} <$><!--$$ basic relations, where l, e, o and r stands for to the left of, equal to, opposite to and to the right of, thus orl denotes that orientation y is opposite to x, z is to the right of y and z is to the left of x (Isli & Cohn, Reference Isli and Cohn2000: 156)

Motivated by cognitive considerations and based on relative direction information about spatial environments, the concept of view point is introduced in the ternary double-cross calculus (Freksa, Reference Freksa1992), as shown in Figure 7. A relation in the double-cross calculus can be seen as the relationship of a target point c w.r.t. a vector ab, denoted by ab : c, as there is no difference between view point and reference point. A binary composition operation and unary operations are defined: INV (derive ab : c from ba : c), HM (map ab : c to bc : a) and SC (derive ac : b from ab : c; Zimmermann & Freksa, Reference Zimmermann and Freksa1996) to compute all the possibilities between the three points. More relations can be derived when the double-cross calculus is extended to 3D space, as shown in Figure 8; this naturally increases the complexity of the calculus. Three models under different granularity are proposed to reduce the complexity and dealing with coarse direction information: length coarse model, height coarse model and general coarse model, where an accurate model can be derived from the integration of the above three coarse models (Pacheco et al., Reference Pacheco, Escrig and Toledo2002).

Figure 7

Fifteen base relations in the double-cross direction calculus, where l, s, r, f, i, b and n stand for left, straight, right, front, identical, back and neutral (Isli et al., Reference Isli, Haarslev and Möller2003: 7)

Figure 8

Double-cross direction calculus in 3D space (Pacheco et al., Reference Pacheco, Escrig and Toledo2002: 91)

A ternary point-based calculus is RST (the initials of rotation, scaling and translation) (Scivos & Nebel, Reference Scivos and Nebel2004) if the relations are invariant when all points are mapped by rotations, scalings or translations. Examples for such RST calculi are the double-cross (Freksa, Reference Freksa1992), the flip-flop (Ligozat, Reference Ligozat1993) (also called $$\[--><$> {\cal L}{\cal R} <$><!--$$ in Scivos and Nebel (Reference Scivos and Nebel2004), as shown in Figure 9) and the Ternary Point Configuration Calculus (TPCC; Moratz & Ragni, Reference Moratz and Ragni2008). However, it has been proved (Wolter & Lee, Reference Wolter and Lee2010) that a qualitative calculus expressive enough to distinguish from left to right of including flip-flop (Ligozat, Reference Ligozat1993), double-cross (Freksa, Reference Freksa1992), dipole (Moratz et al., Reference Moratz, Renz and Wolter2000), $$\[--><$> {\cal O}{\cal P}{\cal R}{\cal A} <$><!--$$ (Moratz, Reference Moratz2006) and TPCC (Moratz & Ragni, Reference Moratz and Ragni2008), existing relation algebraic approach is too weak for deciding consistency problems and all reasonable sub-algebras remain NP-hard, that is, directional relation calculi are inherently intractable.

Figure 9

Pictorial illustration of seven base relations in the $$\[--><$> {\cal L}{\cal R} <$><!--$$ calculus when $$\[--><$> x\not= y <$><!--$$ . l, f, r, b and c stand for left, further, right, back and closer (Scivos & Nebel, Reference Scivos and Nebel2004: 285)

The above is a brief summary of point-based direction. Direction relations between extended objects are more complex, for extended objects often have intrinsic directions and shapes in themselves. Therefore, to simplify the process, MBRs (Minimal Bounding Rectangles) are often used as the approximation of such objects. This approach translates the direction relation between the MBRs into a pair of interval relations, where the intervals are the projections of MBRs on each axis. Examples of such approaches are: 2D-String (Chang et al., Reference Chang, Shi and Yan1987) as shown in Figure 10, its extension 2D-CString (Lee & Hsu, Reference Lee and Hsu1990) and 2D-GString (Chang et al., Reference Chang, Jungert, Green, Gray and Powers1996), the two-dimensional extension of Interval Algebra (Allen, Reference Allen1983), as shown in Figure 11, the Rectangle Algebra (Balbiani et al., Reference Balbiani, Condotta and del Cerro1998, Reference Balbiani, Condotta and del Cerro1999a), as shown in Figure 12, and the three-dimensional extension the Block Algebra (Balbiani et al., Reference Balbiani, Condotta and del Cerro1999b). It should be noticed that these string-based and interval algebra-based methods can represent not only the direction information but also topological informationFootnote ⁴. A string-based model only dealing with topological information is presented in Li and Liu (Reference Li and Liu2010).

Figure 10

An example of a 2D-string (Chang et al., Reference Chang, Shi and Yan1987: 414)

Figure 11

The 13 basic relations of the Interval Algebra (Allen, Reference Allen1983: 835)

Figure 12

An example of the basic rectangle algebra relation x (m, p) y

The direction information described by MBR-based calculi is relatively coarse and cannot express the direction influenced by the shape of the objects in precise reasoning. The cardinal direction matrix (direction matrix for brevity; Goyal & Egenhofer, Reference Goyal and Egenhofer2000, Reference Goyal and Egenhofer2001) and Cardinal Direction Calculus (CDC; Skiadopoulos & Koubarakis, Reference Skiadopoulos and Koubarakis2004, Reference Skiadopoulos and Koubarakis2005) are the two most well-known binary direction relation calculi.

A direction matrix is a 3 × 3 matrix (Goyal & Egenhofer, Reference Goyal and Egenhofer2000, Reference Goyal and Egenhofer2001), whose elements have the same topological organization as the nine direction tiles formed by the corresponding MBR of the reference object, as shown in Figure 13. The content of each entry of a direction matrix is decided by whether the target object intersects with it. After taking into account the constraints imposed by simple regions, it turns out that only 218 of the 2⁹ − 1 = 511 matrices are realizable. When dealing with objects with different dimensions, the deep direction relation matrix (Goyal & Egenhofer, Reference Goyal and Egenhofer2000) is used, where each cell of the matrix is a nine-bit neighbor code recording the information about intersections with the direction tiles and the neighboring boundary. Instead of the Boolean value of the intersection, the cell of the matrix can also represent the percentage of how much the target object intersects with each direction tile, which is useful for similarity assessment (Goyal & Egenhofer, Reference Goyal and Egenhofer2001). In a topological calculus, usually each basic relation corresponds to only one basic relation when inverted: for example, the converse relation of PP (x, y) is PP⁻¹ (y, x). However, in the direction matrix calculus, one direction matrix may have several valid converse matrices; for example, the matrix representing the direction relation NE:E and E are both valid converses of the matrix of W. It has been proved (Cicerone & Felice, Reference Cicerone and Felice2004) that of the 218² possibilities, only 2004 pairs of matrices are realizable over simple regions, although this is still a huge number of relations.

Figure 13

A pictorial example of the nine direction tiles divided by the Minimal Bounding Rectangle (MBR) of reference object y and the corresponding representations in direction matrix and Cardinal Direction Calculus (CDC)

In contrast to direction matrices, an arbitrary basic CDC relation (Skiadopoulos & Koubarakis, Reference Skiadopoulos and Koubarakis2004, Reference Skiadopoulos and Koubarakis2005) is a binary relation involving a target object and a reference object, and a symbol that is a non-empty subset of nine atomic relations, which has similar semantics to the nine direction tiles in direction matrix. The most important difference between the two calculi is the semantics of intersections of the target object and the direction tiles (Chen et al., Reference Chen, Jia, Liu and Zhang2010a). In the direction matrix, the only question is whether there is an intersection, so the intersecting part can be a point, a line or a region. But in the CDC, the intersecting part must at least be a sub region of the target object, as shown in Figure 14.

Figure 14

A pictorial example of the difference between the direction matrix representation and Cardinal Direction Calculus (CDC): x and y intersect on y′s left border, but due to the definitions, the direction relations between x and y are different in direction matrix and CDC (Chen et al., Reference Chen, Jia, Liu and Zhang2010a: 280)

An O(n ⁵) and an improved cubic consistency checking algorithm for the basic CDC constraints are given in Skiadopoulos and Koubarakis (Reference Skiadopoulos and Koubarakis2005) and Liu et al. (Reference Liu, Zhang, Li and Ying2010), respectively. It has been proved that composition in CDC is weak composition (Skiadopoulos & Koubarakis, Reference Skiadopoulos and Koubarakis2004) and consistency checking a set of unrestricted CDC constraints is NP-complete (Skiadopoulos & Koubarakis, Reference Skiadopoulos and Koubarakis2005; Liu et al., Reference Liu, Zhang, Li and Ying2010). However, by introducing the rectangle algebra into CDC, a tractable subset including 36 base rectangular relations has been identified (Navarrete & Sciavicco, Reference Navarrete and Sciavicco2006); the rectangle-based inverting rules (Chen et al., Reference Chen, Jia, Liu and Zhang2010a) and composition (Chen et al., Reference Chen, Jia, Liu and Zhang2010b) are given, and these can be easily extended to cubic space. Neither the direction matrix nor CDC can handle direction information between overlapping and contained regions properly. ICD (Internal Cardinal Direction; Liu et al., Reference Liu, Wang, Jin and Wu2005) solves this problem partially, but the notable inherent shortcoming is that the ICD relations are not closed under converse. For example, if x and y have a specific ICD relation, the relationship between y and x will not be in ICD anymore. The interior-boundary direction calculus settles this problem (Du et al., Reference Du, Guo and Wang2008a).

However, it can be argued that the direction partition in the direction matrix and CDC is unnatural. Typically, people tend to organize surrounding space using lines with angles similar to the cone-based model, and hence the cone-based partition is arguably more intuitive and descriptive (Huttenlocher et al., Reference Huttenlocher, Hedges and Duncan1991; Franklin et al., Reference Franklin, Henkel and Zangas1995). An alternative family of direction relation models (Skiadopoulos et al., Reference Skiadopoulos, Sarkas, Sellis and Koubarakis2007) is proposed, where the reference object is approximated by its MBR as with the direction matrix and CDC, but the space around the reference object is partitioned into five zones using the cone-based model; thus, the family contains an infinite number of models identified by the unique value for $$\[--><$> \varphi {{(0}^ \circ } \, \lt \,\varphi \, \lt \,{{90}^ \circ } ) <$><!--$$ defining the original angle of the space partitioning lines, as shown in Figure 15. For a given $$\[--><$> \varphi <$><!--$$ , the five partitioned zones correspond to five atomic relations, and result in 2⁵ − 1 = 31 basic relations in the calculus, which is significantly smaller than the respective sets of CDC or direction matrix, which contains 511 basic relations, respectively.

Figure 15

The five direction tiles formed by the Minimal Bounding Rectangle (MBR) of reference object y and the four lines starting at the vertices of the MBR with a horizontal angle of $$\[--><$> \varphi <$><!--$$ in the cone-shaped Cardinal Direction Calculus (CDC; Skiadopoulos et al., Reference Skiadopoulos, Sarkas, Sellis and Koubarakis2007: 1118)

The projective direction calculus is the most prominent ternary calculus. This calculus is built on a partition of the plane into five separate zones: before, between, after, left side and right side, which are obtained from projective properties of two reference objects as shown in Figure 16. Then, by considering the empty/non-empty intersections of a primary object with these zones, the model is able to distinguish 34 different projective relations (Clementini & Billen, Reference Clementini and Billen2006). Its extension to a spherical surface is addressed in Clementini (Reference Clementini2008). The converse, rotation and composition rules are discussed in Clementini et al. (Reference Clementini, Skiadopoulos, Billen and Tarquini2010).

Figure 16

A pictorial example of five separate zones in ternary projective relations, where a is on the left side and after b and c, denoted by ls:af (a, b, c) (Clementini & Billen, Reference Clementini and Billen2006: 805)

Although above direction calculi partially support complex objects such that the target object is a multi-part region, they cannot always yield precise or may give counterintuitive results for certain spatial scenarios. For example, according to the CDC model, Argentina lies in partially same location and partially south of Brazil; however, in human intuition, Argentina lies partially to the southwest and west of Brazil. The main reason is that for complex objects one needs to consider the influence of shape in a much better manner. A two-phase model, called the Objects Interaction Matrix (OIM; Schneider et al., Reference Schneider, Chen, Viswanathan and Yuan2012), is proposed to solve these problems and determine the cardinal direction even between complex regions. It consists of a tiling and interpretation phase. In the tiling phase, a tiling strategy first determines a bounding grid called objects interaction grid. Then for each grid cell it stores the information on how the region objects intersect with the corresponding tile, which leads to the OIM. In the subsequent interpretation phase, an interpretation method is used to the OIM and determines the detail of cardinal directions.

3.3 DistanceFootnote ⁵

The spatial representation of distance can be classified into two main groups: absolute and relative. Absolute approaches usually measure the distance between two objects, such as ‘the distance between A and B is 100 meters’ or ‘A is close to B’. Relative approaches often involve the comparison to a third object. For example, ‘A is closer to B than that to C’. Absolute approaches can be qualitative or quantitative, whereas relative approaches are in generally qualitative.

Distance relations alone are not enough in reasoning, normally direction relations are needed too: for instance, given the distance from A to B and from A to C, to determine the distance from B to C, the direction relations between these three points are necessary. A straightforward idea is to combine directions as represented by segments of the compass with a separate distance metric, which leads to a unified framework across different levels of granularities in Clementini et al. (Reference Clementini, Felice and Hernández1997), as shown in Figure 17. One approach combines the Delta calculus (Zimmermann & Freksa, Reference Zimmermann and Freksa1996) with point-based directions, but only a restricted set of distance distinctions can be identified (Zimmermann, Reference Zimmermann1993). Another approach combines qualitative distance with qualitative direction angles and then formulates a set of qualitative inference rules called qualitative trigonometry and qualitative arithmetic (Liu, Reference Liu1998). Several examples are illustrated as to how to use this method in qualitative spatial constraints analysis, such as reducing the search space in a simulated annealing-based quantitative value assignment problem. TPCC is proposed in Moratz and Ragni (Reference Moratz and Ragni2008), where direction knowledge is represented in the double-cross calculus (Freksa, Reference Freksa1992) and distance measurements are based on the two of the three points. It has 27 atomic JEPD relations as shown in Figure 18 and hence gives finer distinction than in previously published calculi.

Figure 17

An iconic representation of the combination of cone-shaped direction and absolute distance: very close(vc), close(cl), commensurate(cm), far(fr) and very far(vf) (Clementini et al., Reference Clementini, Felice and Hernández1997: 324)

Figure 18

A pictorial representation of 27 basic relations in Ternary Point Configuration Calculus (TPCC), where f, b, l, r, s, d, c stand for front, back, left, right, straight, distant and close (Moratz & Ragni, Reference Moratz and Ragni2008: 79)

3.4 Moving objects

With the popularization of mobile positioning and communication, moving objects have become a new point of focus for QSR. To facilitate information collection and processing, moving objects are often abstracted as points, and the focus is mainly on the relationships between the trajectories formed by these moving points. Although certain direction information is included for moving objects, the essential difference is that this kind of calculus commonly describes the relative motion between objects but not the relative direction between the static objects at any given time point.

One simple method approximates trajectories as oriented line segments and then expressing movements by the relative position between the segments, which leads to several segment-based calculi. One approach abstracts such oriented line segments as dipoles constituted by the start points and end points. It distinguishes the location and orientation of different dipoles according to whether a point lies to the left, to the right or shares the same point with the start or the end point of the referring dipole. Then it forms a relation algebra called the Dipole calculus (Moratz et al., Reference Moratz, Renz and Wolter2000) including 24 basic relations; however, reasoning over these relations is NP-hard. For example, ‘x ells y’ as shown in Figure 19 denotes the case that the start point of x shares the same point with the end point of y, the end point of x lies to the left of y, whereas the start point of y lies to the left of x and the end point of y and shares the same point with the start point of x. Another approach is based on interval algebra (Allen, Reference Allen1983). By considering whether the direction of two intervals is same or not, the interval algebra can be extended to the directed interval algebra (DIA) (Renz, Reference Renz2001). DIA can be seen as the Cartesian product of the interval algebra with {=, ≠}, which represent whether the orientations of two intervals are same or not; thus, the calculus includes 26 basic relations, as shown in Figure 20. Path consistency decides the consistency for a certain subset of DIA, which contains all basic relations. The major disadvantage of the DIA is that it is only suitable for movements in one dimension; free or restricted 2D movements are not supported by the DIA. A corresponding refinement of DIA on a road network is introduced in Wang et al. (Reference Wang, Liu and Liu2005).

Figure 19

Basic relations of the Dipole calculus, where l, r, s, e stand for left, right, start point and end point, and the oriented line segment x and y are denoted by solid and dotted line separately (Moratz et al., Reference Moratz, Renz and Wolter2000: 235)

Figure 20

Basic relations of directed interval algebra (DIA), where b, f, m, o, c, e, eq stand for behind, in-front-of, meets, overlaps,contained in, extends and equals, respectively. = denotes that both intervals have the same orientation and ≠ for opposite. x is represented by a solid arrowed interval while y is by a dotted arrowed interval (Renz, Reference Renz2001: 52)

Rather than comparing relative movements over a pair of fixed intervals, the family of QTC (Qualitative Trajectory Calculus) calculi compares trajectories point by point by considering instantaneous relative motions. In these calculi, the point-wise relative motions between different spatial entities are mapped to one of the qualitative values {−, +, 0}, denoting toward, away from and stable. In the basic Qualitative Trajectory Calculus (QTC_B; de Weghe et al., Reference de Weghe, Cohn and Maeyer2004), the direction frame is compass-like and the base relations can be represented by tuples of qualitative values as shown in Figure 21. For example, (+, 0) means that the first object is moving away from the second object's position and the second object is stable with respect to the first object_’s position. QTC_B is expressive enough to describe movements such as a carnivore hunting a prey; however, for movements such as vehicles traversing crossroads, the complex double-cross direction (Freksa, Reference Freksa1992) frame is needed, and therefore the QTC Double-Cross (QTC_C; de Weghe et al., Reference de Weghe, Cohn, Maeyer and Witlox2005a) has been defined. QTC_C includes 81 base relations and the rules for composing relations are given in de Weghe et al. (Reference de Weghe, Kuijpers, Bogaert and Maeyer2005b).

Figure 21

Basic relations of basic Qualitative Trajectory Calculus (QTC_B) in a conceptual neighborhood diagram. The solid dots represent the stationary objects and the open dots represent the moving objects (de Weghe et al., Reference de Weghe, Cohn and Maeyer2004: 1103)

According to Moreira et al. (Reference Moreira, Ribeiro and Saglio1999), there are two types of moving objects: objects that have a completely free trajectory, which is only constrained by the dynamics of the object itself (e.g. a bird flying through the sky), and objects that have a constrained trajectory (e.g. a car on a road network). QTC_B and QTC_C can describe two objects moving freely in a plane but not objects with constrained trajectories in a network. The network version of QTC, QTC_N (Bogaert et al., Reference Bogaert, de Weghe, Cohn, Witlox and Maeyer2006), is proposed where the movement toward or away from is defined along the shortest path in a network between two objects, rather than the Euclidean distance as in QTC_B. Whereas the topological structure of the network can change with time, the QTC on changing networks QTC_DN (Delafontaine et al., Reference Delafontaine, de Weghe, Bogaert and Maeyer2008) is derived from QTC_N. A prototype of QTC-based information system has been implemented in Delafontaine et al. (Reference Delafontaine, Cohn and de Weghe2011).

3.5 Shape

Shape is perhaps one of the most important characteristics of an object, but it is also particularly difficult to describe qualitatively. Topological information can express limited shape information, such as whether there is a hole in a region or the interior is connected; this information is too weak for finer grained distinctions for shape information. Although direction and distance have already added something to pure mereotopology, these calculi and models are not directly applicable for shape description.

Region-based methods focus on the interior of objects. A hierarchical representation approach is presented in Cohn (Reference Cohn1995). It uses two primitive notions: that of two regions connecting and the convex hull of a region, computing the topological relationships between the concavities in the convex hull and number of concavities, and then a wide variety of concave shapes can be distinguished as shown in Figure 22. However, the predicate to detect whether two concavities i ₁ and i ₂ in the convex hull of region x lie on the same side of x, SameSide (i ₁, i ₂, x) in Cohn (Reference Cohn1995) does not always give the correct answer. This problem is solved in Ouyang et al. (Reference Ouyang, Fu and Liu2009a) by an improved SameSide* predicate definition and an algorithm based on detecting concave concavities and transforming them to convex concavities, which are amenable to the revised SameSide predicate definition. The convex hull is a powerful primitive and it has been shown that any pair of bounded, regular regions in 2D space can be distinguished by the three primitives: external connection, proper part of and being convex, if and only if they are not related by an affine transformation (Davis et al., Reference Davis, Gotts and Cohn1999).

Figure 22

Concave regions with different shapes distinguishable using convex hulls (Cohn, Reference Cohn1995: 313)

Most boundary-based methods distinguish shapes mainly by the sequence of different types of curvature extrema along its contour or the boundary segments. Galton and Meathrel (Reference Galton and Meathrel1999) generalized much of this work. Process-Grammar (Leyton, Reference Leyton1988) expresses the smooth shape evolution of a smooth 2D curve in terms of transitions at five extrema: M+, m+, M−, m− and 0 corresponding to actions: protrusion, squashing, internal resistance, indentation and zero-curvature, respectively, as shown in Figure 23.

Figure 23

A pictorial example of Process-Grammar (Leyton, Reference Leyton1988: 220)

In contrast to the smooth outline assumption in Leyton (Reference Leyton1988), a representation of outlines by means of strings over an alphabet of seven qualitative curvature types (as shown in Figure 24) is proposed in Galton and Meathrel (Reference Galton and Meathrel1999) that forms a formal language for the qualitative representation of two-dimensional outlines. $$\[--><$> {\cal T}{\cal L}{\cal T} <$><!--$$ (Tripartite Line Tracks; Gottfried, Reference Gottfried2003a, Reference Gottfried2003b) considers three end-point-connected lines then the medial line determines an orientation grid, which has 15 partitions. And the two endpoints are described with respect to the medial line by their position in the orientation grid. If only considers the general position (i.e., not considering the position on the lines), then it at most can one discern 36 different cases. Removing all the symmetrical relations of $$\[--><$> {\cal T}{\cal L}{{{\cal T}}_{36}} <$><!--$$ , there remain 12 distinguishable relations denoted by $$\[--><$> {\cal T}{\cal L}{{{\cal T}}_{12}} <$><!--$$ , where the subscript is the number of possible relations. Omitting the length information encoded in $$\[--><$> {\cal T}{\cal L}{{{\cal T}}_{12}} <$><!--$$ , only six relations are left. Thus, $$\[--><$> {\cal T}{\cal L}{\cal T} <$><!--$$ can describe 2D polygonal outlines by a sequence of different types of $$\[--><$> {\cal T}{\cal L}{{{\cal T}}} <$><!--$$ under different granularities (Figure 25).

Figure 24

A picture of the seven qualitative curvature types (Galton & Meathrel, Reference Galton and Meathrel1999: 1063)

Figure 25

Left: The orientation grid formed by line segment BC and an example polygon described by $$\[--><$> {\cal TLT}_{36}} <$><!--$$ ; Middle: Iconic representations of $$\[--><$> {\cal TLT}_{36}} <$><!--$$ ; Right: Iconic representations of $$\[--><$> {\cal TLT}_{12}} <$><!--$$ and $$\[--><$> {\cal TLT}_6} <$><!--$$ (Gottfried, Reference Gottfried2003b: 103, 104, 106)

Instead of considering three end-point-connected line segments, the $$\[--><$> {\cal B}{\cal A} <$><!--$$ (Bipartite Arrangements) Calculus (Gottfried, Reference Gottfried2004) describes arbitrary pairs of line segments and has 23 different base relations as shown in Figure 26. If one line of a polygon is made the basis, then the position of every other line can be described relative to it, using the relations of $$\[--><$> {\cal B}{\cal A} <$><!--$$ . Consequently, the list of $$\[--><$> {\cal B}{\cal A} <$><!--$$ relations so formed gives a qualitative shape representation, which is used in similarity assessment (Gottfried, Reference Gottfried2006, Reference Gottfried2008).

Figure 26

Left: Conceptual neighborhood of $$\[--><$> {\cal BA}{{}_{{\rm{23}}}} <$><!--$$ (right); Middle: iconic instantiations of all relations; Right: an example polygonal outlines described by $$\[--><$> {\cal BA}{{}_{{\rm{23}}}} <$><!--$$ , the bold vertical segment being the reference segment which is oriented upwards (Gottfried, Reference Gottfried2006: 114, 119)

6.3.6 Combinations of binary qualitative calculi

Many types or aspects of spatial relations are formed by making different abstractions of the objective (metric) spatial relations. Topology, distance, direction and shape are classified by the subjective motivations of how people observe the world. These aspects can be integrated. Compared with single-aspect spatial relations, integrating multi-aspect spatial relations has more potential for practical application, as expressiveness is increased and has become a focus in QSR research.

In QSR, existing calculi can be combined to create new formalisms (Wölfl & Westphal, Reference Wölfl and Westphal2009); for example, the rectangle algebra (block algebra) can be defined as a specific twofold (threefold) product of the interval algebra. Compared with such orthogonal cases (where there is no interaction between the component algebra), it is more challenging to combine calculi with interdependent semantics such as the work (Gerevini & Renz, Reference Gerevini and Renz2002) combining RCC8 and Point Algebra (Vilain et al., Reference Vilain, Kautz and van Beek1990). Two possible combining strategies (Wölfl & Westphal, Reference Wölfl and Westphal2009) can be found in these non-orthogonal combinations: loose combining and tight combining. Loose combining focuses more on reasoning and interactions between the component calculi, whereas tight combining in general leads to a new constraint language and can be more expressive.

The combinations of RCC8 with either qualitative or metric-size information are obvious examples of loose combinations (Gerevini & Renz, Reference Gerevini and Renz2002). It has been shown that, in each of the three maximal tractable subsets of RCC8, qualitative-size information does not increase reasoning complexity. However, with respect to the metric size, even when the set of topological relations is restricted to the eight basic relations, constraint network satisfaction is intractable; however, if some basic relation(s) are not used, then deciding the consistency becomes polynomial; for example, if PO is not permitted, which is a realistic assumption for applications where the variables represent physical objects. If we assume that all changes are continuous, then relations adjacent in time must be neighbors in the conceptual neighborhood diagram, and one can formalize temporal information and integrate it with topological and size information (Wang et al., Reference Wang, Liu, Hu and Wang2003).

Other loose combination examples concentrate on integrating topological information with region-based direction calculi. In Li (Reference Li2007), it is shown that, for the three maximal tractable subsets of RCC8, the satisfiability of a joint network of RCC8 and DIR₉ (MBR-based direction relations) is decided by the two satisfiability problems in RCC8 and rectangle algebra. In Liu et al. (Reference Liu, Li and Renz2009), it is proven that only considering basic relations, the joint network of RCC8 and rectangle algebra is tractable, but that of RCC8 and CDC is NP-complete. Furthermore, in Li and Cohn (Reference Li and Cohn2012), the bipath-consistency algorithm in Gerevini and Renz (Reference Gerevini and Renz2002) is proven to be able to separate the topological constraints in polynomial time from directional ones, when the topological constraints are taken from two tractable subclasses of RCC8 ( $$\[--><$> {{\hat{{\cal H}}}_8} <$><!--$$ , $$\[--><$> {{{\cal C}}_8} <$><!--$$ ), and directional constraints are from a sub-algebra of the rectangle algebra, termed DIR₄₉. Considering the mutual influence between topological and directional relations, it is natural to derive topological relations from direction relations, when topological information is unavailable for computing topological relations. In Guo and Du (Reference Guo and Du2009), it presents such computation methods for deriving topological relations from one and two CDC relations. In turn, because topological relations are less constrained than direction information; it makes little sense to derive direction information from topological relations. If the topological information is that x and y share a same part, then x must share a same part with MBR(y); therefore, only base CDC relation O can be exactly derived. If no same part is shared between x and y, then no useful direction information can be derived.

Tight combinations commonly form a new set of relations that can express multiple aspects of spatial information. In Sistla and Yu (Reference Sistla and Yu2000), a set of qualitative relations and reasoning rules are presented to describe both topological and directional information. The set of basic relations includes $$\[--><$> left\_of,\,right\_of,\,behind,\,in\_front\_of,\,above,\,below,\,inside,\,outside <$><!--$$ and overlaps, and it has been proven that its deductive system is complete for 3D space but is not complete for 2D space. The $$\[--><$> {\cal I}{\cal N}{\cal D}{\cal U} <$><!--$$ calculus (Pujari et al., Reference Pujari, Kumari and Sattar1999) can be seen as a tight combination of Interval Algebra with Point Algebra, that is, each basic relation includes not only the interval relations but also the size information represented by the point algebra, and it forms a JEPD relation set including 25 basic relations, as shown in Figure 27. The detailed analysis of its consistency is in Balbiani et al. (Reference Balbiani, Condotta and Ligozat2006). Extended rectangle relations (Chen et al., Reference Chen, Jia, Liu and Zhang2010c), the twofold product of $$\[--><$> {\cal I}{\cal N}{\cal D}{\cal U} <$><!--$$ relations, can be used for the integrating coarse representing and reasoning of the topological, directional and size information over MBRs.

Figure 27

25 basic relations of $$\[--><$> {\cal INDU} <$><!--$$ calculus (Pujari et al., 1999: 294)

3.7 Uncertainty

Uncertainty is an inherent characteristic of almost every aspect of knowledge representation in the real world. Although qualitative approaches can be seen as a technique dealing with uncertainty in some degree, as precise quantitative information may be unavailable or unnecessary; in practice, some situations cannot be properly represented by qualitative relations. For example, it is hard to define the accurate boundaries of regions. One reason is the limitation of observations: the object may have an explicit boundary but cannot be measured accurately. Another reason is intrinsic to the objects themselves, such as the boundary between a canyon and a river, or between mountains and flatlands: there is no exact boundary, but one would still like to represent that the mountains are adjacent to the flatlands.

Existing techniques for representing and reasoning about such uncertainty can be mainly classified into two categories: one approach extends existing spatial calculi specifically to express the indeterminacy, whereas the other applies mathematical tools, such as fuzzy sets and rough sets, to express the vagueness of the spatial objects or the spatial relationships.

Approaches in the former category often approximate the vagueness of regions by two nested crisp regions or a broad boundary. A vague region with indefinite boundary is represented by egg-yolk pairs (Cohn & Gotts, Reference Cohn and Gotts1996), a pair of nested traditional crisp regions. The yolk represents a minimum extension of the indefinite region, whereas the egg represents its maximum extension. The topological relations between the indefinite regions are represented by a quadruple of RCC relations between the component crisp regions. For example, $$\[--><$> F(yolk(x),egg(y)) <$><!--$$ means the RCC5 relation between the minimum extension of x and the maximum extension of y. A total of 46 different mereological relationships are identified by the quadruples. A generalization of the egg-yolk calculus (Roy & Stell, Reference Roy and Stell2001) is based on Lukasiewicz algebra, where the indeterminate regions include the crisp ones as a special case. A refinement of the egg-yolk model (Yu et al., Reference Yu, Liu and Liu2004) is based on the three predicates: P(x, y), C(x, y) and I(x, y), which mean that x has a part of y, x contains y and y contains x, respectively. Owing to the uncertainty, the value of the predicates is no longer a Boolean value but a value in a lattice, as shown in Figure 28. Value A means that all regions satisfy the predicate, N means there are no regions satisfying the predicate; {B, L, R, E} are refinements of the value M, that is, there may exist regions satisfying the predicate. Only considering boundary-insensitive RCC5, this approach can discriminate 14 different topological relations when the values of predicates are in {A, M, N} and 51 different topological relations, whereas the range of the predicates is {A, B, L, R, E, N}.

Figure 28

The value lattice (Yu et al., Reference Yu, Liu and Liu2004: 613)

The extension of the nine-intersection models (Clementini & Felice, Reference Clementini and Felice1997) looks very similar to the egg-yolk calculus but is not equivalent, as only 44 relations are discerned rather than the 46 relations in egg-yolk theory, and the conceptual neighborhood graph is different from that in egg-yolk theory; this difference arises from different assumptions about the nature of the regions. In the latter, it is assumed that the broad boundary is not so broad as to accommodate the other region. The indefinite boundary is approximated as a broad boundary ( $$\[--><$> \rDelta A <$><!--$$ ) in place of a sharp boundary ( $$\[--><$> \partial x <$><!--$$ ), as shown in Figure 29. It is shown in Clementini and Felice (Reference Clementini and Felice1997) that this extension can be used to reason not only about regions with indeterminate boundaries but also can be specialized to cover various regions such as the convex hulls of regions, buffer zones, MBRs and raster images. An extension of broad boundaries to complex regions offers a solution to the problem of representing the uncertainty commonly affecting the boundaries of spatial objects (Clementini & Felice, Reference Clementini and Felice2001). An alternative four-tuple equivalent representation of the extended nine-intersection relations and composition table are presented in Du et al. (Reference Du, Qin, Wang and Ma2008b) that aids in transforming the topological relationships between broad boundary regions into four tuples of the topological relationships between the crisp regions composing of the broad boundary regions, that is, the topological relations of lower crisp w.r.t. lower crisp, lower crisp to upper crisp, upper crisp to lower crisp and upper crisp to upper crisp. However, it should be mentioned that this quadruple representation is inherently different from that in egg-yolk theory. The first difference is that both the yolk and the white are closed sets, whereas the interior in Du et al. (Reference Du, Qin, Wang and Ma2008b) is open and the broad boundary is closed. The second difference lies in the semantic groups of the base relations. A third difference is that the four relations in the quadruples of Du et al. (Reference Du, Qin, Wang and Ma2008b) can express topological relations between objects with different dimensions, whereas egg-yolk theory requires that both objects have the same dimension.

Figure 29

9-intersection matrix with broad boundary (Clementini & Felice, Reference Clementini and Felice1997b: 179)

Similar to the approaches handling uncertainty in topological relations, one approach to handling uncertainty in directional relations partitions the space by the pair of MBRs of minimum and maximum extension of an indeterminate region, and obtains 25 direction tiles, as shown in Figure 30, represented by a 5 × 5 direction matrix. In contrast to the empty and non-empty values of the 9-intersection, each entry of the matrix stores one of the four values, expressing the four different situations the target objects can have when intersecting with the direction tiles, which give rise to a huge number (4²⁵) of potential base relations (Cicerone & Felice, Reference Cicerone and Felice2000). Another approach expresses the direction relation between broad boundary regions as a four-tuple of direction relations (Figure 31) between the crisp regions, which are the direction relations of lower crisp w.r.t. lower crisp, lower crisp to upper crisp, upper crisp to lower crisp and upper crisp to upper crisp (Dong et al., Reference Dong, Liu, Wang, Wang and Lü2011).

Figure 30

A pictorial example of 5 × 5 direction tiles (Cicerone & Felice, Reference Cicerone and Felice2000: 17)

Figure 31

An example of the Cardinal Direction Calculus (CDC) quadruple between the broad boundary regions (Dong et al., Reference Dong, Liu, Wang, Wang and Lü2011: 331)

When treating uncertainty numerically, fuzzy sets and rough sets are the main tools to express the vagueness of the spatial entities and their relations. In Zhan's approach (Zhan, Reference Zhan1998; Zhan & Lin, Reference Zhan and Lin2003), a vague region is treated as a fuzzy set, which can be decomposed into three parts in: the core, the indeterminate boundary and the exterior. The indeterminate boundary is approximated by a set of α-boundaries, each of which corresponds to the boundary of an α-cut-level region; thus, a binary topological relation between fuzzy regions only belongs to a prototypical topological relation to some degree. The fuzzy extension of the nine-intersection calculus (Du et al., Reference Du, Qin, Wang and Li2005) is quite similar to Zhan's approach. According to the definitions of the membership functions, the topological space is divided into the fuzzy exterior, fuzzy boundary and fuzzy interior. Therefore, the domain of each element in nine-intersection matrix is a value in the interval [0, 1], rather than a Boolean value. The uncertainty of topological relations in fuzzy nine-intersection calculus is indicated by a membership degree. Unlike the previous discussion pertaining to continuous space, a finite resolution fuzzy spatial algebra (Schneider, Reference Schneider2000, Reference Schneider2003) is introduced achieving a uniform treatment of continuous and discrete space, and applied into the fuzzy extension of nine-interesection calculus. A fuzzification of the well-known RCC framework adapted for the finite discrete space domain is presented in Palshikar (Reference Palshikar2004).

Contrasting with approaches focusing on the fuzzy representation of regions, the fuzzy RCC (Schockaert et al., Reference Schockaert, Cornelis, Cock and Kerre2006, Reference Schockaert, Cock, Cornelis and Kerre2008, Reference Schockaert, Cock and Kerre2009) only requires that the fuzzy version of the C relation is reflexive and symmetric, as in standard RCC. It does not impose any constraints on how regions are represented, nor how connection should be interpreted. Therefore, it is applicable in a wide variety of contexts, including those where space is used in a metaphorical way.

Rough set-based approaches often relate to the partition of the plane. In Bittner and Stell (Reference Bittner and Stell2000, Reference Bittner and Stell2002), the indefiniteness also relates to locations. The rough location of a spatial object within a regional partition is characterized by a set of relations between parts of the object and parts of regions forming the regional partition, whereas the exact location is the region of space taken up by the object. For example, the rough location of boundary-insensitive approximations are defined by functions from the partition to the value set {fo, po, no}, which means the region covers all, some but not all and none of the cells defined by the partition. Thus, the indefiniteness is expressed by the pairs of greatest minimal and least maximal regions. Another way of expressing this is that the vague region defined by rough location consists of the three concentric regions: core, wide boundary and exterior, which coincide with the idea approximating vagueness by a broad boundary and pair of crisp regions in the former category of approaches dealing with uncertainty (Cohn & Gotts, Reference Cohn and Gotts1996; Clementini & Felice, Reference Clementini and Felice1997; Cicerone & Felice, Reference Cicerone and Felice2000; Roy & Stell, Reference Roy and Stell2001; Dong et al., Reference Dong, Liu, Wang, Wang and Lü2011). When applying this rough location extension to the nine-intersection matrix, an algebra with 249 base relations emerges (Wang et al., Reference Wang, Liu, Hu and Wang2003). A combined description of topological and direction relations between broad boundary regions is given in Du et al. (Reference Du, Qin, Wang and Ma2006).

Granularity is another concept worth mentioning relating to rough set approaches dealing with uncertainty. It characterizes the scale or level of detail (partition of the space), and therefore reflects the common phenomenon in knowledge stratification that knowledge can be organized into a hierarchical structure according to different granularities. Uncertainty can be managed by selecting appropriate granularities. Temporal and spatial granularity techniques are proposed, respectively, in Bittner (Reference Bittner2002), Bittner and Smith (Reference Bittner and Smith2001) and applied in knowledge discovery (Bédard et al., Reference Bédard, Merrett and Han2001; Roddick & Spiliopoulou, Reference Roddick and Spiliopoulou2002). A qualitative extent for spatio-temporal granularity is addressed in Stell (Reference Stell2003), which shows how the three spatial extents (everywhere, somewhere and nowhere) can be generalized to the granular description of spatio-temporal regions. The framework in Li and Nebel (Reference Li and Nebel2007) hierarchically represents and reasons about topological information, which implements jumping between different granularities of the topological relations.