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

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

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

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

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

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

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

在計(jì)算幾何中，Voronoi圖作為一種基礎(chǔ)的幾何結(jié)構(gòu)有著廣泛地應(yīng)用與拓展。DU等[1]在普通的Voronoi圖的基礎(chǔ)上約束站點(diǎn)至質(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圖通過控制每個(gè)站點(diǎn)的權(quán)重值來控制站點(diǎn)的容量，從而弱化了Voronoi圖的剛性限制。相較于Voronoi圖，Power圖擁有精確限容的特性，因而在各種實(shí)際應(yīng)用中被廣泛使用。在計(jì)算機(jī)圖形學(xué)中，Power圖被應(yīng)用于藍(lán)噪生成[4]、模型網(wǎng)格優(yōu)化[5]、流體仿真[6-7]、計(jì)算機(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]針對平面點(diǎn)集上Power圖的性質(zhì)給出了理論證明。對于Power圖的計(jì)算，早期吳壯志等[15]利用正則三角化輔助生成Power圖，但未考慮到容量優(yōu)化問題。BALZER和HECK[16]通過不斷迭代和調(diào)整站點(diǎn)權(quán)重的方法從而達(dá)到容量限制條件，并提出有限域和連續(xù)域下[17]的容量限制Power圖的計(jì)算方法，再結(jié)合Lloyd方法[18]優(yōu)化站點(diǎn)從而滿足質(zhì)心限制，從而得到基于質(zhì)心的容量限制Power圖。然而文獻(xiàn)[16]提出的試探法通常需要多次迭代，花費(fèi)時(shí)間較長，鄭利平等[19]在其基礎(chǔ)上改進(jìn)算法，采用解析的方法直接計(jì)算權(quán)重值，使其計(jì)算效率有了顯著地提升，但仍需采取逐點(diǎn)迭代的優(yōu)化策略。文獻(xiàn)[4]將容量限制看成等式約束條件，通過拉格朗日方法來優(yōu)化Power圖，使用Newton法優(yōu)化權(quán)重，梯度下降法優(yōu)化站點(diǎn)位置，兩者交替進(jìn)行，從而得到質(zhì)心容量限制Power圖(centroidal capacity constrained Power diagram，CCCPD)。XIN等[20]提出一種超線性收斂的CCCPD生成算法，并結(jié)合L-BFGS方法和梯度下降法計(jì)算之。

然而，不論是容量限制Power圖(capacity constrained Power diagram，CCPD)還是質(zhì)心容量限制Power圖的研究中，都明確給定了每個(gè)站點(diǎn)的限定容量值，但在有些實(shí)際應(yīng)用中，站點(diǎn)的限定容量值往往是一個(gè)最大閾值或限制區(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圖的求解，提出一種基于站點(diǎn)Power單元來調(diào)整權(quán)重值的算法用于計(jì)算變?nèi)萘肯拗芇ower圖，并結(jié)合Lloyd方法優(yōu)化站點(diǎn)位置滿足質(zhì)心約束，得到變?nèi)萘肯拗瀑|(zhì)心Power圖。

1 相關(guān)工作

1.1 Voronoi圖和Power圖

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

1.2 質(zhì)心Power圖

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

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

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

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

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

2.1 問題定義

若站點(diǎn)容量的限制是一個(gè)給定的最大閾值或一個(gè)區(qū)間，此時(shí)的容量限制為不等式約束，即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)化，計(jì)算Power單元的容量在預(yù)設(shè)容量限制區(qū)間外的站點(diǎn)。

3 實(shí)驗(yàn)與算法分析

3.1 參數(shù)分析

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

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

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

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

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

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

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

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

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

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

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

3.3 密度分析

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

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

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

3.4 性能分析

3.4.1 算法收斂性分析

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

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

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

3.4.2 算法計(jì)算效率分析

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

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

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

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

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

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

4 結(jié) 束語

本文提出一種變?nèi)萘肯拗瀑|(zhì)心Power圖的計(jì)算方法，能夠適用于不同密度、不同容量限制區(qū)間下質(zhì)心Power圖的求解；該方法通過調(diào)整站點(diǎn)的權(quán)重和使用Lloyd法交替迭代優(yōu)化站點(diǎn)的容量與位置；從而得到滿足條件的質(zhì)心Power圖。在不同密度、不同預(yù)設(shè)容量限制區(qū)間下的實(shí)驗(yàn)結(jié)果表明本文提出的變?nèi)萘抠|(zhì)心Power圖的計(jì)算方法能夠得到精確的Power圖，且具有高效、適應(yīng)性強(qiáng)等優(yōu)點(diǎn)。但在本文算法中，Power圖的計(jì)算效率與權(quán)重調(diào)整密切相關(guān)，且如果容量區(qū)間過小時(shí)計(jì)算比較費(fèi)時(shí)，今后將進(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ì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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)體操隊(duì)形輔助設(shè)計(jì)平臺[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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ì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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ì)算機(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] 鄭利平, 郜文燦, 李尚林, 等. 定點(diǎn)容量限制質(zhì)心Power圖生成[J]. 中國圖象圖形學(xué)報(bào), 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é)基金項(xiàng)目(61972128，61702155)

National Natural Science Foundation of China (61972128, 61702155)

姚裕友(1996-)，男，安徽桐城人，博士研究生。主要研究方向?yàn)橛?jì)算機(jī)輔助幾何設(shè)計(jì)。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–)，男，安徽合肥人，教授，博士。主要研究方向?yàn)榭梢暬?、群體和疏散仿真。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