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

1、關于傳統(tǒng)空間緩沖區(qū)生成算法的分析 摘要：本文通過對各類空間緩沖區(qū)生成的算法思想及算法實現(xiàn)進行分析與比較，給出了避免在緩沖區(qū)生成結果的過程中出現(xiàn)的失真與尖角等問題的最適合的解決方法。 關鍵詞：緩沖區(qū)；柵格；矢量；角平分法；凸角圓弧法 中圖分類號：TP301.6 文獻標識碼：A文章編號：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ū)是指空間目標的一種影響范圍或服務范圍，其數(shù)學定義為，空間目標對象 緩沖區(qū)為： 。即當空間目標對象 的緩沖半徑為R時，其緩沖區(qū)可以用距離對象 的距離d小于或等于R的全部點的集合。而對于一些對象集合來說，其緩沖半徑為R的緩沖區(qū)是各個對象緩沖區(qū)的并，用公式表示為： ?？臻g目標可分為

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

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

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

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

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