Delaunay三角网通用合并算子及分治算法的简化

Delaunay三角网在未来地学数值模拟中将发挥重要作用。分治算法是一种著名的经典构网算法,但其子网合并过程十分复杂,限制了其应用。提出使用通用算子的概念,并用从以往算法中独立出来的算子和3个新算子来简化分治算法的子网合并。扩展三角形算子用于构造每个新三角形并维护三角网的拓扑关系和边界链表。凹边界填充算子对边界链表用递归来自动完成凹边界的智能三角形填充。子网合并算子先用一个新三角形连接两个子三角网,再合并边界链表,调用凹边界填充算子填充子网间的缝隙区域。所有算子都基于有向边的数据结构和用链表管理的三角网外边界,借助链表操作,使算法的构建简洁而又高效。除分治法外,这些算子还被成功用于构建其他算法。由随机点集以及LiDAR点云的测试表明,所有算法的构网均准确无误且分治算法的执行效率较高。

多波束测深系统中的海底地形可视化技术研究

针对直接使用大数据量的离散深度数据实现海底地形可视化时,基于不规则三角网的海底地形建模速度慢、稳健性低的问题,提出一种联合矢积测试的子网合并双向缝合算法,设计了一种基于二叉树的动态分块合并机制。该算法能够避免相交三角形或线形三角形的产生并使缝合后新生成的初始三角形形状趋于最优,提高了子网合并速度与整个构网程序的稳健性,实现了基于快速Delaunay构网的海底地形建模和三维可视化。实验结果表明,该算法能够明显提高子网合并速度与程序稳健性,适用于大数据量离散测深数据的海底地形绘制。