简单多边形的动态Delaunay三角剖分算法

提出了一种简单多边形的动态Delaunay三角剖分算法,其时间复杂度为O(n).从理论上证明了算法的正确性,并利用Python语言开发了一款动态Delaunay三角网生成软件,最后通过大量数据测试了该软件的健壮性并得到实例证实.

生成Delaunay三角网的快速合成算法

合成算法结合了传统的递归分割法和逐点插入法的优点,兼顾空间和时间性能.然而,该算法不可避免地继承了两种传统算法的不足,在执行效率上受到限制.为了解决执行效率问题,提出了快速合成算法,对合成算法进行了改进和优化.该算法基于面积坐标的点定位算法和简化的高效空外接圆判断算法,从而大大提高算法的整体执行效率;同时充分考虑平面点集的任意性,适用于对任意平面点集构建Delaunay三角网.

基于钻孔数据的地质面Delaunay三角剖分

利用钻孔数据对地质面进行三角剖分是三维地质建模的一个重要部分,Delaunay三角剖分具有优美的数学特性,且已有很多成熟的算法,对传统凸包生成、三角剖分和空外接圆检测等算法进行了改进。分析表明,提高了算法效率。

三角形增长算法构建Delaunay三角网DEM的原理与实现

本文主要论述了三角形增长算法建立Delaunay三角网DEM。首先通过最优边找首三角形,其次通过直线与点几何关系来寻找可能扩展点,通过找最大夹角来判断满足狄洛尼法则的扩展点,最后通过新加入边与已扩展边的数目来判断是否为重复狄洛尼扩展点,符合条件则构建三角网。然后通过空外接圆法则验证了所构三角网符合狄洛尼三角网的条件。狄洛尼三角网的建立和空外接圆的验证程序采用M语言来编写。

基于无弦圈的覆盖漏洞边界检测算法研究

针对无线传感器网络中覆盖漏洞问题,提出了一种基于无弦圈的传感器网络覆盖漏洞检测算法。算法从本地距离信息中计算出相对r-map坐标,对感知邻近图进行DECM三角剖分;每个节点根据剖分三角形的空外接圆性质匹配判断自身是否为覆盖漏洞边界节点,得到预筛选边界节点集;依据覆盖漏洞边界节点分布连续性,利用无弦圈的覆盖漏洞搜索算法,对预筛选边界节点集进行精确识别,剔除非边界节点。仿真结果表明,CC-CHDA算法能够有效的识别覆盖漏洞边界节点和覆盖区域外边界节点,比CG-DCHD算法的识别覆盖漏洞边界节点准确率更高。

二维离散点集Delaunay三角网生长算法的改进

Delaunay三角剖分在计算几何、计算机图形学、计算机辅助设计、有限元分析、地理信息系统等邻域有广泛的应用,是一项极为基础且重要的离散数据网格化技术。生长算法是一种重要的Delaunay剖分算法,具有较高的理论价值和实际意义,该算法思路简单且容易扩展,可以拓展到三维点云曲面的构造中。但是现有的生长法效率不高,无法处理海量数据,本文经研究提出了一种基于Delaunay空圆性质的改进算法,在逐边定向扩展过程中直接利用Delaunay空圆性质,迅速缩小备选扩展点集的范围,大幅提高了三角网生长速度。大量的随机和规则数据测试表明该改进算法效率提升显著,与已有生长算法相比有10倍以上的提高,且数据量越大效率提升越明显。

D-TIN生成算法

Delaunay三角网作为一种主要的DEM表示法,具有极其广泛的应用。在系统地研究、对比了三角网数字高程模型D-TIN构建过程中的几个关键问题后,提出了快速定位点所在的三角形算法及简易的空外接圆检测公式。