skip to main content
article

Topological relationships between complex spatial objects

Published: 01 March 2006 Publication History

Abstract

For a long time topological relationships between spatial objects have been a focus of research in a number of disciplines like artificial intelligence, cognitive science, linguistics, robotics, and spatial reasoning. Especially as predicates they support the design of suitable query languages for spatial data retrieval and analysis in spatial databases and geographical information systems (GIS). Unfortunately, they have so far only been defined for and applicable to simplified abstractions of spatial objects like single points, continuous lines, and simple regions. With the introduction of complex spatial data types an issue arises regarding the design, definition, and number of topological relationships operating on these complex types. This article closes this gap and first introduces definitions of general and versatile spatial data types for complex points, complex lines, and complex regions. Based on the well known 9-intersection model, it then determines the complete sets of mutually exclusive topological relationships for all type combinations. Completeness and mutual exclusion are shown by a proof technique called proof-by-constraint-and-drawing. Due to the resulting large numbers of predicates and the difficulty of handling them, the user is provided with the concepts of topological cluster predicates and topological predicate groups, which permit one to reduce the number of predicates to be dealt with in a user-defined and/or application-specific manner.

References

[1]
Abler, R. 1987. The National Science Foundation Center for Geographic Information and Analysis. Int. J. Geograph. Inform. Syst. 1, 4, 303--326.
[2]
Behr, T. and Schneider, M. 2001. Topological relationships of complex points and complex regions. In Proceedings of the International Conference on Conceptual Modeling. 56--69.
[3]
Clementini, E. and Di Felice, P. 1996. A model for representing topological relationships between complex geometric features in spatial databases. Inform. Syst. 90, 1--4, 121--136.
[4]
Clementini, E. and Di Felice, P. 1998. Topological invariants for lines. IEEE Trans. Knowl. Data Eng. 10, 1, 38--54.
[5]
Clementini, E., Di Felice, P., and Califano, G. 1995. Composite regions in topological queries. Inform. Syst. 20, 7, 579--594.
[6]
Clementini, E., Di Felice, P., and van Oosterom, P. 1993. A small set of formal topological relationships suitable for end-user interaction. In Proceedings of the 3rd International Symposium on Advances on Spatial Databases. Lecture Notes on Computer Science, vol. 692, Springer, Berlin, Germany, 277--295.
[7]
Cui, Z., Cohn, A. G., and Randell, D. A. 1993. Qualitative and topological relationships. In Proceedings of the 3rd International Symposium on Advances in Spatial Databases. Lecture Notes on Computer Science, vol. 692, Springer, Berlin, Germany, 296--315.
[8]
Davis, J. R. 1998. IBM's DB2 spatial extender: Managing geo-spatial information within the DBMS. Tech. rep., IBM Corporation, Yorktown Heights, NY.
[9]
De Berg, M., van Krefeld, M., Overmars, M., and Schwarzkopf, O. 2000. Computational Geometry: Algorithms and Applications, 3rd ed. Springer-Verlag, Berlin, Germany.
[10]
Egenhofer, M. J., Clementini, E., and Di Felice, P. 1994. Topological relations between regions with Holes. Int. J. Geograph. Inform. Syst. 8, 2, 128--142.
[11]
Egenhofer, M. J. and Franzosa, R. 1995. On the equivalence of topological relations. Int. J. Geograph. Inform. Syst. 9, 2, 133--152.
[12]
Egenhofer, M. J. 1989. A formal definition of binary topological relationships. In Proceedings of the 3rd International Conference on Foundations of Data Organization and Algorithms. Lecture Notes in Computer Science, vol. 367. Springer-Verlag, Berlin, Germany, 457--472.
[13]
Egenhofer, M. J. 1993. Definitions of line-line relations for geographic databases. In Proceedings of the 16th International Conference on Data Engineering. 40--46.
[14]
Egenhofer, M. J. 1994. Spatial SQL: A query and presentation language. IEEE Trans. Knowl. Data Eng. 6, 1, 86--94.
[15]
Egenhofer, M. J. and Franzosa, R. D. 1991. Point-set topological spatial relations. Int. J. Geograph. Inform. Syst. 5, 2, 161--174.
[16]
Egenhofer, M. J. and Herring, J. 1990a. Categorizing binary topological relations between regions, lines, and points in geographic databases. Tech. rep. 90-12. National Center for Geographic Information and Analysis, University of California, Santa Barbara, Santa Barbara, CA.
[17]
Egenhofer, M. J. and Herring, J. 1990b. A mathematical framework for the definition of topological relationships. In Proceedings of the 4th International Symposium on Spatial Data Handling. 803--813.
[18]
Egenhofer, M. J. and Mark, D. 1995. Modeling conceptual neighborhoods of topological line-region relations. Int. J. Geograph. Inform. Syst. 9, 5, 555--565.
[19]
Erwig, M. and Schneider, M. 2002. Spatio-temporal predicates. IEEE Trans. Knowl. Data Eng. 14, 4, 1--42.
[20]
ESRI. 1995. ESRI Spatial Database Engine (SDE). Environmental Systems Research Institute, Inc., Redlands, CA.
[21]
Freeman, J. 1975. The modelling of spatial relations. Comput. Graph. Image Process. 4, 156--171.
[22]
Gaal, S. 1964. Point Set Topology. Academic Press, New York, NY.
[23]
Güting, R. H., Böhlen, M. H., Erwig, M., Jensen, C. S., Lorentzos, N. A., Schneider, M., and M.Vazirgiannis, M. 2000. A foundation for representing and querying moving objects. ACM Trans. Database Syst. 25, 1, 881--901.
[24]
Güting, R. H. 1988. Geo-relational algebra: A model and query language for geometric database systems. In Proceedings of the International Conference on Extending Database Technology. 506--527.
[25]
Güting, R. H. and Schneider, M. 1993. Realms: A foundation for spatial data types in database systems. In Proceedings of the 3rd International Symposium on Advances in Spatial Databases. Lecture Notes in Computer Science, vol. 692. Springer-Verlag, Berlin, Germany, 14--35.
[26]
Güting, R. H. and Schneider, M. 1995. Realm-based spatial data types: The ROSE Algebra. VLDB J. 4, 100--143.
[27]
Informix. 1997. Informix Geodetic DataBlade Module: User's guide. Informix Press, Menlo Park, CA.
[28]
OGC. 1999. OGC Abstract Specification OpenGIS Consortium (OGC). URL: http://www.opengis.org/techno/specs.htm.
[29]
OGC. 2001. OGC Geography Markup Language (GML) 2.0. OpenGIS Consortium (OGC). URL: http://www.opengis.net/gml/01-029/GML2.html.
[30]
Oracle. 1997. Oracle8: Spatial Cartridge. An Oracle technical white paper. Oracle Corporation, Redwood Shores, CA.
[31]
Orenstein, J. A. and Manola, F. A. 1988. PROBE Spatial data modeling and query processing in an image database application. IEEE Trans. Softw. Eng. 14, 611--629.
[32]
Roussopoulos, N., Faloutsos, C., and Sellis, T. 1988. An efficient pictorial database system for PSQL. IEEE Trans. Softw. Eng. 14, 639--650.
[33]
Schneider, M. 1997. Spatial Data Types for Database Systems---Finite Resolution Geometry for Geographic Information Systems. Lecture Notes in Computer Science, vol. 1288. Springer-Verlag, Berlin, Heidelberg, Germany.
[34]
Schneider, M. 2001. A design of topological predicates for complex crisp and fuzzy regions. In Proceedings of the International Conference on Conceptual Modeling. 103--116.
[35]
Schneider, M. 2002. Implementing topological predicates for complex regions. In Proceedings of the International Symposium on Spatial Data Handling. 313--328.
[36]
Shekar, S. and Chawla, S. 2003. Spatial Databases: A Tour. Prentice Hall, Englewood Cliffs, NJ.
[37]
Tilove, R. B. 1980. Set membership classification: A unified approach to geometric intersection problems. IEEE Trans. Comput. C-29, 874--883.
[38]
Worboys, M. F. and Bofakos, P. 1993. A canonical model for a class of areal spatial objects. In Proceedings of the 3rd International Symposium on Advances in Spatial Databases. Lecture Notes in Computer Science, vol. 692. Springer-Verlag, Berlin, Germany, 36--52.

Cited By

View all
  • (2024)Extension of RCC*-9 to Complex and Three-Dimensional Features and Its Reasoning SystemISPRS International Journal of Geo-Information10.3390/ijgi1301002513:1(25)Online publication date: 10-Jan-2024
  • (2024)Per Segment Plane Sweep Line Segment Intersection on the GPUACM Transactions on Spatial Algorithms and Systems10.1145/3701989Online publication date: 28-Oct-2024
  • (2023)Spatial Index Structures for Modern Storage Devices: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.324220735:9(9578-9597)Online publication date: 1-Sep-2023
  • Show More Cited By
  1. Topological relationships between complex spatial objects

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Transactions on Database Systems
    ACM Transactions on Database Systems  Volume 31, Issue 1
    March 2006
    438 pages
    ISSN:0362-5915
    EISSN:1557-4644
    DOI:10.1145/1132863
    Issue’s Table of Contents

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 01 March 2006
    Published in TODS Volume 31, Issue 1

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. 9-intersection model
    2. Topological predicate
    3. complex spatial data type
    4. proof-by-constraint-and-drawing
    5. topological cluster predicate
    6. topological constraint rule
    7. topological predicate group

    Qualifiers

    • Article

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)35
    • Downloads (Last 6 weeks)6
    Reflects downloads up to 13 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Extension of RCC*-9 to Complex and Three-Dimensional Features and Its Reasoning SystemISPRS International Journal of Geo-Information10.3390/ijgi1301002513:1(25)Online publication date: 10-Jan-2024
    • (2024)Per Segment Plane Sweep Line Segment Intersection on the GPUACM Transactions on Spatial Algorithms and Systems10.1145/3701989Online publication date: 28-Oct-2024
    • (2023)Spatial Index Structures for Modern Storage Devices: A SurveyIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.324220735:9(9578-9597)Online publication date: 1-Sep-2023
    • (2023)Enhanced Approach for Agglomerative Clustering Using Topological RelationsIEEE Access10.1109/ACCESS.2023.325237411(21945-21967)Online publication date: 2023
    • (2023)Defining and designing spatial queries: the role of spatial relationshipsGeo-spatial Information Science10.1080/10095020.2022.216392427:6(1868-1892)Online publication date: 17-May-2023
    • (2023)Representing and processing polygonal maps with Sector ListsComputers & Geosciences10.1016/j.cageo.2023.105418179(105418)Online publication date: Oct-2023
    • (2022)A Generalized 9-Intersection Model for Topological Relations between Regions with HolesISPRS International Journal of Geo-Information10.3390/ijgi1104021811:4(218)Online publication date: 23-Mar-2022
    • (2022)Topological relationship model for geographical flowsCartography and Geographic Information Science10.1080/15230406.2022.210437749:6(528-544)Online publication date: 9-Sep-2022
    • (2022)Discovery of Spatial Association Rules from Fuzzy Spatial DataConceptual Modeling10.1007/978-3-031-17995-2_13(179-193)Online publication date: 17-Oct-2022
    • (2021)A Decentralized Fuzzy Rule-Based Approach for Computing Topological Relations between Spatial Dynamic Continuous Phenomena with Vague Boundaries Using Sensor DataSensors10.3390/s2120684021:20(6840)Online publication date: 14-Oct-2021
    • Show More Cited By

    View Options

    Login options

    Full Access

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media