Расчет связей регионов
 | Эта статья включает список общих ссылок , но в ней отсутствуют соответствующие встроенные цитаты . ( Ноябрь 2016 ) |
Исчисление связей регионов ( RCC ) предназначено для качественного пространственного представления и рассуждений . RCC абстрактно описывает регионы (в евклидовом пространстве или в топологическом пространстве ) с помощью их возможных отношений друг к другу. RCC8 состоит из 8 основных отношений, которые возможны между двумя регионами:
- отключен (постоянный ток)
- внешне подключенный (EC)
- равный (EQ)
- частично перекрывающиеся (ПО)
- тангенциальная собственная часть (ТСП)
- тангенциальная инверсная собственная часть (TPPi)
- некасательная собственная часть (НТСЧ)
- некасательная собственная обратная часть (NTPPi)
Из этих основных отношений можно строить комбинации. Например, собственная часть (PP) является объединением TPP и NTPP.
Аксиомы
RCC регулируется двумя аксиомами. [1]
- для любого региона x, x соединяется с самим собой
- для любого региона x, y, если x соединяется с y, y соединяется с x
Замечание по аксиомам
Две аксиомы описывают две особенности отношения соединения, но не характерную особенность отношения соединения. [2] Например, мы можем сказать, что объект находится на расстоянии менее 10 метров от самого себя и что если объект A находится на расстоянии менее 10 метров от объекта B, то объект B будет находиться на расстоянии менее 10 метров от объекта A. Таким образом, отношение «менее 10 метров» также удовлетворяет двум приведенным выше аксиомам, но не говорит об отношении соединения в предполагаемом смысле RCC.
Состав таблицы
Состав RCC8 выглядит следующим образом :
| Р 2 (б, в)→ Р 1 (а, б)↓ | округ Колумбия | ЕС | ПО | ТЭС | НТПП | ТППи | НТППи | эквалайзер |
|---|---|---|---|---|---|---|---|---|
| округ Колумбия | * | ДК, ЕС, ПО, ТПП, НТПП | ДК, ЕС, ПО, ТПП, НТПП | ДК, ЕС, ПО, ТПП, НТПП | ДК, ЕС, ПО, ТПП, НТПП | округ Колумбия | округ Колумбия | округ Колумбия |
| ЕС | DC, EC, PO, TPPi, NTPPi | DC, EC, PO, TPP, TPPi, EQ | ДК, ЕС, ПО, ТПП, НТПП | ЕС, ПО, ТПП, НТПП | ПО, ТПП, НТПП | Округ Колумбия, ЕС | округ Колумбия | ЕС |
| ПО | DC, EC, PO, TPPi, NTPPi | DC, EC, PO, TPPi, NTPPi | * | ПО, ТПП, НТПП | ПО, ТПП, НТПП | DC, EC, PO, TPPi, NTPPi | DC, EC, PO, TPPi, NTPPi | ПО |
| ТЭС | округ Колумбия | Округ Колумбия, ЕС | ДК, ЕС, ПО, ТПП, НТПП | ТЭС, НТЭС | НТПП | DC, EC, PO, TPP, TPPi, EQ | DC, EC, PO, TPPi, NTPPi | ТЭС |
| НТПП | округ Колумбия | округ Колумбия | ДК, ЕС, ПО, ТПП, НТПП | НТПП | НТПП | ДК, ЕС, ПО, ТПП, НТПП | * | НТПП |
| ТППи | DC, EC, PO, TPPi, NTPPi | ЕС, PO, TPPi, NTPPi | ПО, ТППи, НТППи | ПО, ТПП, ТППи, ЭКВ | ПО, ТПП, НТПП | ТППи, НТППи | НТППи | ТППи |
| НТППи | DC, EC, PO, TPPi, NTPPi | ПО, ТППи, НТППи | ПО, ТППи, НТППи | ПО, ТППи, НТППи | ПО, ТПП, НТПП, ТППи, НТППи, эквалайзер | НТППи | НТППи | НТППи |
| эквалайзер | округ Колумбия | ЕС | ПО | ТЭС | НТПП | ТППи | НТППи | эквалайзер |
- «*» обозначает универсальное отношение, ни одно отношение не может быть отброшено.
Пример использования: если TPP b и b EC c, (строка 4, столбец 2) таблицы говорит, что DC c или EC c.
Примеры
Исчисление RCC8 предназначено для рассуждений о пространственных конфигурациях. Рассмотрим следующий пример: два дома соединены дорогой. Каждый дом расположен на собственной территории. Первый дом, возможно, касается границы территории; второй, безусловно, нет. Какой вывод мы можем сделать о связи второй территории с дорогой?
Пространственная конфигурация может быть формализована в RCC8 как следующая сеть ограничений:
дом1 DC дом2дом1 {ТПП, НТПП} недвижимость1дом1 {DC, EC} недвижимость2дом1 EC дорогадом2 { DC, EC } недвижимость1дом2 НТПП недвижимость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) property2 , либо является касательной собственной частью его. Но если дорога является касательной собственной частью property2 , то дорога может быть только внешне связана (EC) с property1 . То есть, дорога PO property1 невозможна, когда дорога TPP property2 . Этот факт не очевиден, но может быть выведен, как только мы рассмотрим последовательные "singleton-labelings" сети ограничений. В следующем параграфе кратко описываются singleton-labelings.
Во-первых, отметим, что алгоритм согласованности путей также сократит возможные свойства между house2 и property1 с {DC, EC} до просто DC . Таким образом, алгоритм согласованности путей оставляет несколько возможных ограничений на 5 ребрах в сети ограничений. Поскольку каждое из нескольких ограничений включает 2 ограничения, мы можем сократить сеть до 32 (2 5 ) возможных уникальных сетей ограничений, каждая из которых содержит только одиночные метки на каждом ребре ( «singleton labelings »). Однако из 32 возможных singleton labelings только 9 являются согласованными. (Подробнее см. в qualreas.) Только одна из согласованных singleton labelings имеет ребровую дорогу TPP property2 , и та же самая маркировка включает дорогу EC property1 .
Другие версии исчисления связности областей включают RCC5 (только с пятью основными отношениями — различие, касаются ли две области друг друга, игнорируется) и RCC23 (который позволяет рассуждать о выпуклости).
Использование RCC8 в GeoSPARQL
RCC8 был частично [ требуется разъяснение ] реализован в GeoSPARQL , как описано ниже:
Реализации
- GQR — это рассуждение для RCC-5, RCC-8 и RCC-23 (а также других исчислений для пространственных и временных рассуждений)
- qualreas — это фреймворк Python для качественных рассуждений в сетях реляционных алгебр, таких как RCC-8, интервальная алгебра Аллена и другие.
Смотрите также
Ссылки
- ^ Рэнделл, Куи и Кон 1992.
- ^ Донг 2008.
Библиография
- Рэнделл, ДА; Куи, З; Кон, АГ (1992). «Пространственная логика, основанная на регионах и связях». 3-я Международная конференция по представлению знаний и рассуждениям . Морган Кауфманн. С. 165–176 .
- Энтони Г. Кон; Брэндон Беннетт; Джон Гудей; Михолас Марк Готтс (1997). «Качественное пространственное представление и рассуждение с помощью исчисления связей регионов». GeoInformatica . 1 (3): 275– 316. Bibcode : 1997GInfo...1..275C. doi : 10.1023/A:1009712514511. S2CID 14841370..
- Ренц, Дж. (2002). Качественное пространственное рассуждение с топологической информацией . Конспект лекций по информатике. Том 2293. Springer Verlag. doi :10.1007/3-540-70736-0. ISBN 978-3-540-43346-0. S2CID 8236425.
- Дун, Тяньси (2008). «Комментарий к RCC: от RCC к RCC⁺⁺». Журнал философской логики . 34 (2): 319– 352. doi :10.1007/s10992-007-9074-y. JSTOR 41217909. S2CID 6243376..
