|
|||||
|
|
| 基于EMST的平面点集Delaunay三角剖分 | |
| 引用本文： | 余楚才,吴荣泉,许延武. 基于EMST的平面点集Delaunay三角剖分[J]. 计算机工程, 2008, 34(Z1) |
| 作者姓名： | 余楚才 吴荣泉 许延武 |
| 作者单位： | 华东计算技术研究所,上海,200233 |
| 摘 要： | 提出一种基于欧几里德最小支撑树(EMST)的平面点集Delaunay三角剖分算法.该算法使用线性时间的随机算法求出平面点集的EMST,逐次加入一边构成三角网络,按照最小角最大化的三角化准则,通过局部变换得到平面点集的Delaunay三角剖分.采用的随机化算法有效节省了寻找EMST的计算时间,提高了整个算法的效率. |
| 关 键 词： | 欧几里德最小支撑树 Delaunay三角剖分 随机算法 |
Plane Points Set Delaunay Triangulation Based on EMST |
|
| YU Chu-cai,WU Rong-quan,XU Yan-wu. Plane Points Set Delaunay Triangulation Based on EMST[J]. Computer Engineering, 2008, 34(Z1) | |
| Authors: | YU Chu-cai WU Rong-quan XU Yan-wu |
| Affiliation: | YU Chu-cai,WU Rong-quan,XU Yan-wu (East China Institute of Computer Technology,Shanghai 200233) |
| Abstract: | An EMST-based plane points set Delaunay triangulation algorithm is presented.The algorithm finds the EMST in linear time by using randomized algorithm,and adds an edge to the EMST once a time,which will construct a triangulation network.A plane Delaunay triangulation through local transformation based on the Maximize the Minimum Angle Criteria can be got.It can save some time in finding EMST with randomized algorithm,and make the whole algorithm more effectively. |
| Keywords: | EMST Delaunay triangulation randomized algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |