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.     

Efficiently implementable algebra for distributed in-network spatial analysis

Existing sensor network query processors (SNQPs) have demonstrated that in-network processing is an effective and efficient means of interacting with wireless sensor networks (WSNs) for data collection tasks. Inspired by these findings, this article investigates the question as to whether spatial analysis over WSNs can be built upon established distributed query processing techniques, but, here, emphasis is on the spatial aspects of sensed data, which are not adequately addressed in the existing SNQPs. By spatial analysis, we mean the ability to detect topological relationships between spatially referenced entities (e.g. whether mist intersects a vineyard or is disjoint from it) and to derive representations grounded on such relationships (e.g. the geometrical extent of that part of a vineyard that is covered by mist). To support the efficient representation, querying and manipulation of spatial data, we use an algebraic approach. We revisit a previously proposed centralized spatial algebra comprising a set of spatial data types and a comprehensive collection of operations. We have redefined and re-conceptualized the algebra for distributed evaluation and shown that it can be efficiently implemented for in-network execution. This article provides rigorous, formal definitions of the spatial data types, points, lines and regions, together with spatial-valued and topological operations over them. The article shows how the algebra can be used to characterize complex and expressive topological relationships between spatial entities and spatial phenomena that, due to their dynamic, evolving nature, cannot be represented a priori.     

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.     

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

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

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.     

基于单元复形的数字图像多级别层次表达

基于复形理论定义了数字图像空间的拓扑元素及其性质,在此基础上提出一套完备的保持拓扑等价性的层次表达数字图像的数学模型体系框架,并验证了层次表达结构中的Jordan曲线定理.同时,基于单元复形扩展模型,对SPOT影像实施了渐进式离散分割,有效地利用影像蕴含的空间信息,获得了比最大似然分类法更优的分割结果.     

SIRO-DBMS SIRO-DBMS: a database tool-kit for geographical information systems

Abstract

Progress in technical database management systems offers alternative strategies for the design and implementation of databases for geographical information systems. Desirable extensions in the user data types and database management are reviewed. A prototype geographical database tool-kit, SIRO-DBMS, which provides some spatial data types and spatial access methods as external attachments to a kernel relational database management system, is described. An ability to fragment a large set of entities into several relations while retaining the ability to search the full set as a logical unit is provided. Implementation of the geometric data types is based on mapping the types of data into a set of attributes of the atomic types supported by the kernel and specifying the relational designs for the set of atomic attributes.     

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

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

PAN graphs An aid to GIS analysis

Abstract

Many data structures are possible for the storage of topological information for computer-based maps. The PAN graph is here suggested as an aid in the selection of a strategy appropriate to the application. Examples are given for the mapping of triangular networks and Thiessen polygons. Application of the technique is appropriate to both education in, and design of, spatial data structures for automated cartography and geographical information systems     

A spatial data model design for feature-based geographical information systems

Abstract

In state-of-the-art GIS, geographical features are represented as geometric objects with associated topological relations and classification attributes. Semantic relations and intrinsic interrelations of the features themselves are generally neglected. In this paper, a feature-based model that enhances the representation of geographical features is described. Features, as the fundamental depiction of geographical phenomena, encompass both real world entities and digital representation. A feature-based object incorporates both topological relations among geometric elements and non-topological (semantic) relations among features. The development of an object-oriented prototype feature-based GIS that supports relations between feature attributes and feature classes is described. Object-oriented concepts such as class inheritance and polymorphism facilitate the development of feature-based GTS.     

地理空间中的空间关系表达和推理

针对地理空间中的应用,归纳了在空间关系的表达与推理中不同于人工智能领域研究的一些特点:在人工智能领域,更注重建立形式化的推理系统;而在地理信息科学中,则需更关注地理空间的特点以及地物的地理语义。该文基于地理空间和地理现象的本质且顾及地理空间认知,总结了地理空间中空间关系表达和推理的特点,具体包括空间的有限性、地球的球面特征、地物的地理语义、地物形状的复杂性、面状地物、特殊的空间关系、空间关系的层次性与尺度相应原则、不确定性、三维与时态特性九方面;进而介绍了地理空间关系表达的两个应用,即地理信息检索和基于对象的图像分析。该文的探讨可为地理信息科学中的相关研究提供方向性指导。     

A combinatorial data model for representing topological relations among 3D geographical features in micro‐spatial environments

This research is motivated by the need for 3D GIS data models that allow for 3D spatial query, analysis and visualization of the subunits and internal network structure of ‘micro‐spatial environments’ (the 3D spatial structure within buildings). It explores a new way of representing the topological relationships among 3D geographical features such as buildings and their internal partitions or subunits. The 3D topological data model is called the combinatorial data model (CDM). It is a logical data model that simplifies and abstracts the complex topological relationships among 3D features through a hierarchical network structure called the node‐relation structure (NRS). This logical network structure is abstracted by using the property of Poincaré duality. It is modelled and presented in the paper using graph‐theoretic formalisms. The model was implemented with real data for evaluating its effectiveness for performing 3D spatial queries and visualization.     

Natural trees—neighbourhood-location in a nutshell

Abstract

We present the notion of a natural tree as an efficient method for storing spatial information for quick access. A natural tree is a representation of spatial adjacency, organised to allow efficient addition of new data, access to existing data, or deletions. The nodes of a natural tree are compound elements obtained by a particular Delaunay triangulation algorithm. Improvements to that algorithm allow both the construction of the triangulation and subsequent access to neighbourhood information to be O(N log N). Applications include geographical information systems, contouring, and dynamical systems reconstruction.     

Quantitative measures for spatial information of maps

The map is a medium for recording geographical information. The information contents of a map are of interest to spatial information scientists. In this paper, existing quantitative measures for map information are evaluated. It is pointed out that these are only measures for statistical information and some sort of topological information. However, these measures have not taken into consideration the spaces occupied by map symbols and the spatial distribution of these symbols. As a result, a set of new quantitative measures is proposed, for metric information, topological information and thematic information. An experimental evaluation is also conducted. Results show that the metric information is more meaningful than statistical information, and the new index for topological information is more meaningful than the existing one. It is also found that the new measure for thematic information is useful in practice.     

Cardinal directions: a comparison of direction relation matrix and objects interaction matrix

How to express and reason with cardinal directions between extended objects such as lines and regions is an important problem in qualitative spatial reasoning (QSR), a common subfield of geographical information science and Artificial Intelligence (AI). The direction relation matrix (DRM) model, proposed by Goyal and Egenhofer in 1997, is one very expressive relation model for this purpose. Unlike many other relation models in QSR, the set-theoretic converse of a DRM relation is not necessarily representable in DRM. Schneider et al. regard this as a serious shortcoming and propose, in their work published in ACM TODS (2012), the objects interaction matrix (OIM) model for modelling cardinal directions between complex regions. OIM is also a tiling-based model that consists of two phases: the tiling phase and the interpretation phase. Although it was claimed that OIM is a novel concept, we show that it is not so different from DRM if we represent the cardinal direction of two regions a and b by both the DRM of a to b and that of b to a. Under this natural assumption, we give methods for computing DRMs from OIMs and vice versa, and show that OIM is almost the same as DRM in the tiling phase, and becomes less precise after interpretation. Furthermore, exploiting the similarity between the two models, we prove that the consistency of a complete basic OIM network can be decided in cubic time. This answers an open problem raised by Schneider et al. regarding efficient algorithms for reasoning with OIM.