cálculo de conexión de regiones

El cálculo de conexión de regiones ( RCC ) está diseñado para servir como representación y razonamiento espacial cualitativo . El RCC describe abstractamente las regiones (en el espacio euclidiano o en un espacio topológico ) mediante sus posibles relaciones entre sí. El RCC8 consta de 8 relaciones básicas posibles entre dos regiones:

• desconectado (CC)
• conectado externamente (EC)
• igual (EQ)
• superpuesto parcialmente (PO)
• parte propia tangencial (TPP)
• Parte propia tangencial inversa (TPPi)
• parte propia no tangencial (NTPP)
• Inversa de la parte propia no tangencial (NTPPi)

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

RCC se rige por dos axiomas. ^{[ 1 ]}

• 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.

Los dos axiomas describen dos características de la relación de conexión, pero no la característica principal de dicha relación. ^{[ 2 ]} Por ejemplo, podemos decir que un objeto está a menos de 10 metros de sí mismo y que si el objeto A está a menos de 10 metros del objeto B, el objeto B estará a menos de 10 metros del objeto A. Por lo tanto, la relación "menos de 10 metros" también satisface los dos axiomas anteriores, pero no se refiere a la relación de conexión en el sentido previsto por RCC.

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

• "*" denota la relación universal, ninguna relación puede descartarse.

Ejemplo de uso: si un TPP b y b EC c, (fila 4, columna 2) de la tabla dice que un DC c o un EC c.

El cálculo RCC8 está diseñado para razonar sobre configuraciones espaciales. Consideremos el siguiente ejemplo: dos casas están conectadas por una carretera. Cada casa se encuentra en su propia propiedad. La primera casa posiblemente toca el límite de la propiedad; la segunda, sin duda, no. ¿Qué podemos inferir sobre la relación de la segunda propiedad con la carretera?

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

casa1 DC casa2 casa1 {TPP, NTPP} propiedad1 casa1 {DC, EC} propiedad2 Casa 1, carretera EC casa2 { DC, EC } propiedad1 casa2 propiedad NTPP2 Casa 2, carretera EC propiedad1 { DC, EC } propiedad2 carretera { DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi } propiedad1 carretera { DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi } propiedad2

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

carretera { PO, EC } propiedad1 carretera { PO, TPP } propiedad2

Es decir, la carretera se superpone (PO) a la propiedad 2 , o es una parte propia tangente de ella. Pero, si la carretera es una parte propia tangente de la propiedad 2 , entonces solo puede conectarse externamente (EC) a la propiedad 1. Es decir, la carretera PO propiedad 1 no es posible cuando la carretera TPP propiedad 2. Este hecho no es obvio, pero se puede deducir una vez que examinamos las "etiquetas de un solo elemento" consistentes de la red de restricciones. El siguiente párrafo describe brevemente las etiquetas de un solo elemento.

Primero, observamos que el algoritmo de consistencia de ruta también reducirá las posibles propiedades entre casa2 y propiedad1 de { DC, EC } a solo DC . Por lo tanto, el algoritmo de consistencia de ruta deja múltiples restricciones posibles en 5 de las aristas en la red de restricciones. Dado que cada una de las múltiples restricciones involucra 2 restricciones, podemos reducir la red a 32 (2 ⁵ ) posibles redes de restricciones únicas, cada una conteniendo solo etiquetas únicas en cada arista ( "etiquetas únicas "). Sin embargo, de las 32 posibles etiquetas únicas, solo 9 son consistentes. (Ver qualreas para más detalles). Solo una de las etiquetas únicas consistentes tiene la arista road TPP property2 y la misma etiqueta 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) y RCC23 (que permite razonar sobre la convexidad).

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

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

• Relación espacial
  • DE-9IM

• Randell, DA; Cui, Z; Cohn, AG (1992). "Una lógica espacial basada en regiones y conexiones". 3.ª Conferencia Internacional sobre Representación del Conocimiento y Razonamiento . Morgan Kaufmann. pp. 165–176 . 
• Anthony G. Cohn; Brandon Bennett; John Gooday; Micholas Mark Gotts (1997). "Representación espacial cualitativa y razonamiento con el cálculo de conexión de regiones". GeoInformatica . 1 (3): 275– 316. Bibcode : 1997GInfo...1..275C . doi : 10.1023/A:1009712514511 . S2CID 14841370 . .
• Renz, J. (2002). Razonamiento espacial cualitativo con información topológica . 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). " Un comentario sobre RCC: De RCC a RCC⁺⁺". Journal of Philosophical Logic . 34 (2): 319– 352. doi : 10.1007/s10992-007-9074-y . JSTOR 41217909. S2CID 6243376 .  .