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.     

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.     

Computing the fuzzy topological relations of spatial objects based on induced fuzzy topology

For modeling the topological relations between spatial objects, the concepts of a bound on the intersection of the boundary and interior, and the boundary and exterior are defined in this paper based on the newly developed computational fuzzy topology. Furthermore, the qualitative measures for the intersections are specified based on the α‐cut induced fuzzy topology, which are (A_α∧?A)(x)<1?α and ((A^c)_α∧?A)(x)<1?α. In other words, the intersection of the interior and boundary or boundary and exterior are always bounded by 1?α, where α is a value of a level cutting. Specifically, the following areas are covered: (a) the homeomorphic invariants of the fuzzy topology; (b) a definition of the connectivity of the newly developed fuzzy topology; (c) a model of the fuzzy topological relations between simple fuzzy regions in GIS; and (d) the quantitative values of topological relations can be calculated.     

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.     

Boolean matrix operators for computing binary topological relations between complex regions

Complex regions are composed of a finite number of simple regions, and are always defined by hierarchical representation methods. This article focuses on a unified method for computing n-intersection-based binary topological relations between complex regions based on hierarchical characteristics, using known topological relations between simple regions. The hierarchical representation of complex regions is defined as the recursive process of region decomposition using a context-free grammar. To distinguish multiple components of a region and whether the interior of a hole is a part of the inner exterior or the outer exterior, three region operators are proposed to describe the configuration of a region represented as a formal expression. Then, three corresponding 25-intersection (25I) based Boolean matrix operators are proposed to compute topological relations based on the relationships between decomposed regions. Herein, the invalid conditions of the operators are verified in detail, and the invalidities can be eliminated by either applying our definition of complex regions or with the inclusion of additional information. The proposed 25I-based operators, as shown in our cases, can be used as a ‘bridge’ to link different n-intersection models, and as a useful computation tool for analyzing topological relations between regions with specific configurations.     

Algebraic approach to spatial reasoning

Abstract

A simple, exemplary system is described that performs reasoning about the spatial relationships between members of a set of spatial objects. The main problem of interest is to make sound and complete inferences about the set of all spatial relationships that hold between the objects, given prior information about a subset of the relationships. The spatial inferences are formalized within the framework of relation algebra and procedurally implemented in terms of constraint satisfaction procedures. Although the approach is general, the particular example employs a new ‘complete’ set of topological relationships that have been published elsewhere. In particular, a relation algebra for these topological relations is developed and a computational implementation of this algebra is described. Systems with such reasoning capabilities have many applications in geographical analysis and could be usefully incorporated into geographical information systems and related systems.     

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

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

A Coal Burst Risk Assessment Model of Seismic Events Based on Multiple Seismic Source Parameters: A Case Study of the Huating Coal Mine,Gansu Province,China

Mining-induced tremors are indispensable events that gestate and trigger coal bursts. The radiated energy is usually considered a key index to assess coal burst risk of seismic events. This paper presents a model to assess coal burst risk of seismic events based on multiple seismic source parameters. By considering the distribution and relation laws of the seismic source parameters of coal bursts, the model aims to identify dangerous seismic events that more closely match the characteristics of multiple seismic source parameters of coal bursts. The new coal burst risk index T is proposed. It consists of the similarity index SI (representing the similarity degree of relations between seismic events and coal burst events based on seismic source parameters) and the strength index ST (representing the burst strength of seismic events). We studied 79 coal burst events that occurred during extraction in LW250105 of the Huating coal mine in Gansu Province, China. We obtained the distribution and relation laws of multiple seismic source parameters of coal burst events to establish SI and ST. Two groups of seismic events with different energy distributions were examined to compare the assessment results based on the new model and energy criteria. The results show that 80% and 89% of seismic events with strong coal burst risk in Groups A and B, respectively, were coincident, and the seismic events with medium coal burst risk were slightly less compared to those based on radiated energy. The results indicate that the assessment based on the T value is a modification and optimization of that based on radiated energy. This model is conducive to improving the efficiency of monitoring and early warning of coal burst risk.

     

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.     

Efficient methods for Isoline extraction from a TIN

Abstract

A data structure is presented to store a triangulated irregular network digital elevation model, from which isolines (contour lines) can be extracted very efficiently. If the network is based on n points, then for any elevation, the isolines can be obtained in O (logn + k) query time, where k is the number of line segments that form the isolines. This compares favourably with O(n) time by straightforward computation. When a structured representation of the isolines is needed, the same query time applies. For a fully topological representation (with adjacency), the query requires additional O(c log c) or O(c log logo) time, where c is the number of connected components of isolines. In all three cases, the required data structure has only linear size.     

A Review of “The Experience of Return Migration: Caribbean Perspectives”

Abstract

Commuting in Italy has always been addressed without regard to gender differences. Following the issuance of a comprehensive database by the National Statistical Institute, it is now possible to analyze gender differences in personal mobility for the first time in Italy. For our analyses we used Local Labor Systems (LLS) zoning in lieu of administrative zoning. LLSs are territorial subdivisions based on the principle of a self-contained labor market and are widely used in Italy. This article also reports the results of a multidimensional data analysis aimed at highlighting relations between different gender-based commuting patterns and a set of variables (education level, age, household structure, occupational category, and position, etc.). The analysis points out gender differences in the relationship among commuting and socioeconomic characteristics, reveals that these relationships are in turn related to the economic structure and geographical context of different regional labor markets, and suggests to analysts that they be sensitive to singular context when interpreting the meaning of gender differences in commuting.

     

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.     

Finding community structure in spatially constrained complex networks

One feature discovered in the study of complex networks is community structure, in which vertices are gathered into several groups where more edges exist within groups than between groups. Many approaches have been developed for identifying communities; these approaches essentially segment networks based on topological structure or the attribute similarity of vertices, while few approaches consider the spatial character of the networks. Many complex networks are spatially constrained such that the vertices and edges are embedded in space. In geographical space, nearer objects are more related than distant objects. Thus, the relations among vertices are defined not only by the links connecting them but also by the distance between them. In this article, we propose a geo-distance-based method of detecting communities in spatially constrained networks to identify communities that are both highly topologically connected and spatially clustered. The algorithm is based on the fast modularity maximisation (CNM) algorithm. First, we modify the modularity to geo-modularity Q^geo by introducing an edge weight that is the inverse of the geographic distance to the power of n. Then, we propose the concept of a spatial clustering coefficient as a measure of clustering of the network to determine the power value n of the distance. The algorithm is tested with China air transport network and BrightKite social network data-sets. The segmentation of the China air transport network is similar to the seven economic regions of China. The segmentation of the BrightKite social network shows the regionality of social groups and identifies the dynamic social groups that reflect users’ location changes. The algorithm is useful in exploring the interaction and clustering properties of geographical phenomena and providing timely location-based services for a group of people.     

An event-based spatiotemporal data model (ESTDM) for temporal analysis of geographical data

Abstract

Representations historically used within GIS assume a world that exists only in the present. Information contained within a spatial database may be added-to or modified over time, but a sense of change or dynamics through time is not maintained. This limitation of current GIS capabilities has recently received substantial attention, given the increasingly urgent need to better understand geographical processes and the cause-and-effect interrelationships between human activities and the environment. Models proposed so-far for the representation of spatiotemporal data are extensions of traditional raster and vector representations that can be seen as location- or feature-based, respectively, and are therefore best organized for performing either location-based or feature-based queries. Neither form is as well-suited for analysing overall temporal relationships of events and patterns of events throughout a geographical area as a temporally-based representation.

In the current paper, a new spatio-temporal data model is proposed that is based on time as its organizational basis, and is thereby intended to facilitate analysis of temporal relationships and patterns of change through time. This model is named the Event-based Spatio Temporal Data Model (ESTDM). It is shown that temporally-based queries relating to locations can be implemented in an efficient and conceptually straightforward manner using ESTDM by describing algorithms for three fundamental temporally-based retrieval tasks based on this model: (1) retrieving location(s) that changed to a given value at a given time, (2) retrieving location(s) that changed to a given value over a given temporal interval, and (3) calculation of the total area that has changed to a given value over a given temporal interval. An empirical comparison of the space efficiency of ESTDM and compressed and uncompressed forms of the ‘snapshot’ model is also given, showing that ESTDM is also a compact representation of spatio-temporal information.     

A Trapezoidal Three-Dimensional Model for Gas Extraction Based on Shapes of Caved Overlying Strata and Numerical Calculation

Gas emission from the working face in a gas-bearing coal seam impairs safe production. Especially in the coal face, influenced by mining, pressure-relief gas in adjacent seams flows into the working face through the goaf. Moreover, caved overlying strata in different regions show differences in pore and seepage characteristics. Thus, the caving of overlying strata in the goaf of a working face was explored by carrying out physical similarity simulation. Then, based on the characteristics of the geometric shapes of caved overlying strata after mining, a trapezoidal three-dimensional model for gas extraction was established. According to the calculation result, the parameters of field high-level boreholes were optimized. Then, the controllability of gas concentration at the working face after gas extraction was assessed by applying statistical process control. The result showed that after the observed surface of the physical similarity model was lightened, it was more favorable for conducting the test. Moreover, the maximum gas concentration in the goaf was negatively correlated with the diameter of high-level boreholes and the negative pressure for gas extraction. A statistical process control chart revealed that the gas concentrations at the working face were safe after gas extraction based on high-level boreholes, which also validated the feasibility and effectiveness of the model.

     

A complete classification of spatial relations using the Voronoi-based nine-intersection model

In this article we show that the Voronoi-based nine-intersection (V9I) model proposed by Chen et al. (2001, A Voronoi-based 9-intersection model for spatial relations. International Journal of Geographical Information Science, 15 (3), 201–220) is more expressive than what has been believed before. Given any two spatial entities A and B, the V9I relation between A and B is represented as a 3 × 3 Boolean matrix. For each pair of types of spatial entities that is, points, lines, and regions, we first show that most Boolean matrices do not represent a V9I relation by using topological constraints and the definition of Voronoi regions. Then, we provide illustrations for all the remaining matrices. This guarantees that our method is sound and complete. In particular, we show that there are 18 V9I relations between two areas with connected interior, while there are only nine four-intersection relations. Our investigations also show that, unlike many other spatial relation models, V9I relations are context or shape sensitive. That is, the existence of other entities or the shape of the entities may affect the validity of certain relations.     

Geographic information systems and the BBC's Domesday interactive videodisk

Abstract

The Domesday Project is an ambitious attempt by BBC Enterprises Ltd to present a contemporary snapshot of the United Kingdom in the 1980s on interactive video disk. Two disks are being produced: the first, the local or community disk, consists essentially of information collected by the British people. The second, the national disk, has (amongst other material) a selection of data from both government and quasi-government sources. In total, the disks will hold about 250 Mb vies of digital data. ;is well as some 50000 photographs and around 20 million words of text. The paper introduces the idea of interactive video and the local disk. It then concentrates on methods of access to, and cartographic display of, data on the national disk. We conclude that it is a significant geographical information system which will ultimately form one of the most widely-used data base systems for the foreseeable future.     

栅格空间中三维地学实体拓扑关系表达的K6N9-I模型

论述栅格空间中三维地学实体拓扑空间关系研究的理论基础和现实意义,基于数字拓扑理论定义了栅格实体的6邻域内部I6、6邻域边界B6和k阶6邻域E6k,并以此分别替换9-I模型中实体的内部I、边界B和外部E,形成一种适用于栅格空间三维实体拓扑关系描述和分析的新9-I模型,即k阶6邻9-I模型(K6N9-I)。以基于规则六面体表达的地学实体为研究对象,通过扩展关系数据库SQL形成空间关系查询语言,实现了栅格空间中三维地学实体拓扑关系的定性表示和定量计算。以若干地学实体为例进行了初步实验,表明该模型实用方便,且在复杂地学实体的度量、方位等空间关系研究方面亦有较好的应用前景。     

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

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