Change detection for 3D vector data: a CGA-based Delaunay–TIN intersection approach

In this paper, conformal geometric algebra (CGA) is introduced to construct a Delaunay–Triangulated Irregular Network (DTIN) intersection for change detection with 3D vector data. A multivector-based representation model is first constructed to unify the representation and organization of the multidimensional objects of DTIN. The intersection relations between DTINs are obtained using the meet operator with a sphere-tree index. The change of area/volume between objects at different times can then be extracted by topological reconstruction. This method has been tested with the Antarctica ice change simulation data. The characteristics and efficiency of our method are compared with those of the Möller method as well as those from the Guigue–Devillers method. The comparison shows that this new method produces five times less redundant segments for DTIN intersection. The computational complexity of the new method is comparable to Möller’s and that of Guigue–Devillers methods. In addition, our method can be easily implemented in a parallel computation environment as shown in our case study. The new method not only realizes the unified expression of multidimensional objects with DTIN but also achieves the unification of geometry and topology in change detection. Our method can also serve as an effective candidate method for universal vector data change detection.     

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.     

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.     

A scale-explicit model for checking directional consistency in multi-resolution spatial data

Multi-resolution spatial data always contain the inconsistencies of topological, directional, and metric relations due to measurement methods, data acquisition approaches, and map generalization algorithms. Therefore, checking these inconsistencies is critical for maintaining the integrity of multi-resolution or multi-source spatial data. To date, research has focused on the topological consistency, while the directional consistency at different resolutions has been largely overlooked. In this study we developed computation methods to derive the direction relations between coarse spatial objects from the relations between detailed objects. Then, the consistency of direction relations at different resolutions can be evaluated by checking whether the derived relations are compatible with the relations computed from the coarse objects in multi-resolution spatial data. The methods in this study modeled explicitly the scale effects of direction relations induced by the map generalization operator – merging, thus they are efficient for evaluating consistency. The directional consistency is an essential complement to topological and object-based consistencies.     

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.     

Modelling conceptual neighbourhoods of topological line-region relations

Abstract

Based on the 9-intersection for binary topological relations, two models of conceptual neighbourhoods among topological relations between a line and a region are developed. The snapshot model derives the neighbourhoods by comparing pairs of topological relations and selects neighbours based on least noticeable differences, whereas the smooth-transition model develops neighbourhoods based on the knowledge of the deformations that may change a topological relation. The resulting similarity diagrams show some differences, which were compared with the results from tests in which human subjects were asked to organized line-region relations into groups of similar relations. The groupings the subjects made indicate that the smooth-transition model captures more important aspects of the similarity of topological line-region relations than the snapshot model.     

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.     

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.     

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.     

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.     

Using geolifespans to model dynamic geographic domains

Geographic objects are characterized by having different durations of existence, or geolifespans. A typology based on the concept of a geolifespan is developed to model variations in the longevity of entities that are stored in geographic information systems. The typology consists of two upper-level classes: Persistent and Ephemeral. The Ephemeral class is composed of three subclasses: Temporary, Transient and Brief. The set of possible transitions between classes in the typology is described, capturing how objects can change from one class to another, e.g., from Temporary to Brief or from Transient to Persistent. A transition sequence models the geolifespan class(es) to which an object belongs over a period of time and captures the evolution of dynamic geographic objects with respect to their longevity. Geolifespan classes are applied to scenarios of spatial change as well as a geosensor network to illustrate their role in modelling geographic dynamics.     

Spatiotemporal data model for network time geographic analysis in the era of big data

There has been a resurgence of interest in time geography studies due to emerging spatiotemporal big data in urban environments. However, the rapid increase in the volume, diversity, and intensity of spatiotemporal data poses a significant challenge with respect to the representation and computation of time geographic entities and relations in road networks. To address this challenge, a spatiotemporal data model is proposed in this article. The proposed spatiotemporal data model is based on a compressed linear reference (CLR) technique to transform network time geographic entities in three-dimensional (3D) (x, y, t) space to two-dimensional (2D) CLR space. Using the proposed spatiotemporal data model, network time geographic entities can be stored and managed in classical spatial databases. Efficient spatial operations and index structures can be directly utilized to implement spatiotemporal operations and queries for network time geographic entities in CLR space. To validate the proposed spatiotemporal data model, a prototype system is developed using existing 2D GIS techniques. A case study is performed using large-scale datasets of space-time paths and prisms. The case study indicates that the proposed spatiotemporal data model is effective and efficient for storing, managing, and querying large-scale datasets of network time geographic entities.     

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.     

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.     

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.     

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.     

简单要素模型下多边形叠置分析算法

现有的矢量空间叠置分析多采用拓扑模型,要求建立完整的数据拓扑关系。该文采用简单要素模型,以多边形叠置交运算为例,介绍简单要素模型下空间叠置分析的具体实现,着重讨论多边形交运算的交替搜索算法,在线段求交中对连续出入点、重交点等特殊数据进行处理。在实际应用中,该算法可较好解决大规模复杂数据层的叠置交运算,比同规模的拓扑叠置运算效率高。     

地理空间数据本质特征语义相关度计算模型

关联数据是跨网域整合多源异构地理空间数据的有效方式,语义丰富的关联是准确、快速发现目标数据的关键。根据地理空间数据在空间、时间、内容上的语义关系,提出地理空间数据本质特征语义相关度计算模型。通过构建本质特征的关联指标体系,分层次逐级计算地理空间数据的语义相关度。与传统的语义相关度计算方式不同,以地理元数据为语料库,充分考虑地理空间数据的特点及空间、时间、内容在检索中不同的重要程度,分别采用几何运算、数值运算、词语语义相似度计算和类别层次相关度计算的方式,构建地理空间数据的语义相关度计算模型。该模型具有构建简单、适用于多源异构数据、充分结合了数学运算和专家经验知识等特点。实验表明：模型能够有效地计算地理空间数据本质特征的语义相关度,并具备一定的扩展性。