乘權(quán)Voronoi圖的動態(tài)構(gòu)造法

劉 欣，劉穎華，王 輝

(承德石油高等專科學(xué)校社科與數(shù)理部，河北 承德 067000)

1 背景簡介

普通Voronoi圖，是計算幾何的一個重要分支，在計算幾何理論和應(yīng)用中起著重要作用。而完全按照普通Voronoi圖的算法劃分區(qū)域，有很大的局限性。為擴(kuò)展Voronoi圖使其應(yīng)用在更廣泛的領(lǐng)域，在Voronoi圖中引入了權(quán)的概念。在研究全國城鎮(zhèn)體系、討論地理輸送系統(tǒng)以及交通網(wǎng)絡(luò)中被廣泛地應(yīng)用。在確定城市中心功能區(qū)中必不可少地需要引用權(quán)值，因此越來越多的學(xué)者開始研究乘權(quán)Voronoi圖。傳統(tǒng)的算法構(gòu)造乘權(quán)Voronoi圖時，運(yùn)算效率與母點(diǎn)個數(shù)有密切關(guān)系[1-4］。而動態(tài)構(gòu)造算法幾乎與母點(diǎn)個數(shù)無關(guān)，且母點(diǎn)個數(shù)越多，其相對效率越高。進(jìn)行構(gòu)造時，對以不同顏色區(qū)分Voronoi區(qū)域的乘權(quán)Voronoi圖進(jìn)行橫向掃描，在掃描過程中，如果某像素與其后續(xù)像素顏色不同，就將該像素置為指定的顏色(例如黑色);否則置為另一種顏色(例如白色);再進(jìn)行縱向掃描，處理同上。兩次掃描完成后，其結(jié)果便為由指定顏色畫出的乘權(quán)Voronoi圖。

2 定義

2.1 經(jīng)典 Voronoi圖

2.2 乘權(quán) Voronoi圖

乘權(quán)Voronoi圖的乘權(quán)距離定義如下:

我們稱這個距離為乘權(quán)Voronoi距離或MW距離。則平分線為

2.3 動態(tài)的乘權(quán)Voronoi圖的構(gòu)造

現(xiàn)在我們以9個生成元分為例，用離散算法構(gòu)造乘權(quán)Voronoi圖。組圖3顯示了其動態(tài)生成過程。圖3所示括號中的數(shù)字代表該生成元的權(quán)重。首先，我們分配不同的顏色代表不同的生成元點(diǎn)，然后以畫圓圈的點(diǎn)為中心，以生成元乘權(quán)距離為半徑，最后得到乘權(quán)網(wǎng)絡(luò)Voronoi圖。我們把生成元的黑色和分配的其他像素的白色，然后構(gòu)造出乘權(quán)Voronoi圖。

3 結(jié)論

乘權(quán)Voronoi圖的動態(tài)構(gòu)造算法能克服多種缺點(diǎn)，因?yàn)槲覀冎恍枰紤]生成元變化。所以結(jié)果表明，它比傳統(tǒng)的算法更簡單，高效，并且具有較高的理論意義和廣泛的應(yīng)用價值，能較好地解決加權(quán)Voronoi圖在地理信息處理、模式識別、生態(tài)研究、城市規(guī)劃、最優(yōu)化配置等許多領(lǐng)域的問題[5-7］。

[1]張有會，淺也哲夫，小保方幸次.關(guān)于一般圖形Voronoi圖的近似構(gòu)造法的研究[J］.數(shù)值計算與計算機(jī)應(yīng)用，2002，9(3):216－225.

[2]楊秀芬，李濤.公共自行車服務(wù)系統(tǒng)推廣模型[J］.承德石油高等?？茖W(xué)校學(xué)報，2014(6):61－65.

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

[4]周培德，盧開澄.計算幾何算法分析與設(shè)計[M］.北京:清華大學(xué)出版社，2000.

[5]王新生，郭慶勝.Voronoi圖的擴(kuò)展、生成及其應(yīng)用于界定城市空間影響范圍[J］.華中師范大學(xué)學(xué)報(自然科學(xué)版)，2002，36(1):107 －111.

[6]周德培.計算幾何-算法分析與設(shè)計[M］.北京:清華大學(xué)出版社，2000.

[7]楊洋，沈法華，董晶晶，等.多普勒測風(fēng)激光雷達(dá)校準(zhǔn)儀中激光入射和接收角度設(shè)計[J］.中國儀器儀表，2007(12):29－31.