564:
22:
528:. So, the path-consistency algorithm leaves multiple possible constraints on 5 of the edges in the constraint network. Since each of the multiple constraints involves 2 constraints, we can reduce the network to 32 (2^5) possible unique constraint networks, each containing only single labels on each edge (
459:
house1 DC house2 house1 {TPP, NTPP} property1 house1 {DC, EC} property2 house1 EC road house2 { DC, EC } property1 house2 NTPP property2 house2 EC road property1 { DC, EC } property2 road { DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi } property1 road { DC, EC, TPP, TPPi, PO, EQ, NTPP, NTPPi } property2
448:
The RCC8 calculus is intended for reasoning about spatial configurations. Consider the following example: two houses are connected via a road. Each house is located on an own property. The first house possibly touches the boundary of the property; the second one surely does not. What can we infer
156:
The two axioms describe two features of the connection relation, but not the characteristic feature of the connect relation. For example, we can say that an object is less than 10 meters away from itself and that if object A is less than 10 meters away from object B, object B will be less than 10
547:
Other versions of the region connection calculus include RCC5 (with only five basic relations - the distinction whether two regions touch each other are ignored) and RCC23 (which allows reasoning about convexity).
567:
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.
509:. This fact is not obvious, but can be deduced once we examine the consistent "singleton-labelings" of the constraint network. The following paragraph briefly describes singleton-labelings.
157:
meters away from object A. So, the relation 'less-than-10-meters' also satisfies the above two axioms, but does not talk about the connection relation in the intended sense of RCC.
468:
130:
654:
Anthony G. Cohn; Brandon
Bennett; John Gooday; Micholas Mark Gotts (1997). "Qualitative Spatial Representation and Reasoning with the Region Connection Calculus".
453:
464:
586:
is a Python framework for qualitative reasoning over networks of relation algebras, such as RCC-8, Allen's interval algebra and more.
563:
701:
98:) by their possible relations to each other. RCC8 consists of 8 basic relations that are possible between two regions:
771:
65:
43:
36:
127:
From these basic relations, combinations can be built. For example, proper part (PP) is the union of TPP and NTPP.
781:
776:
580:
is a reasoner for RCC-5, RCC-8, and RCC-23 (as well as other calculi for spatial and temporal reasoning)
87:
512:
First, we note that the path-consistency algorithm will also reduce the possible properties between
786:
30:
440:
Usage example: if a TPP b and b EC c, (row 4, column 2) of the table says that a DC c or a EC c.
47:
645:
Randell, D.A.; Cui, Z; Cohn, A.G. (1992). "A spatial logic based on regions and connection".
8:
766:
744:
736:
707:
671:
697:
95:
675:
748:
728:
711:
689:
663:
596:
532:"). However, of the 32 possible singleton labelings, only 9 are consistent. (See
91:
533:
732:
667:
760:
536:
for details.) Only one of the consistent singleton labelings has the edge
693:
740:
688:. Lecture Notes in Computer Science. Vol. 2293. Springer Verlag.
583:
557:
452:
The spatial configuration can be formalized in RCC8 as the following
577:
86:) is intended to serve for qualitative spatial representation and
436:"*" denotes the universal relation, no relation can be discarded.
147:
for any region x, y, if x connects with y, y will connect with x
601:
719:
Dong, Tiansi (2008). "A Comment on RCC: From RCC to RCC⁺⁺".
686:
Qualitative
Spatial Reasoning with Topological Information
647:
3rd Int. Conf. on
Knowledge Representation and Reasoning
449:
about the relation of the second property to the road?
129:
485:, or is a tangential proper part of it. But, if the
474:
road { PO, EC } property1 road { PO, TPP } property2
471:, we can refine the network in the following way:
758:
165:The composition table of RCC8 are as follows:
123:non-tangential proper part inverse (NTPPi)
497:can only be externally connected (EC) to
66:Learn how and when to remove this message
562:
551:
144:for any region x, x connects with itself
29:This article includes a list of general
556:RCC8 has been partially implemented in
151:
90:. RCC abstractly describes regions (in
759:
117:tangential proper part inverse (TPPi)
649:. Morgan Kaufmann. pp. 165–176.
160:
15:
13:
571:
35:it lacks sufficient corresponding
14:
798:
120:non-tangential proper part (NTPP)
128:
20:
638:
540:and the same labeling includes
489:is a tangential proper part of
140:RCC is governed by two axioms.
721:Journal of Philosophical Logic
644:
625:
616:
391:PO, TPP, NTPP, TPPi, NTPPi, EQ
1:
609:
114:tangential proper part (TPP)
7:
590:
443:
167:
10:
803:
718:
653:
469:path-consistency algorithm
111:partially overlapping (PO)
80:region connection calculus
733:10.1007/s10992-007-9074-y
683:
307:DC, EC, PO, TPP, TPPi, EQ
237:DC, EC, PO, TPP, TPPi, EQ
135:
105:externally connected (EC)
772:Knowledge representation
668:10.1023/A:1009712514511
379:DC, EC, PO, TPPi, NTPPi
350:DC, EC, PO, TPPi, NTPPi
310:DC, EC, PO, TPPi, NTPPi
281:DC, EC, PO, TPPi, NTPPi
278:DC, EC, PO, TPPi, NTPPi
266:DC, EC, PO, TPPi, NTPPi
263:DC, EC, PO, TPPi, NTPPi
234:DC, EC, PO, TPPi, NTPPi
50:more precise citations.
782:Computational topology
777:Constraint programming
568:
694:10.1007/3-540-70736-0
566:
552:RCC8 use in GeoSPARQL
505:is not possible when
481:either overlaps (PO)
336:DC, EC, PO, TPP, NTPP
327:DC, EC, PO, TPP, NTPP
298:DC, EC, PO, TPP, NTPP
240:DC, EC, PO, TPP, NTPP
217:DC, EC, PO, TPP, NTPP
214:DC, EC, PO, TPP, NTPP
211:DC, EC, PO, TPP, NTPP
208:DC, EC, PO, TPP, NTPP
560:as described below:
530:"singleton labelings
152:Remark on the axioms
622:Randell et al. 1992
353:EC, PO, TPPi, NTPPi
569:
538:road TPP property2
507:road TPP property2
454:constraint network
703:978-3-540-43346-0
684:Renz, J. (2002).
542:road EC property1
503:road PO property1
465:composition table
433:
432:
359:PO, TPP, TPPi, EQ
243:EC, PO, TPP, NTPP
161:Composition table
102:disconnected (DC)
96:topological space
76:
75:
68:
794:
752:
715:
679:
650:
632:
629:
623:
620:
597:Spatial relation
168:
132:
71:
64:
60:
57:
51:
46:this article by
37:inline citations
24:
23:
16:
802:
801:
797:
796:
795:
793:
792:
791:
787:Logical calculi
757:
756:
704:
641:
636:
635:
630:
626:
621:
617:
612:
593:
574:
572:Implementations
554:
475:
463:Using the RCC8
461:
446:
388:PO, TPPi, NTPPi
385:PO, TPPi, NTPPi
382:PO, TPPi, NTPPi
356:PO, TPPi, NTPPi
172:
163:
154:
138:
92:Euclidean space
72:
61:
55:
52:
42:Please help to
41:
25:
21:
12:
11:
5:
800:
790:
789:
784:
779:
774:
769:
755:
754:
727:(2): 319–352.
716:
702:
681:
662:(3): 275–316.
656:GeoInformatica
651:
640:
637:
634:
633:
624:
614:
613:
611:
608:
607:
606:
605:
604:
592:
589:
588:
587:
581:
573:
570:
553:
550:
473:
458:
445:
442:
438:
437:
431:
430:
427:
424:
421:
418:
415:
412:
409:
406:
402:
401:
398:
395:
392:
389:
386:
383:
380:
377:
373:
372:
369:
366:
363:
360:
357:
354:
351:
348:
344:
343:
340:
337:
334:
331:
328:
325:
322:
319:
315:
314:
311:
308:
305:
302:
299:
296:
293:
290:
286:
285:
282:
279:
276:
273:
270:
267:
264:
261:
257:
256:
253:
250:
247:
244:
241:
238:
235:
232:
228:
227:
224:
221:
218:
215:
212:
209:
206:
203:
199:
198:
195:
192:
189:
186:
183:
180:
177:
174:
162:
159:
153:
150:
149:
148:
145:
137:
134:
125:
124:
121:
118:
115:
112:
109:
106:
103:
74:
73:
28:
26:
19:
9:
6:
4:
3:
2:
799:
788:
785:
783:
780:
778:
775:
773:
770:
768:
765:
764:
762:
750:
746:
742:
738:
734:
730:
726:
722:
717:
713:
709:
705:
699:
695:
691:
687:
682:
677:
673:
669:
665:
661:
657:
652:
648:
643:
642:
628:
619:
615:
603:
600:
599:
598:
595:
594:
585:
582:
579:
576:
575:
565:
561:
559:
549:
545:
543:
539:
535:
531:
527:
523:
519:
515:
510:
508:
504:
500:
496:
492:
488:
484:
480:
477:That is, the
472:
470:
466:
457:
455:
450:
441:
435:
434:
428:
425:
422:
419:
416:
413:
410:
407:
404:
403:
399:
396:
393:
390:
387:
384:
381:
378:
375:
374:
370:
367:
364:
362:PO, TPP, NTPP
361:
358:
355:
352:
349:
346:
345:
341:
338:
335:
332:
329:
326:
323:
320:
317:
316:
312:
309:
306:
303:
300:
297:
294:
291:
288:
287:
283:
280:
277:
275:PO, TPP, NTPP
274:
272:PO, TPP, NTPP
271:
268:
265:
262:
259:
258:
254:
251:
248:
246:PO, TPP, NTPP
245:
242:
239:
236:
233:
230:
229:
225:
222:
219:
216:
213:
210:
207:
204:
201:
200:
196:
193:
190:
187:
184:
181:
178:
175:
170:
169:
166:
158:
146:
143:
142:
141:
133:
131:
122:
119:
116:
113:
110:
107:
104:
101:
100:
99:
97:
93:
89:
85:
81:
70:
67:
59:
56:November 2016
49:
45:
39:
38:
32:
27:
18:
17:
724:
720:
685:
659:
655:
646:
639:Bibliography
627:
618:
555:
546:
541:
537:
529:
525:
521:
517:
513:
511:
506:
502:
501:. That is,
498:
494:
490:
486:
482:
478:
476:
462:
451:
447:
439:
164:
155:
139:
126:
83:
79:
77:
62:
53:
34:
493:, then the
365:TPPi, NTPPi
48:introducing
761:Categories
610:References
522:{ DC, EC }
173:R1(a, b)↓
171:R2(b, c)→
108:equal (EQ)
94:, or in a
31:references
767:Reasoning
631:Dong 2008
558:GeoSPARQL
518:property1
499:property1
491:property2
483:property2
301:TPP, NTPP
88:reasoning
741:41217909
676:14841370
591:See also
584:qualreas
534:qualreas
524:to just
467:and the
444:Examples
749:6243376
712:8236425
44:improve
747:
739:
710:
700:
674:
602:DE-9IM
514:house2
400:NTPPi
376:NTPPi
295:DC, EC
249:DC, EC
136:Axioms
33:, but
745:S2CID
737:JSTOR
708:S2CID
672:S2CID
520:from
426:NTPPi
397:NTPPi
394:NTPPi
371:TPPi
368:NTPPi
347:TPPi
342:NTPP
318:NTPP
194:NTPPi
698:ISBN
516:and
495:road
487:road
479:road
423:TPPi
420:NTPP
333:NTPP
330:NTPP
313:TPP
304:NTPP
289:TPP
191:TPPi
188:NTPP
78:The
729:doi
690:doi
664:doi
578:GQR
429:EQ
417:TPP
405:EQ
284:PO
260:PO
255:EC
231:EC
226:DC
202:DC
197:EQ
185:TPP
84:RCC
763::
743:.
735:.
725:34
723:.
706:.
696:.
670:.
658:.
544:.
526:DC
456::
414:PO
411:EC
408:DC
324:DC
321:DC
292:DC
252:DC
223:DC
220:DC
182:PO
179:EC
176:DC
753:.
751:.
731::
714:.
692::
680:.
678:.
666::
660:1
339:*
269:*
205:*
82:(
69:)
63:(
58:)
54:(
40:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
