Modeling the scale dependences of topological relations between lines and regions induced by reduction of attributes

The scale dependences of topological relations are caused by the changes of spatial objects at different scales, which are induced by the reduction of attributes. Generally, the detailed partitions and multi-scale attributes are stored in spatial databases, while the coarse partitions are not. Consequently, the detailed topological relations can be computed and regarded as known information, while the coarse relations stay unknown. However, many applications (e.g., multi-scale spatial data query) need to deal with the topological relations at multiple scales. In this study new methods are proposed to model and derive the scale dependences of topological relations between lines and multi-scale region partitions. The scale dependences of topological relations are modeled and used to derive the relations between lines and coarse partitions from the relations about the detailed partitions. The derivation can be performed in two steps. At the first step, the topological dependences between a line and two meeting, covered and contained regions are computed and stored into composition tables, respectively. At the second step, a graph is used to represent the neighboring relations among the regions in a detailed partition. The scale dependences and detailed relations are then used to derive topological relations at the coarse level. Our methods can also be extended to handle the scale dependences of relations about disconnected regions, or the combinations of connected and disconnected regions. Because our methods use the scale dependences to derive relations at the coarse level, rather than generating coarse partition and computing the relations with geometric information, they are more efficient to support scale-dependent applications.     

Rank-based strategies for cleaning inconsistent spatial databases

A spatial data set is consistent if it satisfies a set of integrity constraints. Although consistency is a desirable property of databases, enforcing the satisfaction of integrity constraints might not be always feasible. In such cases, the presence of inconsistent data may have a negative effect on the results of data analysis and processing and, in consequence, there is an important need for data-cleaning tools to detect and remove, if possible, inconsistencies in large data sets. This work proposes strategies to support data cleaning of spatial databases with respect to a set of integrity constraints that impose topological relations between spatial objects. The basic idea is to rank the geometries in a spatial data set that should be modified to improve the quality of the data (in terms of consistency). An experimental evaluation validates the proposal and shows that the order in which geometries are modified affects both the overall quality of the database and the final number of geometries to be processed to restore consistency.     

Indexing large geographic datasets with compact qualitative representation

This paper develops a new mechanism to efficiently compute and compactly store qualitative spatial relations between spatial objects, focusing on topological and directional relations for large datasets of region objects. The central idea is to use minimum bounding rectangles (MBRs) to approximately represent region objects with arbitrary shape and complexity and only store spatial relations that cannot be unambiguously inferred from the relations of corresponding MBRs. We demonstrate, both in theory and practice, that our approach requires considerably less construction time and storage space, and can answer queries more efficiently than the state-of-the-art methods.     

Database design for a multi-scale spatial information system

Abstract

Growth in the available quantities of digital geographical data has led to major problems in maintaining and integrating data from multiple sources, required by users at differing levels of generalization. Existing GIS and associated database management systems provide few facilities specifically intended for handling spatial data at multiple scales and require time consuming manual intervention to control update and retain consistency between representations. In this paper the GEODYSSEY conceptual design for a multi-scale, multiple representation spatial database is presented and the results of experimental implementation of several aspects of the design are described. Object-oriented, deductive and procedural programming techniques have been applied in several contexts: automated update software, using probabilistic reasoning; deductive query processing using explicit stored semantic and spatial relations combined with geometric data; multiresolution spatial data access methods combining poini, line, area and surface geometry; and triangulation-based generalization software that detects and resolves topological inconsistency.     

拓扑关系和方向关系的定性组合描述

空间关系理论研究是当前GIS界重点研究的前沿课题之一,但就目前研究成果看,空间关系理论中的拓扑关系和方向关系的理论研究多采用独立的描述模型,影响了空间推理和空间表达的精度。该文在分析拓扑关系和方向关系描述模型的基础上,提出将拓扑关系和方向关系定性表示相结合的TD模型,并用实例说明该模型能较全面地描述空间对象的空间关系。     

Integrative representation and inference of qualitative locations about points,lines, and polygons

Qualitative knowledge representation of spatial locations and relations is popular in many text-based media, for example, postings on social networks, news reports, and encyclopedia, as representing qualitative spatial locations is indispensable to infer spatial knowledge from them. However, an integrative model capable of handling direction-based locations of various spatial objects is missing. This study presents an integrative representation and inference framework about direction-based qualitative locations for points, lines, and polygons. In the framework, direction partitions of different types of reference objects are first unified to create a partition consisting of cells, segments, and corners. They serve as a frame of reference to locate spatial objects (e.g., points, lines, and polygons). Qualitative relations are then defined to relate spatial objects to the elements in a cell partition, and to form the model of qualitative locations. Last, based on the integrative representation, location-based reasoning mechanism is presented to derive topological relations between objects from their locations, such as point–point, line–line, point–line, point–polygon, line–polygon, and polygon–polygon relations. The presented model can locate any type of spatial objects in a frame of reference composed of points, lines, and polygons, and derive topological relations between any pairs of objects from the locations in a unified method.     

A vector field model to handle the displacement of multiple conflicts in building generalization

In map generalization, the displacement operation attempts to resolve proximity conflicts to guarantee map legibility. Owing to the limited representation space, conflicts may occur between both the same and different features under different contexts. A successful displacement should settle multiple conflicts, suppress the generation of secondary conflicts after moving some objects, and preserve the distribution patterns. The effect of displacement can be understood as a force that pushes related objects away with properties of propagation and distance decay. This study borrows the idea of vector fields from physics discipline and establishes a vector field model to handle the displacement of multiple conflicts in building generalization. A scalar field is first constructed based on a Delaunay triangulation skeleton to partition the buildings being examined (e.g., a street block). Then, we build a vector field to conduct displacement measurements through the detection of conflicts from multiple sources. The direction and magnitude of the displacement force are computed based on an iso-line model of vector field. The experiment shows that this global method can settle multiple conflicts and preserve the spatial relations and important building patterns.     

地理空间意像模式的Voronoi模型

提出用Voronoi空间模型来表达意像模式，Voronoi模型无岐义空间邻近关系，构建能封装对象间空间关系的拓扑网络，使用该模型将各种空间介词映射为不同的拓扑结构，GIS采用该模型，可按自然语言中空间介词描述的定性空间关系查询检索模糊地理信息。     

An inconsistency measure of spatial data sets with respect to topological constraints

An inconsistency measure can be used to compare the quality of different data sets and to quantify the cost of data cleaning. In traditional relational databases, inconsistency is defined in terms of constraints that use comparison operators between attributes. Inconsistency measures for traditional databases cannot be applied to spatial data sets because spatial objects are complex and the constraints are typically defined using spatial relations. This paper proposes an inconsistency measure to evaluate how dirty a spatial data set is with respect to a set of integrity constraints that define the topological relations that should hold between objects in the data set. The paper starts by reviewing different approaches to quantify the degree of inconsistency and showing that they are not suitable for the problem. Then, the inconsistency measure of a data set is defined in terms of the degree in which each spatial object in the data set violates topological constraints, and the possible representations of spatial objects are points, curves, and surfaces. Finally, an experimental evaluation demonstrates the applicability of the proposed inconsistency measure and compares it with previously existing approaches.     

Multicriteria generalization (MCG): a decision-making framework for formalizing multiscale environmental data reduction

Environmental simulation models need automated geographic data reduction methods to optimize the use of high-resolution data in complex environmental models. Advanced map generalization methods have been developed for multiscale geographic data representation. In the case of map generalization, positional, geometric and topological constraints are focused on to improve map legibility and communication of geographic semantics. In the context of environmental modelling, in addition to the spatial criteria, domain criteria and constraints also need to be considered. Currently, due to the absence of domain-specific generalization methods, modellers resort to ad hoc methods of manual digitization or use cartographic methods available in off-the-shelf software. Such manual methods are not feasible solutions when large data sets are to be processed, thus limiting modellers to the single-scale representations. Automated map generalization methods can rarely be used with confidence because simplified data sets may violate domain semantics and may also result in suboptimal model performance. For best modelling results, it is necessary to prioritize domain criteria and constraints during data generalization. Modellers should also be able to automate the generalization techniques and explore the trade-off between model efficiency and model simulation quality for alternative versions of input geographic data at different geographic scales. Based on our long-term research with experts in the analytic element method of groundwater modelling, we developed the multicriteria generalization (MCG) framework as a constraint-based approach to automated geographic data reduction. The MCG framework is based on the spatial multicriteria decision-making paradigm since multiscale data modelling is too complex to be fully automated and should be driven by modellers at each stage. Apart from a detailed discussion of the theoretical aspects of the MCG framework, we discuss two groundwater data modelling experiments that demonstrate how MCG is not just a framework for automated data reduction, but an approach for systematically exploring model performance at multiple geographic scales. Experimental results clearly indicate the benefits of MCG-based data reduction and encourage us to continue expanding the scope of and implement MCG for multiple application domains.     

A spatial fuzzy influence diagram for modelling spatial objects’ dependencies: a case study on tree-related electric outages

Spatial objects can be interconnected and mutually dependent in complex ways. In Geographical Information Science, spatial objects’ topological relationships are not discussed together with their attributes’ dependencies, and the vagueness of spatial objects is often ignored during the spatial modelling process. To address this, a spatial fuzzy influence diagram (SFID) is introduced. Compared to the traditional statistical or fuzzy modelling approach, the influence diagram brings advantages in helping decision-makers structure complex interdependency problems. A questionnaire was developed to evaluate the applicability of using an influence diagram in modelling spatial objects’ dependencies. As a case study, an SFID is applied to tree-related electric outages. The result of the case study is represented as a vulnerability map of electrical networks. The map shows areas at risk due to tree-related electric outages. The results were first validated by using a visual comparison of the vulnerability map and electricity fault data. In the second validation step, the percentage of fault data, which has received values in different vulnerability categories, was calculated. The results of the case study can be used to support the decision-making process of electrical network maintenance and planning.     

Topology revisited: representing spatial relations

Topology is a central, defining feature of geographical information systems (GIS). The advantages of topological data structures are that data storage for polygons is reduced because boundaries between adjacent polygons are not stored twice, explicit adjacency relations are maintained, and data entry and map production is improved by providing a rigorous, automated method to handle artifacts of digitizing. However, what explains the resurgence of non-topological data structures and why do contemporary desktop GIS packages support them? The historical development of geographical data structures is examined to provide a context for identifying the advantages and disadvantages of topological and non-topological data structures. Although explicit storage of adjacent features increases performance of adjacency analyses, it is not required to conduct these operations. Non-topological data structures can represent features that conform to planar graph theory (i.e. non-overlapping, space-filling polygons). A data structure that can represent proximal and directional spatial relations, in addition to topological relationships is described. This extension allows a broader set of functional relationships and connections between geographical features to be explicitly represented.     

Planar and non-planar topologically consistent vector map simplification

This article contains a mathematical analysis of strategies for determining topological consistency of vector map simplifications. Such techniques exploit assumptions that can be made regarding the similarity of corresponding objects in successive simplifications. We propose that all topological relationships may be classified as planar or non-planar. A formal analysis of techniques for determining topological consistency of a simplification in terms of such relationships is presented. For each technique we analyse any corresponding constraints that are imposed. This provides a unified understanding of the benefits and limitations of individual techniques and the relationships that exist between techniques. Subsequently, a new strategy for determining the topological consistency of a simplification is proposed. This technique integrates the benefits all methods studied to provide a solution which is subject to less constraints. The effectiveness of this approach is demonstrated through fusion with an existing simplification technique resulting in simplifications that have equal topology and similar shaped features to the original map.     

A Euler number-based topological computation model for land parcel database updating

Intersection relations are important topological considerations in database update processes. The differentiation and identification of non-empty intersection relations between new updates and existing objects is one of the first steps in the automatic incremental update process for a land parcel database. The basic non-empty intersection relations are meet, overlap, cover, equal and inside, but these basic relationships cannot reflect the complex and detailed non-empty relations between a new update and the existing objects. It is therefore necessary to refine the basic non-empty topological relations to support and trigger the relevant update operations. Such relations have been refined by several researchers using topological invariants (e.g., dimension, type and sequence) to represent the intersection components. However, the intersection components often include only points and lines, and the refined types of 2-dimensional intersection components that occur between land parcels have not been defined. This study examines the refinement of non-empty relations among 2-dimensional land parcels and proposes a computation model. In this model, an entire spatial object is directly used as the operand, and two set operations (i.e., intersection (∩) and difference (\)) are applied to form the basic topological computation model. The Euler number is introduced to refine the relations with a single 2-dimensional intersection (i.e., cover, inside and overlap) and to distinguish the refined types of 2-dimensional intersection components for the relations with multiple intersections. In this study, the cover and overlap relations with single intersections between regions are refined into seven cases, and nine basic types of 2-dimensional intersection components are distinguished. A composite computation model is formed with both Euler number values and dimensional differences. In this model, the topological relations with single intersections are differentiated by the value of the dimension and the Euler number of the resulting set of the whole-object intersection and differences, whereas the relations with multiple intersections are discriminated by the value of the resulting set at a coarse level and are further differentiated by the type and sequence of the whole-object intersection component in a hierarchical manner. Based on the refined topological relations, an improved method for automatic and incremental updating of the land parcel database is presented. The effectiveness of the models and algorithms was verified by the incremental update of a land cover database. The results of this study represent a new avenue for automatic spatial data handling in incremental update processes.     

Qualitative spatial reasoning: cardinal directions as an example

ABSTRACT

Abstract. Geographers use spatial reasoning extensively in large-scale spaces, i.e., spaces that cannot be seen or understood from a single point of view. Spatial reasoning differentiates several spatial relations, e.g. topological or metric relations, and is typically formalized using a Cartesian coordinate system and vector algebra. This quantitative processing of information is clearly different from the ways human draw conclusions about spatial relations. Formalized qualitative reasoning processes are shown to be a necessary part of Spatial Expert Systems and Geographical Information Systems.

Addressing a subset of the total problem, namely reasoning with cardinal directions, a completely qualitative method, without recourse to analytical procedures, is introduced and a method for its formal comparison with quantitative formula is defined. The focus is on the analysis of cardinal directions and their properties. An algebraic method is used to formalize the meaning of directions. The standard directional symbols (N, W, etc.) are supplemented with a symbol corresponding to an undetermined direction between points too close to each other which greatly increases the power of the inference rules. Two specific systems to determine and reason with cardinal directions are discussed in some detail.

From this example and some other previous work, a comprehensive set of research steps is laid out, following a mathematically based taxonomy. It includes the extension of distance and direction reasoning to extended objects and the definitions of other metric relations that characterize situations when objects are not disjointed. The conclusions compare such an approach with other concepts.     

Crossing natural and data set boundaries: coastal terrain modelling in the South-West Finnish Archipelago

Geographical information systems (GIS) are important tools in coastal research and management. Coastal GIS applications involve special challenges, because the coastal environment is a complex transitional system between the terrestrial and marine realms. Also acquisition methods and responsibilities for spatial data (and thus their properties) change at the shoreline. This article explores the consequences of this land-sea divide for coastal terrain modelling. We study how methods designed for terrestrial environments can be used to create integrated raster coastal terrain models (CTMs) from coarse elevation and depth data. We focus on shore slopes, because many particularities of coastal terrain and the data which describe it as well as the resulting problems are concentrated in the shore zone. Based on shorelines, terrestrial contours, depth contours and depth points, we used the ANUDEM algorithm to interpolate CTMs at different spatial resolutions, with and without drainage enforcement, for two test areas in a highly complex archipelago coast. Slope aspect and gradient rasters were derived from the CTMs using Horn's algorithm. Values were assigned from the slope rasters to thousands of points along the test areas' shorelines in different ways. Shore slope gradients and aspects were also calculated directly from the shorelines and contours. These modelled data were compared to each other and to field-measured shore profiles using a combination of qualitative and quantitative methods. As far as the coarse source data permitted, the interpolation and slope calculations delivered good results at fine spatial resolutions. Vector-based slope calculations were very sensitive to quality problems of the source data. Fine-resolution raster data were consequently found most suitable for describing shore slopes from coarse coastal terrain data. Terrestrial and marine parts of the CTMs were subject to different errors, and modelling methods and parameters had different consequences there. Thus, methods designed for terrestrial applications can be successfully used for coastal terrain modelling, but the choice of methods and parameters and the interpretation of modelling results require special attention to the differences of terrestrial and marine topography and data.     

Exploring spatial data uncertainties in land‐use change scenarios

This paper evaluates errors and uncertainties in representing landscapes that arise from different data rasterization methods, spatial resolutions, and downscaled land‐use change (LUC) scenarios. A vector LU dataset for Luxembourg (minimum mapping unit: 0.15 ha; year 2000) was used as the baseline reference map. This map was rasterized at three spatial resolutions using three cell class assignment methods. The landscape composition and configuration of these maps were compared. Four alternative scenarios of future LUC were also generated for the three resolutions using existing LUC scenarios and a statistical downscaling method creating 37 maps of LUC for the year 2050. These maps were compared in terms of composition and spatial configuration using simple metrics of landscape fragmentation and an analysis of variance (ANOVA). Differences in landscape composition and configuration between the three cell class assignment methods and the three spatial resolutions were found to be at least as large as the differences between the LUC scenarios. This occurred in spite of the large LUC projected by the scenarios. This demonstrates the importance of the rasterization method and the level of aggregation as a contribution to uncertainty when developing future LUC scenarios and in analysing landscape structure in ecological studies.     

Multidimensional-unified topological relations computation: a hierarchical geometric algebra-based approach

This article presents a geometric algebra-based model for topological relation computation. This computational model is composed of three major components: the Grassmann structure preserving hierarchical multivector-tree representation (MVTree), multidimensional unified operators for intersection relation computation, and the judgement rules for assembling the intersections into topological relations. With this model, the intersection relations between the different dimensional objects (nodes at different levels) are computed using the Tree Meet operator. The meet operation between two arbitrary objects is accomplished by transforming the computation into the meet product between each pair of MVTree nodes, which produces a series of intersection relations in the form of MVTree. This intersection tree is then processed through a set of judgement rules to determine the topological relations between two objects in the hierarchy. Case studies of topological relations between two triangles in 3D space are employed to illustrate the model. The results show that with the new model, the topological relations can be computed in a simple way without referring to dimension. This dimensionless way of computing topological relations from geographic data is significant given the increased dimensionality of geographic information in the digital era.     

Scale- and orientation-invariant scene similarity metrics for image queries

In this paper we extend our previous work on shape-based queries to support queries on configurations of image objects. Here we consider spatial reasoning, especially directional and metric object relationships. Existing models for spatial reasoning tend to rely on pre-identified cardinal directions and minimal scale variations, assumptions that cannot be considered as given in our image applications, where orientations and scale may vary substantially, and are often unknown. Accordingly, we have developed the method of varying baselines to identify similarities in direction and distance relations. Our method allows us to evaluate directional similarities without a priori knowledge of cardinal directions, and to compare distance relations even when query scene and database content differ in scale by unknown amounts. We use our method to evaluate similarity between a user-defined query scene and object configurations. Here we present this new method, and discuss its role within a broader image retrieval framework.