Числення з'єднаності областей

Чи́слення з'є́днаності областе́й (англ. region connection calculus, RCC) призначене для якісного просторового подання та міркування. Воно абстрактно описує області (в евклідовому або в топологічному просторі) через можливі відношення між ними. RCC8 складається з 8 основних відношень, можливих між двома областями:

• роз'єднані (англ. 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)

З цих базових відношень можливо будувати поєднання. Наприклад, власна частина (англ. proper part, PP) це об'єднання TPP та NTPP.

Аксіоми

RCC керується двома аксіомами.^[1]

• для будь-якої області x, x з'єднана сама з собою.
• для будь-яких областей x та y, якщо x з'єднана з y, то y також з'єднана з x.

Зауваження щодо аксіом

Ці дві аксіоми описують дві ознаки відношення з'єднаності, але не визначають його характерну ознаку.^[2] Наприклад, можливо сказати, що об'єкт перебуває на відстані менш ніж 10 метрів від самого себе і що, якщо об'єкт A перебуває на відстані менш ніж 10 метрів від об'єкта B, то об'єкт B також перебуває на відстані менш ніж 10 метрів від об'єкта A. Таким чином, відношення «менш ніж за 10 метрів» також задовольняє наведені дві аксіоми, але не стосується відношення з'єднаності у сенсі, передбаченому RCC.

Таблиця композиції

Таблиця композиції RCC8 виглядає так:

R2(b, c) → R1(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

• «*» позначує універсальне відношення, жодне відношення не може бути виключене.

Приклад використання: якщо a TPP b і b EC c, (рядок 4, стовпець 2) таблиці вказує, що a DC c або a EC c.

Приклади

RCC8 призначене для міркувань про просторові конфігурації. Розгляньмо наступний приклад: два будинки з'єднані дорогою. Кожен будинок розташований на окремій ділянці. Перший будинок, можливо, торкається межі своєї ділянки; другий будинок точно не торкається. Що можна дізнатися про відношення другої ділянки до дороги?

Цю просторову конфігурацію можливо формалізувати в RCC8 як наступну мережу обмежень:

будинок1 DC будинок2  
будинок1 {TPP, NTPP} ділянка1  
будинок1 {DC, EC} ділянка2  
будинок1 EC дорога  
будинок2 {DC, EC} ділянка1  
будинок2 NTPP ділянка2  
будинок2 EC дорога  
ділянка1 {DC, EC} ділянка2  
дорога {DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi} ділянка1  
дорога {DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi} ділянка2  

Використовуючи таблицю композиції RCC8 і алгоритм шляхової узгодженості, ми можемо уточнити цю мережу наступним чином:

дорога {PO, EC} ділянка1  
дорога {PO, TPP} ділянка2  

Це означає, що дорога або перекривається (PO) з ділянка2, або є її дотичною власною частиною (TPP). Але якщо дорога є дотичною власною частиною ділянка2, тоді дорога може бути лише зовнішньо з'єднаною (EC) з ділянка1. Отже, дорога PO ділянка1 неможливо, коли дорога TPP ділянка2. Цей факт неочевидний, але його можливо вивести, якщо розглянути узгоджені «одиночні розмітки» (англ. singleton-labelings) цієї мережі обмежень. Наступний абзац коротко описує одиночні розмітки.

Спершу зазначимо, що алгоритм шляхової узгодженості також скоротить можливі відношення між будинок2 і ділянка1 від {DC, EC} до лише DC. Таким чином, алгоритм шляхової узгодженості залишає по кілька можливих обмежень на 5 ребрах у мережі обмежень. Оскільки кожне з множинних обмежень містить 2 обмеження, мережу можливо звести до 32 (2⁵) можливих унікальних мереж обмежень, кожна з яких містить лише по одній мітці на кожному ребрі («одиночні розмітки»). Проте з 32 можливих одиночних розміток лише 9 узгоджені. (Докладніше див. qualreas.) Лише одна з узгоджених одиночних розміток має ребро дорога TPP ділянка2, і та сама розмітка містить дорога EC ділянка1.

До інших версій числення з'єднаності областей належать RCC5 (з лише п'ятьма базовими відношеннями, при цьому ігнорується розрізнення, чи торкаються дві області одна одної) та RCC23 (яке дозволяє міркувати про опуклість).

Використання RCC8 у GeoSPARQL

RCC8 частково^{[уточнити]} втілено в GeoSPARQL(інші мови) як описано нижче:

Графічне подання числення з'єднаності областей (Region Connection Calculus, RCC: Randell, Cui and Cohn, 1992) і зв'язки з еквівалентними найменуваннями Open Geospatial Consortium (OGC) з їхніми еквівалентними URI.

Втілення

• GQR — система для міркування в численнях RCC-5, RCC-8, RCC-23 (а також інших численнях для просторового та часового міркування).
• qualreas — система мовою Python для якісного міркування над мережами алгебр відношень, як-от RCC-8, алгебра проміжків Аллена тощо.

Див. також

• Просторове відношення(інші мови)
  • DE-9IM(інші мови)