姚裕友，張高峰，徐本柱，鄭利平

變?nèi)萘肯拗瀑|(zhì)心Power圖的計算

姚裕友，張高峰，徐本柱，鄭利平

(合肥工業(yè)大學(xué)計算機(jī)與信息學(xué)院，安徽 合肥 230601)

Power圖作為Voronoi圖的拓展，引入“權(quán)重”使其有著良好的限容特性。對普通Power圖增加容量約束，使得每個站點的容量等于預(yù)設(shè)的容量值，則可以得到容量限制Power圖；在此基礎(chǔ)上，再增加質(zhì)心約束，使每個站點剛好位于對應(yīng)Power區(qū)域的質(zhì)心，進(jìn)一步得到質(zhì)心容量限制Power圖。在質(zhì)心容量限制Power圖中，容量限制條件均有明確的值，然而在某些應(yīng)用中其往往是一個區(qū)間。針對區(qū)間容量限制問題，提出一種變?nèi)萘肯拗瀑|(zhì)心Power圖的計算方法。一方面，該方法通過不斷調(diào)整各站點的權(quán)重以使得站點的容量滿足區(qū)間限制；另一方面，Lloyd方法被用于優(yōu)化各站點的位置到對應(yīng)Power區(qū)域的質(zhì)心；兩者交替迭代優(yōu)化，從而得到滿足區(qū)間容量限制的質(zhì)心Power圖。在不同的密度和不同容量限制區(qū)間下的實驗結(jié)果表明，該方法適用于不同密度下變?nèi)萘肯拗瀑|(zhì)心Power圖的計算，并且具有高效、適應(yīng)性強(qiáng)等優(yōu)點。

Power圖；變?nèi)萘肯拗?；區(qū)間；質(zhì)心；密度

在計算幾何中，Voronoi圖作為一種基礎(chǔ)的幾何結(jié)構(gòu)有著廣泛地應(yīng)用與拓展。DU等[1]在普通的Voronoi圖的基礎(chǔ)上約束站點至質(zhì)心位置，得到基于質(zhì)心的Voronoi圖(centroidal Voronoi tessellation，CVT)；鄭利平等[2]在CVT的基礎(chǔ)上引入容量限制，得到容量限制的質(zhì)心Voronoi圖(capacity constrained centroidal Voronoi tessellation，CCCVT)，并將其應(yīng)用于城市選址布局問題中。然而Voronoi圖因其得到的剖分過于剛性，難以滿足容量限制要求。

AURENHAMMER等[3]對Voronoi圖進(jìn)行拓展得到Power圖，Power圖通過控制每個站點的權(quán)重值來控制站點的容量，從而弱化了Voronoi圖的剛性限制。相較于Voronoi圖，Power圖擁有精確限容的特性，因而在各種實際應(yīng)用中被廣泛使用。在計算機(jī)圖形學(xué)中，Power圖被應(yīng)用于藍(lán)噪生成[4]、模型網(wǎng)格優(yōu)化[5]、流體仿真[6-7]、計算機(jī)動畫[8-9]等；在運(yùn)籌學(xué)中，Power圖被應(yīng)用于解決選址分配問題[10]、扇區(qū)劃分問題[11]等；在材料科學(xué)領(lǐng)域，Power圖亦被應(yīng)用于顆粒結(jié)構(gòu)的表示[12]等。

隨著Power圖概念的提出，研究者們對其進(jìn)行了全面而深入的研究。AURENHAMMER[13]對Power圖的理論和應(yīng)用做了總結(jié)，IMAI等[14]針對平面點集上Power圖的性質(zhì)給出了理論證明。對于Power圖的計算，早期吳壯志等[15]利用正則三角化輔助生成Power圖，但未考慮到容量優(yōu)化問題。BALZER和HECK[16]通過不斷迭代和調(diào)整站點權(quán)重的方法從而達(dá)到容量限制條件，并提出有限域和連續(xù)域下[17]的容量限制Power圖的計算方法，再結(jié)合Lloyd方法[18]優(yōu)化站點從而滿足質(zhì)心限制，從而得到基于質(zhì)心的容量限制Power圖。然而文獻(xiàn)[16]提出的試探法通常需要多次迭代，花費時間較長，鄭利平等[19]在其基礎(chǔ)上改進(jìn)算法，采用解析的方法直接計算權(quán)重值，使其計算效率有了顯著地提升，但仍需采取逐點迭代的優(yōu)化策略。文獻(xiàn)[4]將容量限制看成等式約束條件，通過拉格朗日方法來優(yōu)化Power圖，使用Newton法優(yōu)化權(quán)重，梯度下降法優(yōu)化站點位置，兩者交替進(jìn)行，從而得到質(zhì)心容量限制Power圖(centroidal capacity constrained Power diagram，CCCPD)。XIN等[20]提出一種超線性收斂的CCCPD生成算法，并結(jié)合L-BFGS方法和梯度下降法計算之。

然而，不論是容量限制Power圖(capacity constrained Power diagram，CCPD)還是質(zhì)心容量限制Power圖的研究中，都明確給定了每個站點的限定容量值，但在有些實際應(yīng)用中，站點的限定容量值往往是一個最大閾值或限制區(qū)間，例如城市應(yīng)急救援中心、商品配送中心等，被稱之為變?nèi)萘肯拗芇ower圖(variable capacity constrained Power diagram，VCCPD)。如果對其施加質(zhì)心約束，即可得到變?nèi)萘肯拗瀑|(zhì)心Power圖(variable capacity constrained centroidal Power diagram，VCCCPD)。本文方法聚焦于變?nèi)萘肯拗茥l件下質(zhì)心Power圖的求解，提出一種基于站點Power單元來調(diào)整權(quán)重值的算法用于計算變?nèi)萘肯拗芇ower圖，并結(jié)合Lloyd方法優(yōu)化站點位置滿足質(zhì)心約束，得到變?nèi)萘肯拗瀑|(zhì)心Power圖。

1 相關(guān)工作

1.1 Voronoi圖和Power圖

其中，為歐式距離，特別地，當(dāng)Power圖中所有站點的權(quán)重相等時，此時的Power圖退化為Voronoi圖[13]。

1.2 質(zhì)心Power圖

文獻(xiàn)[1]證明了，根據(jù)站點位置構(gòu)造出的Voronoi圖為質(zhì)心Voronoi圖時，能量函數(shù)()的值最小。

與CVT類似，如果在Power圖中也增加質(zhì)心約束，則稱該P(yáng)ower圖為質(zhì)心Power圖(centroidal Power diagram，CPD)。為了有效地求解CVT和CPD，Lloyd方法作為最為普遍的算法是在每次迭代過程中將站點的位置移至其區(qū)域的質(zhì)心處，具有線性收斂的速度[18]；然而LIU等[21]提出的quasi-Newton方法加速了質(zhì)心的優(yōu)化，具有超線性收斂的速度。

1.3 質(zhì)心容量限制Power圖

在現(xiàn)有的容量限制Power圖定義中，對于每個站點的Power單元的容量，都有著明確的限制數(shù)值；然而，在某些實際的應(yīng)用問題中,這些容量限制往往只是給定一個最大閾值或一個區(qū)間，在優(yōu)化過程中，站點的容量不能超出給定的最大閾值或區(qū)間。因而，本文聚焦于如何在不確定容量限制條件下計算Power圖。

2 變?nèi)萘肯拗瀑|(zhì)心Power圖

2.1 問題定義

若站點容量的限制是一個給定的最大閾值或一個區(qū)間，此時的容量限制為不等式約束，即VCCPD；若在此基礎(chǔ)上再引入質(zhì)心約束，即可得到VCCCPD。

2.2 求解思路

圖2 變?nèi)萘肯拗芇ower圖容量優(yōu)化過程((a)調(diào)整權(quán)重優(yōu)化容量；(b)多邊形最大內(nèi)切圓)

2.3 求解算法

本文算法步驟如下：

步驟2. 容量優(yōu)化，計算Power單元的容量在預(yù)設(shè)容量限制區(qū)間外的站點。

3 實驗與算法分析

3.1 參數(shù)分析

在本文提出的變?nèi)萘肯拗瀑|(zhì)心Power圖算法中，參數(shù)的選擇對實驗的性能會產(chǎn)生重要影響。在調(diào)整權(quán)重使得站點的容量約束至預(yù)設(shè)容量區(qū)間時，如果參數(shù)的取值過大，則在優(yōu)化過程中站點的權(quán)重變化過大，導(dǎo)致在構(gòu)造Power圖時出現(xiàn)某些站點的Power單元為空，影響算法的性能；然而如果參數(shù)的取值過小，則權(quán)重變化過小，導(dǎo)致容量變化過小，因此需要很多次的迭代才能使其容量約束至預(yù)設(shè)容量區(qū)間內(nèi)，會導(dǎo)致需要消耗過多的計算時間，從而嚴(yán)重影響了算法的效率。

通過調(diào)節(jié)參數(shù)的取值與實驗結(jié)果的分析，可以確定參數(shù)的取值與站點的數(shù)量有關(guān)。圖3為不同密度條件下，在預(yù)設(shè)容量限制區(qū)間選擇不同，分別在40和100個站點時，的取值對變?nèi)萘肯拗瀑|(zhì)心Power圖算法計算時間的影響，其中橫坐標(biāo)為常數(shù)，縱坐標(biāo)為計算時間，與橫坐標(biāo)的關(guān)系為

圖3 參數(shù)α的取值對VCCCPD計算的影響

3.2 復(fù)雜容量限制適應(yīng)性分析

為了測試變?nèi)萘肯拗瀑|(zhì)心Power圖算法在復(fù)雜容量限制下的算法適應(yīng)性，本文首先在均勻密度下，分別在10，40和100個站點，不同的預(yù)設(shè)容量限制區(qū)間(區(qū)間跨度比例大小一致)情況下進(jìn)行實驗，實驗結(jié)果如圖4所示，常密度下該幾何域的總?cè)萘繛?.0。

圖4 10，40和100個站點不同預(yù)設(shè)容量限制區(qū)間優(yōu)化的VCCCPD結(jié)果((a)初始化(10站點)；(b)容量限制區(qū)間相同(10站點)；(c)容量區(qū)間不同(差異小，10站點)；(d)容量區(qū)間不同(差異大，10站點)；(e)初始化(40站點)；(f)容量限制區(qū)間相同(40站點)；(g)容量區(qū)間不同(差異小，40站點)；(h)容量區(qū)間不同(差異大，40站點)；(i)初始化(100站點)；(j)容量限制區(qū)間相同(100站點)；(k)容量區(qū)間不同(差異小，100站點)；(l)容量區(qū)間不同(差異大，100站點))

圖4(a)，(e)，(i)分別為隨機(jī)放置10，40和100個站點，得到的初始Power圖，此時各站點位置既不在其Power單元的質(zhì)心，各站點的容量也不滿足預(yù)設(shè)的容量限制區(qū)間；圖4(b)，(f)，(j)分別為10，40和100個站點等容量限制區(qū)間下優(yōu)化得到的變?nèi)萘肯拗瀑|(zhì)心Power圖；圖4(c)～(d)，(g)～(h)，(k)～(l)分別為10，40和100個站點容量限制區(qū)間不同時優(yōu)化得到的變?nèi)萘肯拗瀑|(zhì)心Power圖。圖4中變?nèi)萘肯拗瀑|(zhì)心Power圖的預(yù)設(shè)容量限制區(qū)間見表1。

從圖4中可以看出，本文算法在不同站點數(shù)量下都能有效地優(yōu)化生成變?nèi)萘肯拗瀑|(zhì)心Power圖；同時，針對不同的容量限制區(qū)間，本文算法也能取得良好的計算結(jié)果。

為了進(jìn)一步表明本文提出的變?nèi)萘肯拗瀑|(zhì)心Power圖算法對復(fù)雜容量限制的適應(yīng)性，圖5為常密度下100個站點在區(qū)間跨度比例不同的容量限制區(qū)間下VCCCPD計算結(jié)果，其中容量區(qū)大小設(shè)置如下：

表1 變?nèi)萘肯拗瀑|(zhì)心Power圖的預(yù)設(shè)容量限制區(qū)間

圖5 100個站點不同容量限制區(qū)間放縮比例下優(yōu)化的VCCCPD結(jié)果

3.3 密度分析

為了測試變?nèi)萘肯拗瀑|(zhì)心Power圖算法在各種密度函數(shù)下的有效性，本文分別在線性密度(linear density，LD)、非線性高斯密度(non-linear density，NLD)下進(jìn)行實驗，密度函數(shù)為

實驗中站點的數(shù)量選擇分別為40個和100個，各站點預(yù)設(shè)容量限制區(qū)間大小相等，分別與圖4(f)，(j)保持一致，各種密度函數(shù)下實驗結(jié)果如圖6所示。

圖6(a)～(d)展示了隨機(jī)40個站點初始化的Power圖，以及在3種不同的密度函數(shù)下優(yōu)化得到的變?nèi)萘肯拗瀑|(zhì)心Power圖的結(jié)果，其中圖6(b)，(f)對應(yīng)的密度是線性密度LD，圖6(c)，(g)對應(yīng)的密度是非線性的二次多項式密度NLD–1，圖6(d)，(h)對應(yīng)的密度是非線性的高斯密度NLD–2。從圖6中的實驗結(jié)果可以看出，本文提出的變?nèi)萘抠|(zhì)心Power圖算法能夠較好應(yīng)用于各種密度函數(shù)，并且都能得到良好的優(yōu)化結(jié)果。

3.4 性能分析

3.4.1 算法收斂性分析

本文提出的VCCCPD優(yōu)化算法目標(biāo)是求解CCCPD，使得優(yōu)化后每個站點的容量均在預(yù)設(shè)容量限制區(qū)間內(nèi)部。首先，對于站點位置，本文通過Lloyd方法優(yōu)化，每次優(yōu)化后總能保證各個站點位于其Power單元的質(zhì)心位置。其次，對于站點容量，從理論分析看，站點的容量與其對應(yīng)的權(quán)重值大小密切相關(guān)。當(dāng)某個站點的權(quán)重增大時，其Power單元會向外擴(kuò)張，從而增大其容量；反之，當(dāng)某個站點的權(quán)重減小時，其Power單元會向內(nèi)收縮，從而減小其容量。本文算法基于該理論優(yōu)化容量；通過反復(fù)迭代，直到所有的站點的容量均收斂到對應(yīng)的容量限制區(qū)間內(nèi)。從實驗結(jié)果看，以常密度下40個站點VCCCPD的優(yōu)化為例，表2展示了容量限制區(qū)間相同和容量限制區(qū)間相異時優(yōu)化得到的VCCCPD結(jié)果中站點的容量，從中可以看出，優(yōu)化后得到的各個站點的容量均能滿足預(yù)設(shè)的限制。

圖6 40和100個站點不同密度函數(shù)優(yōu)化的VCCCPD結(jié)果((a)初始化(40站點)；(b)線性密度(40站點)；(c)二次多項式密度 (40站點)；(d)非線性高斯密度((40站點))；(e)初始化(100站點)；(f)線性密度(100站點)；(g)二次多項式密度(100站點)；(h) 非線性高斯密度(100站點))

表2 復(fù)雜容量限制下優(yōu)化后的VCCCPD中站點的最終容量

3.4.2 算法計算效率分析

為了進(jìn)一步更直觀地體現(xiàn)VCCCPD算法的高效性，將本文的VCCCPD算法與文獻(xiàn)[20]提出的CCCPD算法進(jìn)行對比，為了保持一致性，實驗中幾何域選擇均為1×1的正方形，中心位置為(0.5,0.5)，密度選擇本文中的線性密度LD、非線性的二次多項式密度NLD–1和非線性的高斯密度NLD–2，對比試驗結(jié)果見表3。其中VCCCPD算法的優(yōu)化時間為本文3.2和3.3節(jié)實驗中各種條件下變?nèi)萘肯拗瀑|(zhì)心Power圖的優(yōu)化時間消耗。

從表3中可以看出，隨著站點數(shù)的增多，算法優(yōu)化時間消耗逐漸增加，同時如果站點的容量限制區(qū)間不同，此時的優(yōu)化時間消耗也會有所增加，且在不同密度下變?nèi)萘肯拗瀑|(zhì)心Power圖的優(yōu)化時間消耗會高于常密度下變?nèi)萘肯拗瀑|(zhì)心Power圖的優(yōu)化時間。值得注意的是，本文設(shè)置的實驗算法優(yōu)化時間均在10 s以內(nèi)，相較于CCCPD算法擁有較好的時間性能，但是2種算法對容量限制條件的考慮是不同的，CCCPD算法中容量限制為確定的量，而本文的VCCCPD算法中容量限制為給定的區(qū)間限制，這在一定程度上放松了對容量的約束，因此VCCCPD算法較CCCPD算法有著更優(yōu)的時間性能。

表3 VCCCPD與CCCPD算法優(yōu)化時間消耗對比(s)

3.5 復(fù)雜問題域分析

在本文前述的實驗中，問題域默認(rèn)選擇 邊長為1的正方形區(qū)域；然而，在實際的場景中，問題域往往是各種更為復(fù)雜的形狀。為了驗證本文算法在各種復(fù)雜問題域下VCCCPD的計算效果，本文選擇4種較為復(fù)雜的問題域：三角形問題域、十字架形問題域、非凸問題域1和更為復(fù)雜的非凸問題域2，優(yōu)化得到的VCCCPD實驗結(jié)果如圖7所示。在該實驗中，站點數(shù)量選擇為100，密度選擇為常密度，容量限制區(qū)間調(diào)整比例參數(shù)選擇10%。從圖7可以看出，針對較為復(fù)雜的問題域，本文算法依然能夠有效求解VCCCPD。

圖7 100個站點不同問題域下優(yōu)化的VCCCPD結(jié)果((a)三角形問題域；(b)十字型問題域；(c)非凸問題域1；(d)非凸問題域2)

4 結(jié) 束語

本文提出一種變?nèi)萘肯拗瀑|(zhì)心Power圖的計算方法，能夠適用于不同密度、不同容量限制區(qū)間下質(zhì)心Power圖的求解；該方法通過調(diào)整站點的權(quán)重和使用Lloyd法交替迭代優(yōu)化站點的容量與位置；從而得到滿足條件的質(zhì)心Power圖。在不同密度、不同預(yù)設(shè)容量限制區(qū)間下的實驗結(jié)果表明本文提出的變?nèi)萘抠|(zhì)心Power圖的計算方法能夠得到精確的Power圖，且具有高效、適應(yīng)性強(qiáng)等優(yōu)點。但在本文算法中，Power圖的計算效率與權(quán)重調(diào)整密切相關(guān)，且如果容量區(qū)間過小時計算比較費時，今后將進(jìn)一步研究更合理的變?nèi)萘肯拗葡碌娜萘績?yōu)化方法，提高算法效率。

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

[2] 鄭利平, 劉玉飛, 江婷, 等. 稠密需求下城市應(yīng)急中心布局方法[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 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ī)制的團(tuán)體操隊形輔助設(shè)計平臺[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 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] 吳壯志, 楊欽, 懷進(jìn)鵬. Power圖的性質(zhì)及構(gòu)造算法研究[J]. 計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報, 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]. 計算機(jī)應(yīng)用, 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] 鄭利平, 郜文燦, 李尚林, 等. 定點容量限制質(zhì)心Power圖生成[J]. 中國圖象圖形學(xué)報, 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

國家自然科學(xué)基金項目(61972128，61702155)

National Natural Science Foundation of China (61972128, 61702155)

姚裕友(1996-)，男，安徽桐城人，博士研究生。主要研究方向為計算機(jī)輔助幾何設(shè)計。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