顾及制图规则的地图多要素协同移位方法

在地图自动编制中,有时多类地图要素多个空间目标之间同时发生空间冲突,在移位过程中会影响到邻近区域的地图目标,这就需要对地图要素移位进行协同处理。在自动识别邻近空间冲突区的条件下,提出了一种顾及地图制图规则的解决地图目标群空间冲突的协同处理方法,并用参数表方法形式化表达了地形图上地图要素移位的常用制图规则。首先利用约束性Delaunay三角网识别出可能的空间冲突区域,并建立移位操作区;然后,建立移位传播关联线网,依据制图规则在关联线网上以能量最小化Beam移位模型为基础,对整个空间冲突区的地图目标群进行协同移位;最后,用实验验证了所提方法的有效性和适用性。     

地图目标群间骨架线提取的算法研究

基于Delaunay三角网提取的骨架线是地图综合中广泛应用的一种空间剖分结构。改进了一种基于约束Delaunay三角网的地图目标群间骨架线提取算法,从程序设计的角度详细描述了算法的数据结构和控制流程。按照三角网中三角形包含约束边的数目,将三角形分为0、1、2、3四类,将0类、2类和单连通的1类三角形视为骨架线追踪的起点或终点,将双连通的1类作为中间通道,对整个三角网进行遍历。针对三角网中的环路、3类三角形等特殊情况,在改进的算法中提出了相应的处理方法。该算法成功地用于等高线的内插和街区地图目标群的邻近分析,验证了算法的可行性和健壮性。     

支持地图综合的面状目标约束Delaunay三角网剖分

针对多边形面状目标的综合问题,建立了二维空间中约束Ｄｅｌａｕｎａｙ三角网剖分结构,融入多边形的环、岛屿、边界、顶点的描述,通过形式化条件检索,在该结构上提取二维空间中各种感兴趣的由剖分三角形组成的区域,用于支持地图综合中邻近多边形的搜索、多边形弯曲部位的识别、冲突关系探测、多边形合并等操作。并对基于骨架线的图结构建立、分枝宽度计算等几何问题进行了详细讨论,指出了其在诸如双线河中轴化、街道中轴线网络模型建立、多边形合并中的邻近关系分析、面状目标注记自动定位领域的支持作用。     

支持地图综合的面状目标约束Delaunay三角网剖分

针对我边形面状目标的综合问题,建立了二维空间中约束Ｄｅｌａｕｎａｙ三角网剖分结构,融入多边形的环、岛屿、边界、顶点的描述,通过形式化条件检索,在该结构上提取二维空间中各种感兴趣的由剖分三角形组成的区域,用于支持地图综合中邻近多边形的搜索、多边形弯曲部位的识别、冲突关系探测、多边形合并等操作。并对其于骨架线的图结构建立、分枝宽度计算等几何问题进行了详细讨论,指出了其在诸如双线河中轴化、街道中轴线网络     

相邻多边形共享边界的一致化改正

针对相邻多边形叠置不能保证精确的拓扑邻近 ,往往产生大量的“碎片”和“缝隙” ,破坏了面状目标间的拓扑一致性这一问题。依据相邻多边形之间的空间关系 ,将共享边界不一致区分为相交型、相离型、交织型 ,将拓扑一致化处理的操作分为咬合式处理和平差式处理 ,并基于Delaunay三角网模型邻近分析 ,探测由三角形集表达的边界不一致局部区域 ,通过三角网骨架线提取来进行边界不一致改正。     

地图水系综合中等高线簇与河网协同的汇水区域提取方法

在地图水系自动综合中河流选取需要建立对不同河流重要性程度的有效判别。由于河流汇水区域直接反映河流的作用空间,因而其面积大小成为关键性的量化指标。目前基于河流的汇水区域自动提取方法主要从河流单一要素出发,按“空间均衡竞争”思想平分河流之间的区域,由于未考虑地形因素使得提取的汇水区域往往存在偏差,而传统基于DEM的汇水区域提取虽然考虑了地形,但没有与河流目标建立显性的对应关系。河流是一种天然的沟谷地性线,与山脊线具有对生互补的空间耦合关系,本文提出了一种等高线簇与河网双要素协同的河流汇水区域提取方法,该方法对河流与等高线的目标集合构建约束Delaunay三角网(CD-TIN)并将三角形分类,对不同类型的三角形分别采用骨架线提取规则与梯度向量引导的分水线搜索规则提取分水线段,连接形成网络结构并依此计算各河段的汇水区域。实验结果表明,本算法能更准确地提取河流汇水区域,从而为河流综合选取提供有效支持。     

相邻多边形共享边界的一致化改正

针对相邻多边形叠置不能保证精确的拓扑邻近,往往产生大量的“碎片”和“缝隙”,破坏了面状目标间的拓扑一致性这一问题。依据相邻多边形之间的空间关系,将共享边界不一致区分为相交型,相离型,交织型,将拓扑一致化处理的操作分为咬合式处理和平差式处理,并基于Ｄｅｌａｕｎａｙ三角网模型邻近分析,探测由三角形集表达的边界不一致局部区域,通过三角网骨架线提取来进行边界不一致改正。     

直线排列建筑物群渐进式典型化方法

地图综合中,建筑物群的排列结构是需要重点考虑的因素。当不同排列的子建筑物群之间存在空间图形冲突时,这些建筑物群的综合就显得更为复杂。直线排列建筑物群的综合在大比例尺地形图上以典型化操作为主。本文提出一种相互之间存在潜在空间图形冲突的多个直线排列建筑物子群的渐进式典型化方法,渐进式地处理多个直线排列建筑物子群之间的空间图形冲突,保留建筑物群重要的直线排列结构;以建筑物表达的视觉图形约束为限制条件,自动确定典型化后的建筑物位置、形状、大小和方位。本文还研究了基于建筑物群空间邻近图的直线排列建筑物子群的自动识别方法,分析了这些直线排列之间的邻近关系和相交关系。最后,以1：5000地图上的建筑物群综合为1：25 000为试验对象,验证了所提出算法的可用性和有效性。     

线图形简化与移位算子的协同方法

在地图综合过程中,线的图形简化和移位算子通常是分别执行的,图形简化和移位有时都会产生新的空间冲突。本文试图把这两种算子进行协同,避免在地图综合过程中进行空间冲突的多次探测,提高地图综合数据处理的效率。本文通过把线图形简化转换为线上的点移位,并构建邻近地图目标之间的移位传播路径,在考虑空间上下文关系和地图感受规则的前提下,使移位过程能考虑到线图形简化,并尽量保持有关地图目标的空间特征。最后,以道路和其周边的建筑物群为例,验证了该算法的有效性和可行性。     

线要素移位的Morphing变换方法

移位是解决地图制图和GIS中空间冲突的基本算子之一。Morphing变换可以实现源对象到目标对象的连续平滑变换,通过从两个方面拓展Morphing变换,从而实现对线要素进行移位。首先分析了线要素空间冲突的类型。在线要素弯曲识别的基础上,以弯曲作为冲突检查和线要素移位的基本单元;然后,用Delaunay三角网探测冲突区域,将冲突位置定义在局部的线要素弯曲(组);最后拓展Morphing变换实施线要素移位,即先对冲突发生弯曲(组)进行镜像变换,再对冲突发生弯曲(组)和它们的镜像进行Morphing变换,并给出了变换参数与移位距离和方向的定量关系。实验证明了该方法有效、可行。引入图形镜像避免了普通Morphing变换中的特征点识别和匹配等两个难点。将弯曲作为冲突发生的范围和化解冲突的操作单元,可以实现要素局部与全局移位的有机统一。     

Building Displacement Based on the Topological Structure

Map data at smaller scales than their source can result in spatial conflict, whereby map symbols become too close, or overlaid. Server map generalisation operators may be applied to solve this problem, including displacement. In this paper, we show how an optimisation algorithm, the snake algorithm, was used to displace multiple objects in order to resolve spatial conflicts and maintain important spatial relationships between objects during displacement. Two principles based on the snake algorithm are proposed in this paper. First, the truss structure mirroring spatial proximity relationships between buildings and between building and road is formed based on the weighted proximity graph derived from constrained Delaunay triangulations (CDT) in each map partition. In the weighted proximity graph, each connecting line is determined as a snake and as an element unit to assemble the global stiffness matrix in snake algorithm. Second, a buffer method that calculates force between a building and a road (or other linear features) or between pair of buildings is adopted in the snake algorithm. This avoids the imbalance phenomenon caused by different force calculation methods during the displacement. The feasibility of the approach is demonstrated in obtaining real geographic data. Finally, the results are cartographically usable and in particular, the spatial relationships between objects are preserved.     

地图综合中目标空间关系维护

在地图综合的过程中,比例尺的变化以及各种综合算子都可能导致目标产生空间关系冲突。以往在对空间关系进行维护时,通常只是对拓扑关系变化进行探测与控制。由于方向关系是人们在日常生活中用途最为广泛的空间关系,研究在地图综合中如何有效维护目标间的方向关系具有重要的科学意义。本文采用定性空间推理的方法,建立考虑目标方向关系的移位安全区,从而可以综合检测与控制拓扑关系与方向关系的冲突及其传播,并就本方法存在的问题和今后的研究方向提出了一些看法和思路。     

道路网增量更新中拓扑冲突的检测方法

为提高空间数据增量更新中拓扑冲突的检测效率,针对道路网数据,首先分析了增量要素进行更新时可能产生的拓扑冲突的类型和特点,运用规则格网进行邻近区域的表达;然后使用5元组模型描述增量要素与邻近区域要素间的拓扑关系,与设定的拓扑冲突表达进行比较,判断是否存在拓扑冲突。实验结果表明,本方法对于道路网数据增量更新中的拓扑冲突的类型区分准确全面,检测效率较高,具有很好的实用性和可靠性。     

Map Generalization with a Triangulated Data Structure

Automation of map generalization requires facilities to monitor the spatial relationships and interactions among multiple map objects. An experimental map generalization system has been developed which addresses this issue by representing spatial objects within a simplicial data structure (SDS) based on constrained Delaunay triangulation of the source data. Geometric generalization operators that have been implemented include object exaggeration, collapse, amalgamation, boundary reduction and displacement. The generalization operators exploit a set of primitive SDS functions to determine topological and proximal relationships, measure map objects, apply transformations, and detect and resolve spatial conflicts. Proximal search functions are used for efficient analysis of the structure and dimensions of the intervening spaces between map objects. Because geometric generalization takes place within a fully triangulated representation of the map surface, the presence of overlap conflicts, resulting from individual operators, can be detected due to the introduction of singularities in the triangulation, the structure of which is used to generate displacement vectors to resolve the conflict. Examples of the application of the implemented operators are described and illustrated using large scale topographic map data.     

地图目标移位的面目标变形约束及其处理(英文)

The displacement operator is an important and still a hot topic in map generalization. In the generalization product, symbols must be unambiguous and easily perceived and readily understood, which makes space competition among features an important obstacle in the process of map objects displacement. Space conflict between objects, through propagation process, may be spread and more objects may drift into it. In order to maintain symbols equilibrium and spatial relationship between objects, some unimportant symbols or parts of symbols should be distorted under constraints according to visual graphic resolution thresholds to figure out space competition among map features. Three constraints including position, legibility and characteristics are important for the maintenance of symbols equilibrium and spatial relationship, which are discussed in this paper. The skeleton is introduced to represent area objects figure characteristic, in which an area object can be separated to parts hierarchically according to their importance in the construction. Then, the finite element method is applied to the map objects’ displacement and distortion, in which a strategy for the parameters of finite element method is discussed. Supported by the National Science Foundation of China (No.40401050), the Leading Academic Discipline Project of Shanghai Educational Committee (No.J50104), the Science Foundation of Shanghai Education Department (07ZZ09).     

Solving Space Conflicts in Map Generalization: Using a Finite Element Method

A finite element method was developed to handle conflicts during the generalization of maps. The method is holistic and solves conflict problems for the entire map surface simultaneously. When a generalized object changes size, the method immediately causes displacements in surrounding objects. Boundary constraints were introduced which make it possible to maintain the shape of objects, and simultaneously change the size of the objects. An iterative solution procedure for the Finite Element problem was shown to give solutions that better fulfill topological requirements than a direct solution of the problem.     

A spatial contextual immune genetic algorithm to building cartographic displacement

In map generalization, displacement is the most frequently used operator to reduce the proximity conflicts caused by reducing scales or other generalization operations. Building displacement can be formalized as a combinatorial optimization problem, and a heuristic or intelligent search algorithm can be borrowed to obtain the solution. In this way, we can explicitly resolve minimum distance conflicts and control positional accuracy during the displacement. However, maintaining spatial relations and patterns of buildings can be challenging. To address spatial conflicts as well as preserve the significant spatial relations and patterns of buildings, we propose a new spatial contextual displacement algorithm based on an immune genetic algorithm. To preserve important spatial relations and global patterns of map objects and avoid topology errors, displacement safety zones are constructed by overlapping the Voronoi tessellation and buffer areas of the buildings. Additionally, a strategy to shift the buildings in a building group synchronously is used to maintain local building patterns. To demonstrate the effectiveness of our algorithm, two data sets with different building densities were tested. The results indicate that the new algorithm has obvious advantages in preventing topology errors and preserving spatial relations and patterns.