Abstract
Separate mechanisms exist for the compositions of binary topological relations and binary direction relations. They are appropriate for homogeneous spatial reasoning, i.e., the inference of new topological relations from a set of topological relations, or the derivation of new direction relations from a set of direction relations; however, these composition mechanisms are insufficient for heterogeneous spatial reasoning, such as the inference of spatial relations from the combination of topological relations and cardinal directions. This paper discusses the shortcomings of current inference methods for heterogeneous spatial reasoning and presents a new method for heterogeneous directiontopology reasoning. The results demonstrate that using a canonical model, in particular Allen's interval relations, leads to a powerful heterogeneous reasoning mechanism. The spatial objects are approximated by their minimum bounding rectangles and the topological and direction relations are mapped onto interval relations. Compositions are performed using the composition table for interval relations. The results of the compositions are then reverse mapped onto directions. This process enables complex three-step inferences over topological and direction relations such as A West of B, B overlap C, and C West of D imply A West of D.
This research was partially supported by the National Science Foundation under grants IRI-9309230 (Principal Investigator: Max J. Egenhofer) and SBR-8810917 for the National Center for Geographic Information and Analysis, and a University of Maine Graduate Research Assistantship (UGRA). This support is gratefully acknowledged.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdelmoty, A. I., and El-Geresy, B. A. (1994). An Intersection-Based Formalism for Representing Orientation Relations in a Geographic Database. In 2nd ACM Conference on Advances in GIS Theory. Gaithersburg, MD: ACM Press.
Abdelmoty, A. I., and Williams, M. H. (1994). Approaches to the Representation of Qualitative Spatial Relationships for Geographic Databases. In M. Molenaar (Ed.), Advanced Geographic Data Modelling (AGDM 94). Delft, Netherlands: Netherlands Geodetic Commission.
Allen, J. F. (1983). Maintaining Knowledge about Temporal Intervals. Communications of the ACM, 26(11), 832–843.
Chang, S. K., Shi, Q. Y., and Yan, C. W. (1987). Iconic Indexing by 2-D strings. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-9(6), 413–428.
Clementini, E., Sharma, J., Egenhofer, M. J. (1994a). Modelling Topological Spatial Relations: Strategies for Query Processing. Computers and Graphics, 18(6), 815–822.
Clementini, E., Di Felice, P., and Hernández, D. (1994b). Qualitative Representation of Positional Information (Technical Report), University of L'Aquila.
Egenhofer, M. J. (1993). A Model for Detailed Binary Topological Relationships. Geomatica, 47(3 & 4), 261–273.
Egenhofer, M. J. (1994). Deriving the Composition of Binary Topological Relations. Journal of Visual Languages and Computing, 5, 133–149.
Egenhofer, M. J., and Franzosa, R. (1991). Point-Set Topological Spatial Relations. International Journal of Geographic Information Systems, 5(2), 161–174.
Frank, A. (1992). Qualitative Reasoning about Distances and Directions in Geographic Space. Journal of Visual Languages and Computing, 3(4), 343–371.
Hernández, D. (1994). Qualitative Representation of Spatial Knowledge. New York: Springer-Verlag.
Papadias, D. (1994) Relation-Based Representation of Spatial Knowledge. PhD. Thesis. National Technical University of Athens.
Papadias, D., and Sellis, T. (1992). Spatial Reasoning Using Symbolic Arrays. In A. U. Frank, I. Campari, and U. Formentini (Ed.), From Space to territory: Theories and Models of Spatio-Temporal Reasoning, (pp. 153–161). Pisa, Italy: Springer-Verlag.
Papadias, D., Theodoridis, Y., Sellis, T., and Egenhofer, M. J. (1995). Topological Relations in the World of Minimum Bounding Rectangles: a Study with R-trees. In ACM SIGMOD. San Jose, CA: ACM Press.
Peuquet, D. J., and Ci-Xiang, Z. (1987). An algorithm to determine the directional relationship between arbitarily shaped polygons in the plane. Pattern Recognition, 20(1), 65–74.
Sistla, A. P., Yu, C., and Haddad, R. (1994). Reasoning about Spatial Relationships in Picture Retrieval Systems. In 20th International Conference on Very Large Databases. Santiago, Chile.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1995 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sharma, J., Flewelling, D.M. (1995). Inferences from combined knowledge about topology and directions. In: Egenhofer, M.J., Herring, J.R. (eds) Advances in Spatial Databases. SSD 1995. Lecture Notes in Computer Science, vol 951. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-60159-7_17
Download citation
DOI: https://doi.org/10.1007/3-540-60159-7_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60159-3
Online ISBN: 978-3-540-49536-9
eBook Packages: Springer Book Archive