龐 慧 王慶林

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

線段2經(jīng)過已知點(diǎn)(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］則兩線段不相交.兩線段可能平行，這時(shí)兩條直線的斜率相等即，平行時(shí)又分為兩種情況平行不重合時(shí)表示可以添加;兩條直線重合時(shí)，舍去.這樣我們就可以通過判斷兩條線段是否相交來添加若干條線段生成元.

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

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

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

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

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

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

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

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