容量限制Power图快速计算算法

摘要

Comparing with Voronoi diagram, power diagram has the useful characteristics of precise capacity holding, thus it can be applied in many fields. Capacity constrained power diagram (CCPD) can be obtained by imposing capacity constraint to the ordinary power diagram by adding a weight to each site. However, power diagram computation is hard and complex due to its high time complexity. In this paper, we firstly prove the monotonicity of power diagram weight against capacity theoretically, and then based on Balzer's method, we present an improved and fast analytic algorithm to directly calculate power weights instead of the counterpart false position method. Experiment results exhibit that proposed algorithm has the advantages of good efficiency, high accuracy, easy to implementation, and strong adaptability for complex density fields.%与Voronoi图不同, Power图有着精确限容的特性, 可应用于众多领域. 在普通Power图上, 通过给每个站点增加权重来添加容量限制约束, 即得到容量限制Power图. 现有容量限制Power图的生成算法时间复杂度高, 速度较慢. 本文首先对Power图权值对于容量的单调性进行理论证明, 然后提出了一种Power图权值的快速计算方法, 相比于现有的试位法, 能大幅提升容量限制 Power 图的生成性能. 实验结果表明, 文中算法具有速度快, 精确度高, 便于计算, 密度适应性强等优点.