Geospatial topology

Last updated
Examples of topological spatial relations. TopologicSpatialRelarions2.png
Examples of topological spatial relations.

Geospatial topology is the study and application of qualitative spatial relationships between geographic features, or between representations of such features in geographic information, such as in geographic information systems (GIS). [1] For example, the fact that two regions overlap or that one contains the other are examples of topological relationships. It is thus the application of the mathematics of topology to GIS, and is distinct from, but complementary to the many aspects of geographic information that are based on quantitative spatial measurements through coordinate geometry. Topology appears in many aspects of geographic information science and GIS practice, including the discovery of inherent relationships through spatial query, vector overlay and map algebra; the enforcement of expected relationships as validation rules stored in geospatial data; and the use of stored topological relationships in applications such as network analysis. [2] [3] [4] Spatial topology is the generalization of geospatial topology for non-geographic domains, e.g., CAD software.

Contents

Topological relationships

In keeping with the definition of topology, a topological relationship between two geographic phenomena is any spatial relation that is not sensitive to measurable aspects of space, including transformations of space (e.g. map projection). Thus, it includes most qualitative spatial relations, such as two features being "adjacent," "overlapping," "disjoint," or one being "within" another; conversely, one feature being "5km from" another, or one feature being "due north of" another are metric relations. One of the first developments of Geographic Information Science in the early 1990s was the work of Max Egenhofer, Eliseo Clementini, Peter di Felice, and others to develop a concise theory of such relations commonly called the 9-Intersection Model, which characterizes the range of topological relationships based on the relationships between the interiors, exteriors, and boundaries of features. [5] [6] [7] [8]

These relationships can also be classified semantically:

Topological data structures and validation

The ARC/INFO Coverage data structure (1981), a topological data model based on POLYVRT ArcINFO Coverage.svg
The ARC/INFO Coverage data structure (1981), a topological data model based on POLYVRT

Topology was a very early concern for GIS. The earliest vector systems, such as the Canadian Geographic Information System, did not manage topological relationships, and problems such as sliver polygons proliferated, especially in operations such as vector overlay. [9] In response, topological vector data models were developed, such as GBF/DIME (U.S. Census Bureau, 1967) and POLYVRT (Harvard University, 1976). [10] The strategy of the topological data model is to store topological relationships (primarily adjacency) between features, and use that information to construct more complex features. Nodes (points) are created where lines intersect and are attributed with a list of the connecting lines. Polygons are constructed from any sequence of lines that forms a closed loop. These structures had three advantages over non-topological vector data (often called "spaghetti data"): First, they were efficient (a crucial factor given the storage and processing capacities of the 1970s), because the shared boundary between two adjacent polygons was only stored once; second, they facilitated the enforcement of data integrity by preventing or highlighting topological errors, such as overlapping polygons, dangling nodes (a line not properly connected to other lines), and sliver polygons (small spurious polygons created where two lines should match but do not); and third, they made the algorithms for operations such as vector overlay simpler. [11] Their primary disadvantage was their complexity, being difficult for many users to understand and requiring extra care during data entry. These became the dominant vector data model of the 1980s.

By the 1990s, the combination of cheaper storage and new users who were not concerned with topology led to a resurgence in spaghetti data structures, such as the shapefile. However, the need for stored topological relationships and integrity enforcement still exists. A common approach in current data is to store such as an extended layer on top of data that is not inherently topological. For example, the Esri geodatabase stores vector data ("feature classes") as spaghetti data, but can build a "network dataset" structure of connections on top of a line feature class. The geodatabase can also store a list of topological rules, constraints on topological relationships within and between layers (e.g., counties cannot have gaps, state boundaries must coincide with county boundaries, counties must collectively cover states) that can be validated and corrected. [12] Other systems, such as PostGIS, take a similar approach. A very different approach is to not store topological information in the data at all, but to construct it dynamically, usually during the editing process, to highlight and correct possible errors; this is a feature of GIS software such as ArcGIS Pro and QGIS. [13]

Topology in spatial analysis

Several spatial analysis tools are ultimately based on the discovery of topological relationships between features:

Oracle and PostGIS provide fundamental topological operators allowing applications to test for "such relationships as contains, inside, covers, covered by, touch, and overlap with boundaries intersecting." [14] [15] Unlike the PostGIS documentation, the Oracle documentation draws a distinction between "topological relationships [which] remain constant when the coordinate space is deformed, such as by twisting or stretching" and "relationships that are not topological [which] include length of, distance between, and area of." These operators are leveraged by applications to ensure that data sets are stored and processed in a topologically correct fashion. However, topological operators are inherently complex and their implementation requires care to be taken with usability and conformance to standards. [16]

See also

Related Research Articles

<span class="mw-page-title-main">Geographic information system</span> System to capture, manage and present geographic data

A geographic information system (GIS) consists of integrated computer hardware and software that store, manage, analyze, edit, output, and visualize geographic data. Much of this often happens within a spatial database, however, this is not essential to meet the definition of a GIS. In a broader sense, one may consider such a system also to include human users and support staff, procedures and workflows, the body of knowledge of relevant concepts and methods, and institutional organizations.

<span class="mw-page-title-main">Esri</span> Geospatial software & SaaS company

Environmental Systems Research Institute, Inc., doing business as Esri, is an American multinational geographic information system (GIS) software company headquartered in Redlands, California. It is best known for its ArcGIS products. With a 40% market share, Esri is the world's leading supplier of GIS software, web GIS and geodatabase management applications.

A coverage is the digital representation of some spatio-temporal phenomenon. ISO 19123 provides the definition:

A GIS file format is a standard for encoding geographical information into a computer file, as a specialized type of file format for use in geographic information systems (GIS) and other geospatial applications. Since the 1970s, dozens of formats have been created based on various data models for various purposes. They have been created by government mapping agencies, GIS software vendors, standards bodies such as the Open Geospatial Consortium, informal user communities, and even individual developers.

<span class="mw-page-title-main">GRASS GIS</span> Geographical information system software

Geographic Resources Analysis Support System is a geographic information system (GIS) software suite used for geospatial data management and analysis, image processing, producing graphics and maps, spatial and temporal modeling, and visualizing. It can handle raster, topological vector, image processing, and graphic data.

A GIS software program is a computer program to support the use of a geographic information system, providing the ability to create, store, manage, query, analyze, and visualize geographic data, that is, data representing phenomena for which location is important. The GIS software industry encompasses a broad range of commercial and open-source products that provide some or all of these capabilities within various information technology architectures.

ArcSDE is a server-software sub-system that aims to enable the usage of Relational Database Management Systems for spatial data. The spatial data may then be used as part of a geodatabase.

<span class="mw-page-title-main">Shapefile</span> Geospatial vector data format

The shapefile format is a geospatial vector data format for geographic information system (GIS) software. It is developed and regulated by Esri as a mostly open specification for data interoperability among Esri and other GIS software products. The shapefile format can spatially describe vector features: points, lines, and polygons, representing, for example, water wells, rivers, and lakes. Each item usually has attributes that describe it, such as name or temperature.

<span class="mw-page-title-main">ArcGIS</span> Geographic information system maintained by Esri

ArcGIS is a family of client, server and online geographic information system (GIS) software developed and maintained by Esri.

A spatial database is a general-purpose database that has been enhanced to include spatial data that represents objects defined in a geometric space, along with tools for querying and analyzing such data.

<span class="mw-page-title-main">QGIS</span> Open-source desktop GIS software

QGIS is a geographic information system (GIS) software that is free and open-source. QGIS supports Windows, macOS, and Linux. It supports viewing, editing, printing, and analysis of geospatial data in a range of data formats. QGIS was previously also known as Quantum GIS.

JTS Topology Suite is an open-source Java software library that provides an object model for Euclidean planar linear geometry together with a set of fundamental geometric functions. JTS is primarily intended to be used as a core component of vector-based geomatics software such as geographical information systems. It can also be used as a general-purpose library providing algorithms in computational geometry.

An object-based spatial database is a spatial database that stores the location as objects. The object-based spatial model treats the world as surface littered with recognizable objects, which exist independent of their locations.

A georelational data model is a geographic data model that represents geographic features as an interrelated set of spatial and attribute data. The georelational model was the dominant form of vector file format during the 1980s and 1990s, including the Esri coverage and Shapefile.

A geographic data model, geospatial data model, or simply data model in the context of geographic information systems, is a mathematical and digital structure for representing phenomena over the Earth. Generally, such data models represent various aspects of these phenomena by means of geographic data, including spatial locations, attributes, change over time, and identity. For example, the vector data model represents geography as collections of points, lines, and polygons, and the raster data model represent geography as cell matrices that store numeric values. Data models are implemented throughout the GIS ecosystem, including the software tools for data management and spatial analysis, data stored in a variety of GIS file formats, specifications and standards, and specific designs for GIS installations.

<span class="mw-page-title-main">DE-9IM</span> Topological model

The Dimensionally Extended 9-Intersection Model (DE-9IM) is a topological model and a standard used to describe the spatial relations of two regions, in geometry, point-set topology, geospatial topology, and fields related to computer spatial analysis. The spatial relations expressed by the model are invariant to rotation, translation and scaling transformations.

<span class="mw-page-title-main">Sliver polygon</span> Type of error in vector GIS

A sliver polygon, in the context of Geographic Information Systems (GIS), is a small polygon found in vector data that is an artifact of error rather than representing a real-world feature. They have been a recognized source of error since overlay was first invented in the 1970s.

Vector overlay is an operation in a geographic information system (GIS) for integrating two or more vector spatial data sets. Terms such as polygon overlay, map overlay, and topological overlay are often used synonymously, although they are not identical in the range of operations they include. Overlay has been one of the core elements of spatial analysis in GIS since its early development. Some overlay operations, especially Intersect and Union, are implemented in all GIS software and are used in a wide variety of analytical applications, while others are less common.

A spatial join is an operation in a geographic information system (GIS) or spatial database that combines the attribute tables of two spatial layers based on a desired spatial relation between their geometries. It is similar to the table join operation in relational databases in merging two tables, but each pair of rows is correlated based on some form of matching location rather than a common key value. It is also similar to vector overlay operations common in GIS software such as Intersect and Union in merging two spatial datasets, but the output does not contain a composite geometry, only merged attributes.

A Geodatabase is a proprietary GIS file format developed in the late 1990s by Esri to represent, store, and organize spatial datasets within a geographic information system. A geodatabase is both a logical data model and the physical implementation of that logical model in several proprietary file formats released during the 2000s. The geodatabase design is based on the spatial database model for storing spatial data in relational and object-relational databases. Given the dominance of Esri in the GIS industry, the term "geodatabase" is used by some as a generic trademark for any spatial database, regardless of platform or design.

References

  1. "Topology - GIS Wiki | The GIS Encyclopedia". wiki.gis.com. Retrieved 2021-02-02.
  2. ESRI White Paper GIS Topology "GIS Topology". ESRI. 2005. Retrieved 2011-11-25.
  3. Gentle GIS introduction "7. Topology — QGIS Documentation documentation". docs.qgis.org. Retrieved 2021-02-02.
  4. Ubeda, Thierry; Egenhofer, Max J. (1997). "Topological error correcting in GIS". Advances in Spatial Databases. Lecture Notes in Computer Science. Vol. 1262. pp. 281–297. doi:10.1007/3-540-63238-7_35. ISBN   978-3-540-63238-2.
  5. Egenhofer, M.J.; Franzosa, R.D. (1991). "Point-set topological spatial relations". Int. J. GIS. 5 (2): 161–174. doi: 10.1080/02693799108927841 .
  6. Egenhofer, M.J.; Herring, J.R. (1990). "A Mathematical Framework for the Definition of Topological Relationships" (PDF). In Brassel, K.; Kishimoto, H. (eds.). Proceedings of the fourth International Symposium on SDH (Extended abstract). pp. 803–813. Archived from the original (PDF) on 2010-06-14.
  7. Clementini, Eliseo; Di Felice, Paolino; van Oosterom, Peter (1993). "A small set of formal topological relationships suitable for end-user interaction". In Abel, David; Ooi, Beng Chin (eds.). Advances in Spatial Databases: Third International Symposium, SSD '93 Singapore, June 23–25, 1993 Proceedings. Lecture Notes in Computer Science. Vol. 692/1993. Springer. pp. 277–295. doi:10.1007/3-540-56869-7_16. ISBN   978-3-540-56869-8.
  8. Clementini, Eliseo; Sharma, Jayant; Egenhofer, Max J. (1994). "Modelling topological spatial relations: Strategies for query processing". Computers & Graphics. 18 (6): 815–822. doi:10.1016/0097-8493(94)90007-8.
  9. Goodchild, Michael F. (1977). "Statistical Aspects of the Polygon Overlay Problem". In Dutton, Geoffrey (ed.). Harvard Papers in Geographic Information Systems: First International Symposium on Data Structures for Geographic Information Systems. Vol. 6: Spatial algorithms. Harvard University.
  10. Cooke, Donald F. (1998). "Topology and TIGER: The Census Bureau's Contribution". In Foresman, Timothy W. (ed.). The History of Geographic Information Systems: Perspectives from the Pioneers. Prentice Hall. pp. 47–57.
  11. Peucker, Thomas K.; Chrisman, Nicholas (1975). "Cartographic Data Structures". The American Cartographer. 2 (1): 55–69. doi:10.1559/152304075784447289.
  12. "Geodatabase topology". ArcGIS Pro Documentation. Retrieved 6 January 2022.
  13. "Topology Checks". QGIS 3.16 documentation. OSGEO. Retrieved 6 January 2022.
  14. Oracle (2003). "Topology Data Model Overview". Oracle 10g Part No. B10828-01. Oracle. Retrieved 2011-11-25.
  15. "Geometry Relationship Functions". Refractions Research Inc. Archived from the original on 2018-10-06. Retrieved 2011-11-25.
  16. Riedemann, Catharina (2004). "Towards Usable Topological Operators at GIS User Interfaces" (PDF). In Toppen, F.; P. Prastacos (eds.). Proceedings 2004: The 7th AGILE Conference on Geographic Information Science. pp. 669–674. Archived from the original (PDF) on 2017-01-13. Retrieved 2017-01-11.