劉 欣,劉穎華,王 輝
(承德石油高等專科學(xué)校社科與數(shù)理部,河北 承德 067000)
普通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圖。
乘權(quán)Voronoi圖的乘權(quán)距離定義如下:
我們稱這個距離為乘權(quán)Voronoi距離或MW距離。則平分線為
現(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圖。
乘權(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.