關(guān)于傳統(tǒng)空間緩沖區(qū)生成算法的分析

1、關(guān)于傳統(tǒng)空間緩沖區(qū)生成算法的分析 摘要：本文通過對(duì)各類空間緩沖區(qū)生成的算法思想及算法實(shí)現(xiàn)進(jìn)行分析與比較，給出了避免在緩沖區(qū)生成結(jié)果的過程中出現(xiàn)的失真與尖角等問題的最適合的解決方法。 關(guān)鍵詞：緩沖區(qū)；柵格；矢量；角平分法；凸角圓弧法 中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1007-9599 (2011) 20-0000-01 Analysis of Generation by Traditional Spatial Buffer Algorithm Liu Lijuan,Min Jie (Xinyang Agricultural College,Xinyang464000,Chin

2、a) Abstract:In this paper,the author had analysed the thinking of algorithm of the traditional space buffer generation,compared the implementation of the algorithm,and given The summary of the aberration and the buffer distortion.kinds of issues are arised in the process of the implementation of the

3、 algorithm.such as the computing speed of algorithm,sharp corners,depression. Keywords:Buffer;Grid;Vector;Angular bisectrix method;Circular arcs method 一、引言 空間緩沖區(qū)是指空間目標(biāo)的一種影響范圍或服務(wù)范圍，其數(shù)學(xué)定義為，空間目標(biāo)對(duì)象 緩沖區(qū)為： 。即當(dāng)空間目標(biāo)對(duì)象 的緩沖半徑為R時(shí)，其緩沖區(qū)可以用距離對(duì)象 的距離d小于或等于R的全部點(diǎn)的集合。而對(duì)于一些對(duì)象集合來說，其緩沖半徑為R的緩沖區(qū)是各個(gè)對(duì)象緩沖區(qū)的并，用公式表示為： ?？臻g目標(biāo)可分為

4、點(diǎn)目標(biāo)、線目標(biāo)和面目標(biāo)，其中點(diǎn)目標(biāo)的緩沖區(qū)比較容易生成。面目標(biāo)也可當(dāng)作一個(gè)特殊的線目標(biāo)。因此大部分的文獻(xiàn)中，關(guān)于緩沖區(qū)生成算法的研究都是基于線目標(biāo)來闡述的。本文也是把線目標(biāo)的緩沖區(qū)生成作為問題分析的主要對(duì)象。 二、傳統(tǒng)緩沖區(qū)生成算法思想 目前對(duì)于緩沖區(qū)的生成算法的學(xué)術(shù)研究主要從數(shù)學(xué)運(yùn)算法、柵格算法和混合算法這個(gè)三個(gè)方面入手。其中柵格方法在原理上較簡單，容易實(shí)現(xiàn)。矢量方法在機(jī)器精度范圍內(nèi)盡可能保持原始精度?；旌纤惴▽⑦@兩種方法結(jié)合起來，取利去弊，目前還是一種比較合理并使用廣泛的方法。 （一）基于柵格的緩沖區(qū)生成算法。柵格方法的核心思想是基于數(shù)學(xué)形態(tài)學(xué)的擴(kuò)張算子的，也可叫做點(diǎn)陣法。柵格方法在實(shí)現(xiàn)過

5、程中是先將點(diǎn)、線和面這些空間目標(biāo)柵格化，再向目標(biāo)柵格周圍進(jìn)行量化擴(kuò)張，最終通過邊界提取方式來生成結(jié)果多邊形。 （二）基于矢量的緩沖區(qū)生成算法。平行雙線算法是用矢量方法建立緩沖區(qū)的核心算法，在很多文獻(xiàn)資料也將其稱為計(jì)算機(jī)圖形加粗法、加寬線法或中心線擴(kuò)張等。矢量算法的主要思路是首先確定緩沖目標(biāo)，其次將緩沖目標(biāo)分成若干個(gè)單獨(dú)目標(biāo)并逐一生成緩沖多邊形，然后進(jìn)行多邊形求交得出所有可能多邊形，最后根據(jù)拓?fù)潢P(guān)系，生成結(jié)果多邊形。空間實(shí)體目標(biāo)緩沖區(qū)邊界線的矢量生成算法有多種，這其中最具代表性的是角平分線法與凸角圓弧法。很多學(xué)者都是圍繞這個(gè)兩種傳統(tǒng)方法進(jìn)行算法改進(jìn)的。其中角平分線法的緩沖區(qū)生成是分線目標(biāo)的端點(diǎn)與

6、線目標(biāo)本身兩個(gè)步來實(shí)現(xiàn)的。分別在軸線起始點(diǎn)與終止點(diǎn)處作軸線的垂線，以左右側(cè)緩沖半徑 和 截出左右緩沖邊線的起點(diǎn)與終點(diǎn)；在軸線的轉(zhuǎn)折點(diǎn)處緩沖頂點(diǎn)的是用與該點(diǎn)關(guān)聯(lián)的兩鄰邊距軸線的兩平行線的交點(diǎn)。凸角圓弧算法與角平線算法的區(qū)別在于對(duì)目標(biāo)線拐點(diǎn)的緩沖端點(diǎn)的生成上，其采用半徑為緩沖距的圓弧進(jìn)行擬合思路。根據(jù)拐點(diǎn)的凸凹性作不同的處理，在拐點(diǎn)的凸側(cè)用緩沖距為半徑的進(jìn)行圓弧擬合。 三、傳統(tǒng)算法存在的問題 （一）柵格算法的海量問題。根據(jù)上文論述，柵格算法雖然在原理上較簡單，容易實(shí)現(xiàn)，由于不能保證緩沖區(qū)精度，而且內(nèi)存的開銷大，其難以實(shí)現(xiàn)海量空間目標(biāo)的緩沖區(qū)生成。因此建議當(dāng)目標(biāo)數(shù)據(jù)量相對(duì)比較多，盡量避免使用柵格方法

7、。當(dāng)對(duì)計(jì)算機(jī)硬件要求不高時(shí)，可以從柵格游程編碼、圖像膨脹等角度把空間目標(biāo)柵格化來生成空間目標(biāo)的緩沖區(qū)，這樣就可在運(yùn)算效率和內(nèi)存開銷有很大的改進(jìn)。 （二）緩沖區(qū)失真現(xiàn)象。角平分線的算法的一個(gè)最大的缺陷在于，當(dāng)軸線轉(zhuǎn)角太大時(shí)難以最大限度地保證左右邊界的等寬性。轉(zhuǎn)角處的凸側(cè)角點(diǎn)將隨著角度的進(jìn)一步變銳而沿角分線遠(yuǎn)離軸線頂點(diǎn)。目前對(duì)于緩沖區(qū)生成的研究都在從這點(diǎn)入手，對(duì)算法對(duì)作了大量的修正，但效果不明顯，幾乎處于瓶頸狀態(tài)。尖角和凹陷的失真現(xiàn)象。在利用凸角圓弧的算法生成緩沖區(qū)時(shí)，當(dāng)目標(biāo)線出現(xiàn)尖銳轉(zhuǎn)角時(shí)，平行線交點(diǎn)隨緩沖距的增大將會(huì)迅速遠(yuǎn)離軸線，會(huì)出現(xiàn)如圖1所示的尖角和凹陷。當(dāng)建立左右緩沖距不相等的緩沖區(qū)時(shí)，

8、在軸線兩端處，由于左右緩沖距離不相等，在軸線兩端會(huì)產(chǎn)生如圖2所示尖角。一些研究者就從這一點(diǎn)入手，運(yùn)用旋轉(zhuǎn)點(diǎn)變換公式來簡化尖角的糾正過程，來達(dá)到平緩尖角和凹陷的目的。 圖1：線的緩沖區(qū)失真現(xiàn)象圖2：不對(duì)稱緩沖區(qū)端點(diǎn)處圓弧擬合 （三）緩沖區(qū)的自相交。當(dāng)線目標(biāo)的彎曲空間不能容許緩沖區(qū)邊界線自身無壓蓋地通過時(shí)，緩沖區(qū)邊界線就會(huì)產(chǎn)生若干個(gè)如圖3所示自相交多邊形。某些目標(biāo)實(shí)體其自身就有相交現(xiàn)象（如圖4所示）。對(duì)于這兩種自相交現(xiàn)象，可以運(yùn)用遞歸方法來這種不確定性。 圖3線的緩沖區(qū)邊界自相交多邊形圖4軸線自相交情況 四、小結(jié) 為了解決柵格與矢量算法產(chǎn)生的大量缺陷，專家們采用相應(yīng)的補(bǔ)救措施，但是由于空間目標(biāo)實(shí)體的復(fù)雜性，采用的算法模型進(jìn)行相應(yīng)的處理時(shí)，依然會(huì)出現(xiàn)各種異常情況。因而對(duì)于空間目標(biāo)的緩沖區(qū)生成，我們?nèi)孕枰M(jìn)一步研究與探索。 參考文獻(xiàn)： 1毋河海.關(guān)于GIS緩沖區(qū)的建立問題J.武漢測(cè)繪科技大