Region connection calculus

From Wikipedia, the free encyclopedia
  (Redirected from RCC8)
Jump to: navigation, search

The region connection calculus (RCC) serves for qualitative spatial representation and reasoning. RCC abstractly describes regions (in Euclidean space, or in a topological space) by their possible relations to each other. RCC8 consists of 8 basic relations that are possible between two regions:

  • disconnected (DC)
  • externally connected (EC)
  • equal (EQ)
  • partially overlapping (PO)
  • tangential proper part (TPP)
  • tangential proper part inverse (TPPi)
  • non-tangential proper part (NTPP)
  • non-tangential proper part inverse (NTPPi)

From these basic relations, combinations can be built. For example, proper part (PP) is the union of TPP and NTPP. RCC8.jpg

Composition table[edit]

The composition table of RCC8 are as follows:

o DC EC PO TPP NTPP TPPi NTPPi EQ
DC * DC,EC,PO,TPP,NTPP DC,EC,PO,TPP,NTPP DC,EC,PO,TPP,NTPP DC,EC,PO,TPP,NTPP DC DC DC
EC DC,EC,PO,TPPi,NTPPi DC,EC,PO,TPP,TPPi,EQ DC,EC,PO,TPP,NTPP EC,PO,TPP,NTPP PO,TPP,NTPP DC,EC DC EC
PO DC,EC,PO,TPPi,NTPPi DC,EC,PO,TPPi,NTPPi * PO,TPP,NTPP PO,TPP,NTPP DC,EC,PO,TPPi,NTPPi DC,EC,PO,TPPi,NTPPi PO
TPP DC DC,EC DC,EC,PO,TPP,NTPP TPP,NTPP NTPP DC,EC,PO,TPP,TPPi,EQ DC,EC,PO,TPPi,NTPPi TPP
NTPP DC DC DC,EC,PO,TPP,NTPP NTPP NTPP DC,EC,PO,TPP,NTPP * NTPP
TPPi DC,EC,PO,TPPi,NTPPi EC,PO,TPPi,NTPPi PO,TPPi,NTPPi PO,TPP,TPPi,EQ PO,TPP,NTPP TPPi,NTPPi NTPPi TPPi
NTPPi DC,EC,PO,TPPi,NTPPi PO,TPPi,NTPPi PO,TPPi,NTPPi PO,TPPi,NTPPi PO,TPP,NTPP,TPPi,NTPPi,EQ NTPPi NTPPi NTPPi
EQ DC EC PO TPP NTPP TPPi NTPPi EQ
  • "*" denotes the universal relation.

Examples[edit]

The RCC8 calculus can be used for reasoning about spatial configurations. Consider the following example: two houses are connected via a road. Each house is located on an own property. The first house possibly touches the boundary of the property; the second one surely does not. What can we infer about the relation of the second property to the road?

The spatial configuration can be formalized in RCC8 as the following constraint network:

house1 DC house2
house1 {TPP, NTPP} property1
house1 {DC, EC} property2
house1 EC road
house2 { DC, EC } property1
house2 NTPP property2
house2 EC road
property1 { DC, EC } property2
road { DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi } property1
road { DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi } property2

Using the RCC8 composition table and the path-consistency algorithm, we can refine the network in the following way:

road { PO, EC } property1
road { PO, TPP } property2

That is, the road either overlaps with the second property, or is even (tangential) part of it.

Other versions of the region connection calculus include RCC5 (with only five basic relations - the distinction whether two regions touch each other are ignored) and RCC23 (which allows reasoning about convexity).

RCC8 use in GeoSPARQL[edit]

RCC8 has been implemented in GeoSPARQL as described below:

A graphical representation of Region Connection Calculus (RCC: Randell, Cui and Cohn, 1992) and the links to the equivalent naming by the Open Geospatial Consortium (OGC) with their equivalent URIs.
A graphical representation of Region Connection Calculus (RCC: Randell, Cui and Cohn, 1992) and the links to the equivalent naming by the Open Geospatial Consortium (OGC) with their equivalent URIs.

References[edit]

  • Randell, D. A., Cui, Z. and Cohn, A. G.: A spatial logic based on regions and connection, Proc. 3rd Int. Conf. on Knowledge Representation and Reasoning, Morgan Kaufmann, San Mateo, pp. 165–176, 1992.
  • Anthony G. Cohn, Brandon Bennett, John Gooday, Micholas Mark Gotts: Qualitative Spatial Representation and Reasoning with the Region Connection Calculus. GeoInformatica, 1, 275–316, 1997.
  • J. Renz: Qualitative Spatial Reasoning with Topological Information. Lecture Notes in Computer Science 2293, Springer Verlag, 2002.