Delaunay三角化中特征约束细分嵌入算法

基金项目: 船舶行业国防预研基金资助项目(06J3.8.6)；哈尔滨工程大学基础研究基金资助项目(HEUFP07002)

详细信息

A Node Refinement Algorithm for Inserting Feature Constraints in Delaunay Triangulation

¹College of Automation,Harbin Engineering University,145 Nantong Street,Harbin 150001,China

Funds: 船舶行业国防预研基金资助项目(06J3.8.6)；哈尔滨工程大学基础研究基金资助项目(HEUFP07002)

摘要: 在Delaunay三角化中,以在特征约束上插入附加点的方式对特征约束细分,可使剖分网格在表达特征约束的同时仍满足Delaunay三角网格特性。本文提出了一种改进的细分嵌入算法——端点外接圆法(ETCM),该算法具有线性时间复杂度。以剖分结果的稳定性、附加点个数、运算耗时和网格质量为评价标准,对ETCM和现有的细分嵌入算法进行了评估。实验结果表明,在运算耗时方面,ETCM受数据分布的影响最小,且耗时最少;在其他方面,与现有算法的最好表现持平。
- Delaunay三角化 /
- 特征约束 /
- 细分嵌入
Abstract: An improved algorithm of node refinement scheme called endpoint triangle's circumcircle method(ETCM) is proposed,which has a linear time complexity.Regarding stability,new nodes quantity,time costs and meshes quality as criterions,ETCM and several existing node refinement algorithms were evaluated by simulations.The results show that ETCM has the least time costs,and is more independent of data distribution.Moreover,the performances on other criterions of ETCM are almost the same as those of the best of existing algorithms.
- Delaunay triangulation /
- feature constrains /
- node refinement