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

劉 旭，范磊磊，王寶水，閆玉強(qiáng)

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

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

劉 旭1，范磊磊1，王寶水2，閆玉強(qiáng)3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

式中，l?[0，Li]。Li為第i段的弦長(zhǎng)：

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

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

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

可得：

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

其中，

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

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

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

2 算法設(shè)計(jì)

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

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

等高線上的點(diǎn)（x，y）類型：

typedef struct{double x; //點(diǎn)的x值 double y; //點(diǎn)的y值} BPoint;

等高線類型：

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

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

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

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

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

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

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

2.2 等高線的讀取

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

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

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

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

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

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

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

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

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

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

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

2.4 點(diǎn)自動(dòng)加密算法設(shè)計(jì)

圖2 自動(dòng)加密點(diǎn)算法流程圖

2.5 算法實(shí)現(xiàn)

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

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

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

void OnWriteDxfFile();

//儲(chǔ)存等高線點(diǎn)加密后DXF文件

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

class CCubicSpline : public CObject{

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

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); //矩陣相乘 }

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

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

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

3）以DXF格式寫(xiě)出文件。

3 算法驗(yàn)證

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

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

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

圖4 等高線上點(diǎn)加密效果圖

4 結(jié) 語(yǔ)

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

[1] 陳丹.地形圖等高線自動(dòng)識(shí)別與提取中的若干方法研究[D].武漢:武漢大學(xué),2004

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

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

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

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

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

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

P208

B

1672-4623（2015）04-0148-03

10.3969/j.issn.1672-4623.2015.04.053

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

2013-09-17。