The region connection calculus (RCC) is intended to serve for qualitative spatial representation and
reasoning
Reason is the capacity of consciously applying logic by drawing conclusions from new or existing information, with the aim of seeking the truth. It is closely associated with such characteristically human activities as philosophy, science, lang ...
. RCC abstractly describes regions (in
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
, or in a
topological space
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points ...
) 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.
Axioms
RCC is governed by two axioms.
* for any region x, x connects with itself
* for any region x, y, if x connects with y, y will connects with x
Remark on the axioms
The two axioms describe two features of the connection relation, but not the characteristic feature of the connect relation.
[Dong 2008] For example, we can say that an object is less than 10 meters away from itself and that if object A is less than 10 meters away from object B, object B will be less than 10 meters away from object A. So, the relation 'less-than-10-meters' also satisfies the above two axioms, but does not talk about the connection relation in the intended sense of RCC.
Composition table
The composition table of RCC8 are as follows:
* "*" denotes the universal relation, no relation can be discarded.
Usage example: if a TPP b and b EC c, (row 4, column 2) of the table says that a DC c or a EC c.
Examples
The RCC8 calculus is intended 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
Constraint may refer to:
* Constraint (computer-aided design), a demarcation of geometrical characteristics between two or more entities or solid modeling bodies
* Constraint (mathematics), a condition of an optimization problem that the solution m ...
:
house1 DC house2
house1 property1
house1 property2
house1 EC road
house2 property1
house2 NTPP property2
house2 EC road
property1 property2
road property1
road property2
Using the RCC8
composition table
Composition or Compositions may refer to:
Arts and literature
* Composition (dance), practice and teaching of choreography
*Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include ...
and the
path-consistency algorithm, we can refine the network in the following way:
road property1
road property2
That is, the ''road'' either overlaps (PO) ''property2'', or is a tangential proper part of it. But, if the ''road'' is a tangential proper part of ''property2'', then the ''road'' can only be externally connected (EC) to ''property1''. That is, ''road PO property1'' is not possible when ''road TPP property2''. This fact is not obvious, but can be deduced once we examine the consistent "singleton-labelings" of the constraint network. The following paragraph briefly describes singleton-labelings.
First, we note that the path-consistency algorithm will also reduce the possible properties between ''house2'' and ''property1'' from ' to just ''DC''. So, the path-consistency algorithm leaves multiple possible constraints on 5 of the edges in the constraint network. Since each of the multiple constraints involves 2 constraints, we can reduce the network to 32 (5^2) possible unique constraint networks, each containing only single labels on each edge (''"singleton labelings''"). However, of the 32 possible singleton labelings, only 9 are consistent. (Se
qualreasfor details.) Only one of the consistent singleton labelings has the edge ''road TPP property2'' and the same labeling includes ''road EC property1''.
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
RCC8 has been partially implemented in
GeoSPARQL
GeoSPARQL is a standard for representation and querying of geospatial linked data for the Semantic Web from the Open Geospatial Consortium (OGC). The definition of a small ontology based on well-understood OGC standards is intended to provide a st ...
as described below:
Implementations
GQRis a reasoner for RCC-5, RCC-8, and RCC-23 (as well as other calculi for spatial and temporal reasoning)
qualreasis a Python framework for qualitative reasoning over networks of relation algebras, such as RCC-8, Allen's interval algebra and more.
See also
*
Spatial relation
A spatial relationD. M. Mark and M. J. Egenhofer (1994), "Modeling Spatial Relations Between Lines and Regions: Combining Formal Mathematical Models and Human Subjects Testing"PDF/ref> specifies how some object is located in space in relation to s ...
**
DE-9IM
The Dimensionally Extended 9-Intersection Model (DE-9IM) is a topological model and a standard used to describe the spatial relations of two regions (two geometries in two-dimensions, R2), in geometry, point-set topology, geospatial topology, ...
References
Bibliography
*
* .
*
* {{cite journal, ref=tdong, first=Tiansi , last= Dong , title=A Comment on RCC: From RCC to RCC⁺⁺, jstor=41217909, journal=Journal of Philosophical Logic, volume=34, issue=2, pages=319–352, date=2008, doi=10.1007/s10992-007-9074-y, s2cid=6243376 .
Reasoning
Knowledge representation
Constraint programming
Computational topology
Logical calculi