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

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

一种生成Delaunay三角网的合成算法

结过２０多年的研究,自动生成Ｄｅｌａｕｎａｙ三角网的算法已趋于成熟。它们基本上可分为分治算法、逐点插入法、三角网生长法等３类。其中前两类较第３类在应用上更加广泛。但即使这两类算法也分别存在着时间和空间效率站的缺陷,使它们的应用受到了一定的限制。提出了一个融以上两类算法优点于一体,兼顾空间与时间性能的合成算法。经测试,它的运算效率大大高于逐点插入法,在大多数情况下,也高于分治算法,在分割阈值约为总数     

Delaunay三角网的并行构网算法

针对传统的Delaunay三角网的并行构建算法负载均衡性不高、运行效率较低等问题,该文在综合逐点插入算法和分治算法各自优点的基础上,提出了一种Delaunay三角网并行构建算法。该算法首先使用动态格网剖分点要素集,从而得到若干点要素子集;然后根据点要素子集数量初始化线程池,每个点要素子集由一个线程按照插入点法构建Delaunay子网;当所有线程完成子三角网构建,最后使用逐点插入法合并所有子网,从而实现所有点要素的Delaunay三角网构建。分析与实验结果表明,相对于传统的并行算法,该并行算法的负载均衡性好、运行时间少、加速比高,具有较好的构建效率,而且构建结果满足Delaunay规则。     

基于分治算法与逐点插入法的Delaunay三角网建立算法的改进

Delaunay三角化在诸多应用领域都具有极其广泛的用途,也一直是GIS领域的重要研究内容。本文针对在Delaunay三角网建立中比较常用的分治算法即逐点插入法的缺点提出一些改进方案,在对逐点插入法改进的前提下提出将分治算法与逐点插入法相结合的综合算法。该综合算法既具有分治算法的高效率又具有逐点插入法的内存消耗小的优点,同时又较好地解决了分治算法与逐点插入法各自的缺点。     

Delaunay三角网的生成算法研究

Ｄｅｌａｕｎａｙ三角作为一种主要的ＤＴＭ表示法,具有极其广泛的用途。经过二十多年来的研究,它的生成算法已趋于成熟。本文简要介绍了Ｄｅｌａｕｎａｙ三角网的定义及其特性,在简单回顾和评价了分割－归并法,逐步插入法,三角网生长法等三类主流算法的基础上,提出了一个融以上算法优点于一体,兼顾空间与时间性能的合成算法。经测试,一般情况下它的运算速度远快于逐点插入法,与分割－归并法相当,较好的情况下快于分割－归     

利用点角改进Delaunay三角网生长算法

分析常规三角网生长算法的优缺点,提出点角概念,在生成Delaunay三角形的过程中,逐步缩小离散点的搜索范围,克服常规算法时间效率低的缺点。构网过程中,完全遵守Delaunay三角网的剖分准则,验证算法的稳定性和高效性。     

球面Delaunay三角网的透视投影算法

为解决球面Delaunay构网中的拼接问题,顾及球面数据的位置特点,提出了利用透视投影模型将球面构网整体平面化的算法,其核心是置投影中心于球面,通过球面位置(x、y与z坐标)共同约束,进而构成球面与投影平面位置间的一一映射。实验结果表明,此算法具有有效性及通用性,其时间复杂度取决于所采用的平面Delaunay三角网构建算法。     

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

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

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

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

约束Delaunay三角网生成算法研究

对约束Delaunay三角网的构建算法进行研究,并提出一种约束Delaunay 三角网生成算法,它充分利用分治算法与生长算法的优点,对离散点、构网中实时生成的边及三角形采用分块进行网格索引,有效地减少了搜索目标点、边及三角形的时间,从而提高构网速度.     

基于TIN的半自动多影像同名线段匹配算法研究

提出了根据同名像点构成三角网 (TIN)来进行同名直线的匹配。依据TIN预测左影像上一条给定直线在右影像上同名直线的搜索范围,计算给定直线与候选直线的灰度相关系数,取最大相关系数所对应的直线为同名直线。实验证明,该算法简单、可行。     

一种Delaunay三角网的快速生成算法

本文以Lawson提出的逐点插入法为基础，借鉴方向搜索的思想，在确定插入点的影响凸包时，采用递归的局部搜索策略，形成了一种Delaunay三角网的快速生成算法。实验证明，新算法构网时间与点数基本成线性增长关系，具有较高的效率。     

Delaunay三角网建立的改进算法

本文深入研究了Delaunay三角网建立算法中的逐点插入法,详细介绍了算法的实现步骤,分析了其中影响算法效率的关键环节,并采用数据点集分块管理、三角形快速定位、改变点插入顺序等方法进行了算法优化,对三角形快速定位方法进行了改进。测试实验的结果说明,算法改进后Delaunay三角网建立的效率提高了4~6倍。     

Delaunay三角化中特征约束细分嵌入算法

在Delaunay三角化中,以在特征约束上插入附加点的方式对特征约束细分,可使剖分网格在表达特征约束的同时仍满足Delaunay三角网格特性。本文提出了一种改进的细分嵌入算法——端点外接圆法(ETCM),该算法具有线性时间复杂度。以剖分结果的稳定性、附加点个数、运算耗时和网格质量为评价标准,对ETCM和现有的细分嵌入算法进行了评估。实验结果表明,在运算耗时方面,ETCM受数据分布的影响最小,且耗时最少;在其他方面,与现有算法的最好表现持平。     

基于三角网的"种子法"多边形生成

将传统上广泛使用的“种子法”和“矢量求交法”的思想相结合 ,提出了一种基于约束Delaunay三角网结构的多边形生成算法。详细描述了该方法的基本思想 ,在实验基础上分析了算法的特点。     

基于约束Delaunay三角网建立等高线层次结构的方法

分析了以等高线、高程点和地形突变线为基础建立的约束Delaunay三角网(Delaunay triangulation,DT)的特征,为了识别这些约束目标之间的邻近关系,对约束DT的边进行了详细分类,并按照相关的规则提出了构建等高线层次结构的方法。在此层次结构的基础上,研究了调整等高线走向的方法。     

基于Delaunay三角网表达的图像分割

由于图像的复杂性和模糊性进一步增强,传统的图像分割算法已经无法满足其对分割精度的要求。为了进一步提高图像分割的精度,本文提出了一种结合SIFT特征提取与Delaunay三角网表达的图像分割方法,该方法可以有效削弱噪声对图像分割结果的影响,与传统去噪滤波相比,平滑过程中模糊图像边缘的程度比较低,同时,运用超像素思想,将传统基于像素单元的分割方法运用到超像素上,对被三角网划分的子区域进行聚类,最后得出分割结果。与传统算法相比,本文算法在分割精度方面有显著提高。     

基于Delaunay三角网的等高线树生成方法

研究如何利用Delaunay三角网构建等高线树,提出一种新的等高线树生成方法。该方法充分利用Delaunay三角网在领域分析中的优势,通过两次利用Delaunay三角网来判明等高线的空间关系进而达到统一被图廓截断的等高线以生成等高线树的目的。本文将等高线作为约束边构建约束型Delaunay三角网,利用Delaunay三角网查找具有邻接关系的等高线,在此基础上结合邻近等高线的高程关系判明、识别,最终统一被截断的等高线;然后对统一后的等高线再次利用Delaunay三角网查找具有邻接关系的等高线对,利用等高线对的高程关系判断出其为父子关系或兄弟关系,据此将等高线插入到相应的位置,逐步生长成等高线树。     

基于格网划分的海量数据Delaunay三角剖分

提出基于格网划分、面向海量数据的Delaunay三角剖分方法,它首先把数据集划分为若干格网块,按照格网划分的逆序对每个格网块采用基于自适应格网划分的分割-合并算法进行Delaunav三角剖分,把格网块Delaunay三角网中不受边界影响的三角形进行存储并释放内存,然后顺序合并相邻格网块Delaunav三角网,形成全局或类全局Delaunay三角网.该方法对计算机硬件配置要求较低,适合于并行处理,可以实现面向海量数据的Delaunay三角剖分.     

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

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