提高Delaunay三角网生成效率的算法研究

"本文主要探讨了如何改进平面域Delaunay三角网的生成算法，以提高构网速度和定位效率。研究中，作者关注了Delaunay三角剖分在多个领域的广泛应用，如科学计算可视化、有限元分析等，并指出现有算法的改进主要集中在逐点插入法和分治算法的搜索策略上。文章提出了一种结合网格分块和改进的点线关系方向定位的新方法，旨在提高定位目标点所在三角形的速度。 在Delaunay三角剖分的过程中，逐点插入法是常用的一种算法，它需要首先确定插入点所在的三角形，然后进行点的插入和优化，最终生成新的三角网。这一过程中，关键步骤包括点线关系、点与三角形的拓扑关系的判断。传统方法中，如文献[1-2]采用网格分块提高点定位速度，但需要搜索大量三角形，效率有限；文献[3]则通过点与有向线段的融合定位，但因缺乏网格索引，整体定位速度不高。 针对这些问题，本文提出的改进方法是将网格分块和改进的点线关系方向定位算法相结合。通过网格分块，可以快速定位目标点的大致区域，减少搜索范围；而改进的定位算法则减少了计算重心的次数，简化了点与三角形关系的判断，从而提高了定位效率。具体来说，利用三角形矢量面积判断点与三角形的关系，避免了复杂的三角函数运算，提高了算法的执行速度。 图1展示了利用有向线段P1P2和点P0形成的矢量坐标来计算三角形面积的原理，这种方法有助于简化点与三角形关系的判断，进而提升整个构网过程的效率。 该论文提出的改进算法不仅在理论上提高了Delaunay三角网生成的速度，而且通过实际测试验证了其高效性和稳定性。这为未来Delaunay三角剖分算法的研究提供了新的思路，有望在需要快速构建大规模三角网的场景中得到广泛应用。"