乘權Voronoi圖的動態構造法

劉 欣，劉穎華，王 輝

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

1 背景簡介

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

2 定義

2.1 經典 Voronoi圖

2.2 乘權 Voronoi圖

乘權Voronoi圖的乘權距離定義如下:

我們稱這個距離為乘權Voronoi距離或MW距離。則平分線為

2.3 動態的乘權Voronoi圖的構造

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

3 結論

乘權Voronoi圖的動態構造算法能克服多種缺點，因為我們只需要考慮生成元變化。所以結果表明，它比傳統的算法更簡單，高效，并且具有較高的理論意義和廣泛的應用價值，能較好地解決加權Voronoi圖在地理信息處理、模式識別、生態研究、城市規劃、最優化配置等許多領域的問題[5-7］。

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

[2]楊秀芬，李濤.公共自行車服務系統推廣模型[J］.承德石油高等專科學校學報，2014(6):61－65.

[3]吳壯志，楊欽，懷進鵬.Power圖的性質及構造算法研究[J］.計算機輔助設計與圖形學學報，2001，13(12):1057－1062.

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

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

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

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