韓金峰 張亞超

【摘要】本文主要討論了曲線矢量數(shù)據(jù)的壓縮算法，分析將其運用到等高線或其他曲線矢量數(shù)據(jù)壓縮。在Spliting算法基礎(chǔ)上提出了一種針對無拓?fù)涫噶繑?shù)據(jù)的快速壓縮算法，并在AUTOCAD中實現(xiàn)該算法過程。

【關(guān)鍵詞】矢量數(shù)據(jù)，壓縮算法，精確度，等高線

中圖分類號：U212.33+2曲 文獻標(biāo)識碼：A 文章編號：

一﹑引言

在計算機自動制圖中應(yīng)用計算機處理已得到的數(shù)字化的資料就不能不注重計算機的容量和計算量。因此，就產(chǎn)生了計算機自動制圖中的曲線壓縮問題。曲線壓縮實質(zhì)上是信息壓縮問題，從信息論上講曲線矢量數(shù)據(jù)壓縮就是從組成曲線的點序集合A中抽取一個點序子集。用這個子集作為一個新的信息源，在規(guī)定的精度范圍內(nèi)對該子集從內(nèi)容上盡可能地反映原集合，而于數(shù)量上則盡可能精簡。

由于各種原因，系統(tǒng)接收的原圖數(shù)據(jù)中，有一些等高線、曲線等線狀要素的坐標(biāo)點非常密集，存在大量冗余點。冗余點不但占用大量存儲空間，使曲線上出現(xiàn)許多不應(yīng)有的微小波動，還給對曲線的編輯帶來困難。這有時是不必要的，而且常常造成系統(tǒng)處理受限制。因此，需要利用一定的壓縮算法消除冗余點，對數(shù)據(jù)進行簡化，并且在保證精度的前提下使曲線具有原來的輪廓和關(guān)系，節(jié)約存儲空間。

曲線矢量數(shù)據(jù)壓縮是從組成曲線的點序集合A中抽取一個點序A'，也就是說A'是A中的一部分，不是新的點。而由曲線擬合的方法也可以得到一個逼近的曲線，但擬合出來的曲線不一定通過原來曲線的點，為了避免誤差的傳遞還是用上述方法壓縮。

二、曲線壓縮方法討論

對于封閉曲線它是先確定曲線最左邊或最右邊兩點作為起始端點，而對于非封閉曲線可選擇兩個斷點為起始點，如圖1，

圖1

找出兩端點之間的曲線上的離散點與兩端點的連線的最大距離點，如果該距離值大于給定的精度值，則保留該點，如：2′大于精度值則保留2點。如果2′小于精度值，則再用分別得到的相鄰點4作為起始端點重新進行判斷以確定下一個要保留的點。依次反復(fù)進行直到兩直線之間曲線上的點到直線的 距離大于精度值為止。最后，作為端點的末點與曲線的 最后一個端點重合進行判斷并保留最后一個端點。

從以上可知，此法可以很大程度上滿足即能保留曲線原始的點，能體現(xiàn)曲線的精度不受太大的變化。這在地形圖作業(yè)上是一個很好的壓縮方法。

三、曲線壓縮的原理和步驟

曲線數(shù)據(jù)壓縮方法三部分：

⑴把等高線上的離散點提取出來作為待處理的點；

⑵對相鄰兩點的距離進行比較如果大于距離精度值則保留第二個點；在滿足前面條件的情況下對兩個端點之間的離散點進行判斷如果到兩端點的距離大于偏離精確值，則保留該離散點；

⑶對保留的點進行繪圖使它成為與原等高線相近的曲線。

3.1對曲線的離散點進行精度壓縮原理

基本思想是去除偏離曲線距離小于規(guī)定值δ（例如圖0.1mm）的點。假設(shè)（圖1）中1、2、3、4、5、6為待壓縮的曲線上的點。首先保留第一點1，并以1為起點，連接1、3兩點，若點2到連線13的垂距22'大于δ，則保留點2，以點3為起點繼續(xù)計算。若小于δ，則連接1、4兩點，分別考察2、3兩點到連線14的垂距，若任意一個垂距超過δ，則去掉點2，以點3為起點繼續(xù)計算；否則，連接1、5兩點，考察2、3、4各點到連線15的垂距，……，如此進行下去，直到點1與點i連線時，其間至少有一個點到連線1i的垂距超過δ，則去掉2、3，…，i-2各點，然后以i-1為起點繼續(xù)計算。重復(fù)上述步驟，直到曲線的終點。用這種方法壓縮曲線時，在曲線變化平緩的地方，曲線上被壓縮掉的點很多，剩下的點間距較大，繪制曲線時點之間會產(chǎn)生多余的擺動。為避免這種情況，壓縮過程中可以加入距離條件，即當(dāng)點的間距超過某一閾值Δ時必須保留一個點，即使其間各點到連線的垂距均不超限。

3.2在曲線矢量數(shù)據(jù)壓縮過程中的實現(xiàn)

1對等高線上的離散點進行提取。

建立一個選擇集把提取出的等高線上離散點存入新定義的數(shù)組中，其實現(xiàn)程序（見附錄）

3.2.2對數(shù)據(jù)進行壓縮計算。

該算法實際上是一個遞歸的過程，其實現(xiàn)一直以來也都采用遞歸的方式，本文通過利用堆和棧的數(shù)據(jù)結(jié)構(gòu)，提出了該算法的一種非遞歸實現(xiàn)方法。在算法的實現(xiàn)過程中，用一個數(shù)組D來存放曲線的樣點列P。，P ,…P ，用數(shù)組的位置索引來指示樣點，同時采用了一個與之相配合的隊和一個棧，記隊尾元素為n，棧頂元素為b。具體步驟如下：

(1)將曲線起點D[0]和終點D[n]的下標(biāo)分別放入隊和棧中，此時，n=0，b=n,。

(2)連接D[n]和D[b]，在D[n]和D[b]之間的點列中尋找與直線D[n]D[b]具有最大距離的點，記為D[c]，若D[n]與D[b]之間沒有中間點，轉(zhuǎn)(4)。若之間有最大距離點，利用兩點之間的距離公式： 判斷D(n)與D(c)的距離是否大于距離精度值，若大于則保留點D(c),若小于則轉(zhuǎn)（4）。

(3)判段D[c]到直線D[n]D[b]之間的距離是否小于閾值，利用點到直線公式判斷。若否，則將D[c]的下標(biāo)c壓入棧中，此時，棧頂元素為c，即b=c，回到(2)。

(4)判斷b是否等于n,，若否，將棧頂元素壓入隊中，此時，b出棧，隊尾元素為b．，即n=b，回到(2)。

(5)將b壓入隊中，隊中的元素即為所提取特征點的下標(biāo)。

(6)以隊中元素為下標(biāo)，從隊頭到隊尾依次取數(shù)，組D中的點，即為所提取的特征點。

(7)將保留的特征點在圖中依次連接起來用不同的顏色顯示作為比較。

具體實現(xiàn)代碼見附錄。

3.3起始點的處理

從上所述可以看出，用上述方法所確定的曲線壓縮后的保留點與起始點的選擇密切相關(guān)，即不同起始點所得到的壓縮后的保留點不盡相同。因此，起始點的選擇對獲取最大壓縮比的保留點至關(guān)重要。選擇那些不引起始點變化而變化的曲線壓縮后的保留點為起始點較為合理。對于非閉合曲線，其兩端點總是壓縮后的保留點。因此對于非閉合曲線可選擇該曲線的任一端點作為起始點。而在壓縮過程中要不斷的存儲保留點，并把保留點作為起點，而終點則由起點的變化根據(jù)情況來確定。

四﹑實驗結(jié)果和結(jié)論

（2）

根據(jù)上述原理對一條等高線進行曲線矢量數(shù)據(jù)壓縮。如圖（1）為一條等高線的其中一段，有大量的矢量點組成，利用這條等高線進行矢量數(shù)據(jù)壓縮實驗，實驗的等高線有418個矢量點組成。用本文的方法進行矢量數(shù)據(jù)壓縮，其結(jié)果如圖（2）所視，壓縮后剩余158個點，大大壓縮的矢量數(shù)據(jù)。并與原圖比較（如圖2）保留了原本的曲線形態(tài)。為矢量數(shù)據(jù)的存儲節(jié)省了大量的空間，簡化曲線的計算量，同時壓縮后的數(shù)據(jù)能夠保留曲線的原始精度在一定的范圍內(nèi)。

曲線簡化在自動制圖綜合、應(yīng)用模型邊界簡化等方面有著較廣泛的應(yīng)用，但由于曲線形態(tài)的復(fù)雜性，算法設(shè)計仍存在一定困難，主要表現(xiàn)在它的過程、指標(biāo)和方法難以數(shù)量化和模型化。本文的研究為此提供了一種思路和途徑，在這些初步工作的基礎(chǔ)上，還可以進一步綜合考慮曲線壓縮。從我個人的實驗了來看壓縮效果很明顯。能夠滿足等高線的矢量數(shù)據(jù)壓縮，但還存在著一些問題，不足之處請指教。

五﹑結(jié)束語

本文介紹了一種常用的矢量曲線數(shù)據(jù)壓縮的算法，該算法在通過距離精度的算法進行壓縮的基礎(chǔ)上進行偏離精度壓縮，最大限度地保留原曲線的特征點減小誤差，并有效地壓縮了矢量曲線數(shù)據(jù)地壓縮，為系統(tǒng)節(jié)省了空間，同時為工作減輕了壓力。希望該算法能為CAD的矢量曲線數(shù)據(jù)提供技術(shù)支持和幫助。

參考文獻

（1）龔有亮，付子傲，翟翊 —— 一種實用的等高線內(nèi)插算法（信息工程大學(xué)牪饣嫜г海河南犞Ｖ藎450052）

（2）翟戰(zhàn)強，管華，王雙亭——一種快速空間矢量數(shù)據(jù)壓縮方法 （北京大學(xué)遙感所，北京10087E52．解放軍信息工程大學(xué)測繪學(xué)院，鄭州）

（3）易輝偉，江資斌，周翠竹，鄒嶺蝶 ——地形圖矢量化的后處理（中南大學(xué)信息物理學(xué)院，長沙410083；2．湖南省建筑學(xué)校，湘潭411001）

（4）張帆，鄭立楷，盧擇臨，王成煌——AutoCAD VBA二次開發(fā)教程（北京.清華大學(xué)出版社）

（5）張帆，鄭立楷，王華杰——AutoCAD VBA開發(fā)精彩實例教程（北京.清華大學(xué)出版社）