×

A model for describing and composing direction relations between overlapping and contained regions. (English) Zbl 1161.68839

Summary: Current models of direction relations are not designed to describe direction information inside the minimum bounding rectangle of a reference region. Thus, the direction relations between overlapping and contained regions cannot be effectively described and derived. To resolve this problem, a new model of direction relations, namely interior-boundary direction relations, is proposed in this study to describe direction concepts relative to the interior or boundary of a region, such as “east part of a region”, “west border of a region”, “a line goes through east part of a region”, and etc. By combining the interior and exterior direction relations, three types of compositions of direction relations are investigated: (1) composing two interior direction relations which can be used to derive the interior or exterior direction relations between two regions with the same parent region; (2) composing an interior direction relation with an exterior direction relation; and (3) composing an interior with an exterior direction relation. The results indicate that the new interior-boundary direction relations and its compositions with exterior direction relations are powerful in describing and deriving direction relations between overlapped and contained regions.

MSC:

68U35 Computing methodologies for information systems (hypertext navigation, interfaces, decision support, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

Spatial SQL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aufaure-Portier, M. A., A high level interface language for GIS, Journal of Visual Languages and Computing, 6, 2, 167-182 (1995)
[2] Bertolotto, M.; Carswell, J. D.; McLoughlin, E.; O’Sullivan, D.; Wilson, D., Using sketches and knowledge bases for geo-spatial image retrieval, Computers, Environment and Urban Systems, 30, 1, 29-53 (2006)
[3] Chen, T.; Ai, T., Automatic extraction of skeleton and center of area feature, Geomatics and Information Science of Wuhan University, 29, 5, 443-446 (2004)
[4] Cicerone, S.; Di Felice, P., Cardinal directions between spatial objects: the pairwise-consistency problem, Information Sciences, 164, 1-4, 165-188 (2004) · Zbl 1094.68678
[5] Claramunt, C.; Thériault, M., Fuzzy semantics for direction relations between composite regions, Information Sciences, 160, 1-4, 73-90 (2004)
[6] Clementini, E.; Di Felice, P., A global framework for qualitative shape description, Geoinformatica, 1, 1, 11-27 (1997)
[7] Chang, S. K.; Shi, Q. Y.; Yan, C., Iconic indexing by 2D strings, IEEE Transactions on Patter Analysis and Machine Intelligence, 9, 3, 413-428 (1987)
[8] A.G. Cohn, A hierarchical representation of qualitative shape based on connection and convexity, in: Spatial Information Theory: A Theoretical Basis for GIS, Lecture Notes in Computer Science 988, 1995, pp. 311-325.; A.G. Cohn, A hierarchical representation of qualitative shape based on connection and convexity, in: Spatial Information Theory: A Theoretical Basis for GIS, Lecture Notes in Computer Science 988, 1995, pp. 311-325.
[9] Corral, A.; Almendros-Jiménez, J. M., A performance comparison of distance-based query algorithms using \(R\)-trees in spatial databases, Information Sciences, 177, 11, 2207-2237 (2007)
[10] Duckham, M.; Lingham, J.; Mason, K.; Worboys, M., Qualitative reasoning about consistency in geographic information, Information Sciences, 176, 6, 601-627 (2006)
[11] M.J. Egenhofer, J. Herring, Categorizing binary topological relations between regions, lines and points in geographic databases, Technical Report, University of Maine, Department of Surveying Engineering, 1991.; M.J. Egenhofer, J. Herring, Categorizing binary topological relations between regions, lines and points in geographic databases, Technical Report, University of Maine, Department of Surveying Engineering, 1991.
[12] Egenhofer, M. J., Spatial SQL: a query and presentation language, IEEE Transactions on Knowledge and Data Engineering, 6, 1, 86-95 (1994)
[13] M.J. Egenhofer, Spatial-Query-by-Sketch, in: M. Burnett, W. Citrin (Eds.), IEEE Symposium on Visual Languages, 1996, pp. 60-67.; M.J. Egenhofer, Spatial-Query-by-Sketch, in: M. Burnett, W. Citrin (Eds.), IEEE Symposium on Visual Languages, 1996, pp. 60-67.
[14] Egenhofer, M. J., Query processing in Spatial-Query-by-Sketch, Journal of Visual Languages and Computing, 8, 4, 403-424 (1997)
[15] Egenhofer, M. J.; Shariff, A. R., Metric details for natural-language spatial relations, ACM Transactions on Information Systems, 16, 4, 295-321 (1998)
[16] A.U. Frank, Qualitative spatial reasoning: cardinal directions as an example, in: D. Mark, D. White (Eds.), Auto-Carto 10, 1995, pp. 148-167.; A.U. Frank, Qualitative spatial reasoning: cardinal directions as an example, in: D. Mark, D. White (Eds.), Auto-Carto 10, 1995, pp. 148-167.
[17] R. Goyal, Similarity assessment for cardinal directions between extended spatial objects, Ph.D. Dissertation, Department of Surveying Engineering, University of Maine, 2000.; R. Goyal, Similarity assessment for cardinal directions between extended spatial objects, Ph.D. Dissertation, Department of Surveying Engineering, University of Maine, 2000.
[18] R. Haar, Computational models of spatial relations, Technical Report, University of Maryland, College Park, Department of Computer Science, 1976.; R. Haar, Computational models of spatial relations, Technical Report, University of Maryland, College Park, Department of Computer Science, 1976.
[19] J.-F. Hangouët, Storing Voronoi diagrams in geographical databases, in: Proceedings of GeoComputation 2000, Greenwich, UK. <http://www.geocomputation.org/2000/GC005/Gc005.htm>.; J.-F. Hangouët, Storing Voronoi diagrams in geographical databases, in: Proceedings of GeoComputation 2000, Greenwich, UK. <http://www.geocomputation.org/2000/GC005/Gc005.htm>.
[20] J.H. Hong, M.J. Egenhofer, A.U. Frank, On the robustness of qualitative distance and directions reasoning, in: D. Peuquet (Eds.), Autocarto 12, 1995, pp. 301-310.; J.H. Hong, M.J. Egenhofer, A.U. Frank, On the robustness of qualitative distance and directions reasoning, in: D. Peuquet (Eds.), Autocarto 12, 1995, pp. 301-310.
[21] A. Klippel, C. Dewey, M. Knauff, et al., Direction concepts in wayfinding assistance systems, in: J. Baus, C. Kray, R. Porzel (Eds.), Workshop on Artificial Intelligence in Mobile Systems, 2004, pp. 1-8.; A. Klippel, C. Dewey, M. Knauff, et al., Direction concepts in wayfinding assistance systems, in: J. Baus, C. Kray, R. Porzel (Eds.), Workshop on Artificial Intelligence in Mobile Systems, 2004, pp. 1-8.
[22] Lee, A. J.T.; Hong, R.; Ko, W., Mining spatial association rules in image databases, Information Sciences, 177, 7, 1593-1608 (2007)
[23] Mark, D.; Egenhofer, M. J., Modeling spatial relations between lines and regions: combining formal mathematical models and human subjects testing, Cartography and Geographical Information Systems, 21, 195-212 (1994)
[24] Morris, A. J.; Abdelmoty, A. I.; El-geresy, B. A.; Jones, C. B., A filter flow visual querying language and interface for spatial databases, Geoinformatica, 8, 2, 107-141 (2004)
[25] Morrison, P.; Zou, J., Triangle refinement in a constrained Delaunay triangulation skeleton, Pattern Recognition, 40, 10, 2754-2765 (2007) · Zbl 1132.68794
[26] Neumann, B.; Möller, R., On scene interpretation with description logics, Image and Vision Computing, 26, 1, 82-101 (2008)
[27] Papadias, D.; Theodoridis, Y., Spatial relations, minimum bounding rectangles, and spatial data structures, International Journal of Geographical Information Science, 11, 2, 111-138 (1997)
[28] Papadias, D.; Egenhofer, M. J., Hierarchical spatial reasoning about direction relations, Geoinformatica, 1, 3, 251-273 (1997)
[29] Papadias, D.; Karacapilidis, N.; Arkoumanis, D., Processing fuzzy spatial queries: a configuration similarity approach, International Journal of Geographical Information Science, 13, 2, 93-118 (1999)
[30] Peuquet, D.; Zhang, C. X., An algorithm to determine the directional relationship between arbitrarily-shaped polygons in the plane, Pattern Recognition, 20, 1, 65-74 (1987)
[31] Shariff, A. R.; Egenhofer, M. J.; Mark, D., Natural-Language spatial relations between linear and areal objects: the topology and metric of english-language terms, International Journal of Geographical Information Science, 12, 3, 215-246 (1998)
[32] Skiadopoulos, S.; Koubarakis, M., Composing cardinal direction relations, Artificial Intelligence, 152, 2, 143-171 (2004) · Zbl 1082.68108
[33] Skiadopoulos, S.; Giannoukos, C.; Sarkas, N.; Vassiliadis, P.; Sellis, T.; Koubarakis, M., Computing and managing cardinal direction relations, IEEE Transaction on Knowledge and Date Engineering, 17, 12, 1610-1623 (2005)
[34] Skiadopoulos, S.; Koubarakis, M., On the consistency of cardinal directions constraints, Artificial Intelligence, 163, 1, 91-135 (2005) · Zbl 1132.68713
[35] Stefanidis, A.; Agouris, P.; Georgiadis, C.; Bertolotto, M.; Carswell, J. D., Scale- and orientation- invariant scene similarity metrics for image queries, International Journal of Geographical Information Science, 16, 8, 749-772 (2002)
[36] Sung, S. Y.; Hu, T., Iconic pictorial retrieval using multiple attributes and spatial relationships, Knowledge-Based Systems, 19, 8, 687-695 (2006)
[37] Yan, H.; Chu, Y.; Li, Z.; Guo, R., A quantitative description model for direction relations based on direction groups, Geoinformatica, 10, 2, 177-196 (2006)
[38] Yau, S. S.-T.; Zhang, Q. L., On completeness of reasoning about planar spatial relationships in pictorial retrieval systems, Communications in Information and Systems, 4, 3, 211-234 (2004) · Zbl 1101.68543
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.