基于三次參數(shù)樣條的等高線點加密算法

劉 旭，范磊磊，王寶水，閆玉強

（1.徐州市賈汪區(qū)國土資源局，江蘇 徐州 221011；2.江陰市城市規(guī)劃信息咨詢中心，江蘇 江陰 214433；3.蘇州工業(yè)園區(qū)測繪地理信息有限公司，江蘇 蘇州 215027）

基于三次參數(shù)樣條的等高線點加密算法

劉 旭1，范磊磊1，王寶水2，閆玉強3

（1.徐州市賈汪區(qū)國土資源局，江蘇 徐州 221011；2.江陰市城市規(guī)劃信息咨詢中心，江蘇 江陰 214433；3.蘇州工業(yè)園區(qū)測繪地理信息有限公司，江蘇 蘇州 215027）

分析了DXF格式結(jié)構(gòu)中各組碼段與對應(yīng)代碼段的含義及關(guān)系特點，實現(xiàn)DXF文件的讀寫，并根據(jù)提取地形圖中等高線的信息，利用VisualC++編寫三次參數(shù)樣條自動實現(xiàn)對等高線進行點加密算法。通過實例驗證，該算法可保證等高線原始趨勢不變，特別是出現(xiàn)大撓度等高線時，對等高線進行點加密，能保證地形圖的準確性，提高工作效率。

Visual C++；三次參數(shù)樣條；等高線；點加密

等高線是一種重要的反映區(qū)域地貌形態(tài)的基礎(chǔ)數(shù)據(jù)[1,2]，工程中時常需要對等高線進行點加密，使其能更為細致地表示地貌特征[3]?；赩isualC++平臺對DXF格式文件進行讀寫，根據(jù)等高線上已知的（x，y）信息，利用三次參數(shù)樣條對等高線上的點進行加密，能有很好的效果。

1 DXF文件及三次參數(shù)樣條差值

1.1 DXF文件的結(jié)構(gòu)

從結(jié)構(gòu)上，DXF文件[3]是由一系列的組構(gòu)成的。組作為DXF文件中的最小單元，與一行整數(shù)型組碼及連續(xù)的下一行組值（對組碼的描述說明）構(gòu)成。

DXF文件由6節(jié)構(gòu)成[4]，其中實體節(jié)包含圖形中所有的實體（如多段線、點、構(gòu)造線等）信息，如點的高程、坐標、所在圖層、顏色等，以組碼2及對應(yīng)組值ENTITIES標志開始。

等高線是以多段線的方式表現(xiàn)的，在DXF格式文件中多段線以組碼0及對應(yīng)組值LWPOLYLINE，主要實體數(shù)據(jù)[4]見表1。

表1 多段線的實體數(shù)據(jù)表

1.2 三次參數(shù)樣條插值

目前常用的曲線插值方法有拉格朗日插值法、分段低次插值法、張力樣條插值法、樣條插值法等[4]。其中以樣條插值中的三次樣條插值、三次參數(shù)樣條插值最為常用[5]。

三次樣條插值在曲線小撓度的情況下滿足要求，當撓度過大時，不能很好地控制曲線的彎曲度，樣條曲線與實際曲線撓度偏差較大，使得曲線失真[6]。

1.2.1 三次參數(shù)樣條函數(shù)

三次參數(shù)樣條曲線函數(shù)是以曲線的弦長li作為參數(shù)的函數(shù)，表達形式一般為：空間曲線上的節(jié)點為pti（xi，yi，zi）（i=0，1，…，n）。若函數(shù)S（x）是該空間曲線的函數(shù)，每個區(qū)間[pti，pti+1]，（i=0，1，…，n-1）是三次多項式的形式：

式中，l?[0，Li]。Li為第i段的弦長：

且在節(jié)點處滿足連續(xù)性條件：

由式（1）～（3）可知，共有4n-2個條件。還需2個條件，在區(qū)間邊界點pt0和ptn處各增加1個條件（邊界條件）。常用的邊界條件有3種：夾持端、自由端、拋物端。

1.2.2 構(gòu)造三次參數(shù)樣條函數(shù)

可得：

將式（5）代入式（1），由樣條曲線二階導數(shù)連續(xù)可得：

其中，

由上式可得到4n-2個方程，根據(jù)邊界條件可增加2個方程，見表2。則式（6）寫為矩陣形式BY'=D：

表2 三次參數(shù)樣條曲線的邊界條件

代入式（1），得到曲線方程Si（li）中yi（li）的方程。同理，求得曲線方程Si（li）中的xi（li）及zi（li）。

2 算法設(shè)計

2.1 數(shù)據(jù)格式

由于等高線在CAD中以多段線的形式體現(xiàn)，對應(yīng)表1，以結(jié)構(gòu)體typedef struct的形式聲明等高線類型。

等高線上的點（x，y）類型：

typedef struct{double x; //點的x值 double y; //點的y值} BPoint;

等高線類型：

typedef struct{CString layer; //圖層名 int color; //顏色值 int bz; // 0開曲線，1閉曲線

int ds; //等高線上的點數(shù) double h;//等高線的高程 BPoint *pt; //等高線上的點 }Pline;

定義變量Pline addpl，表示一次讀取的等高線。由于在讀取DXF文件時等高線的總條數(shù)不可知，在doc類中以動態(tài)數(shù)組Carray[7]的形式定義類型為Pline的全局變量CArray＜Pline,Pline&＞m_Pline，為了便于讀寫加密等函數(shù)對其賦值修改等。將每次獲取的等高線添加到數(shù)組m_Pline中，m_Pline.Add(addpl)。

以結(jié)構(gòu)體的形式聲明三次參數(shù)樣條曲線上節(jié)點類型：

typedef struct{ double l; double y; }SPoint;

其中，第i條等高線對應(yīng)參數(shù)樣條曲線上節(jié)點總數(shù)為int ds=m_Pline.GetAt(i).ds。

定義每條進行三次參數(shù)樣條插值曲線的節(jié)點動態(tài)數(shù)組Spoint *spl; spl=new Spoint [ds],并根據(jù)對應(yīng)等高線進行賦值。

2.2 等高線的讀取

由于在DXF文件中每個組信息中組碼和組值各占一行，故每次讀取兩行。根據(jù)不同組碼所對應(yīng)的組值信息不同，可用if…else if…語句對add_pt中的變量賦值。

定義CString型變量cs,data，并將讀入的字符串賦值給cs，data。

組碼定義為int型變量code，并將讀入的第一行賦值給code，data包含組值信息。

1）等高線對應(yīng)的多段線是一種實體，定義開始（結(jié)束）讀取實體節(jié)的標志，并初始化，根據(jù)組結(jié)構(gòu)，判斷是否開始（結(jié)束）讀取實體節(jié)。

2）進入實體節(jié)，定義開始（結(jié)束）讀取多段線的標志，并初始化，根據(jù)組結(jié)構(gòu)判斷是否讀取多段線。

3）定義中間變量，根據(jù)表1多段線的實體數(shù)據(jù)表中組的對應(yīng)格式，從data中賦值。

2.3 構(gòu)造三次參數(shù)樣條函數(shù)矩陣

定義Pline pl=m_Pline.GetAt(i)，獲取第i條等高線的信息?？纱_定總點數(shù)int n=pl.ds即B、D矩陣的大小為n×n、n×1。

三次參數(shù)樣條節(jié)點數(shù)組Spoint *spt=new Spoint[n];將pl.pt賦值給spl。由于多段線上各處高程hi相等，定義變量double L[n-1],U[n],Lmd[n-1],D[n][1]。由式（2）、式（7），對L、U、Led、D進行普通情況下的賦值。

對于不同的邊界條件（見表2），λn，μ1，D1，Dn不同，定義變量 int choice，switch…case…語句，確定邊界條件，偽代碼形式見圖1。確定矩陣B及D，然后求得矩陣Y'。

圖1 選取邊界條件偽代碼圖

2.4 點自動加密算法設(shè)計

圖2 自動加密點算法流程圖

2.5 算法實現(xiàn)

通過消息映射的方式，在菜單欄中映射doc類函數(shù)：

void OnReadDxfFile(); //讀取DXF文件

void OnPointEncryption(); //等高線上點加密

void OnWriteDxfFile();

//儲存等高線點加密后DXF文件

將加密算法封裝到CCubicSpline類中。其中包含：

class CCubicSpline : public CObject{

public : void EncryptPline(Pline pl,Pline &newpl); //對等高線上的點加密

private: void PraCubSpline(SPoint *spl,int n,SPoint *spt,int ptn); //三次參數(shù)樣條曲線

double **InvMatrixl(double **A,int n); //高斯列主元消去法求逆矩陣

double **MulMatrix(double**A,double**B,int m,int n,int k); //矩陣相乘 }

算法的實現(xiàn)流程：

1）讀取DXF格式文件，并將提取的等高線信息賦值給m_Pline。

2）對等高線pl上的點進行加密。將等高線點賦值給三次參數(shù)樣條節(jié)點并進行加密；差值后三次參數(shù)樣條節(jié)點賦值到等高線中，并通過m_Pline.SetAt（i，pl）賦值到等高線動態(tài)數(shù)組中。

3）以DXF格式寫出文件。

3 算法驗證

三次樣條曲線在小撓度情況下，效果較好，當撓度過大時，樣條曲線與實際曲線有很大的偏差。而三次參數(shù)樣條可以很好地解決大撓度問題，見圖3。

圖3 三次樣條與三次參數(shù)樣條對比圖

從整體趨勢分析，三次參數(shù)樣條在3種邊界條件下，邊界條件選取夾持端效果較好。故在對等高線進行點加密時采用夾持端的方法進行加密。加密后的效果見圖4。

圖4 等高線上點加密效果圖

4 結(jié) 語

本文算法在不破壞原始等高線趨勢的情況下利用三次參數(shù)樣條對等高線進行點加密，生成的等高線有較高的光滑性。較三次樣條插值精度更高，避免了大撓度情況下出現(xiàn)失真情況，能準確地反映實地地形特征，大大縮短工作時間，且該算法程序基于Visual C++編寫，實現(xiàn)簡單，可代替?zhèn)鹘y(tǒng)的手工方法。

[1] 陳丹.地形圖等高線自動識別與提取中的若干方法研究[D].武漢:武漢大學,2004

[2] 夏春林,王雪,葉長青.等高線自動識別方法的研究[J].礦山測量,2007(1):32-34

[3] 郭慶勝,于江佩,徐崢,等.等高線圖形綜合策略的研究[J].測繪信息與工程,2005,30(6):16-18

[4] 劉傳亮,陸建德.AutoCAD DXF文件格式與二次開發(fā)圖形軟件編程[J].微機發(fā)展,2004,14(9):101-104

[5] 郭朝勇. AutoCAD R14二次開發(fā)技術(shù)[M].北京:清華大學出版社,1999

[6] 李慶揚,王能超,易大義,等.數(shù)值分析[M].北京:清華大學出版社,2006

[7] 陳鳳祥,李汪根.C++動態(tài)數(shù)組的實現(xiàn)與重用[J].計算機技術(shù)與發(fā)展,2010(2):79-82

P208

B

1672-4623（2015）04-0148-03

10.3969/j.issn.1672-4623.2015.04.053

劉旭，工程師，主要從事工程測量相關(guān)工作。

2013-09-17。