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

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

Аксіоми RCC керується двома аксіомами.

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

Зауваження щодо аксіом Ці дві аксіоми описують дві ознаки відношення з'єднаності, але не визначають його характерну ознаку. Наприклад, можливо сказати, що об'єкт перебуває на відстані менш ніж 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. Цей факт неочевидний, але його можливо вивести, якщо розглянути узгоджені «одиночні розмітки» () цієї мережі обмежень. Наступний абзац коротко описує одиночні розмітки.

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

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

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

RCC8 частково втілено в як описано нижче:

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

Див. також

Примітки

Джерела

.

.