科研之友
微信
新浪微博
Facebook
分享链接
摘要
Voronoi图是计算几何领域中的一个重要研究方向，其生成算法是该领域的关键技术。确定归属算法符合计算机的离散特征，是精度最优的栅格Voronoi图生成算法之一，但该算法在海量数据处理时效率不高。针对这一问题，提出一种基于结合边缘归属与双向扫描的栅格Voronoi生成算法。在深入探究确定归属算法精度优异和效率较低原因的基础上，首先将数据边界栅格通过确定归属计算赋予Voronoi区域归属，建立3×3的邻域模板，进行正向扫描；然后在深入剖析正向扫描结果的基础上，通过逆向纠错确保所有栅格归属的正确性；最后利用不同规模的数据进行了实验对比。结果表明，所提算法具有与确定归属算法相同的精度，但却省去80%以上的计算量，效率提高四倍以上，且数据规模越大，算法优势越明显。
- 单位
