基于EMST的平面点集Delaunay三角剖分.docx

基于EMST的平面点集Delaunay三角剖分
基于EMST的平面点集Delaunay三角剖分
摘要：
Delaunay三角剖分是计算机图形学领域中常用的一个基本问题，可以在给定平面点集上构建出一组互不重叠且包含所有点的三角形。EMST（EuclideanMinimumSpanningTree）是指在给定平面点集的基础上，找到一个连通无环的子集，使得该子集上的边的长度之和最小。本文基于EMST的思想，提出一种改进的平面点集Delaunay三角剖分方法。我们首先计算点集的EMST，然后根据EMST的边构建Delaunay三角剖分。实验证明，这种方法在剖分质量上表现出色，同时具有较低的时间复杂度。
1.引言
Delaunay三角剖分是计算机图形学领域中一个重要的问题，广泛应用于地理信息系统、计算机辅助设计等领域。Delaunay三角剖分具有最优性和稳定性等重要性质，被认为是最合理的三角剖分方法之一。Delaunay三角剖分的性质决定其在各种应用中的重要性，因此其构建算法的研究一直是计算机图形学领域的热点之一。
2.相关工作
在Delaunay三角剖分的研究中，传统的方法通常基于Bowyer-Watson算法或法向量法。Bowyer-Watson算法通过维护一个边界的点和Delaunay三角剖分的非Delaunay边来构建剖分。法向量法则通过计算点的法向量和约束的法向量之间的夹角来构建剖分。这些方法在剖分质量和时间复杂度上都存在一定的局限性。
3.EMST在Delaunay剖分中的应用
EMST是指在给定平面点集的基础上，找到一个连通无环的子集，使得该子集上的边的长度之和最小。EMST是一种具有广泛应用的图形算法，常被用来解决聚类分析、最小生成树等问题。我们发现EMST在Delaunay剖分中也有较好的应用价值。
4.改进的Delaunay剖分算法
本文提出了一种改进的Delaunay剖分算法，基于EMST的思想，通过计算点集的EMST并根据EMST的边构建Delaunay三角剖分。该算法的主要步骤如下：
1)计算点集的EMST；
2)构建Delaunay剖分的初始三角形；
3)根据EMST的边和初始三角形生成更多的三角形；
4)通过图优化方法进一步优化剖分。
5.实验结果与分析
我们在多个数据集上进行了实验，并与传统的Delaunay剖分算法进行了对比。实验证明，改进的算法在剖分质量和时间复杂度上均有显著提升。与传统方法相比，改进的算法能够产生更加均匀、规整的三角剖分结果，并且具有较低的时间复杂度。
6.总结与展望
本文基于EMST的思想，提出了一种改进的平面点集Delaunay三角剖分方法。实验结果表明，该方法在剖分质量和时间复杂度上具有优势。进一步的研究可以考虑应用其他图优化方法来进一步优化剖分结果，并将该方法扩展到三维平面点集的Delaunay剖分中。
参考文献：
[1]WatsonDF.Computingthen-DDelaunaytessellationwithapplicationtoVoronoipolytopes[J].CommunicationsoftheACM,1981,24(9):564-569.
[2]RuppertJ.ADelaunayrefinementalgorithmforquality2-Dmeshgeneration[J].Journalofalgorithms,1995,18(3):548-585.
[3]ShewchukJR.Delaunayrefinementalgorithmsfortriangularmeshgeneration[J].ComputationalGeometry,2002,22(1-3):21-74.
[4]LiX,QinH,WanF.AnewmethodforDelaunaytriangulationofplanarpointsets[C]//201219thInternationalConferenceonGeoinformatics.IEEE,2012:1-6.