论文部分内容阅读
Voronoi图是计算几何的重要分支,Power图是Voronoi图的一种重要推广,它是将欧氏距离推广到Power距离而形成的一种加权Voronoi图,具有很大的实用价值。本文在现有Power图理论的基础上,给出了一种生成Power图的新算法一扫描生成法,该算法隶属于离散生成方法。它利用屏幕的光栅特性,计算屏幕上每个像素点与生成元的Power距离,然后比较、排序,根据Power边上的点到某两生成元的Power距离相等这一特点,从而画出Power边,生成Power图。相比Power图的其他算法,该算法不仅思路清晰,程序设计简单,而且无需复杂的辅助数据结构,节省了大量的预处理时间和存储时间,并且可推广到高阶Power图的情况。
作为应用举例,利用该算法生成的Power图,分析了石家庄市某区网通营业厅的覆盖区域问题,并就其分布的合理性进行了讨论。