变容量限制质心Power图的计算

姚裕友，张高峰，徐本柱，郑利平

变容量限制质心Power图的计算

姚裕友，张高峰，徐本柱，郑利平

(合肥工业大学计算机与信息学院，安徽 合肥 230601)

Power图作为Voronoi图的拓展，引入“权重”使其有着良好的限容特性。对普通Power图增加容量约束，使得每个站点的容量等于预设的容量值，则可以得到容量限制Power图；在此基础上，再增加质心约束，使每个站点刚好位于对应Power区域的质心，进一步得到质心容量限制Power图。在质心容量限制Power图中，容量限制条件均有明确的值，然而在某些应用中其往往是一个区间。针对区间容量限制问题，提出一种变容量限制质心Power图的计算方法。一方面，该方法通过不断调整各站点的权重以使得站点的容量满足区间限制；另一方面，Lloyd方法被用于优化各站点的位置到对应Power区域的质心；两者交替迭代优化，从而得到满足区间容量限制的质心Power图。在不同的密度和不同容量限制区间下的实验结果表明，该方法适用于不同密度下变容量限制质心Power图的计算，并且具有高效、适应性强等优点。

Power图；变容量限制；区间；质心；密度

在计算几何中，Voronoi图作为一种基础的几何结构有着广泛地应用与拓展。DU等[1]在普通的Voronoi图的基础上约束站点至质心位置，得到基于质心的Voronoi图(centroidal Voronoi tessellation，CVT)；郑利平等[2]在CVT的基础上引入容量限制，得到容量限制的质心Voronoi图(capacity constrained centroidal Voronoi tessellation，CCCVT)，并将其应用于城市选址布局问题中。然而Voronoi图因其得到的剖分过于刚性，难以满足容量限制要求。

AURENHAMMER等[3]对Voronoi图进行拓展得到Power图，Power图通过控制每个站点的权重值来控制站点的容量，从而弱化了Voronoi图的刚性限制。相较于Voronoi图，Power图拥有精确限容的特性，因而在各种实际应用中被广泛使用。在计算机图形学中，Power图被应用于蓝噪生成[4]、模型网格优化[5]、流体仿真[6-7]、计算机动画[8-9]等；在运筹学中，Power图被应用于解决选址分配问题[10]、扇区划分问题[11]等；在材料科学领域，Power图亦被应用于颗粒结构的表示[12]等。

随着Power图概念的提出，研究者们对其进行了全面而深入的研究。AURENHAMMER[13]对Power图的理论和应用做了总结，IMAI等[14]针对平面点集上Power图的性质给出了理论证明。对于Power图的计算，早期吴壮志等[15]利用正则三角化辅助生成Power图，但未考虑到容量优化问题。BALZER和HECK[16]通过不断迭代和调整站点权重的方法从而达到容量限制条件，并提出有限域和连续域下[17]的容量限制Power图的计算方法，再结合Lloyd方法[18]优化站点从而满足质心限制，从而得到基于质心的容量限制Power图。然而文献[16]提出的试探法通常需要多次迭代，花费时间较长，郑利平等[19]在其基础上改进算法，采用解析的方法直接计算权重值，使其计算效率有了显著地提升，但仍需采取逐点迭代的优化策略。文献[4]将容量限制看成等式约束条件，通过拉格朗日方法来优化Power图，使用Newton法优化权重，梯度下降法优化站点位置，两者交替进行，从而得到质心容量限制Power图(centroidal capacity constrained Power diagram，CCCPD)。XIN等[20]提出一种超线性收敛的CCCPD生成算法，并结合L-BFGS方法和梯度下降法计算之。

然而，不论是容量限制Power图(capacity constrained Power diagram，CCPD)还是质心容量限制Power图的研究中，都明确给定了每个站点的限定容量值，但在有些实际应用中，站点的限定容量值往往是一个最大阈值或限制区间，例如城市应急救援中心、商品配送中心等，被称之为变容量限制Power图(variable capacity constrained Power diagram，VCCPD)。如果对其施加质心约束，即可得到变容量限制质心Power图(variable capacity constrained centroidal Power diagram，VCCCPD)。本文方法聚焦于变容量限制条件下质心Power图的求解，提出一种基于站点Power单元来调整权重值的算法用于计算变容量限制Power图，并结合Lloyd方法优化站点位置满足质心约束，得到变容量限制质心Power图。

1 相关工作

1.1 Voronoi图和Power图

其中，为欧式距离，特别地，当Power图中所有站点的权重相等时，此时的Power图退化为Voronoi图[13]。

1.2 质心Power图

文献[1]证明了，根据站点位置构造出的Voronoi图为质心Voronoi图时，能量函数()的值最小。

与CVT类似，如果在Power图中也增加质心约束，则称该Power图为质心Power图(centroidal Power diagram，CPD)。为了有效地求解CVT和CPD，Lloyd方法作为最为普遍的算法是在每次迭代过程中将站点的位置移至其区域的质心处，具有线性收敛的速度[18]；然而LIU等[21]提出的quasi-Newton方法加速了质心的优化，具有超线性收敛的速度。

1.3 质心容量限制Power图

在现有的容量限制Power图定义中，对于每个站点的Power单元的容量，都有着明确的限制数值；然而，在某些实际的应用问题中,这些容量限制往往只是给定一个最大阈值或一个区间，在优化过程中，站点的容量不能超出给定的最大阈值或区间。因而，本文聚焦于如何在不确定容量限制条件下计算Power图。

2 变容量限制质心Power图

2.1 问题定义

若站点容量的限制是一个给定的最大阈值或一个区间，此时的容量限制为不等式约束，即VCCPD；若在此基础上再引入质心约束，即可得到VCCCPD。

2.2 求解思路

图2 变容量限制Power图容量优化过程((a)调整权重优化容量；(b)多边形最大内切圆)

2.3 求解算法

本文算法步骤如下：

步骤2. 容量优化，计算Power单元的容量在预设容量限制区间外的站点。

3 实验与算法分析

3.1 参数分析

在本文提出的变容量限制质心Power图算法中，参数的选择对实验的性能会产生重要影响。在调整权重使得站点的容量约束至预设容量区间时，如果参数的取值过大，则在优化过程中站点的权重变化过大，导致在构造Power图时出现某些站点的Power单元为空，影响算法的性能；然而如果参数的取值过小，则权重变化过小，导致容量变化过小，因此需要很多次的迭代才能使其容量约束至预设容量区间内，会导致需要消耗过多的计算时间，从而严重影响了算法的效率。

通过调节参数的取值与实验结果的分析，可以确定参数的取值与站点的数量有关。图3为不同密度条件下，在预设容量限制区间选择不同，分别在40和100个站点时，的取值对变容量限制质心Power图算法计算时间的影响，其中横坐标为常数，纵坐标为计算时间，与横坐标的关系为

图3 参数α的取值对VCCCPD计算的影响

3.2 复杂容量限制适应性分析

为了测试变容量限制质心Power图算法在复杂容量限制下的算法适应性，本文首先在均匀密度下，分别在10，40和100个站点，不同的预设容量限制区间(区间跨度比例大小一致)情况下进行实验，实验结果如图4所示，常密度下该几何域的总容量为1.0。

图4 10，40和100个站点不同预设容量限制区间优化的VCCCPD结果((a)初始化(10站点)；(b)容量限制区间相同(10站点)；(c)容量区间不同(差异小，10站点)；(d)容量区间不同(差异大，10站点)；(e)初始化(40站点)；(f)容量限制区间相同(40站点)；(g)容量区间不同(差异小，40站点)；(h)容量区间不同(差异大，40站点)；(i)初始化(100站点)；(j)容量限制区间相同(100站点)；(k)容量区间不同(差异小，100站点)；(l)容量区间不同(差异大，100站点))

图4(a)，(e)，(i)分别为随机放置10，40和100个站点，得到的初始Power图，此时各站点位置既不在其Power单元的质心，各站点的容量也不满足预设的容量限制区间；图4(b)，(f)，(j)分别为10，40和100个站点等容量限制区间下优化得到的变容量限制质心Power图；图4(c)～(d)，(g)～(h)，(k)～(l)分别为10，40和100个站点容量限制区间不同时优化得到的变容量限制质心Power图。图4中变容量限制质心Power图的预设容量限制区间见表1。

从图4中可以看出，本文算法在不同站点数量下都能有效地优化生成变容量限制质心Power图；同时，针对不同的容量限制区间，本文算法也能取得良好的计算结果。

为了进一步表明本文提出的变容量限制质心Power图算法对复杂容量限制的适应性，图5为常密度下100个站点在区间跨度比例不同的容量限制区间下VCCCPD计算结果，其中容量区大小设置如下：

表1 变容量限制质心Power图的预设容量限制区间

图5 100个站点不同容量限制区间放缩比例下优化的VCCCPD结果

3.3 密度分析

为了测试变容量限制质心Power图算法在各种密度函数下的有效性，本文分别在线性密度(linear density，LD)、非线性高斯密度(non-linear density，NLD)下进行实验，密度函数为

实验中站点的数量选择分别为40个和100个，各站点预设容量限制区间大小相等，分别与图4(f)，(j)保持一致，各种密度函数下实验结果如图6所示。

图6(a)～(d)展示了随机40个站点初始化的Power图，以及在3种不同的密度函数下优化得到的变容量限制质心Power图的结果，其中图6(b)，(f)对应的密度是线性密度LD，图6(c)，(g)对应的密度是非线性的二次多项式密度NLD–1，图6(d)，(h)对应的密度是非线性的高斯密度NLD–2。从图6中的实验结果可以看出，本文提出的变容量质心Power图算法能够较好应用于各种密度函数，并且都能得到良好的优化结果。

3.4 性能分析

3.4.1 算法收敛性分析

本文提出的VCCCPD优化算法目标是求解CCCPD，使得优化后每个站点的容量均在预设容量限制区间内部。首先，对于站点位置，本文通过Lloyd方法优化，每次优化后总能保证各个站点位于其Power单元的质心位置。其次，对于站点容量，从理论分析看，站点的容量与其对应的权重值大小密切相关。当某个站点的权重增大时，其Power单元会向外扩张，从而增大其容量；反之，当某个站点的权重减小时，其Power单元会向内收缩，从而减小其容量。本文算法基于该理论优化容量；通过反复迭代，直到所有的站点的容量均收敛到对应的容量限制区间内。从实验结果看，以常密度下40个站点VCCCPD的优化为例，表2展示了容量限制区间相同和容量限制区间相异时优化得到的VCCCPD结果中站点的容量，从中可以看出，优化后得到的各个站点的容量均能满足预设的限制。

图6 40和100个站点不同密度函数优化的VCCCPD结果((a)初始化(40站点)；(b)线性密度(40站点)；(c)二次多项式密度 (40站点)；(d)非线性高斯密度((40站点))；(e)初始化(100站点)；(f)线性密度(100站点)；(g)二次多项式密度(100站点)；(h) 非线性高斯密度(100站点))

表2 复杂容量限制下优化后的VCCCPD中站点的最终容量

3.4.2 算法计算效率分析

为了进一步更直观地体现VCCCPD算法的高效性，将本文的VCCCPD算法与文献[20]提出的CCCPD算法进行对比，为了保持一致性，实验中几何域选择均为1×1的正方形，中心位置为(0.5,0.5)，密度选择本文中的线性密度LD、非线性的二次多项式密度NLD–1和非线性的高斯密度NLD–2，对比试验结果见表3。其中VCCCPD算法的优化时间为本文3.2和3.3节实验中各种条件下变容量限制质心Power图的优化时间消耗。

从表3中可以看出，随着站点数的增多，算法优化时间消耗逐渐增加，同时如果站点的容量限制区间不同，此时的优化时间消耗也会有所增加，且在不同密度下变容量限制质心Power图的优化时间消耗会高于常密度下变容量限制质心Power图的优化时间。值得注意的是，本文设置的实验算法优化时间均在10 s以内，相较于CCCPD算法拥有较好的时间性能，但是2种算法对容量限制条件的考虑是不同的，CCCPD算法中容量限制为确定的量，而本文的VCCCPD算法中容量限制为给定的区间限制，这在一定程度上放松了对容量的约束，因此VCCCPD算法较CCCPD算法有着更优的时间性能。

表3 VCCCPD与CCCPD算法优化时间消耗对比(s)

3.5 复杂问题域分析

在本文前述的实验中，问题域默认选择 边长为1的正方形区域；然而，在实际的场景中，问题域往往是各种更为复杂的形状。为了验证本文算法在各种复杂问题域下VCCCPD的计算效果，本文选择4种较为复杂的问题域：三角形问题域、十字架形问题域、非凸问题域1和更为复杂的非凸问题域2，优化得到的VCCCPD实验结果如图7所示。在该实验中，站点数量选择为100，密度选择为常密度，容量限制区间调整比例参数选择10%。从图7可以看出，针对较为复杂的问题域，本文算法依然能够有效求解VCCCPD。

图7 100个站点不同问题域下优化的VCCCPD结果((a)三角形问题域；(b)十字型问题域；(c)非凸问题域1；(d)非凸问题域2)

4 结 束语

本文提出一种变容量限制质心Power图的计算方法，能够适用于不同密度、不同容量限制区间下质心Power图的求解；该方法通过调整站点的权重和使用Lloyd法交替迭代优化站点的容量与位置；从而得到满足条件的质心Power图。在不同密度、不同预设容量限制区间下的实验结果表明本文提出的变容量质心Power图的计算方法能够得到精确的Power图，且具有高效、适应性强等优点。但在本文算法中，Power图的计算效率与权重调整密切相关，且如果容量区间过小时计算比较费时，今后将进一步研究更合理的变容量限制下的容量优化方法，提高算法效率。

[1] DU Q, FABER V, GUNZBYRGER M. Centroidal Voronoi tessellations: applications and algorithm[J]. SIAM Review, 1999, 41(4): 637-676.

[2] 郑利平, 刘玉飞, 江婷, 等. 稠密需求下城市应急中心布局方法[J]. 计算机辅助设计与图形学学报, 2014, 26(6): 948-955.

ZHENG L P, LIU Y F, JIANG T, et al. A layout approach of city emergency centers with dense demand[J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(6): 948-955 (in Chinese).

[3] AURENHAMMER F, HOFFMANN F, ARONOV B. Minkowski-type theorems and least-squares clustering[J]. Algorithmica, 1998, 20(1): 61-76.

[4] DE GOES F, BREEDEN K, OSTROMOUKHOV V, et al. Blue noise through optimal transport[J]. ACM Transactions on Graphics, 2012, 31(6): 1-11.

[5] XIAO Y Y, CHEN Z G, CAO J, et al. Optimal Power diagrams via function approximation[J]. Computer Aided Design, 2018, 102(9): 52-60.

[6] DE GOES F, WALLEZ C, HUANG J, et al. Power particles: an incompressible fluid solver based on Power diagrams[J]. ACM Transactions on Graphics, 2015, 34(4): 1-11.

[7] ZHAI X, HOU F, QIN H, et al. Fluid simulation with adaptive staggered Power particles on GPUs[J]. IEEE Transactions on Visualization and Computer Graphics, 2020, 26(6): 2234-2246.

[8] 郑利平, 赵建明, 刘玉飞, 等. 基于几何约束机制的团体操队形辅助设计平台[J]. 计算机辅助设计与图形学学报, 2013, 25(8): 1198-1203.

ZHENG L P, ZHAO J M, LIU Y F, et al. Formation design platform of group calisthenics based on geometry-constrained mechanism[J]. Journal of Computer-Aided Design & Computer Graphics, 2013, 25(8): 1198-1203 (in Chinese).

[9] ZHENG L P, ZHAO J M, CHENG Y J, et al. Geometry constrained crowd formation animation[J]. Computers & Graphics, 2014, 38(1): 268-276.

[10] BOURNE D, ROPER S. Centroidal power diagrams, Lloyd’s algorithm, and applications to optimal location problems[J]. SIAM Journal on Numerical Analysis, 2015, 53(6): 2545-2569.

[11] LI Z, DAI F Q, JIA H M, et al. Research on the methods of multi-airport sector division based on a Power diagram[C]//The 11th International Conference of Chinese Transportation Professionals. Reston: American Society of Civil Engineers, 2011: 3935-3943.

[12] ANDREAS A, ANDREAS B, PETER G, et al. Generalized balanced Power diagrams for 3D representations of polycrystals[J]. Philosophical Magazine, 2014, 95(9): 1016-1028.

[13] AURENHAMMER F. Power diagrams: properties, algorithms and applications[J]. SIAM Journal on Computing, 1987, 16(1): 78-96.

[14] IMAI H, IRI M, MUROTA K. Voronoi diagram in the Laguerre geometry and its applications[J]. SIAM Journal on Computing, 1985, 14(1): 93-105.

[15] 吴壮志, 杨钦, 怀进鹏. Power图的性质及构造算法研究[J]. 计算机辅助设计与图形学学报, 2001, 13(12): 1057-1062.

WU Z Z, YANG Q, HUAI J P. Research on properties of Power diagram and its construction algorithm[J]. Journal of Computer-Aided Design & Computer Graphics, 2001, 13(12): 1057-1062 (in Chinese).

[16] BALZER M, HECK D. Capacity-constrained Voronoi diagrams in finite spaces[C]//The 5th Annual International Symposium on Voronoi Diagrams in Science and Engineering. Heidelberg: Springer, 2008: 44-56.

[17] BALZER M. Capacity-constrained Voronoi diagrams in continuous spaces[C]//The 5th Annual International Symposium on Voronoi Diagrams in Science and Engineering. Heidelberg: Springer, 2008: 79-88.

[18] LLOYD S. Least squares quantization in PCM’s[J]. IEEE Transactions on Information Theory, 1982, 28(2): 129-136.

[19] 郑利平, 江婷, 周乘龙, 等. 基于Power图求解容量限制P-中值问题[J]. 计算机应用, 2015, 35(6): 1623-1627.

ZHENG L P, JIANG T, ZHOU C L, et al. Solving approach of capacity constrained P-median problem based on Power diagram[J]. Journal of Computer Applications, 2015, 35(6): 1623-1627 (in Chinese).

[20] XIN S Q, LEVY B, CHENG Z G, et al. Centroidal power diagrams with capacity constraints: computation, applications, and extension[J]. ACM Transactions on Graphics, 2016, 35(6): 1-12.

[21] LIU Y, WANG W P, LEVY B, et al. On centroidal Voronoi tessellation--Energy smoothness and fast computation[J]. ACM Transactions on Graphics, 2010, 29(4): 1-17.

[22] 郑利平, 郜文灿, 李尚林, 等. 定点容量限制质心Power图生成[J]. 中国图象图形学报, 2016, 21(9): 1229-1237.

ZHENG L P, GAO W C, LI S L, et al. Generation method for a centroidal capacity constrained Power diagram with fixed sites[J]. Journal of Image and Graphics, 2016, 21(9): 1229-1237 (in Chinese).

Computation method of variable capacity constrained centroidal Power diagram

YAO Yu-you, ZHANG Gao-feng, XU Ben-zhu, ZHENG Li-ping

(School of Computer Science and Information Engineering, Hefei University of Technology, Hefei Anhui 230601, China)

The Power diagram, as an extension of the Voronoi diagram, introduces “weight” to each site, and is characteristic of accurate tolerance. By imposing the capacity constraints to the ordinary Power diagram, a capacity-constrained Power diagram can be obtained, where the capacity of each site equates to the preset capacity constraint. The addition of the centroid constraints on a secondary basis can lead to the centroidal capacity-constrained Power diagram, in which the sites are located at its mass centers of the corresponding Power cells. In these Power diagrams, the capacity constraints are clear values. However, the capacity constraints are often intervals in some practical applications. To address this problem, a computation method was proposed for variable capacity-constrained centroidal Power diagram. On the one hand, the method can continuously update the weights of sites to meet the capacity constraints. On the other hand, the Lloyd’s method is applied to the relocation of the sites to its mass centers of the corresponding Power cells. The two steps interfere with each other in the optimization process to compute the centroidal Power diagram with interval capacity constraints. The experimental results demonstrate that the proposed method can stably compute the variable capacity-constrained centroidal Power diagram under different conditions with the advantages in high efficiency and adaptability.

Power diagram; variable capacity-constrained; interval; centroidal; density

TP 391

10.11996/JG.j.2095-302X.2021030492

A

2095-302X(2021)03-0492-09

2020-11-25；

2020-12-02

25 November，2020；

2 December，2020

国家自然科学基金项目(61972128，61702155)

National Natural Science Foundation of China (61972128, 61702155)

姚裕友(1996-)，男，安徽桐城人，博士研究生。主要研究方向为计算机辅助几何设计。E-mail：yaoyy@mail.hfut.edu.cn

YAO Yu-you (1996-), male, PhD candidate. His main research interest covers computer-aided geometric design. E-mail: yaoyy@mail.hfut.edu.cn

郑利平(1978–)，男，安徽合肥人，教授，博士。主要研究方向为可视化、群体和疏散仿真。E-mail：zhenglp@hfut.edu.cn

ZHENG Li-ping (1978–), male, professor, Ph.D. His main research interests cover visualization, crowd and evacuation simulation. E-mail：zhenglp@hfut.edu.cn