空间对象拓扑关系的研究进展综述

拓扑关系作为最基本的空间关系,一直是国内外学者研究的重点。本文对当前空间对象间拓扑关系的研究进展进行了综述,重点介绍了几种适用于表达带洞空间对象间拓扑关系的模型,如:TPCR模型、9~+_交模型、带洞体拓扑关系模型,分析了它们的表达能力、优点和缺陷,以期为后续的研究提供参考。     

空间对象及其拓扑关系

论文首先讨论了传统的地理信息系统中空间对象的空间数据模型,提出了面向对象的层次矢量数据模型。然后定性地分析了空间对象点与点、点与线和点与区域之间的拓扑关系,并给出了一种形式化表达空间对象成分拓扑关系的模型。最后,将这种模型与空间对象之间的拓扑关系结合起来,使其可以方便地处理地理信息系统中的对象间的拓扑关系。     

三维空间对象拓扑关系的研究

在数字地球、数字城市、地理信息系统等涉及地理数据等许多应用中,三维空间对象的拓扑关系的研究是一个十分重要的问题;弄清三维空间对象的拓扑关系,对于三维空间对象的操作以及操作的算法研究至关重要。由于三维空间对象的复杂性,它们之间拓扑关系的判定大多只是从简单的概念来进行判断,还没有从理论上全面地给定它的判定准则。该文试图在三维空间中,详细地研究空间对象之间拓扑关系成立的条件与结论,利用这些规则,可以全面地得到三维空间对象之间可能存在的所有拓扑关系。     

地理信息系统中空间对象间拓扑关系的推理

首先讨论了地理信息系统中空间对象的空间数据模型,然后定性地分析了空间对象点与点、点与线和点与区域之间的拓扑关系,并给出了空间对象拓扑关系的推理算法.最后,将模糊技术与空间对象之间的拓扑关系的推理算法结合起来,使其可以方便地处理地理信息系统中的模糊性和不确定性.     

基于图形整体拓扑结构的地图线对象矢量化

地图自动矢量化是地理信息系统（GIS）发展的迫切需要。本文从图形整体拓扑特征出发,引入节点域的概念,并介绍了一种二值化扫描地图图像中线对象的整体矢量化方法。     

移动点对象与参考地物空间拓扑关系

针对二维欧氏空间内的平面移动点对象,该文基于“9交模型”,定义了参考地物的空间拓扑关系模型,并将该模型表示为3个连续观测时刻的拓扑关系的三元组,给出了移动点对象与参考点、线和面地物的空间拓扑关系的定性表达。该模型可以清楚地刻画移动点对象相对于参考地物的运动变化情况,对于智能交通、移动位置服务等应用具有重要的意义。     

线对象邻接关系快速重构算法

给定向量化坐标,计算n个线对象两两邻接关系,普通算法时间复杂度为O(n*n);理论最好时间复杂度为O(C),其中C是邻接关系的基数。基于散列桶,给出了建立线对象邻接关系的快速算法,其平均时间复杂度为O(n(1+1/r)),r为算法分配的桶数量与n的比,空间复杂度为O(n)。证明了若不允许使用额外空间,则不可能使用排序算法解决该问题;给出了允许使用额外空间条件下的两遍排序算法,时间复杂度为O(n(lbn+1+2/r))。应用表明快速算法比普通算法速度提高1~3个数量级。     

利用简化9交模型进行三维拓扑分析

针对点、线、面和体等简单空间对象提出新的否定规则，对9交模型进行了简化．利用简化后的9交模型，仅需分析4组相交关系即可得出实际拓扑关系．在此基础上构建了拓扑关系推导表，可进一步分析复合空间对象之间的拓扑关系，并以线与体之间拓扑关系为例讨论了算法实现．与已有的算法相比，该算法能分析更为复杂的空间对象之间的拓扑关系．     

二维空间对象空间关系的定性表示

主要研究了二维空间中空间对象间关系的定性表示。介绍了基于RCC的拓扑关系定性表示,讨论了方向关系的定性表示,给出了一个将拓扑关系定性表示和方向关系定性表示相结合的定性表示模型——SR表示模型。     

跟踪对象族模型拓扑结构变化研究

提出了跟踪对象族模型拓扑变化的新算法,以建立参数和拓扑结构之间的关系,计算参数的临界值,确定模型的依赖实体,计算出模型参数的稳定区间和参数区间,最终系统准确地跟踪对象族模型拓扑结构的变化。该算法运用于自主研发的HUST-CAID系统中,提高了系统的智能性,为设计者确定参数范围提供了依据。     

Multi-level Topological Relations Between Spatial Regions Based Upon Topological Invariants

Topological relations have played important roles in spatial query, analysis and reasoning. In a two-dimensional space (IR²), most existing topological models can distinguish the eight basic topological relations between two spatial regions. Due to the arbitrariness and complexity of topological relations between spatial regions, it is difficult for these models to describe the order property of transformations among the topological relations, which is important for detailed analysis of spatial relations. In order to overcome the insufficiency in existing models, a multi-level modeling approach is employed to describe all the necessary details of region–region relations based upon topological invariants. In this approach, a set of hierarchically topological invariants is defined based upon the boundary–boundary intersection set (BBIS) of two involved regions. These topological invariants are classified into three levels based upon spatial set concept proposed, which include content, dimension and separation number at the set level, the element type at the element level, and the sequence at the integrated level. Corresponding to these hierarchical invariants, multi-level formal models of topological relations between spatial regions are built. A practical example is provided to illustrate the use of the approach presented in this paper.

面目标间拓扑关系的形式化描述

为了更有效地描述和区分空间面目标间的拓扑关系,本文在4交差模型的基础上,结合两面目标交集的维数和边界交集的分离数,建立相应的面目标间的拓扑关系形式化描述模型。该模型可以进一步区分4交差模型无法区分的相接、交叠、覆盖于和覆盖的拓扑关系。     

空间目标的拓扑关系及其GIS应用分析

拓扑关系是GIS中空间目标之间最基本也是最重要的关系之一，在空间数据建模、空间查询、分析、推理、制图综合、图像检索和相似性分析等过程中起着重要的作用。在综合研究空间关系文献基础上，从方法论的角度论述了精确和不精确空间目标间拓扑关系的描述方法及其最新进展，并简要分析了拓扑关系在GIS空间查询、推理和分析中的应用。     

Efficient Implementation Techniques for Topological Predicates on Complex Spatial Objects

Topological relationships like overlap, inside, meet, and disjoint uniquely characterize the relative position between objects in space. For a long time, they have been a focus of interdisciplinary research as in artificial intelligence, cognitive science, linguistics, robotics, and spatial reasoning. Especially as predicates, they support the design of suitable query languages for spatial data retrieval and analysis in spatial database systems and geographical information systems. While, to a large extent, conceptual aspects of topological predicates (like their definition and reasoning with them) as well as strategies for avoiding unnecessary or repetitive predicate executions (like predicate migration and spatial index structures) have been emphasized, the development of robust and efficient implementation techniques for them has been largely neglected. Especially the recent design of topological predicates for all combinations of complex spatial data types has resulted in a large increase of their numbers and stressed the importance of their efficient implementation. The goal of this article is to develop correct and efficient implementation techniques of topological predicates for all combinations of complex spatial data types including two-dimensional point, line, and region objects, as they have been specified by different authors and in different commercial and public domain software packages. Our solution consists of two phases. In the exploration phase, for a given scene of two spatial objects, all topological events like intersection and meeting situations are summarized in two precisely defined topological feature vectors (one for each argument object of a topological predicate) whose specifications are characteristic and unique for each combination of spatial data types. These vectors serve as input for the evaluation phase which analyzes the topological events and determines the Boolean result of a topological predicate (predicate verification) or the kind of topological predicate (predicate determination) by a formally defined method called nine-intersection matrix characterization. Besides this general evaluation method, the article presents an optimized method for predicate verification, called matrix thinning, and an optimized method for predicate determination, called minimum cost decision tree. The methods presented in this article are applicable to all known complete collections of mutually exclusive topological predicates that are formally based on the well known nine-intersection model.

论“创意”与“设计”的拓扑关系

本文通过对创意和设计概念上的剖析,讨论了它们的拓扑关系并归纳出二者的相同点,强调了它们在经济建设中的重要作用,从而建立对二者更理性、更系统的认识。     

拓扑关系形式化描述的基本问题与研究进展

拓扑关系是GIS中空间目标之间最基本也是最重要的关系之一,在GIS空间数据建模、空间查询、空间分析、空间推理、制图综合等过程中起着重要的作用。该文首先介绍了不同的空间数据模型中拓扑信息的表达模式,然后重点回顾和评述了拓扑关系的建模方法以及拓扑关系形式化模型,并探讨了目前研究中存在的问题和有待进一步研究的工作。     

GIS中由单种细节方向关系推理拓扑关系的方法

介绍了一种用细节方向关系来处理与参照对象内部有关方向的方法,以弥补外部方向关系的不足;提出了描述两个方向关系之间的关系的九交模型,并得到了19条根据细节方向关系推理拓扑关系的规则,通过这些规则即可得到未知的拓扑关系,而不需要任何几何计算．由于规则推理比几何计算速度快、内存消耗小,因此推理能够提高基于空间关系的空间数据查询的速度和效率。