Power圖掃描生成算法研究

弓小影 張有會 王丹丹

1. 石家莊經(jīng)濟學(xué)院數(shù)理學(xué)院, 河北 石家莊 050031

2. 河北師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院, 河北 石家莊 050016

引言

Voronoi圖[1]是計算幾何的一個重要分支，它是針對一個有限點集，以點作為生成元(或母點)按照一定規(guī)則將平面分割成若干小區(qū)域，這種分割圖形在表達點與點之間的位置關(guān)系以及點的影響區(qū)域等空間信息時很有優(yōu)勢。考慮到生成元會具有不同的性質(zhì)，因此有必要考慮給生成元加權(quán)。Power圖就是對每個生成元加權(quán)，并且將歐式距離推廣為Power距離[2]而生成的Voronoi圖。

Power圖的傳統(tǒng)構(gòu)造方法有正則三角化構(gòu)造法[2]和近些年提出的離散生成法[3]等.這些算法均對構(gòu)造Power圖做出過歷史性的貢獻，但它們在程序設(shè)計思路或數(shù)據(jù)結(jié)構(gòu)等方面還略顯復(fù)雜。因此，我們力求尋找一種程序設(shè)計思路簡潔，輔助數(shù)據(jù)結(jié)構(gòu)簡單，且能保證圖形效果的算法，下面就給出Power的掃描生成算法。

1 Power圖的定義 [4]

圖1 Power圖

Power圖有許多良好性質(zhì)，具體參見文獻[3]及[5]，不再贅述。

2 Power圖的掃描生成算法

2.1 算法的基本思想

由Power圖的定義，關(guān)鍵將生成元的Power邊畫出來即可，如果將到相鄰兩個母點(生成元)的Power距離相等的點逐個畫出，就可以直接畫出Power邊，進而生成Power圖.該算法具體描述為：任意取屏幕上的像素點 ，計算點到個生成元的Power距離，從這個距離數(shù)值中找出兩個最小距離和次最小距離記錄下來，如果次最小距離和最小距離之差小于事先指定的某閾值，則畫出點，否則就不畫，繼續(xù)判斷屏幕上下一個像素點是否符合上述條件.當(dāng)掃描完屏幕上的所有像素點后，便可以生成Power圖。

2.2 掃描生成算法的具體描述

算法具體如下；

2.3 算法中的關(guān)鍵技術(shù)：考慮相鄰生成元間的距離對Power圖的影響

下面證明：兩個相鄰生成元之間的距離大小會影響到Power邊上的任意一點到這兩個生成元的Power距離差。

圖2

圖3

圖4 生成元距離對Power圖的影響

圖5 考慮M因素后生成的Power圖

上述已經(jīng)證明兩相鄰生成元間的距離在生成Power圖時，對Power圖會產(chǎn)生影響，因此，設(shè)置的閾值應(yīng)與相鄰兩個生成元之間的距離有關(guān)，具體做法如下：

2.4 作圖實例（用VC＋＋6.0實現(xiàn)）

在Visual C++6.0[6]環(huán)境下，本文提供的算法已經(jīng)編程實現(xiàn)，圖6就是由該算法生成Power圖的過程圖例，其中各生成元的坐標(biāo)由隨機產(chǎn)生，權(quán)重由隨機產(chǎn)生。

圖6 掃描法生成Power圖的過程圖

3 Power圖的應(yīng)用實例[7][8][9][10]

下面以石家莊市東南區(qū)域公園分布為例，以公園作為生成元，賦予不同的權(quán)值，利用掃描生成算法構(gòu)造Power圖，通過Power模型分析每個公園控制區(qū)域。

圖7是石家莊電子地圖（2012年版）的一部分，圖中標(biāo)示出了石家莊市東南區(qū)域有五個公園。

圖7 石家莊東南部公園分布圖

隨著人們生活水平的提高，保健意識的增強，公園日益成為人們生活離不開的場所，去公園遛彎、鍛煉一般會選擇平面距離比較近的，因此，平面歐氏距離會影響公園的影響區(qū)域。同時，公園的環(huán)境、鍛煉器材、服務(wù)設(shè)施等也會影響居民的選擇，將這些因素綜合考慮作為公園的影響能力，用不同的權(quán)值代表，這樣就可以將公園抽象為點生成元，進而構(gòu)造出Power圖，結(jié)果如圖8所示，圖中黑點代表公園，數(shù)字代表每個公園不同的權(quán)值。

圖8 以公園為生成元生成的Power圖

由Power圖理論，權(quán)值較大的生成元的覆蓋區(qū)域應(yīng)較大，但由圖8可見，希望綠洲公園權(quán)值較大(因該公園設(shè)施較全、環(huán)境很好、附近居民區(qū)很多，故用較大的權(quán)值來代表這些因素)，但它的覆蓋區(qū)域卻較小，這樣就造成了附近居民比如想去那的健身器材鍛煉，會出現(xiàn)人較多，需要等待，或者去那遛彎人很多，難于找到地方休息等等局面的出現(xiàn)，或者要去較遠的公園，從這個意義上來說，現(xiàn)有公園的布局不能滿足人們的生活需求，在東南角區(qū)域應(yīng)再增加公園。好在現(xiàn)在市政府已經(jīng)意識到這一問題，修建了或正在籌建公園、綠地滿足居民的需求，同時提高人民的生活質(zhì)量。

4 結(jié)語

本文在其他專家工作基礎(chǔ)上給出了Power圖的一種新算法—掃描生成法，該算法簡潔易懂，不需要復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。作為該算法的應(yīng)用，以石家莊市東南區(qū)域公園為抽象的生成元點集，構(gòu)造了Power圖，并依據(jù)Power圖理論，分析了各公園的覆蓋區(qū)域以及影響。

[1]Sugihara K. Voronoi Diagrams[M]. Department of Mathematical Engineering and Information Physics University of Tokyo, Hongo, Bunkyoku 113-8656.

[2]趙曄、張有會等. Power圖的離散生成[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報，2003，9： 1181-1184.

[3]吳壯志,楊欽,懷進鵬. Power圖的性質(zhì)及構(gòu)造算法研究[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報,2001,13(12):1057-1062.

[4]弓小影.Power圖掃面生成算法的研究[D].河北師范大學(xué)碩士學(xué)位論文，2007.

[5]IMAI H, IRI M, UROTA KM. Voronoi diagram in the Laguerre geometry and Its application[J]. SIAM Journal on Computing, 1985,(14)1:93-105.

[6]王萍.C++面向?qū)ο蟪绦蛟O(shè)計[M]，北京：清華大學(xué)出版社，2002.

[7]馬立玲，張有會.分區(qū)加權(quán)Voronoi圖的性質(zhì)及其面積計算[J].計算機科學(xué)，2011，2：195-198.

[8]王勝男，閆衛(wèi)陽. 基于Voronoi 圖的洛陽城市綠地系統(tǒng)分析與設(shè)計[J]. 河南大學(xué)學(xué)報，2009，1：42-46.

[9]張偉松. 基于Voronoi圖的數(shù)字電視地面廣播臺站選址分析[D].北京：中國測繪科學(xué)研究院碩士學(xué)位論文, 2011.

[10]劉金義,趙爽. Voronoi 圖應(yīng)用綜述.工程圖學(xué)學(xué)報,2004,2:125-132. .