利用自适应分块的任意多边形三角剖分算法

三角剖分算法是计算几何领域中的重要课题之一,针对现有多边形三角剖分算法大多不能同时兼顾算法的简单有效性、适用性以及三角网的质量问题,提出一种基于自适应分块的任意多边形三角剖分算法。多边形的自适应分块区别于传统的格子分块,它充分顾及了多边形边作为剖分三角网约束边这一特点,通过选择原始多边形一定数量的边,并对这些边构建最优三角形,将原始多边形分割成若干个小的简单多边形,这些简单多边形之间通过三角形进行连接。至此,原始多边形的三角剖分直接转化为这些简单多边形的三角剖分,这样由一条边寻找一顶点构建最优三角形,直接在该边所在的简单多边形内进行搜索,大大减少了点的搜索范围,提高了算法效率。利用基于边优先的多边形三角剖分算法对分块后的小多边形进行三角剖分,从而完成整个多边形的三角剖分。算法具有适用性广,剖分三角形网形稳定、最优,思路简单,易于实现,执行效率高的特点,最后通过实验证明了本算法的科学性和先进性。     

利用自适应分块的任意多边形三角剖分算法

三角剖分算法是计算几何领域中的重要课题之一,针对现有多边形三角剖分算法大多不能同时兼顾算法的简单有效性、适用性以及三角网的质量问题,提出一种基于自适应分块的任意多边形三角剖分算法.多边形的自适应分块区别于传统的格子分块,它充分顾及了多边形边作为剖分三角网约束边这一特点,通过选择原始多边形一定数量的边,并对这些边构建最优三角形,将原始多边形分割成若干个小的简单多边形,这些简单多边形之间通过三角形进行连接.至此,原始多边形的三角剖分直接转化为这些简单多边形的三角剖分,这样由一条边寻找一顶点构建最优三角形,直接在该边所在的简单多边形内进行搜索,大大减少了点的搜索范围,提高了算法效率.利用基于边优先的多边形三角剖分算法对分块后的小多边形进行三角剖分,从而完成整个多边形的三角剖分.算法具有适用性广,剖分三角形网形稳定、最优,思路简单,易于实现,执行效率高的特点,最后通过实验证明了本算法的科学性和先进性.     

带岛区约束数据域的Delaunay三角剖分通用算法研究

文章提出了一种可解决带岛区约束数据域的三角剖分通用算法,通过对岛区制图边界拓扑结构建立与分析,引入双联点和辅助约束边界概念对岛区外部划分子区(抽象出凸或凹多边形),再采用任意多边形内部三角剖分算法,实现了带岛区约束数据域的Delaunay三角剖分并应用于油气勘探设计等领域。     

一种非凸包边界约束不规则三角网生成算法

数字高程模型(DEM)模拟的大多数地形区域是多种类型区域镶嵌而成的复合体,且子区域的边界一般为非凸多边形,即三角网受到边界的约束。而目前已有的各种Delaunay三角网构网算法生成的不规则三角网的边界都是区域内采样点集的凸包,不能表达复合区域和边界为非凸多边形的区域。本文作者对三角网扩张法作了扩展,使之能够在任意多边形所包围的区域内生成不规则三角网。扩展后的算法具有步骤简单、适合任意多边形边界内生成不规则三角网的优点,而且该算法可用于"分块"式生成数据量较大的三角网,同时保证各"分块"之间完整的邻接关系。     

GIS岛多边形三角剖分算法

结合Delaunay三角剖分原理,在多边形顶点关系的基础上,通过对多边形从外向内间隔相邻级环间的三角剖分,来实现岛多边形的剖分算法。算法涉及图形相交、相邻、相离、包含等几何关系分析,以及Delaunay三角形构建等过程。对图形几何关系判断和三角形构建等过程进行了优化处理,提高了岛内三角剖分的精度和速度,解决了GIS制图中存在的"岛中岛"等复杂几何图形的剖分问题,可以对任意凹凸多边形实现快速三角剖分。首先获取并存储shape文件中多边形的空间坐标数据,然后基于该算法在VC++开发环境中完成岛多边形的三角剖分和显示。通过对不同形状的岛多边形反复测试表明,该算法的三角剖分结果均可达到最优,且效率较高。     

改进的约束数据域三角剖分算法及应用

在逐点插入算法的基础上,通过深入研究影响算法效率提高的因素,对其中的包容盒、空外接圆检测算法、快速查找点所在的三角形算法、快速查找与约束线段相交的边算法进行优化和改进,提出一种改进的约束数据域三角剖分算法,使得构网效率接近或高于现行的大多数算法,且基于此算法能同时处理约束线段和约束区域相关的多种约束数据类型。     

改进的约束数据域三角剖分算法及应用

在逐点插入算法的基础上,通过深入研究影响算法效率提高的因素,对其中的包容盒、空外接圆检测算法、快速查找点所在的三角形算法、快速查找与约束线段相交的边算法进行优化和改进,提出一种改进的约束数据域三角剖分算法,使得构网效率接近或高于现行的大多数算法,且基于此算法能同时处理约束线段和约束区域相关的多种约束数据类型.     

上下扫描线的Delaunay三角剖分算法

为了提高Delauany三角网构网效率,该文借助平面扫描技术,提出了一种基于上下扫描线与Lawson局部优化算法相结合的Delaunay三角剖分算法。该算法通过上扫描线构网,并发现构网过程中可能产生"盆"的现象,下扫描线处理"盆"以减少构网过程中出现狭长病态三角形的问题,在算法整个过程中尽量降低三角网合法性检查的时间消耗。最后就算法的时间复杂度进行了分析,并与其他常见算法就CPU时间运行效率进行了比较。实验表明该算法实现简单,运行效率相对较好。     

基于Arcobjects的约束Delaunay三角网支持下的土地利用图斑综合

关于以约束Delaunay三角网剖分模型为基础的地图综合的研究,已经有了很多成熟的算法理论,但在应用中这些模型算法建立的约束性Delaunay三角网都比较复杂,并且在动态更新上,这些模型在实际应用中存在一定的困难。基于此问题,本文提出了以地类图斑多边形为数据源,利用Arcob jects建立TIN模型,从中获取内部约束性Delaunay三角网并提取骨架线,利用骨架线进行剖分多边形,达到图斑多边形融合的目的,来解决大比例尺到小比例尺数据转换中地类图斑的制图综合问题。     

带约束折线的平面散点集Delaunay三角剖分

首先将原始散点与约束点一起进行三角剖分,形成初始Delaunay三角网,然后再将各条约束线段通过局部更新,依次嵌入已存在的三角网中,从而生成带有约束折线的平面散点集的Delaunay三角剖分。该算法思路简捷,易于编程,生成的三角网形态优良。     

Delaunay三角网内插多边形算法研究

针对Delaunay三角网内插多边形的实用性,提出了一种Delaunay三角网快速内插多边形算法,该算法先将多边形的边作为约束数据入网,然后对多边形内部三角形进行清空处理。在影响区域及多边形内部三角形确定上,提出了一种快速解决方法,大大提高了算法的执行效率。     

Delaunay三角网内插多边形算法研究

针对Delaunay三角网内插多边形的实用性,提出了一种Delaunay三角网快速内插多边形算法,该算法先将多边形的边作为约束数据入网,然后对多边形内部三角形进行清空处理.在影响区域及多边形内部三角形确定上,提出了一种快速解决方法,大大提高了算法的执行效率.     

基于二叉树思想的任意多边形三角剖分递归算法

提出了一种基于二叉树思想的任意多边形三角剖分递归算法。该算法采用二叉树思想，确定剖分三角形的二叉树状结构，并采用递归算法实现。这算法可适用于任意形状的凹或凸多边形，也适用于包含岛屿的多边形。此外，在考虑边界点高程的基础上，可充分顾及地形特征。该算法完全适用于长距离河流流域的三维面状表达。     

一种快速二维 Delaunay 三角网点定位算法

在构建二维Delaunay三角网的逐点插入法中,定位待插点所在三角形的快慢是影响整个算法构网速度的关键因素。针对目前已有算法存在的搜索路径长、搜索路径求解计算量大等问题,结合三角形重心的几何性质,对点定位算法进行改进,避免求三角形重心和相交边的过程。实验结果表明,文中算法较目前其他点定位算法能够有效地缩短搜索路径,减少点定位的计算时间,提高Delaunay三角网构网过程中点定位的效率。     

利用数学形态学提取骨架线的改进算法

地图数字化生产和数字地图编绘中都需要用到提取骨架线算法,如矢量化和等级变换等。提取骨架线的算法较多,基于栅格数据的算法通常采用数学形态学方法,对于矢量数据目前较有代表性的是利用约束Delau-nay三角网提取骨架线。本文给出一种利用数学形态学提取骨架线的改进算法,适用于栅格和矢量数据,并能在矢量化时建立高质量的拓扑关系,还较好地克服了数学形态学方法的缺点——节点畸变和端点内缩。实验表明该算法稳定且行之有效。     

多边形骨架线与形心自动搜寻算法研究

针对GIS中的应用，分析了传统的多边形骨架线与形心提取算法的不足之处，提出了一种基于约束Delaunay三角网结构的多边形主骨架线与形心的自动搜索算法，详细描述了该方法的基本思想，并在实验结果基础上分析了该算法的特点。     

CPU+GPU异构环境下数据密集型矢量多边形地理大数据并行框架

本文提出了面向CPU+GPU异构环境的数据密集型矢量多边形地理大数据并行计算框架(PFGAP)。PFGAP将数据密集型矢量多边形地理大数据的并行计算分解为算子、数据、粒度、并行环境及任务调度5个模块,分别设计相应的负载均衡并行计算策略;通过封装并行计算实现细节及数据密集型多边形算子的快速并行化。试验采用多边形三角剖分、栅格化及投影变换作为测试算例,采用土地利用数据作为测试数据,在不同类型的并行环境中计算并行效率。结果表明,PFGAP能很好地适用于不同类型的数据集、算子及并行计算环境。利用PFGAP实现的并行算法显著地降低了串行执行时间,取得了40.03的最优并行加速比。试验还分别测试了各个模块涉及的并行策略,结果表明取得的并行效率优于现有并行策略。     

Delaunay三角网中点目标快速定位算法研究

为了提高内插法的构网速度及方便数字地面模型的后续应用,本文对三角形定位算法进行了研究,对基于点-线关系的方向定位算法和基于线-线关系的方向定位算法进行了改进,算法极大地减少了定位目标三角形的时间,由于定位三角形的速度是影响内插构网速度的一个关键因素,从而提高了构网速度。同时对两种算法进行了分析比较,得出最速方向定位算法更健壮,其定位路径唯一,效率更高。     

带有边界条件的Delaunay三角网生成算法的研究与实现

Delaunay三角网是构建数字地形模型的主要途径,凸壳是构造Delaunay三角网的基础,一般的凸壳构造方法找到的凸壳为最少点的多边形,但也有多点在一条边界边上的情况。在Delaunay三角网生成算法的基础上,提出了一种新的查找凸壳的算法并导出了带有边界条件的Delaunay三角网生成算法。通过实际数据的测试,表明该算法是有效的。