| 增量构造Voronoi区域的改进算法 |
| |
| 引用本文： | 徐鹏飞,陈志刚. 增量构造Voronoi区域的改进算法[J]. 计算机工程与应用, 2010, 46(8): 8-10. DOI: 10.3778/j.issn.1002-8331.2010.08.003 |
| |
| 作者姓名： | 徐鹏飞 陈志刚 |
| |
| 作者单位： | 1. 湖南师范大学,数学与计算机科学学院,长沙,410081;中南大学,信息科学与工程学院,长沙,410083
2. 中南大学,信息科学与工程学院,长沙,410083 |
| |
| 基金项目： | 国家自然科学基金Grant No.60873082;;湖南师范大学青年基金项目Grand No.60901~~ |
| |
| 摘 要： | 将Voronoi区域的半平面公共交集转换为Voronoi顶点与半平面的位置关系，提出一种简单的裁剪规则实现Voronoi区域的增量构造；该算法可以有效地处理半直线Voronoi边与直线Voronoi边以及节点共线等特殊情况。理论分析与实验结果表明，该增量构造Voronoi区域的平均时间复杂度是近似线性的。
|
| 关 键 词： | Voronoi划分 Delaunay三角剖分 半平面 |
| 收稿时间： | 2009-11-24 |
| 修稿时间： | 2010-1-11 |
Improved incremental construction algorithm of Voronoi region |
| |
| XU Peng-fei,CHEN Zhi-sang. Improved incremental construction algorithm of Voronoi region[J]. Computer Engineering and Applications, 2010, 46(8): 8-10. DOI: 10.3778/j.issn.1002-8331.2010.08.003 |
| |
| Authors: | XU Peng-fei CHEN Zhi-sang |
| |
| Affiliation: | XU Peng-fei1,2,CHEN Zhi-gang21.College of Mathematics , Computer Science,Hunan Normal University,Changsha 410081,China 2.College of Information Science , Engineering,Central South University,Changsha 410083,China |
| |
| Abstract: | This paper transforms the half-plane common collection of Voronoi region into the location relationship of the Voronoi vertex in the half -plane,and presents a simple clipping rule to incrementally construct the Voronoi region.In addition,the algorithm can deal with the Voronoi edge which is the half-line or the line,and can also adapt to collinear nodes.Theoretic analysis and experiment results show that the time complexity of the algorithm is approximately linear. |
| |
| Keywords: | Voronoi tessellation Delaunay triangulation half-plane |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载免费的PDF全文 |
