Cálculo de conexión de regiones - Enciclopedia

El cálculo de conexión de regiones (RCC) está destinado a servir para la representación y razonamiento cualitativo del espacio. RCC describe abstractamente las regiones (en el espacio euclidiano o en un espacio topológico) por sus posibles relaciones entre sí. RCC8 consta de 8 relaciones básicas que son posibles entre dos regiones:

desconectado (DC)
conectado externamente (EC)
igual (EQ)
superpuestos parcialmente (PO)
parte propia tangencial (TPP)
inversa de parte propia tangencial (TPPi)
parte propia no tangencial (NTPP)
inversa de parte propia no tangencial (NTPPi)

A partir de estas relaciones básicas, se pueden construir combinaciones. Por ejemplo, parte propia (PP) es la unión de TPP y NTPP.

Axiomas
RCC se rige por dos axiomas.

para cualquier región x, x se conecta consigo misma
para cualquier región x, y, si x se conecta con y, y se conecta con x

Comentario sobre los axiomas
Los dos axiomas describen dos características de la relación de conexión, pero no la característica principal de la relación de conexión. Por ejemplo, podemos decir que un objeto está a menos de 10 metros de distancia de sí mismo y que si el objeto A está a menos de 10 metros de distancia del objeto B, el objeto B estará a menos de 10 metros de distancia del objeto A. Por lo tanto, la relación 'menos de 10 metros' también satisface los dos axiomas, pero no habla de la relación de conexión en el sentido pretendido de RCC.

Tabla de composición
La tabla de composición de RCC8 es la siguiente:

"*" denota la relación universal, no se puede descartar ninguna relación.
Ejemplo de uso: si TPP b y b EC c, (fila 4, columna 2) de la tabla dice que a DC c o a EC c.

Ejemplos
El cálculo RCC8 está destinado a razonar sobre configuraciones espaciales. Consideremos el siguiente ejemplo: dos casas están conectadas por una carretera. Cada casa está ubicada en una propiedad propia. La primera casa posiblemente toca el límite de la propiedad; la segunda, sin embargo, no. ¿Qué podemos inferir sobre la relación de la segunda propiedad con la carretera?

La configuración espacial puede formalizarse en RCC8 como la siguiente red de restricciones:

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

Usando la tabla de composición RCC8 y el algoritmo de consistencia de camino, podemos refinar la red de la siguiente manera:

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

Esto es, la carretera o se superpone (PO) a property2, o es una parte propia tangencial de ella. Sin embargo, si la carretera es una parte propia tangencial de property2, entonces la carretera solo puede estar conectada externamente (EC) a property1. Esto es, road PO property1 no es posible cuando road TPP property2. Este hecho no es obvio, pero se puede deducir una vez que examinamos las "etiquetaciones de singleton" consistentes de la red de restricciones. El siguiente párrafo describe brevemente las etiquetaciones de singleton.
Primero, notamos que el algoritmo de consistencia de camino también reducirá las posibles propiedades entre house2 y property1 de { DC, EC } a solo DC. Por lo tanto, el algoritmo de consistencia de camino deja múltiples posibles restricciones en 5 de los bordes de la red de restricciones. Ya que cada una de las múltiples restricciones implica 2 restricciones, podemos reducir la red a 32 (25) redes de restricciones posibles únicas, cada una conteniendo solo etiquetas singulares en cada borde ("etiquetaciones de singleton"). Sin embargo, de las 32 posibles etiquetaciones de singleton, solo 9 son consistentes. (Ver qualreas para detalles). Solo una de las etiquetaciones de singleton consistentes tiene el borde road TPP property2 y la misma etiquetación incluye road EC property1.

Otras versiones del cálculo de conexión de regiones incluyen RCC5 (con solo cinco relaciones básicas - se ignora la distinción entre si dos regiones se tocan entre sí) y RCC23 (que permite razonar sobre convexidad).

Uso de RCC8 en GeoSPARQL
RCC8 ha sido implementado parcialmente en GeoSPARQL como se describe a continuación:

Implementaciones
GQR es un razonador para RCC-5, RCC-8 y RCC-23 (así como otros cálculos para el razonamiento espacial y temporal)
qualreas es un framework en Python para el razonamiento cualitativo sobre redes de álgebra de relaciones, como RCC-8, el álgebra de intervalos de Allen y otros.

Véase también
Relación espacial
DE-9IM

Referencias

Bibliografía
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.
Anthony G. Cohn; Brandon Bennett; John Gooday; Micholas Mark Gotts (1997). "Qualitative Spatial Representation and Reasoning with the Region Connection Calculus". GeoInformatica. 1 (3): 275–316. Bibcode:1997GInfo...1..275C. doi:10.1023/A:1009712514511. S2CID 14841370..
Renz, J. (2002). Qualitative Spatial Reasoning with Topological Information. Lecture Notes in Computer Science. Vol. 2293. Springer Verlag. doi:10.1007/3-540-70736-0. ISBN 978-3-540-43346-0. S2CID 8236425.
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.