一种基于拓扑信息的多边形数据自动生成算法

在GIS的众多应用中,多边形数据的自动生成和多边形数据拓扑关系的构建与维护都是一种高频率的操作。该文在分析和总结已有多边形数据自动生成算法和拓扑关系生成算法基础上,提出了一种基于拓扑信息的多边形数据自动生成算法(PG-TI)。介绍了该算法的数据结构以及弧段邻接关系确定、多边形搜索和拓扑关系确定3个核心过程,重点探讨了使用多边形搜索过程中建立的拓扑信息来提升拓扑关系确定过程性能,在此基础上与传统算法和ArcGIS中对应算法的时间复杂度进行了对比分析和验证。     

基于GDF的道路网完全拓扑生成算法

拓扑关系生成是导航空间数据库构建的一个关键环节。该文根据IS0GDF4．0的要求和道路网拓扑关系的特点，研究了一种道路网完全拓扑关系的生成算法，即根据点的几何坐标生成结点—边拓扑关系的算法，以及从标识点出发利用Qj算子生成部分非传统面拓扑关系的算法。实验表明，此算法的时间效率较高，特别是部分面拓扑关系的定义及生成算法能满足实际导航应用的需要。     

一种面向大规模空间数据的拓扑关系检查算法

空间数据拓扑关系检查是GIS应用中空间关系分析及网络分析的重要基础。该文主要面向通用性GIS平台软件中的矢量数据拓扑关系检查,提出一种面向大规模空间数据的拓扑关系检查算法,介绍了算法设计思路、核心数据结构、处理流程等内容,并针对使用较为频繁的"线内无重叠"、"线内无悬线"、"面内无缝隙"3个拓扑关系检查规则进行了算法的详细阐述。最后,对这3个拓扑关系检查算法进行了对比验证和分析。实验表明,该算法在保证拓扑关系检查结果正确性的基础上,具有较高的检查性能,适宜于大规模空间数据的拓扑关系检查。     

基于GDF的道路网完全拓扑生成算法

拓扑关系生成是导航空间数据库构建的一个关键环节。该文根据ISOGDF4.0的要求和道路网拓扑关系的特点,研究了一种道路网完全拓扑关系的生成算法,即根据点的几何坐标生成结点—边拓扑关系的算法,以及从标识点出发利用Qi算子生成部分非传统面拓扑关系的算法。实验表明,此算法的时间效率较高,特别是部分面拓扑关系的定义及生成算法能满足实际导航应用的需要。     

时空拓扑关系描述及其推理研究

空间目标处于一定的时间与空间中,时态拓扑关系和空间拓扑关系经常交织在一起,形成时空拓扑关系,因此有必要在统一框架下研究时空拓扑关系.基于Allen对时态拓扑关系和Egenhofer对空间拓扑关系的研究,对时态拓扑关系和空间拓扑关系分别采用3×3的矩阵进行描述,将时空拓扑关系表示为3×6的矩阵,并描述了简单面/面之间的104种时空拓扑关系.在研究时态拓扑关系推理和空间拓扑关系推理的基础上,提出了一种时空拓扑关系推理方法.该文提出的时空拓扑关系描述和推理方法对于拓展时空拓扑关系的研究具有重要意义.     

基于Hash函数的TIN拓扑关系重建

STL模型是CAD、景观造型器等图形处理软件中常用的三角形网络文件格式,该文件由于不带有三角形的拓扑关系,使其不便与GIS中的地形模型(如TIN)进行叠置分析等操作。提出一种基于Hash函数的STL模型的三角形拓扑重建算法,讨论Hash函数设计和评价,给出基于Hash函数的TIN拓扑重建算法和拓扑检查方法,并通过实例对该算法进行验证。     

面向矢量数据叠加分析的拓扑一致性处理研究

在叠加分析、缓冲区分析、拓扑分析等各种矢量数据分析过程中,首要面对的便是矢量数据拓扑一致性问题。拓扑一致性处理是对GIS矢量数据中由于采集、存储、压缩、转换导致的空间拓扑关系不一致问题进行的拓扑处理,其使得待处理数据在容限范围内具有拓扑一致性,从而便于后续相关分析功能的进行。该文在分析和总结已有拓扑一致性处理算法的基础上,提出了一种更为高效的拓扑一致性处理改进算法,包括弧段间拓扑处理、节点与弧段间拓扑处理、节点间邻近搜索等核心过程。对比实验表明,该算法在保证拓扑一致性处理效果的基础上具有较高的处理性能,是一种实用性较强的拓扑一致性处理算法。     

数字拓扑研究现状及其在GIS中的应用

数字拓扑主要研究栅格空间中离散几何对象的拓扑性质,这些性质在GIS空间分析和栅格数据处理中非常重要。该文从图论、混合拓扑和公理型3方面对数字拓扑的研究现状进行了分类和综述,并讨论数字拓扑在GIS领域的应用,指出三维数字拓扑和球面数字拓扑是数字拓扑在GIS中的两个发展趋势和研究热点。     

模糊区域拓扑关系模型

拓扑关系是地理信息系统中空间要素之间最基本也是最重要的关系之一，是进行绝大多数空间查询和分析的基础。非模糊空间要素之间的拓扑关系在一般拓扑学等理论的基础上已有相关的模型和描述，并在实践中得到广泛的应用，如何建立模糊空间要素这间的拓扑关系是建立模糊要素地理信息系统的基础。该文在模糊扑扑学的基础上提出了模糊区域的定义，建立了用于分析模糊区域之间拓扑关系的理论和模型，提出了4*4-intersection模型拓扑关系矩阵，并分析了不同拓扑关系矩阵对于非模糊区域之间、模糊区域之间建立拓扑关系的区别和联系，最后采和不同公式对模糊区域之间的关系进行了系统的描述。     

复杂体目标之间三维拓扑关系描述模型

三维空间拓扑关系是空间关系研究领域的重要问题。该文分析了三维空间拓扑关系的研究进展和存在的问题,以点集拓扑理论为基础,提出用于描述复杂体目标之间三维拓扑关系的点邻域模型,以15种点邻域结构涵盖三维空间中两个体目标之间任意一点的归属关系,基于点邻域结构设计了描述体目标之间三维拓扑关系的编码。典型三维拓扑关系实例的比较分析表明,对于9IM模型所能区分的三维拓扑关系,点邻域模型均可区分;对于一些复杂的9IM模型无法区分的三维拓扑关系,点邻域模型仍然给出了唯一的描述结果。因此,点邻域模型区分出的复杂体目标之间拓扑关系的种类更多,对三维拓扑关系的描述更加精确。     

基于MapX的最优路径分析

现有基于MapX的最优路径分析,对于TAB格式数据拓扑信息的提取方法单一,且未考虑导航特征。该文结合道路导航特点,提出了一套基于MapX的最优路径分析解决方案。首先由TAB格式数据提取拓扑信息,为最优路径分析奠定数据基础;然后针对导航的特征,即最优路径分析的起点和终点可能出现在道路网外,着重讨论了对于Dijkstra算法的拓展。     

基于格网索引的GIS矢量数据拓扑重建研究

GIS中对原始矢量数据进行拓扑分析和重建是对其进行存储和使用的前提。引入包括规则格网和四叉树格网在内的索引结构,将全局的矢量拓扑分析转化为单个格网范围内足够少的矢量线段求交过程,减少了运算的复杂度;并用一种重组算法实现将原始矢量数据转化为符合“逢交必断”标准的矢量数据。试验表明,该算法适合海量和高散乱度的矢量数据。     

Street‐based topological representations and analyses for predicting traffic flow in GIS

It is well received in the space syntax community that traffic flow is significantly correlated to a morphological property of streets, which are represented by axial lines, forming a so called axial map. The correlation co‐efficient (R ²) approaches 0.8 and even a higher value according to the space syntax literature. In this paper, we study the same issue using the Hong Kong street network and the Hong Kong Annual Average Daily Traffic datasets, and find surprisingly that street‐based topological representations (or street–street topologies) tend to be better representations than the axial map. In other words, vehicle flow is correlated to a morphological property of streets better than that of axial lines. Based on the finding, we suggest the street‐based topological representations as an alternative GIS representation, and the topological analyses as a new analytical means for geographic knowledge discovery.     

基于空间推理的巷道三维拓扑建立

基于空间关系和空间推理理论,结合MGIS领域的需求建立巷道三维拓扑网络模型,研究巷道三维空间关系推理的算法及业务逻辑实现;开发巷道三维拓扑自动生成系统,实现了巷道空间与属性数据管理、三维拓扑自动处理、多尺度成果输出及基于三维拓扑的路径查询,为基于巷道的通风、运输、避灾、多尺度变换等应用奠定了基础。     

SPLITAREA: an algorithm for weighted splitting of faces in the context of a planar partition

Geographic data themes modelled as planar partitions are found in many GIS applications (e.g. topographic data, land cover, zoning plans, etc.). When generalizing this kind of 2D map, this specific nature has to be respected and generalization operations should be carefully designed. This paper presents a design and implementation of an algorithm to perform a split operation of faces (polygonal areas).

The result of the split operation has to fit in with the topological data structure supporting variable-scale data. The algorithm, termed SPLITAREA, obtains the skeleton of a face using a constrained Delaunay triangulation. The new split operator is especially relevant in urban areas with many infrastructural objects such as roads. The contribution of this work is twofold: (1) the quality of the split operation is formally assessed by comparing the results on actual test data sets with a goal/metric we defined beforehand for the ‘balanced’ split and (2) the algorithm allows a weighted split, where different neighbours have different weights due to different compatibility. With the weighted split, the special case of unmovable boundaries is also explicitly addressed.

The developed split algorithm can also be used outside the generalization context in other settings. For example, to make two cross-border data sets fit, the algorithm could be applied to allow splitting of slivers.     

Curvedness feature constrained map matching for low-frequency probe vehicle data

Map matching method is a fundamental preprocessing technique for massive probe vehicle data. Various transportation applications need map matching methods to provide highly accurate and stable results. However, most current map matching approaches employ elementary geometric or topological measures, which may not be sufficient to encode the characteristic of realistic driving paths, leading to inefficiency and inaccuracy, especially in complex road networks. To address these issues, this article presents a novel map matching method, based on the measure of curvedness of Global Positioning System (GPS) trajectories. The curvature integral, which measures the curvedness feature of GPS trajectories, is considered to be one of the major matching characteristics that constrain pairwise matching between the two adjacent GPS track points. In this article, we propose the definition of the curvature integral in the context of map matching, and develop a novel accurate map matching algorithm based on the curvedness feature. Using real-world probe vehicles data, we show that the curvedness feature (CURF) constrained map matching method outperforms two classical methods for accuracy and stability under complicated road environments.     

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.     

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.     

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.