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

• 作 者: 王雯[1]吴蔚[1]苏天赟[2]
• 机 构: 中国海洋大学信息科学与工程学院,青岛 266100
• 出 处: 第17届全国图象图形学学术会议
• 发表日期: 2014年期

　　目的：在构建二维Delaunay三角网的逐点插入法中，定位待插点所在三角形的快慢是影响整个算法构网速度的关键因素。本文提出了一种改进的点定位算法。方法：通过结合三角形重心的几何性质，对点定位算法进行改进，简化了待插点位于三角形两条边外侧时的寻找下一三角形的计算步骤，避免了求三角形重心坐标和相交边的过程。结果：实验表明，本文算法较目前其他点定位算法能够有效地缩短搜索路径，减少点定位的计算时间。结论：本文提出了一种改进的点定位算法，结合三角形重心的几何性质，避免了目前已有算法存在的搜索路径长、搜索路径求解计算量大等问题。实验结果表明，本文算法较其他算法能提高Delaunay三角网构网过程中点定位的效率。