曲線數(shù)據(jù)壓縮方法和實(shí)現(xiàn)

《曲線數(shù)據(jù)壓縮方法和實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、曲線數(shù)據(jù)壓縮方法和實(shí)現(xiàn)　　【摘要】本文主要討論了曲線矢量數(shù)據(jù)的壓縮算法，分析將其運(yùn)用到等高線或其他曲線矢量數(shù)據(jù)壓縮。在Spliting算法基礎(chǔ)上提出了一種針對(duì)無拓?fù)涫噶繑?shù)據(jù)的快速壓縮算法，并在AUTOCAD中實(shí)現(xiàn)該算法過程。【關(guān)鍵詞】矢量數(shù)據(jù)，壓縮算法，精確度，等高線中圖分類號(hào)：U212.33+2曲文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：一﹑引言在計(jì)算機(jī)自動(dòng)制圖中應(yīng)用計(jì)算機(jī)處理已得到的數(shù)字化的資料就不能不注重計(jì)算機(jī)的容量和計(jì)算量。因此，就產(chǎn)生了計(jì)算機(jī)自動(dòng)制圖中的曲線壓縮問題。曲線壓縮實(shí)質(zhì)上是信息壓縮問題，從信息論上講曲線矢量數(shù)

2、據(jù)壓縮就是從組成曲線的點(diǎn)序集合A中抽取一個(gè)點(diǎn)序子集。用這個(gè)子集作為一個(gè)新的信息源，在規(guī)定的精度范圍內(nèi)對(duì)該子集從內(nèi)容上盡可能地反映原集合，而于數(shù)量上則盡可能精簡(jiǎn)。7由于各種原因，系統(tǒng)接收的原圖數(shù)據(jù)中，有一些等高線、曲線等線狀要素的坐標(biāo)點(diǎn)非常密集，存在大量冗余點(diǎn)。冗余點(diǎn)不但占用大量存儲(chǔ)空間，使曲線上出現(xiàn)許多不應(yīng)有的微小波動(dòng)，還給對(duì)曲線的編輯帶來困難。這有時(shí)是不必要的，而且常常造成系統(tǒng)處理受限制。因此，需要利用一定的壓縮算法消除冗余點(diǎn)，對(duì)數(shù)據(jù)進(jìn)行簡(jiǎn)化，并且在保證精度的前提下使曲線具有原來的輪廓和關(guān)系，節(jié)約存儲(chǔ)空間。曲

3、線矢量數(shù)據(jù)壓縮是從組成曲線的點(diǎn)序集合A中抽取一個(gè)點(diǎn)序A’，也就是說A’是A中的一部分，不是新的點(diǎn)。而由曲線擬合的方法也可以得到一個(gè)逼近的曲線，但擬合出來的曲線不一定通過原來曲線的點(diǎn)，為了避免誤差的傳遞還是用上述方法壓縮。二、曲線壓縮方法討論對(duì)于封閉曲線它是先確定曲線最左邊或最右邊兩點(diǎn)作為起始端點(diǎn)，而對(duì)于非封閉曲線可選擇兩個(gè)斷點(diǎn)為起始點(diǎn)，如圖1，圖1找出兩端點(diǎn)之間的曲線上的離散點(diǎn)與兩端點(diǎn)的連線的最大距離點(diǎn)，如果該距離值大于給定的精度值，則保留該點(diǎn)，如：2′大于精度值則保留2點(diǎn)。如果2′小于精度值，則再用分別得到的

4、相鄰點(diǎn)4作為起始端點(diǎn)重新進(jìn)行判斷以確定下一個(gè)要保留的點(diǎn)。依次反復(fù)進(jìn)行直到兩直線之間曲線上的點(diǎn)到直線的距離大于精度值為止。最后，作為端點(diǎn)的末點(diǎn)與曲線的最后一個(gè)端點(diǎn)重合進(jìn)行判斷并保留最后一個(gè)端點(diǎn)。從以上可知，此法可以很大程度上滿足即能保留曲線原始的點(diǎn)，能體現(xiàn)曲線的精度不受太大的變化。這在地形圖作業(yè)上是一個(gè)很好的壓縮方法。7三、曲線壓縮的原理和步驟曲線數(shù)據(jù)壓縮方法三部分：⑴把等高線上的離散點(diǎn)提取出來作為待處理的點(diǎn)；⑵對(duì)相鄰兩點(diǎn)的距離進(jìn)行比較如果大于距離精度值則保留第二個(gè)點(diǎn)；在滿足前面條件的情況下對(duì)兩個(gè)端點(diǎn)之間的離散點(diǎn)

5、進(jìn)行判斷如果到兩端點(diǎn)的距離大于偏離精確值，則保留該離散點(diǎn)；⑶對(duì)保留的點(diǎn)進(jìn)行繪圖使它成為與原等高線相近的曲線。3.1對(duì)曲線的離散點(diǎn)進(jìn)行精度壓縮原理7基本思想是去除偏離曲線距離小于規(guī)定值δ（例如圖0.1mm）的點(diǎn)。假設(shè)（圖1）中1、2、3、4、5、6為待壓縮的曲線上的點(diǎn)。首先保留第一點(diǎn)1，并以1為起點(diǎn)，連接1、3兩點(diǎn)，若點(diǎn)2到連線13的垂距22’大于δ，則保留點(diǎn)2，以點(diǎn)3為起點(diǎn)繼續(xù)計(jì)算。若小于δ，則連接1、4兩點(diǎn)，分別考察2、3兩點(diǎn)到連線14的垂距，若任意一個(gè)垂距超過δ，則去掉點(diǎn)2，以點(diǎn)3為起點(diǎn)繼續(xù)計(jì)算；否則，連接

6、1、5兩點(diǎn)，考察2、3、4各點(diǎn)到連線15的垂距，……，如此進(jìn)行下去，直到點(diǎn)1與點(diǎn)i連線時(shí)，其間至少有一個(gè)點(diǎn)到連線1i的垂距超過δ，則去掉2、3，…，i-2各點(diǎn)，然后以i-1為起點(diǎn)繼續(xù)計(jì)算。重復(fù)上述步驟，直到曲線的終點(diǎn)。用這種方法壓縮曲線時(shí)，在曲線變化平緩的地方，曲線上被壓縮掉的點(diǎn)很多，剩下的點(diǎn)間距較大，繪制曲線時(shí)點(diǎn)之間會(huì)產(chǎn)生多余的擺動(dòng)。為避免這種情況，壓縮過程中可以加入距離條件，即當(dāng)點(diǎn)的間距超過某一閾值Δ時(shí)必須保留一個(gè)點(diǎn)，即使其間各點(diǎn)到連線的垂距均不超限。3.2在曲線矢量數(shù)據(jù)壓縮過程中的實(shí)現(xiàn)1對(duì)等高線上的離散點(diǎn)

7、進(jìn)行提取。建立一個(gè)選擇集把提取出的等高線上離散點(diǎn)存入新定義的數(shù)組中，其實(shí)現(xiàn)程序（見附錄）3.2.2對(duì)數(shù)據(jù)進(jìn)行壓縮計(jì)算。該算法實(shí)際上是一個(gè)遞歸的過程，其實(shí)現(xiàn)一直以來也都采用遞歸的方式，本文通過利用堆和棧的數(shù)據(jù)結(jié)構(gòu)，提出了該算法的一種非遞歸實(shí)現(xiàn)方法。在算法的實(shí)現(xiàn)過程中，用一個(gè)數(shù)組D來存放曲線的樣點(diǎn)列P。，P,…P，用數(shù)組的位置索引來指示樣點(diǎn)，同時(shí)采用了一個(gè)與之相配合的隊(duì)和一個(gè)棧，記隊(duì)尾元素為n，棧頂元素為b。具體步驟如下：(1)將曲線起點(diǎn)D[0]和終點(diǎn)D[n]的下標(biāo)分別放入隊(duì)和棧中，此時(shí)，n=0，b=n,。(2)連

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