Multi-level Topological Relations Between Spatial Regions Based Upon Topological Invariants | GeoInformatica Skip to main content
Springer Nature Link
Log in

Multi-level Topological Relations Between Spatial Regions Based Upon Topological Invariants

  • Published:
GeoInformatica Aims and scope Submit manuscript

Abstract

Topological relations have played important roles in spatial query, analysis and reasoning. In a two-dimensional space (IR2), most existing topological models can distinguish the eight basic topological relations between two spatial regions. Due to the arbitrariness and complexity of topological relations between spatial regions, it is difficult for these models to describe the order property of transformations among the topological relations, which is important for detailed analysis of spatial relations. In order to overcome the insufficiency in existing models, a multi-level modeling approach is employed to describe all the necessary details of region–region relations based upon topological invariants. In this approach, a set of hierarchically topological invariants is defined based upon the boundary–boundary intersection set (BBIS) of two involved regions. These topological invariants are classified into three levels based upon spatial set concept proposed, which include content, dimension and separation number at the set level, the element type at the element level, and the sequence at the integrated level. Corresponding to these hierarchical invariants, multi-level formal models of topological relations between spatial regions are built. A practical example is provided to illustrate the use of the approach presented in this paper.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16

Similar content being viewed by others

References

  1. R.F. Abler. “The national science foundation national center for geographic information and analysis,” International Journal of Geographical Information Systems, Vol. 1(4):303–326, 1987.

    Google Scholar 

  2. M. Breunig. Integration of Spatial Information for Geo-information Systems. Springer: Berlin Heidelberg New York, 1996.

    Google Scholar 

  3. J. Chen, C. Li, Z. Li, and C. Gold. “A Voronoi-based 9-intersection model for spatial relations,” International Journal of Geographical Information Science, Vol. 15(3):201–220, 2001.

    Article  Google Scholar 

  4. E. Clementini, P. Di Felice, and P. van Oosterom. “A small set for formal topological relationships suitable for end-user interaction,” in D. Abel and B.C. Ooi (Eds.), Advances in Spatial Databases—Third International Symposium, SSD’93, Singapore, Lecture Notes in Computer Science, Vol. 692. Springer: Berlin Heidelberg New York, 277–295, 1993.

    Google Scholar 

  5. E. Clementini, P. Di Felice, and G. Califano. “Composite regions in topological queries,” Information Systems, Vol. 20(7):579–594, 1995.

    Article  Google Scholar 

  6. E. Clementini and P. Di Felice. “Topological invariants for lines,” IEEE Transactions on Knowledge and Data Engineering, Vol. 10:38–54, 1998.

    Article  Google Scholar 

  7. E. Clementini, J. Sharma, and M. Egenhofer. “Modeling topological spatial relations: Strategies for query processing,” Computers and Graphics, Vol. 18(6):815–822, 1994.

    Article  Google Scholar 

  8. Z. Cui, A.G. Cohn, and D.A. Randell. “Qualitative and topological relationships in spatial databases,” in D. Abel and B.C. Ooi (Eds.), Advances in Spatial Databases—Third International Symposium, SSD’93, Springer: Berlin Heidelberg New York, 296–315, 1993.

  9. M. Deng. “Approaches for topological relations between spatial regions with uncertainty,” Ph.D. thesis, Asian Institute of Technology, Thailand, 2004.

  10. M. Egenhofer and R. Franzosa. “Point-set topological spatial relations,” International Journal of Geographical Information Systems, Vol. 5(2):161–174, 1991.

    Google Scholar 

  11. M. Egenhofer and J. Herring. “Categorizing binary topological relationships between regions, lines and points in geographic databases,” in M. Egenhofer and J. Herring (Eds.), A Framework for the Definition of Topological Relationships and an Approach to Spatial Reasoning within this Framework, Santa Barbara, CA, 1–28, 1991.

  12. M. Egenhofer and K. Al-Taha. “Reasoning about gradual changes of topological relationships,” in A. Frank, I. Campari, and U. Formentini (Eds.), Proceedings of the International Conference GIS—from Space to Territory: Theories and Methods of Spatio-temporal Reasoning in Geographic Space, Pisa, Italy, Lecture Notes in Computer Science, Vol. 639. Springer: Berlin Heidelberg New York, 196–219, 1992.

    Google Scholar 

  13. M. Egenhofer. “A model for detailed binary topological relationships,” Geomatica, Vol. 47(3–4):261–273, 1993.

    Google Scholar 

  14. M. Egenhofer, E. Clementini, and P. Di Felice. “Topological relations between regions with holes,” International Journal of Geographical Information Systems, Vol. 8(2):129–144, 1994.

    Google Scholar 

  15. M. Egenhofer, E. Clementini, and P. Di Felice. “Evaluating inconsistencies among multiple representations,” in Proceedings of the 6th International Symposium on Spatial Data Handling, Edinburgh, Scotland, UK, 1994.

  16. M. Egenhofer and R. Franzosa. “On the equivalence of topological relations,” International Journal of Geographical Information Systems, Vol. 9(2):133–152, 1995.

    Google Scholar 

  17. B. Faltings. “Qualitative spatial reasoning using algebraic topology,” in Proceedings of COSIT—95, Lecture Notes in Computer Science, Vol. 988, pp. 17–30, Springer: Berlin Heidelberg New York, 1995.

  18. A. Frank. “Qualitative spatial reasoning about distances and directions in geographic space,” Journal of Visual Languages and Computing, Vol. 3:343–371, 1992.

    Article  Google Scholar 

  19. D. Hernández. “Relative representation of spatial knowledge: The 2-D case,” in D. Mark and A. Frank (Eds.), Cognitive and Linguistic Aspects of Geographic Space. Kluwer: Dordrecht, 1991.

    Google Scholar 

  20. J.R. Herring. “The mathematical modeling of spatial and non-spatial information in geographic information systems,” in D. Mark and A. Frank (Eds.), Cognitive and Linguistic Aspects of Geographic Space. Kluwer: Dordrecht, 313–350, 1991.

    Google Scholar 

  21. W. Kainz, M. Egenhofer, and L. Greasley. “Modeling spatial relations and operations with partially ordered sets,” International Journal of Geographical Information Systems, Vol. 7(3):215–229, 1993.

    Google Scholar 

  22. Z. Li, R. Zhao, and J. Chen. “A Voronoi-based spatial algebra for spatial relations,” Progress in Natural Science, Vol. 12(7):528–536, 2002.

    Google Scholar 

  23. D.M. Mark and M. Egenhofer. “Modeling spatial relations between lines and regions: Combining formal mathematical models and human subjects testing,” Cartography and Geographic Information Systems, Vol. 21(3):195–212, 1994.

    Google Scholar 

  24. D.J. Peuquet and C.X. Zhan. “An algorithm to determine the directional relationship between arbitrary-shaped polygons in the plane,” Pattern Recognition, Vol. 20(1):65–74, 1987.

    Article  Google Scholar 

  25. D. Randell, Z. Cui, and A. Cohn. “A spatial logical based on regions and connection,” in M. Kaufmann and M. San (Eds.), Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning. Springer: Berlin Heidelberg New York, 165–176, 1992.

  26. J. Renz and B. Nebel. “On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus,” Artificial Intelligence, Vol. 108(1–2):69–123, 1999.

    Article  Google Scholar 

  27. A.P. Sistla, C. Yu, and R. Haddad. “Reasoning about spatial relationships in picture retrieval systems,” in Proceedings of VLDB—94, Santiago, Chile, pp. 570–581, Morgan Kaufman: San Francisco, CA, 1994.

Download references

Acknowledgements

This work was supported by the RGC of Hong Kong (Project PolyU 5228/06E) and the National Science Foundation of China under grant numbers 40501053 and 40571127.

Author information

Authors and Affiliations

  1. Department of Land Surveying and Geo-Informatics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong

    Min Deng & Zhilin Li

  2. Department of Geomatic Engineering, University College London, Chadwick Building, Gower Street, WC1E 6BT, London, UK

    Tao Cheng

  3. Space Technology Application and Research Program, Asian Institute of Technology, P.O. Box 4, Klong Luang, Pathumthani, 12120, Thailand

    Xiaoyong Chen

Authors
  1. Min Deng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tao Cheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Xiaoyong Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Zhilin Li
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Tao Cheng.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Deng, M., Cheng, T., Chen, X. et al. Multi-level Topological Relations Between Spatial Regions Based Upon Topological Invariants. Geoinformatica 11, 239–267 (2007). https://doi.org/10.1007/s10707-006-0004-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10707-006-0004-x

Keywords

Search

Navigation