摘要
将Voronoi区域的半平面公共交集转换为Voronoi顶点与半平面的位置关系,提出一种简单的裁剪规则实现Voronoi区域的增量构造;该算法可以有效地处理半直线Voronoi边与直线Voronoi边以及节点共线等特殊情况。理论分析与实验结果表明,该增量构造Voronoi区域的平均时间复杂度是近似线性的。
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.
出处
《计算机工程与应用》
CSCD
北大核心
2010年第8期8-10,共3页
Computer Engineering and Applications
基金
国家自然科学基金Grant No.60873082
湖南师范大学青年基金项目Grand No.60901~~