Region connection calculus

<h2 id="axioms">Axioms</h2>
<p>RCC is governed by two axioms.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p>
<ul><li>for any region x, x connects with itself</li>
<li>for any region x, y, if x connects with y, y connects with x</li></ul>
<h2 id="remark-on-the-axioms">Remark on the axioms</h2>
<p>The two axioms describe two features of the connection relation, but not the characteristic feature of the connect relation.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> 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.
</p>
<h2 id="composition-table">Composition table</h2>
<p>The <a href="/facts/Function_composition/r5Pvnmth">composition</a> table of RCC8 are as follows:
</p>
<table><tbody><tr><th>R2(b, c)→R1(a, b)↓</th><th>DC</th><th>EC</th><th>PO</th><th>TPP</th><th>NTPP</th><th>TPPi</th><th>NTPPi</th><th>EQ</th></tr><tr><th>DC</th><td>*</td><td>DC, EC, PO, TPP, NTPP</td><td>DC, EC, PO, TPP, NTPP</td><td>DC, EC, PO, TPP, NTPP</td><td>DC, EC, PO, TPP, NTPP</td><td>DC</td><td>DC</td><td>DC</td></tr><tr><th>EC</th><td>DC, EC, PO, TPPi, NTPPi</td><td>DC, EC, PO, TPP, TPPi, EQ</td><td>DC, EC, PO, TPP, NTPP</td><td>EC, PO, TPP, NTPP</td><td>PO, TPP, NTPP</td><td>DC, EC</td><td>DC</td><td>EC</td></tr><tr><th>PO</th><td>DC, EC, PO, TPPi, NTPPi</td><td>DC, EC, PO, TPPi, NTPPi</td><td>*</td><td>PO, TPP, NTPP</td><td>PO, TPP, NTPP</td><td>DC, EC, PO, TPPi, NTPPi</td><td>DC, EC, PO, TPPi, NTPPi</td><td>PO</td></tr><tr><th>TPP</th><td>DC</td><td>DC, EC</td><td>DC, EC, PO, TPP, NTPP</td><td>TPP, NTPP</td><td>NTPP</td><td>DC, EC, PO, TPP, TPPi, EQ</td><td>DC, EC, PO, TPPi, NTPPi</td><td>TPP</td></tr><tr><th>NTPP</th><td>DC</td><td>DC</td><td>DC, EC, PO, TPP, NTPP</td><td>NTPP</td><td>NTPP</td><td>DC, EC, PO, TPP, NTPP</td><td>*</td><td>NTPP</td></tr><tr><th>TPPi</th><td>DC, EC, PO, TPPi, NTPPi</td><td>EC, PO, TPPi, NTPPi</td><td>PO, TPPi, NTPPi</td><td>PO, TPP, TPPi, EQ</td><td>PO, TPP, NTPP</td><td>TPPi, NTPPi</td><td>NTPPi</td><td>TPPi</td></tr><tr><th>NTPPi</th><td>DC, EC, PO, TPPi, NTPPi</td><td>PO, TPPi, NTPPi</td><td>PO, TPPi, NTPPi</td><td>PO, TPPi, NTPPi</td><td>PO, TPP, NTPP, TPPi, NTPPi, EQ</td><td>NTPPi</td><td>NTPPi</td><td>NTPPi</td></tr><tr><th>EQ</th><td>DC</td><td>EC</td><td>PO</td><td>TPP</td><td>NTPP</td><td>TPPi</td><td>NTPPi</td><td>EQ</td></tr></tbody></table>
<ul><li>"*" denotes the universal relation, no relation can be discarded.</li></ul>
<p>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.
</p>
<h2 id="examples">Examples</h2>
<p>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?
</p><p>The spatial configuration can be formalized in RCC8 as the following constraint network:
</p>
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

<p>Using the RCC8 composition table and the <a href="/facts/Path_consistency/wqM9hKc1">path-consistency algorithm</a>, we can refine the network in the following way:
</p>
road { PO, EC } property1
road { PO, TPP } property2

<p>That is, the <i>road</i> either overlaps (PO) <i>property2</i>, or is a tangential proper part of it.  But, if the <i>road</i> is a tangential proper part of <i>property2</i>, then the <i>road</i> can only be externally connected (EC) to <i>property1</i>.  That is, <i>road PO property1</i> is not possible when <i>road TPP property2</i>.  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.
</p><p>First, we note that the path-consistency algorithm will also reduce the possible properties between <i>house2</i> and <i>property1</i> from <i>{ DC, EC }</i> to just <i>DC</i>.  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 (25) possible unique constraint networks, each containing only single labels on each edge (<i>"singleton labelings</i>").  However, of the 32 possible singleton labelings, only 9 are consistent.  (See <a href="https://github.com/alreich/qualreas#labelings">qualreas</a> for details.)  Only one of the consistent singleton labelings has the edge <i>road TPP property2</i> and the same labeling includes <i>road EC property1</i>.
</p><p>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).
</p>
<h2 id="rcc8-use-in-geosparql">RCC8 use in GeoSPARQL</h2>
<p>RCC8 has been partially implemented in <a href="/facts/GeoSPARQL/Kxx3yccN">GeoSPARQL</a> as described below:
</p>

<h2 id="implementations">Implementations</h2>
<ul><li><a href="https://github.com/m-westphal/gqr">GQR</a> is a reasoner for RCC-5, RCC-8, and RCC-23 (as well as other calculi for spatial and temporal reasoning)</li>
<li><a href="https://github.com/alreich/qualreas">qualreas</a> is a <a href="/facts/Python_(programming_language)/YbuGqofa">Python</a> framework for qualitative reasoning over networks of relation algebras, such as RCC-8, Allen's interval algebra and more.</li></ul>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Spatial_relation/6RFIl1ul">Spatial relation</a>
<ul><li><a href="/facts/DE-9IM/Ha6Mm78o">DE-9IM</a></li></ul></li></ul>

<h2 id="bibliography">Bibliography</h2>
<ul><li>Randell, D.A.; Cui, Z; Cohn, A.G. (1992). "A spatial logic based on regions and connection". <i>3rd Int. Conf. on Knowledge Representation and Reasoning</i>. Morgan Kaufmann. pp. 165–176.</li>
<li>Anthony G. Cohn; Brandon Bennett; John Gooday; Micholas Mark Gotts (1997). "Qualitative Spatial Representation and Reasoning with the Region Connection Calculus". <i>GeoInformatica</i>. 1 (3): 275–316. <a href="/facts/Bibcode_(identifier)/9HtdQSGB">Bibcode</a>:<a href="https://ui.adsabs.harvard.edu/abs/1997GInfo...1..275C">1997GInfo...1..275C</a>. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1023%2FA%3A1009712514511">10.1023/A:1009712514511</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:14841370">14841370</a>..</li>
<li>Renz, J. (2002). <i>Qualitative Spatial Reasoning with Topological Information</i>. Lecture Notes in Computer Science. Vol. 2293. Springer Verlag. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2F3-540-70736-0">10.1007/3-540-70736-0</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-3-540-43346-0. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:8236425">8236425</a>.</li>
<li>Dong, Tiansi (2008). "A Comment on RCC: From RCC to RCC⁺⁺". <i>Journal of Philosophical Logic</i>. 34 (2): 319–352. <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs10992-007-9074-y">10.1007/s10992-007-9074-y</a>. <a href="/facts/JSTOR_(identifier)/YTeVmaJ7">JSTOR</a> <a href="https://www.jstor.org/stable/41217909">41217909</a>. <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:6243376">6243376</a>..</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Randell, Cui & Cohn 1992. - Randell, D.A.; Cui, Z; Cohn, A.G. (1992). "A spatial logic based on regions and connection". 3rd Int. Conf. on Knowledge Representation and Reasoning. Morgan Kaufmann. pp. 165–176. <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Dong 2008. - Dong, Tiansi (2008). "A Comment on RCC: From RCC to RCC⁺⁺". Journal of Philosophical Logic. 34 (2): 319–352. doi:10.1007/s10992-007-9074-y. JSTOR 41217909. S2CID 6243376. <a href="https://doi.org/10.1007%2Fs10992-007-9074-y" target="_blank">https://doi.org/10.1007%2Fs10992-007-9074-y</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Region connection calculus open-in-new

Region connection calculus