基于边扩展法的任意图斑Delaunay三角网与骨架线的同时快速提取

图斑是GIS中矢量面状数据的最小组成单元,图斑骨架线是对图斑总体形状的抽象概括,也描述了图斑的扩展方向,它在地物降维处理、地物剖分等方面有着广泛的应用。本文在传统边扩展算法的基础上,考虑图斑三角网的独有特点,提出任意图斑的Delaunay三角网的生成方法,且在此过程中同步提取出图斑的骨架线;并在GIS环境中建立以上算法的模型,同时给出具体、详细的流程和示例。     

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

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

利用骨架线端点匹配进行面状要素渐变变换

面向空间数据连续地图综合问题,提出了一种基于骨架线端点匹配的面状要素渐变方法,通过在两个关键表达之间进行尺度内插,实时、动态地派生任意中间比例尺地图数据。首先,对面状要素在大小比例尺下的两重表达分别进行约束Delaunay三角网剖分并提取各自的骨架线特征;然后,使用最优子序双射优化技术对骨架端点进行匹配获得多边形边界上相对应的特征点序列;最后,在剖分边界的基础上进行分段常规线性内插,获得面状要素介于始末尺度之间的多尺度表达。实验结果表明,该算法充分顾及了空间数据弯曲结构特征,对于光滑边界面状要素的渐变变换具有良好的渐变效果,可用于空间数据的连续地图综合和多尺度表达。     

顾及居民地分布特征的建筑物分组合并算法研究

建筑物多边形分组合并是城市大比例尺地图综合中的重要问题。本文在建筑物群的约束Delaunay三角网空间剖分模型及目标间"视觉距离"计算模型研究基础上,以广州地区3种具有典型分布特征的建筑物群分组合并操作为研究对象,并基于"分而治之"的思想,分别提出不同处理方法。设计的算子兼顾了适用性和效率,在广州地区序列比例尺空间数据库快速构建中得到了成功应用。     

Delaunay三角网在图斑与点群目标综合中的应用

土地资源调查利用的土地类型数据多为不同比例尺电子矢量地图,以此数据为研究基础,详细介绍了Delaunay三角网及其Voronoi多边形的特性,以及在土地数据类型中的图斑综合与点群目标综合中的算法应用,具体描述了两种算法的实现过程和试验结果,并对几种点群目标算法进行了简要分析和比对,详细介绍了实现过程;重点阐述了图斑综合算法的思想和算法的具体实现。最后以"土地利用数据库智能化自动综合系统"为例验证了算法方案的合理性和可行性。     

Delaunay三角网在图斑与点群目标综合中的应用

土地资源调查利用的土地类型数据多为不同比例尺电子矢量地图,以此数据为研究基础,详细介绍了Delaunay三角网及其Voronoi多边形的特性,以及在土地数据类型中的图斑综合与点群目标综合中的算法应用,具体描述了两种算法的实现过程和试验结果,并对几种点群目标算法进行了简要分析和比对,详细介绍了实现过程;重点阐述了图斑综合算法的思想和算法的具体实现.最后以"土地利用数据库智能化自动综合系统"为例验证了算法方案的合理性和可行性.     

基于边优先的任意多边形最优三角剖分

针对现有多边形三角剖分算法不能同时兼顾算法的简单有效性、适用性以及剖分三角网质量的问题,提出一种基于边优先的任意多边形最优化三角剖分算法:首先直接对多边形的边进行构网,最后再对生成的非约束边进行构网,最终完成整个多边形的三角剖分。剖分得到的三角网为约束Delaunay三角网,网形稳定、最优,算法简单,执行效率较高,且适用于任意复杂多边形。实验证明了该算法的合理性和有效性,较好地解决了现有多边形三角剖分算法存在的问题。     

约束Delaunay三角剖分的“岛屿”类图斑符号填充

针对传统方法对“岛屿”类图斑进行符号填充会造成敏感区域符号布局不合理或符号空间冲突的问题，本文提出了一种约束Delaunay三角剖分的“岛屿”类图斑符号填充方法。首先，对“岛屿”类图斑对应的离散点群进行规则网格化和不规则三角剖分，用于计算等值点；然后，依据附加准则增加“凸”形和“凹”形附加点，顺次连接等值点和附加点作为Delaunay三角剖分的约束边界；最后，构建均匀变化的约束Delaunay三角网，在三角网内进行图元积分，填充“岛屿”类图斑符号。利用电子海图中岛屿边界点数据进行试验分析，与传统方法相比，本文方法填充的“岛屿”类图斑符号变化均匀，交互性较强，便于用户修改和切换，进行二次填充。试验结果表明，本文方法适用于“岛屿”类图斑的符号填充。     

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

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

基于数学形态学的TIN和GRID自动生成研究

在分析了数学形态学的基本原理的基础上,提出了一种基于数学形态变换自动生成Delaunay三角网(TIN)和规则格网(GRID)的数字高程模型的算法,这种算法将离散的地面点的图像集合进行骨架化并自动构成Thiessen多边形,然后,通过序贯条件形态变换,自动建立TIN和GRID.在建立Thiessen多边形的过程中,提出了用逐点生成数字圆盘的方法来保证变换过程的各向同性;在建立Delaunay三角网的过程中,提出了利用正交结构元素进行条件膨胀,从而保证了相邻点之间的正确位置关系.该方法能保持Thiessen多边形和Delaunay三角网的拓扑关系,因而能保证DEM 的高精度,而且具有数据结构简单、运算速度快的特点.最后,给出了试验结果并与有限元法的结果进行了比较.结果表明,这种方法用于建立DEM具有良好的应用前景.     

Proximity-based grouping of buildings in urban blocks: a comparison of four algorithms

Grouping of buildings based on proximity is a pre-processing step of urban pattern (structure) recognition for contextual cartographic generalization. This paper presents a comparison of grouping algorithms for polygonal buildings in urban blocks. Four clustering algorithms, Minimum Spanning Tree (MST), Density-Based Spatial Clustering Application with Noise (DBSCAN), CHAMELEON and Adaptive Spatial Clustering based on Delaunay Triangulation (ASCDT) are reviewed and analysed to detect building groups. The success of the algorithms is evaluated based on group distribution characteristics (i.e. distribution of the buildings in groups) with two methods: S_Dbw and newly proposed Cluster Assessment Circles. A proximity matrix of the nearest distances between the building polygons, and Delaunay triangulation of building vertices are created as an input for the algorithms. A topographic data-set at 1:25,000 scale is used for the experiments. Urban block polygons are created to constrain the clustering processes from topological aspect. Findings of the experiment demonstrate that DBSCAN and ASCDT are superior to CHAMELEON and MST. Among them, MST has exhibited the worst performance for finding meaningful building groups in urban blocks.     

基于蚁群算法的土地利用(图)图斑合并方法

很多地图综合问题可以应用优化算法解决,土地利用(图)图斑合并也可以看作是一个优化问题。本文提出了基于蚁群算法的土地利用(图)图斑合并方法。实验结果表明,基于蚁群算法的图斑合并方法优于普通的迭代方法,该方法使综合后各地类面积变化较小且图斑紧凑性较好,是解决土地利用(图)图斑合并问题的一条可行之路。     

计算几何在地图综合中的应用

地图综合是计算几何中的一个应用问题。计算几何是有效的几何基本规则和算法,为地图目标间的复杂空间关系提供了强大的描述和分析依据。文章讨论地图综合中的条件和要求,尤其提出了比例尺缩小造成地不可感知性,而引起选取、目标拥挤、化简和符号化带来的相交等三个关键问题。根据计算几何的Voronoi、Delaunay等数据结构,简要探讨了目标选择、目标聚类和一致性化简的方法。     

基于约束Delaunay结构的街道中轴线提取及网络模型建立

从街区多边形提街道中轴线并在此基础上建立街道网络模型是城市空间分析及街区地图综合的基础问题,本文基于约束Ｄｅｌａｕｎａｙ三角网结构提出了在邻近街区边界之间的三角形元上提取中轴线从而建立街道网络图模型的方法,区分三种不同三角形元进行中轴线的连接,通过网络图的顶点、边完备地表达出街道、街区、街道交叉口之间的空间关系,并建立了街道中轴线与左右两侧街区多边形边界弧段间的匹配,从而使本文提出的混合数据模型将街道网络结构与街区多边形结构统一起来。     

A method for the extraction of partition lines from long and narrow patches that account for structural features

The extraction of partition lines for long and narrow patches (LN patches) is an important yet difficult problem in the generalization of thematic data. When current methods are used to process polygons with irregular shapes or complex branch convergence zones, the extracted line structural features tend to be inaccurate and topologically erroneous. In this article, we propose an improved partition lines extraction algorithm of constrained Delaunay triangulation to counter these issues. The proposed method aims to maintain consistency between the extracted line structure characteristics and the actual object structure, especially for complex branch convergence zones. First, we describe three types of aggregation patterns (Type A, B, and C aggregation zones) that occur in partition line extractions for LN patches of complex branch convergence zones using Delaunay triangulation. Then, a partition line extraction algorithm that accounts for the direction between the edges of triangles and the distance of nodes in aggregation zones is proposed. Finally, we test our method for a dataset relating to Guizhou Province, China. Compared with the current method that uses quantitative indicators and visualization, the results indicate that our method not only has applicability for simple situations but also is superior for preserving structural features of complex branch convergence zones.     

运用约束Delaunay三角网从众源轨迹线提取道路边界

运用众源车辆轨迹数据提取道路信息需要解决轨迹点采样稀疏、高噪音、密度差异大等问题。为此,本文提出一种运用约束Delaunay三角网从车辆轨迹线集中提取道路边界的方法。首先,通过三角形边长度和Voronoi面积等几何特征表达轨迹点分布的聚集性差异,并将这两种不同几何维数的控制条件集成建立道路边界识别模型,运用"种子点"区域扩展方法实现道路边界的精确提取。最后,运用北京市出租车GPS轨迹进行试验,结果表明该方法适于车辆分布频率悬殊、时间跨度不同、道路网结构复杂的轨迹线数据处理。