多目標(biāo)緩沖區(qū)生成算法

白 帆,張福浩

(1.蘭州交通大學(xué),甘肅 蘭州730070 2.中國(guó)測(cè)繪科學(xué)研究院,北京100083)

0 引 言

緩沖區(qū)分析是地理信息系統(tǒng)重要和基本的空間操作功能之一[1]。其實(shí)現(xiàn)的功能就是在給定的地理實(shí)體集合周圍建立起一定距離的多邊形,以代表該地理實(shí)體集合對(duì)周圍物體環(huán)境的影響范圍及程度。緩沖區(qū)分析是GIS空間分析中基本的功能之一,是很多空間分析方法的基礎(chǔ)?？臻g分析是基于地理實(shí)體的位置和形態(tài)特征而獲取新的空間信息的數(shù)據(jù)分析方法。緩沖區(qū)分析廣泛應(yīng)用在地理信息系統(tǒng)的各種分析中,例如在水污染監(jiān)測(cè)、城市規(guī)劃與管理、地震災(zāi)害和損失估計(jì)、洪水災(zāi)害分析、礦產(chǎn)資源評(píng)估、道路交通管理、地形地貌分析等領(lǐng)域都有廣泛應(yīng)用[2-3],如評(píng)估城市中道路的噪聲對(duì)附近的某居民區(qū)有無影響、海上漏油點(diǎn)對(duì)附近海域環(huán)境污染范圍;計(jì)算一個(gè)國(guó)家領(lǐng)海的范圍等。

1 緩沖區(qū)生成基本算法

緩沖區(qū)的生成算法有柵格和矢量?jī)煞N基本方法。柵格方法又叫點(diǎn)陣法。其基本原理是將矢量圖形柵格化,對(duì)要進(jìn)行分析的地理實(shí)體進(jìn)行像元加粗,然后提取其邊緣。該方法在原理上比較簡(jiǎn)單,實(shí)現(xiàn)也容易,但是其精度受限,而且在面對(duì)大數(shù)據(jù)量的分析時(shí)內(nèi)存開銷大,受性能影響較大。矢量方法原理較柵格方法復(fù)雜,但其精度高,是本文討論的對(duì)象。

矢量方式的緩沖區(qū)生成包括點(diǎn)、線和面三種目標(biāo)緩沖區(qū)的生成。點(diǎn)的緩沖區(qū)生成是以該點(diǎn)為圓心,給定距離為半徑的圓。通常是以正 n邊形表示,緩沖區(qū)的精度取決于n的大小。線緩沖區(qū)生成算法常用的方法是角平分線法和凸角圓弧法。角平分線法的缺點(diǎn)是難以最大限度的保證平行曲線的等寬性,矯正過程復(fù)雜,不易完備的實(shí)現(xiàn)[4]。為了避免上述缺點(diǎn),本文采用凸角圓弧算法。面緩沖區(qū)的生成是對(duì)面的外邊界線的內(nèi)外做平行線,實(shí)現(xiàn)方法同線緩沖區(qū)生成大致相同。其中線狀目標(biāo)的緩沖生成是緩沖區(qū)算法中的核心。

2 改進(jìn)后的緩沖區(qū)算法

該算法是由緩沖半徑繞點(diǎn)旋轉(zhuǎn)生成目標(biāo)緩沖區(qū)邊界并將生成的緩沖區(qū)進(jìn)行合并的一種可靠、簡(jiǎn)便的方法,簡(jiǎn)化了多目標(biāo)緩沖區(qū)生成的過程。下面就點(diǎn)和線的生成過程及在緩沖區(qū)生成過程中出現(xiàn)的特殊情況進(jìn)行討論。

地理信息系統(tǒng)中的曲面通常是以有序點(diǎn)的方式表示,如圓形一般是以正n邊形來近似表示的。因此只要得到了構(gòu)建緩沖區(qū)曲線的有方向性有序點(diǎn)集,即可以得到緩沖區(qū)的曲面。

2.1 點(diǎn)緩沖區(qū)生成算法

點(diǎn)緩沖區(qū)是緩沖區(qū)生成中比較簡(jiǎn)單的一種,即用正n邊形的相應(yīng)折線段來近似表示點(diǎn)狀的緩沖區(qū)。其中正n邊形的邊數(shù)可以代表點(diǎn)緩沖區(qū)的“平滑度”,即緩沖區(qū)多邊形中曲線的分辨率。如果該值取的太小,放大后曲面的鋸齒較為明顯;如果取得較大,則運(yùn)算量增大影響運(yùn)算速度。通常在實(shí)現(xiàn)中取16及以上較為適宜,如圖1所示。

在平面上任一點(diǎn)(X,Y)關(guān)于任意點(diǎn)(Xr,Yr)旋轉(zhuǎn)θ角,得到新點(diǎn)的位置坐標(biāo)(X′,Y′)的公式

此時(shí)X-Xr=r,Y-Yr=0,上面公式則變?yōu)?/p>

如圖1所示,作點(diǎn)目標(biāo)O的緩沖區(qū)邊界多邊形。以緩沖區(qū)半徑作為AO的長(zhǎng)度,根據(jù)上述公式取旋轉(zhuǎn)角θ=0,δ,2δ,3δ…,n*δ,此時(shí)的步長(zhǎng) δ由正n邊形的邊數(shù)決定,即 δ=2π/n。從而就可以得到用來表示點(diǎn)緩沖區(qū)的正n邊形的各點(diǎn)坐標(biāo)。其中需要注意在最后應(yīng)將首點(diǎn)加入到坐標(biāo)點(diǎn)序列中,以使多邊形閉合。

圖1 點(diǎn)緩沖區(qū)生成

2.2 線緩沖區(qū)生成算法

線狀目標(biāo)緩沖區(qū)生成可以分為雙側(cè)緩沖區(qū)和單側(cè)緩沖區(qū),以及雙側(cè)不對(duì)稱緩沖區(qū)。這里以使用最多的雙側(cè)緩沖區(qū)為例說明,其他類型與之類似。

線狀目標(biāo)是矢量,具有方向性。在生成線狀目標(biāo)緩沖區(qū)時(shí)先做第一個(gè)點(diǎn)的右側(cè)緩沖區(qū),然后按照線狀目標(biāo)的走向依次做相鄰兩點(diǎn)及最后一點(diǎn)的右側(cè)緩沖區(qū)線段,然后將點(diǎn)順序倒置,重復(fù)上述過程。所有目標(biāo)緩沖區(qū)生成以后,依次判斷各緩沖區(qū)有無相交。如果有相交則做相交處理;如果沒有相交則將其從緩沖區(qū)隊(duì)列中刪除并加入到最后的結(jié)果隊(duì)列中。

下面以一個(gè)例子來具體說明該算法生成線狀目標(biāo)緩沖區(qū)的實(shí)現(xiàn)過程。

1)沿線狀目標(biāo)前進(jìn)方向,先做首端點(diǎn)的左側(cè)緩沖區(qū);

與上述的點(diǎn)緩沖區(qū)生成方法相似,使用正n邊形來近似替代圓弧。應(yīng)該注意圓弧段的起始角度和終止角度。連接首端點(diǎn)和第二個(gè)結(jié)點(diǎn),形成向量AB。向量AB沿順時(shí)針方向旋轉(zhuǎn)到X軸正半軸掃過的角度為θ。起始角度是θ+π,終止角度是θ+3π/2,其中每次增加角度2π/n。圖2中對(duì)應(yīng)首端點(diǎn)生成了線緩沖區(qū)邊界多邊形上 A段上的若干點(diǎn)。

圖2 線緩沖區(qū)生成

2)作線狀目標(biāo)首端點(diǎn)和末端點(diǎn)之間點(diǎn)的右側(cè)緩沖區(qū)。

假設(shè)現(xiàn)在進(jìn)行判斷的點(diǎn)是B點(diǎn),按照線狀要素前進(jìn)方向,其前一點(diǎn)是A點(diǎn),后一點(diǎn)是C點(diǎn)。首先需要判斷該點(diǎn)的凹凸性。按軸線方向可以得到該點(diǎn)之前的點(diǎn)和之后的點(diǎn),與該點(diǎn)分別構(gòu)成兩個(gè)向量。由矢量代數(shù)可以知道,叉積的計(jì)算遵守右手法則。兩向量AB和BC,

其中,k為垂直于AB和BC的單位正向向量向量積。即當(dāng) λ＞0時(shí),拇指朝上,該點(diǎn)為凸點(diǎn);當(dāng) λ＜0時(shí),拇指朝下,該點(diǎn)為凹點(diǎn);當(dāng)λ=0時(shí),三點(diǎn)共線。

若是凸點(diǎn),則用半徑為緩沖半徑的圓弧段連接,方法類似于首端點(diǎn)緩沖區(qū)的生成,即用正n邊形的部分邊近似表示。其起始角度和終止角度的確定需要用兩向量的數(shù)量積來確定。通過下面公式可以得到σ角,AB沿順時(shí)針方向旋轉(zhuǎn)到X軸所掃過的角度α,起始角度是α+3π/2,終止角度是α+3π/2+σ,其中每次增加角度2π/n。圖2中對(duì)應(yīng)凸點(diǎn)生成了線緩沖區(qū)邊界多邊形上C段上若干點(diǎn)。

若是凹點(diǎn),首先判斷該點(diǎn)是否是尖銳角。取得AB和BC兩者中較小一個(gè)的長(zhǎng)度L,AB和BC之間的夾角為β。如果L×tanβ/2大于半徑值,是非尖銳角情況,否則就是按尖銳角情況處理。非尖銳角情況只需求出兩段線段的右側(cè)平行線的交點(diǎn)即可,將求出的點(diǎn)加入到結(jié)果點(diǎn)集中。右側(cè)平行線可以根據(jù)已知線段的首末兩點(diǎn)和線段方向及角度得出對(duì)應(yīng)兩點(diǎn)(這兩點(diǎn)離原線段首末兩點(diǎn)的距離為緩沖半徑)。確定了平行線段的兩點(diǎn)也就確定了平行線,從而得到兩平行線的交點(diǎn)坐標(biāo),將其加入到結(jié)果點(diǎn)集中。圖2中對(duì)應(yīng)凸點(diǎn)生成了線緩沖區(qū)邊界多邊形上B點(diǎn)。如果是尖銳角情況所求點(diǎn)有三種情況,即是兩弧段交點(diǎn)、弧段和延長(zhǎng)平行線段交點(diǎn)或者兩延長(zhǎng)平行線段交點(diǎn),如圖3所示。這三種情況需要分情況判斷,即用上文中所提到的判斷一個(gè)點(diǎn)凹凸性的方法,分別做尖銳角兩個(gè)邊點(diǎn)的凹凸性判斷。圓弧的生成類似于凸點(diǎn)的生成,該邊沿順時(shí)針方向旋轉(zhuǎn)到X軸所掃過的角度α,起始角度是α+π/2,終止角度是α-π/2。平行線的生成類似于凹點(diǎn)非尖銳角情況,同時(shí),因?yàn)樵诮嵌群苄〉那闆r下平行線段有可能在延長(zhǎng)線上才可能與另一弧段(線段)相交,所以,需要將線段向兩端延長(zhǎng)若干倍數(shù)。這樣得到兩邊的線段(弧段)坐標(biāo)點(diǎn)(集),通過循環(huán)就可以得到交點(diǎn)坐標(biāo),將其加入到結(jié)果點(diǎn)集中。圖2中對(duì)應(yīng)凸點(diǎn)生成了線緩沖區(qū)邊界多邊形上D點(diǎn)。

圖3 尖銳角情況

如果三點(diǎn)共線,則將中間點(diǎn)從線狀目標(biāo)中刪除。

重復(fù)步驟2),直到線狀目標(biāo)的末端點(diǎn)。

3)線狀目標(biāo)的末端點(diǎn)的右側(cè)緩沖區(qū)邊界的方法和首端點(diǎn)的方法類似。

連接倒數(shù)第二個(gè)結(jié)點(diǎn)和末端點(diǎn),形成向量AB。向量AB沿順時(shí)針方向旋轉(zhuǎn)到X軸正半軸掃過的角度為θ。起始角度是θ+3π/2,終止角度是θ+2π,其中每次增加角度2π/n。

4)將線狀目標(biāo)的順序反轉(zhuǎn),重復(fù)上述步驟,就可以得到該線狀目標(biāo)的雙側(cè)緩沖區(qū)上所有的點(diǎn)。

5)這時(shí)得到的緩沖區(qū)點(diǎn)集中可能包含自相交的情況,需要進(jìn)行自相交判斷及處理。

該處理是一個(gè)雙層循環(huán)的遞歸函數(shù),在外層循環(huán)上,依次取的已得到的點(diǎn)集中相臨的兩點(diǎn)組成的線段,在內(nèi)層循環(huán)上依次取外層循環(huán)確定的線段之后的相臨兩點(diǎn)。判斷內(nèi)外層兩條線段是否相交,如果不相交則退出本次內(nèi)層循環(huán),執(zhí)行下一次內(nèi)層循環(huán)。如果相交則求出相交點(diǎn),在交點(diǎn)處將原有的點(diǎn)集分割為兩個(gè)點(diǎn)集,然后分別對(duì)這兩個(gè)點(diǎn)集調(diào)用自相交處理函數(shù)。經(jīng)過這樣的處理,得到的是若干自相交多邊形,需要判斷多邊形緩沖區(qū)的內(nèi)外環(huán)。如果多邊形是順時(shí)針方向,則是島嶼多邊形,構(gòu)成緩沖區(qū)多邊形的內(nèi)環(huán),如果是逆時(shí)針方向,則取其中面積最大的多邊形作為緩沖區(qū)多邊形的外環(huán)。

2.3 面緩沖區(qū)生成算法

面緩沖區(qū)生成算法是以線緩沖區(qū)生成算法作為基礎(chǔ)。面狀要素緩沖區(qū)生成可以分為面擴(kuò)張緩沖區(qū)和面收縮緩沖區(qū)。面緩沖區(qū)生成算法可以按要素的單側(cè)多邊形進(jìn)行處理,將生成的點(diǎn)集加上面的邊界點(diǎn),再進(jìn)行自相交處理即為面狀要素緩沖區(qū)。

2.4 相關(guān)算法

在上述算法中有很多算法都需要用到兩線段相交算法,如自相交算法和尖銳角處理等。如果兩線段相交算法失真或者低效對(duì)整個(gè)算法的影響較大。兩線段相交算法中首先判斷兩線段的外接矩形是否相交,如果相交則繼續(xù)判斷兩線段是否跨立。以兩線段 AB和CD來說明跨立的計(jì)算。計(jì)算[(XC-XA)*(XC-XD)+(YC-YA)*(YCYD)]*[(XC-XD)*(XC-XB)+(YC-YD)*(YC-YB)],如果該值大于等于零則繼續(xù)進(jìn)行。接下來通過方程聯(lián)立求得交點(diǎn),并進(jìn)行垂直、豎直等特殊情況的判斷。這里要注意的是,在數(shù)據(jù)類型中精度是有限的,需要排除末位隨機(jī)數(shù)對(duì)結(jié)果的影響。

3 緩沖區(qū)合并算法

通常需要處理的并非是單一目標(biāo),而預(yù)期結(jié)果是若干目標(biāo)共同的緩沖區(qū)多邊形。這就需要逐個(gè)實(shí)體生成緩沖區(qū),然后進(jìn)行緩沖區(qū)合并。合并以后可以得到一個(gè)整體的多邊形或者若干個(gè)有共同邊的多邊形,這里就第一種情況進(jìn)行討論。上述算法解決了逐個(gè)實(shí)體的緩沖區(qū)生成,下面介紹緩沖區(qū)合并算法。經(jīng)過第2節(jié)的處理,得到一個(gè)外環(huán)和若干個(gè)(或零個(gè))多邊形內(nèi)環(huán)。這樣在進(jìn)行緩沖區(qū)合并的時(shí)候就要分為外環(huán)求并,內(nèi)環(huán)求并以及內(nèi)外環(huán)求差。

外環(huán)求交算法類似于自相交的處理函數(shù)。該函數(shù)中首先取兩個(gè)多邊形外環(huán)進(jìn)行雙層循環(huán),在外層循環(huán)上,依次取第一個(gè)外環(huán)點(diǎn)集中相臨的兩點(diǎn)組成的線段,在內(nèi)層循環(huán)上依次取第二個(gè)外環(huán)點(diǎn)集中相臨的兩點(diǎn)組成的線段。判斷內(nèi)外層兩條線段是否相交,如果相交則求出相交點(diǎn),在交點(diǎn)處將原有的點(diǎn)集分割為兩個(gè)點(diǎn)集,然后分別對(duì)這兩個(gè)點(diǎn)集調(diào)用自相交處理函數(shù)。經(jīng)過這樣的處理,得到的是若干自相交多邊形,將其中最大的順時(shí)針多邊形加入到結(jié)果隊(duì)列中。如果循環(huán)完畢后仍沒有相交,將這兩個(gè)外環(huán)都加入到結(jié)果隊(duì)列中。然后依次取結(jié)果隊(duì)列中的多邊形與其他多邊形循環(huán)。最后在結(jié)果隊(duì)列中的多邊形就是多目標(biāo)緩沖區(qū)的外環(huán)。

內(nèi)外環(huán)求差算法就是將一個(gè)緩沖區(qū)的內(nèi)環(huán)與其他緩沖區(qū)的外環(huán)求差,求差結(jié)果就是緩沖區(qū)內(nèi)環(huán)。具體算法就是首先判斷內(nèi)環(huán)與外環(huán)的外接矩形是否相交,如果相交則進(jìn)行雙層循環(huán)。首先判斷內(nèi)環(huán)第一個(gè)點(diǎn)是否在外環(huán)中,如果在外環(huán)中則判斷下一個(gè)點(diǎn),直到找到一個(gè)不在外環(huán)中的內(nèi)環(huán)點(diǎn),將其設(shè)為內(nèi)層循環(huán)的起始點(diǎn)。內(nèi)層循環(huán)依次取相臨的兩個(gè)點(diǎn)組成的線段,外層循環(huán)依次取外環(huán)上相臨的兩個(gè)點(diǎn)組成的線段。判斷兩條線段是否相交,如果不相交將內(nèi)層循環(huán)第一個(gè)點(diǎn)加入到結(jié)果隊(duì)列,如相交則將相交點(diǎn)加入到結(jié)果隊(duì)列中。并將該點(diǎn)和下次相交點(diǎn)之間的外環(huán)點(diǎn)加入到結(jié)果隊(duì)列中。

內(nèi)環(huán)求并算法與自相交處理過程相同。

4 結(jié) 論

該算法在目標(biāo)很小緩沖區(qū)半徑很大的情況下效果有待改善。另外在自相交檢查時(shí),在多目標(biāo)自相交情況較多的情況下效率有待提高,應(yīng)考慮使用檢索方式提高效率,即用網(wǎng)格將整個(gè)區(qū)域劃分為若干小的網(wǎng)格,在小的網(wǎng)格內(nèi)判斷自相交。這是下一步所考慮實(shí)現(xiàn)的內(nèi)容。

該算法考慮了含有內(nèi)環(huán)的多邊形的緩沖合并情況,并對(duì)一些特殊情況如尖銳角的情況進(jìn)行了討論。上述算法已經(jīng)編程實(shí)現(xiàn),經(jīng)過測(cè)試算法可以滿足用戶對(duì)緩沖區(qū)生成的要求。

[1] 黃杏元.地理信息系統(tǒng)概論[M].2版.北京:高等教育出版社,1989:130-131.

[2] 劉湘南,黃 方,王 平,等.GIS空間分析原理與方法[M].北京:科學(xué)出版社,2005:104-107.

[3] 張成才.GIS空間分析理論與方法[M].武漢:武漢大學(xué)出版社,2006.

[4] 毋河海.關(guān)于GIS中緩沖區(qū)的建立問題[J].武漢測(cè)繪科技大學(xué)學(xué)報(bào),1997,22(4):358-364.

[5] 陳學(xué)工,張文藝,張弛偉,等.一種GIS緩沖區(qū)矢量生成算法及實(shí)現(xiàn)[J].計(jì)算機(jī)技術(shù)與發(fā)展,2007,17(3):13-16.

[6] 董 鵬,毛東軍,李 軍,等.一種有效地GIS緩沖區(qū)生成算法[J].計(jì)算機(jī)工程與應(yīng)用,2004,40(16)4-8.