龐 慧 王慶林

(河北建筑工程學(xué)院，河北張家口075024)

0 引言

計算幾何是計算機(jī)科學(xué)領(lǐng)域中極有生命力的子領(lǐng)域.它是隨著計算機(jī)的發(fā)展起來的一門學(xué)科.由于計算幾何應(yīng)用范圍很廣泛所以被越來越多的學(xué)者研究、推廣、應(yīng)用.該學(xué)科主要研究計算幾何中的算法及其效率問題.其研究成果已在計算機(jī)圖形學(xué)、化學(xué)、統(tǒng)計分析、模式識別、地理信息系統(tǒng)以及其他許多領(lǐng)域中得到了廣泛的應(yīng)用.Voronoi圖是一種平面分割圖，它的剖分結(jié)果能夠很好地表達(dá)點與點之間的鄰近關(guān)系以及點的影響范圍等重要的空間信息.在計算幾何中，Voronoi圖理論上成功地解決了找最近點、求最大空圓、求最小樹等問題.另外Voronoi圖還被廣泛地應(yīng)用于計算機(jī)輔助設(shè)計、地理信息處理、計算機(jī)圖形學(xué)、模式識別、機(jī)器人、生態(tài)研究、城市規(guī)劃、最優(yōu)配置、物理、化學(xué)等方面.如校區(qū)的合理劃分問題;公交車站牌設(shè)置問題;移動設(shè)施服務(wù)點的最優(yōu)配置、基站配置與信號測試點選址問題等等.而線段為生成元的加權(quán)Voronoi圖在地理信息系統(tǒng)及城市規(guī)劃等方面有著重要應(yīng)用.如:綠化區(qū)域的劃分，凈化能力分析，交通道路規(guī)劃等等.本文即利用線段加權(quán)Voronoi圖來解決綠化帶分布問題.

1 加權(quán)Voronoi圖和線段加權(quán)voronoi圖

加權(quán)Voronoi圖是點生成元加權(quán)Voronoi圖的簡稱.它的定義為定義1.1

定義1.1 設(shè)pi(i=1，2，…，n)為二維歐氏空間(平面)上的n個互不相同的點，λi(i=1，2，…，n)是給定的n個正實數(shù)，稱

為點pi的權(quán)重為λi的Voronoi區(qū)域，其中d(p，pi)為p和pi間的Euclid距離.

如果i≠j時非空且非單點集，則稱為pi和pj間的加權(quán)Voronoi邊，其中是vn(pj，λj)的閉包.兩條以上Voronoi邊的交點，稱為加權(quán)Voronoi點也就是加權(quán) Voronoi區(qū)域的頂點.將vn(pi，λi)(i=1，2……，n)及其邊界，稱為以pi(i=1，2，……，n)為生成元，λi(i=1，2，……，n)為權(quán)重的點生成元上加權(quán)的Voronoi圖，通常簡稱為加權(quán)Voronoi圖.

將加權(quán)Voronoi圖的生成元由點擴(kuò)展為線段，就得到了線段加權(quán)Voronoi圖.線段加權(quán)Voronoi圖的定義

定義1.2 設(shè)Li(i=1，2，……，n)為二維歐氏空間(平面)上的n條互不相交的線段，λi(i=1，2，……，n)是給定的個正實數(shù)，稱為L的權(quán)重為λ 的Voronoi多ij邊形，其中為點p和p＇間的歐氏距離.稱 λi為線段Li的權(quán)重.由vn(Li，λi)i(i=1，2，……n)確定的對平面的分割稱為線段加權(quán)的Voronoi圖.

2 線段加權(quán)voronoi圖的離散生成

2.1 判斷新添加的線段是否與已有線段相交

將生成元推廣至線段后，首先遇到的問題就是如何生成互不相交的若干條線段生成元.那么具體函數(shù)的做法是:先畫出兩條線段來，判斷其是否相交，相交則舍去，不相交則添加.再添加第三條線段時，用同樣的方法可以判斷出它是否與前兩條相交，以此類推即可.可用下面方法來判斷兩條線段是否相交.

線段1經(jīng)過已知點(x10，y10)，(x11，y11)其參數(shù)方程為

線段2經(jīng)過已知點(x20，y20)，(x21，y21)其參數(shù)方程為

線段1和線段2解以x，y，t1，t2為參數(shù)的四元一次方程組并確定t1，t2的范圍，如果t1∈［0，1］且t2∈［0，1］，那么兩線段相交;如果t1?［0，1］或t≠?［0，1］或t1，t2?［0，1］則兩線段不相交.兩線段可能平行，這時兩條直線的斜率相等即，平行時又分為兩種情況平行不重合時表示可以添加;兩條直線重合時，舍去.這樣我們就可以通過判斷兩條線段是否相交來添加若干條線段生成元.

2.2 線段加權(quán)Voronoi圖離散生成法的基本思想

用離散生成法畫線段加權(quán)Voronoi圖的基本思想是:首先，對每一條線段生成元指定一種顏色，使不同線段生成元之間的顏色互不相同，并且給每條線段生成元賦以權(quán)重值;然后，在各個生成元的邊界上選取具有代表性的點，稱為母點，如圖1所示.最后，對每個母點，以母點為圓心，用母點所在線段生成元的顏色，以各母點所在線段生成元的權(quán)重逐漸向外擴(kuò)展畫圓.同一線段生成元上母點的顏色以及擴(kuò)展速度是相同的.當(dāng)屏幕上所有的像素都畫上了顏色時，結(jié)束.此時不同顏色區(qū)域的邊界即為線段加權(quán)Voronoi圖的近似曲線，如圖2所示.當(dāng)母點充分密集時，這種近似效果可達(dá)到很高的程度.

3 線段加權(quán)voronoi圖權(quán)重的確定

當(dāng)有多個因素來確定權(quán)值時需要用層次分析法來進(jìn)行計算.我們以公園或綠化帶的選址為例.每個綠化帶空氣凈化影響區(qū)域受綠化帶自身面積、植物類型、周邊污染源污染程度影響，層次模型如圖3所示.評估專家分別對四個參評綠化帶的三個主要因素進(jìn)行評分后，填寫比較表，構(gòu)成判斷矩陣.

經(jīng)過計算后五個影響因素的權(quán)重比例如表1所示

表1 各影響因素權(quán)重表

四個綠化帶的各自權(quán)重如表2所示

表2 四個綠化帶的權(quán)重表

4 線段加權(quán)Voronoi圖在綠化帶選址中的應(yīng)用

根據(jù)層次分析法所得到的權(quán)值由于差距不大這樣會造成在生成加權(quán)voronoi圖時畫圓速度差別不大.為使得這種差別體現(xiàn)得更為明顯，表2中的權(quán)值分別乘以100作為每個綠化帶的權(quán)重.圖4中線段是將綠化帶抽象為線段后的選址位置，以這個位置為生成元，以表2權(quán)值的100倍為權(quán)值，利用離散的方法生成線段加權(quán)Voronoi圖的區(qū)域劃分結(jié)果如圖5所示

從圖5的結(jié)果進(jìn)行分析，voronoi點離綠化帶遠(yuǎn)的區(qū)域是目前綠化帶凈化空氣難以到達(dá)的區(qū)域.在將來進(jìn)行綠化帶選址時首先考慮的增加綠化設(shè)施的區(qū)域即是這些離目前綠化帶遠(yuǎn)的這些區(qū)域.

5 結(jié)束語

本文首先對Voronoi圖與線段加權(quán)Voronoi圖的基本知識進(jìn)行了簡單介紹，然后給出了一種離散法實現(xiàn)線段加權(quán)Voronoi圖.線段加權(quán)Voronoi的權(quán)重是綜合多種因素而得到的權(quán)重，權(quán)重是利用層次分析法而確定的，權(quán)重值更為準(zhǔn)確.線段加權(quán)Voronoi區(qū)域面積本身是更符合生活實際的面積.將綠化區(qū)域抽象為線段后作為生成元生成線段加權(quán)Voronoi，其綠化區(qū)域即為每個Voronoi區(qū)域，可以非常明確地看出那些區(qū)域需要加強(qiáng)新的綠化區(qū)域.這樣可以使得規(guī)劃部門有目的地進(jìn)行新增綠化區(qū)域的選址.

［1］周培德，盧開澄.計算幾何——算法分析與設(shè)計［M］.北京:清華大學(xué)出版社，廣西科學(xué)技術(shù)出版社，2000

［2］趙曄，張有會等.關(guān)于一般圖形 Voronoi圖的離散構(gòu)造法的研究［J］.計算機(jī)應(yīng)用與軟件.Vol 21 No.6，2004，6

［3］許樹柏.層次分析法原理［M］.天津:天津出版社，1998

［4］董蕊，張有會等.線段加權(quán)Voronoi圖的離散生成算法的研究與實現(xiàn)［J］.計算機(jī)應(yīng)用與軟件，2009，7

［5］趙志輝、張有會等.線段障礙Voronoi圖的離散生成［J］.計算機(jī)應(yīng)用與軟件，2004

［6］陳軍.Voronoi動態(tài)空間數(shù)據(jù)模型［M］.北京:測繪出版社，2002