The RCC Spatial Logic

RCC, a qualitative spatial representation, is simultaneously named after David Randell, Tony Cohn and Zhan Cui or as an abbreviation of the "Region Connection Calculus", which is the name now widely used to describe a family of calculi based on a primitive predicate of connection. In its most general form, it is a 1st-order theory based on Clarke's calculus of individuals. A large number of spatial properties and relations are definable within the RCC formalism. Of particular significance is a set of eight topological relations (RCC-8), which are illustrated below. These are: DC (is disconnected from), EC (is externally connected with), PO (partially overlaps), TPP (is a tangential proper part of), NTPP (is a nontangential proper part of), TPPi (inverse of TPP), NTPPi (inverse of NTPP) and EQUAL. These relations are defined in terms of a single primitive dyadic relation: C(x,y), read as `region x connects with region y'. C is both reflexive and symetric and holds whenever regions x and y are "connected". In the original Clarke interpretation, this meant sharing a point. However in the 1992 reformulation of RCC the interpretation was changed to "the closures of the regions sharing a point", for reasons described in the KR'02 paper. In the literature, the term "RCC-8" often is taken to mean a constraint language whose atoms are the eight relations of RCC-8, rather than the full first order theory in which these relations are defined from C(x,y).


The eight basic region-region RCC relations


 




Composition tables, similar to those associated with James Allen's interval calculus, can be generated to provide a basic reasoning mechanism for RCC. Part of the groups work has centered on efficiently generating and testing these, initially by Zhan Cui using a low-level bit-manipulation technique and, more recently, with an efficient approach based on intuitionistic propositional logic developed by Brandon Bennett.

For details of the 1st-order axiomatisation of RCC click on this link .

Extending the expressive power of RCC

We have examined extensions to RCC resulting from the introduction of a convex hull function. Intuitively, if we wrapped an object tightly in cling-film then the region inside the film would correspond to the convex hull of that object. Using this function we can define new base relations that allow us to express the notion of regions being inside, partially inside or outside one another. Yet more relations are obtained if we differentiate between the topological and geometric notions of containment and between different kinds of geometric containment (c.f. the difference between the `inside' of a cup and the inside of its handle, both being part of the cups convex hull and thus its inside).
 
 


Examples of topologically complex objects: `doughnuts'


Nick Gotts has demonstrated how more topologically complex objects, such as the solid torus (or `doughnut') examples from the figure above figure, may be represented. This is achieved using a fine grained taxonomy of further spatial relations defined in terms of C.