Regionförbindelsekalkyl

Regionförbindelsekalkylen ( RCC ) är avsedd att tjäna för kvalitativ rumslig representation och resonemang . RCC beskriver abstrakt regioner (i det euklidiska utrymmet eller i ett topologiskt utrymme ) genom deras möjliga relationer till varandra. RCC8 består av 8 grundläggande relationer som är möjliga mellan två regioner:

  • frånkopplad (DC)
  • externt ansluten (EC)
  • lika (EQ)
  • partiellt överlappande (PO)
  • tangentiell korrekt del (TPP)
  • tangentiell egendel invers (TPPi)
  • icke-tangentiell egen del (NTPP)
  • icke-tangentiell egendel invers (NTPPi)

Utifrån dessa grundläggande relationer kan kombinationer byggas. Till exempel är korrekt del (PP) föreningen av TPP och NTPP.RCC8.jpg

Axiom

RCC styrs av två axiom.

  • för varje region x ansluter x med sig själv
  • för vilken region x, y som helst, om x ansluter till y, kommer y att ansluta med x

Anmärkning om axiomen

De två axiomen beskriver två särdrag i sambandsrelationen, men inte det karakteristiska särdraget i sambandsrelationen. Till exempel kan vi säga att ett objekt är mindre än 10 meter från sig självt och att om objekt A är mindre än 10 meter från objekt B kommer objekt B att vara mindre än 10 meter från objekt A. Så, relationen ' mindre-än-10-meters' uppfyller också ovanstående två axiom, men talar inte om sambandsrelationen i den avsedda betydelsen av RCC.

Sammansättningstabell

Sammansättningstabellen för RCC8 är följande:

R2(b,c)→ Rl(a,b)↓ 		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
  • "*" betecknar den universella relationen, ingen relation kan förkastas.

Användningsexempel: om en TPP b och b EC c, (rad 4, kolumn 2) i tabellen säger att en DC c eller en EC c.

Exempel

RCC8-kalkylen är avsedd för resonemang om rumsliga konfigurationer. Tänk på följande exempel: två hus är sammankopplade via en väg. Varje hus ligger på en egen fastighet. Det första huset tangerar möjligen fastighetens gräns; den andra gör det säkert inte. Vad kan vi sluta oss till om förhållandet mellan den andra fastigheten och vägen?

Den rumsliga konfigurationen kan formaliseras i RCC8 som följande begränsningsnätverk:

hus1 DC hus2 hus1 {TPP, NTPP} fastighet1 hus1 {DC, EC} fastighet2 hus1 EC väghus2 { DC, EC } fastighet1 hus2 NTPP fastighet2 hus2 EC vägfastighet1 { DC, EC } fastighet2 väg { DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi } egenskap1 väg { DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi } egenskap2

Med hjälp av RCC8-sammansättningstabellen och sökvägskonsistensalgoritmen kan vi förfina nätverket på följande sätt:

väg { PO, EC } egenskap1 väg { PO, TPP } egenskap2

Det vill säga, vägen antingen överlappar (PO) egenskap2 eller är en tangentiell korrekt del av den. Men om vägen är en tangentiell egentlig del av fastighet2 , kan vägen endast vara externt ansluten (EC) till fastighet1 . Det vill säga väg PO-egenskap1 är inte möjlig när väg TPP-egenskap2 . Detta faktum är inte uppenbart, men kan härledas när vi undersöker de konsekventa "singleton-märkningarna" av begränsningsnätverket. Följande stycke beskriver kortfattat singleton-märkningar.

Först noterar vi att sökvägskonsistensalgoritmen också kommer att minska de möjliga egenskaperna mellan hus2 och fastighet1 från { DC, EC } till bara DC . Så, sökvägskonsistensalgoritmen lämnar flera möjliga begränsningar på 5 av kanterna i begränsningsnätverket. Eftersom var och en av de multipla begränsningarna involverar 2 begränsningar, kan vi reducera nätverket till 32 (5^2) möjliga unika begränsningsnätverk, som var och en endast innehåller enstaka etiketter på varje kant ("singleton labelings" ) . Av de 32 möjliga singleton-märkningarna är dock endast 9 konsekventa. (Se qualreas för detaljer.) Endast en av de konsekventa singleton-märkningarna har edge road TPP-egenskapen2 och samma märkning inkluderar väg EC-egenskap1 .

Andra versioner av regionkopplingskalkylen inkluderar RCC5 (med endast fem grundläggande relationer - distinktionen om två regioner berör varandra ignoreras) och RCC23 (som tillåter resonemang om konvexitet).

RCC8-användning i GeoSPARQL

RCC8 har delvis [ förtydligande behövs ] implementerats i GeoSPARQL enligt beskrivningen nedan:

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.
En grafisk representation av Region Connection Calculus (RCC: Randell, Cui och Cohn, 1992) och länkarna till motsvarande namngivning av Open Geospatial Consortium (OGC) med motsvarande URI:er.

Genomföranden

  • GQR är ett resonemang för RCC-5, RCC-8 och RCC-23 (liksom andra kalkyler för rumsliga och tidsmässiga resonemang)
  • qualreas är ett Python-ramverk för kvalitativt resonemang över nätverk av relationsalgebror, såsom RCC-8, Allens intervallalgebra med mera.

Se även

Bibliografi

  • Randell, DA; Cui, Z; Cohn, AG (1992). "En rumslig logik baserad på regioner och anslutning". 3:e Int. Konf. om Kunskapsrepresentation och resonemang . Morgan Kaufmann. s. 165–176.
  •   Anthony G. Cohn; Brandon Bennett; John Gooday; Michaels Mark Gotts (1997). "Kvalitativ rumslig representation och resonemang med regionkopplingskalkylen". GeoInformatica . 1 (3): 275–316. doi : 10.1023/A:1009712514511 . S2CID 14841370 . .
  •    Renz, J. (2002). Kvalitativt rumsligt resonemang med topologisk information . Föreläsningsanteckningar i datavetenskap. Vol. 2293. Springer Verlag. doi : 10.1007/3-540-70736-0 . ISBN 978-3-540-43346-0 . S2CID 8236425 .
  •    Dong, Tiansi (2008). "En kommentar om RCC: Från RCC till RCC⁺⁺". Journal of Philosophical Logic . 34 (2): 319–352. doi : 10.1007/s10992-007-9074-y . JSTOR 41217909 . S2CID 6243376 . .
Hämtad från " https://en.wikipedia.org/w/index.php?title=Region_connection_calculus&oldid=1092198260 "