| 基于最优凸壳技术的Delaunay三角剖分算法 |
| |
| 引用本文： | 陈学工,黄晶晶.基于最优凸壳技术的Delaunay三角剖分算法[J].计算机工程,2007,33(17):93-95. |
| |
| 作者姓名： | 陈学工 黄晶晶 |
| |
| 作者单位： | 中南大学信息科学与工程学院，中南大学信息科学与工程学院 长沙 410083，长沙 410083 |
| |
| 基金项目： | 国家高技术研究发展计划(863计划) |
| |
| 摘 要： | 提出了一种基于最优凸壳技术的Delaunay三角剖分算法。该算法对离散点进行扫描线方式排序，利用最优凸壳技术进行凸壳的生成和三角网联结，最后利用有向边的拓扑结构进行三角网优化。该算法不但避免了所有的交点测试，而且使得新加入点与凸壳边的平均比较次数不大于4，从而实现了高效的三角剖分。
|
| 关 键 词： | Delaunay三角剖分 凸壳 三角网优化 |
| 文章编号： | 1000-3428（2007）17-0093-03 |
| 修稿时间： | 2006-09-07 |
Algorithm of Delaunay Triangulation Based on Optimal Convex Hull Technology |
| |
| CHEN Xue-gong,HUANG Jing-jing.Algorithm of Delaunay Triangulation Based on Optimal Convex Hull Technology[J].Computer Engineering,2007,33(17):93-95. |
| |
| Authors: | CHEN Xue-gong HUANG Jing-jing |
| |
| Affiliation: | School of Information Science and Engineering, Central South University, Changsha 410083 |
| |
| Abstract: | A Delaunay triangulation algorithm based on optimal convex hull technology is presented.The algorithm makes the discrete points sort in scan manner,and secondly it constructs convex hull and triangulates the sorted points by the optimal convex hull technology which is proved by the author,and optimizes triangles utilizing topological structures of directed edges.The algorithm avoids the test of point of intersection.Moreover, the average test times of a newly added point is under 4,so that the high efficiency of triangulation can be sure. |
| |
| Keywords: | Delaunay triangulation convex hull triangles optimization |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程》浏览原始摘要信息 |
|
点击此处可从《计算机工程》下载全文 |
