基于彈性力學(xué)思想的河流等高線沖突自動(dòng)處理方法

劉 芳，王光霞，侯 璇，賈奮勵(lì)

（1．61175部隊(duì)，江蘇 南京210049；2．信息工程大學(xué) 地理空間信息學(xué)院，河南 鄭州450052；3．南京市棲霞區(qū)體育局，江蘇 南京210046）

河流等高線沖突是數(shù)字地圖中常見的錯(cuò)誤之一。在數(shù)字制圖中，地圖綜合的位移操作是解決河流等高線沖突的有效方法。位移是在許可的范圍內(nèi)最大限度地保持目標(biāo)的定位精度，并在盡量保持目標(biāo)整體特征、相互關(guān)系以及排列特征的情況下，移開有沖突的目標(biāo)［1］。河流等高線沖突屬于目標(biāo)間沖突，只需要對目標(biāo)的局部范圍進(jìn)行調(diào)整即可解決，不需要對目標(biāo)整體位移，即犧牲目標(biāo)的部分形狀特征換取目標(biāo)大部分區(qū)域位置精度的方法。

線目標(biāo)位移的算法很多，大致可分為機(jī)械式算法和優(yōu)化算法。這兩種算法都能解決一定的位移問題，但是機(jī)械式算法的收斂性不好，不能控制位移的傳播，會(huì)產(chǎn)生新的沖突；優(yōu)化算法效率較低，且不能保證解決所有的原始沖突。

彈性力學(xué)是固體力學(xué)的一個(gè)分支，主要研究彈性體受到外力作用或溫度改變等原因而發(fā)生的應(yīng)力、形變和位移［2］。彈性體變形的基本特征是保持目標(biāo)空間關(guān)系的大體不變性，符合制圖綜合中位移的效果，特別是其中的桿件受力變形與位移有許多共同之處，因此可以用于解決河流等高線的沖突問題。由于平面桿件彈性體的受力變形模型十分復(fù)雜而導(dǎo)致無法利用傳統(tǒng)的解析方法求解。因此本文采用數(shù)值計(jì)算中的有限元法解決此問題。

1 彈性力學(xué)原理與有限元方法

彈性力學(xué)的基本思想是當(dāng)物體受到一定外力作用時(shí)產(chǎn)生形變，當(dāng)外力撤消時(shí)又恢復(fù)原形；如果僅僅是物體的部分受力，則在變形時(shí)物體的總體形狀基本保持不變，只是局部變形［3］。該特點(diǎn)符合數(shù)字制圖中處理河流等高線沖突的基本原則，因此采用這一思想對河流等高線沖突進(jìn)行檢測和糾正。作為彈性目標(biāo)結(jié)構(gòu)，等高線受到來自于河流的引力作用而發(fā)生形狀改變。

有限元方法是一種數(shù)值計(jì)算方法，它主要用于求解復(fù)雜結(jié)構(gòu)或非線性方程組。其基本思想是將連續(xù)的求解區(qū)域離散為一組有限的、且按一定方式相互連接在一起的單元組合。然后利用每個(gè)單元內(nèi)假設(shè)的近似函數(shù)來分片地表示整個(gè)求解區(qū)域上待求的未知場函數(shù)。單元內(nèi)的近似函數(shù)通常由未知函數(shù)及其導(dǎo)數(shù)在單元的各個(gè)結(jié)點(diǎn)的數(shù)值和其插值函數(shù)來表達(dá)。因此，未知場函數(shù)及其導(dǎo)數(shù)在各個(gè)結(jié)點(diǎn)上的數(shù)值就成為新的未知量（即自由度），從而使一個(gè)連續(xù)的無限自由度的問題變成離散的有限自由度的問題。如果單元是滿足收斂要求的，近似解最后將收斂于精確解［3］。其基本步驟有5個(gè)：物體的離散化、挑選形函數(shù)或插值函數(shù)、確定單元的性質(zhì)、組成物體的總性質(zhì)方程組、解方程組［4］。

在本文研究的問題中，河流、等高線作為地理相關(guān)目標(biāo)，具有一定的形態(tài)結(jié)構(gòu)特征，即河流總是流經(jīng)谷底。因此河流與等高線的交點(diǎn)必然是谷底點(diǎn)，若河流與等高線的交點(diǎn)與谷底點(diǎn)不重合，則需要將等高線上的交點(diǎn)移動(dòng)到谷底點(diǎn)位置。從彈性力學(xué)角度講，可把等高線視為一個(gè)彈性體，一個(gè)點(diǎn)的受力變化必然會(huì)引發(fā)相鄰點(diǎn)的受力改變，因而其位置也相對移動(dòng)，且這種改變會(huì)逐漸減小并消失，這就保證了目標(biāo)的相對空間關(guān)系不會(huì)發(fā)生較大改變，達(dá)到期望效果。

2 河流等高線沖突探測

沖突探測是算法中的重要問題。本文將入庫數(shù)據(jù)中河流等高線的沖突歸納為兩種情況。第1種是河流與等高線的交點(diǎn)不在谷底點(diǎn)上，如圖1中數(shù)字1標(biāo)識(shí)的位置，這種情況可以通過對等高線進(jìn)行局部變形來解決。第2種情況是一條河流與同一條等高線有多個(gè)交點(diǎn)，如圖1中數(shù)字2標(biāo)識(shí)的位置，這種沖突情況處理較為復(fù)雜，需要人工干預(yù)。第1種情況可以通過本文算法進(jìn)行自動(dòng)糾正；第2種情況較為復(fù)雜，必須通過人工糾正。

圖1 河流等高線沖突情況

2．1 河流等高線求交點(diǎn)

經(jīng)分析可知，河流等高線發(fā)生沖突的位置在二者的交點(diǎn)附近，因此沖突探測的第一步就是求交計(jì)算。本文采用向量跨立求交算法。所謂跨立是指某條線段的兩個(gè)端點(diǎn)是否與另一線段所在的直線相交，采用叉積方法來確定。其設(shè)計(jì)思想：首先從點(diǎn)條的輔 叉P1助積與出 線，以發(fā)段及向P另1P的一3方線 和 向與段P。1的 P若兩4，兩個(gè)然的個(gè)端后叉叉點(diǎn)計(jì)積積P算，的3從和 正而P負(fù)判4相與 斷引反向出，兩 量 則P3P4跨立P1P2所在的直線，如圖2（a）所示；若兩個(gè)叉積的正負(fù)號相同，則P3P4不能跨立P1P2所在的直線，如圖2（b）所示；若任何一個(gè)叉積為0，則P3和P4兩點(diǎn)中必有一點(diǎn)處于線段P1P2所在的直線上，如圖2（c）所示。

圖2 向量跨立求交算法

只有兩線段的叉積正負(fù)相反時(shí)，才對河流和等高線進(jìn)行求交計(jì)算，同時(shí)記錄交點(diǎn)所處河流的點(diǎn)位、等高線點(diǎn)位及該段河流的坐標(biāo)。去除偽交點(diǎn)和重復(fù)交點(diǎn)，并將交點(diǎn)按照河流的ID號排序。偽交點(diǎn)包括以下2種情況：交點(diǎn)位于線段的兩個(gè)端點(diǎn)；求交線段中的某條位于另一條線段的同一側(cè)。

2．2 求谷底點(diǎn)

定義1 假設(shè)河流等高線交點(diǎn)附近的一段等高線上的n個(gè) 點(diǎn)｛P0，P1，P2，…，Pn｝為 待 定 谷 底 點(diǎn)集合。

定義2 交點(diǎn)處的河流向量為River Vector，交點(diǎn)為Intersection Pt。

定義3 假設(shè)河流等高線交點(diǎn)位于P1和P2之間，則等高線向量。

由谷底點(diǎn)的幾何性質(zhì)可知［5－6］，谷底點(diǎn)為等高線上的局部曲率最大點(diǎn)；河流向量River Vector總是位于等高線向量Contour Vector的順時(shí)針方向。根據(jù)以上兩點(diǎn)性質(zhì)可以確定谷底點(diǎn)。河流向量與等高線向量的關(guān)系歸納見圖3。圖3（a）和圖3（c）中河流向量在等高線向量的逆時(shí)針方向，這時(shí)首先需要將待定谷底點(diǎn)集合｛P0，P1，P2，…，P5｝逆序排列，然后計(jì)算最大曲率點(diǎn)即谷底點(diǎn)；圖3（b）和圖3（d）中河流向量在等高線向量的順時(shí)針方向，此時(shí)直接計(jì)算所有待定谷底點(diǎn)的曲率值，最大曲率點(diǎn)即為谷底點(diǎn)。具體步驟如下所述。

圖3 谷底點(diǎn)與河流向量到等高線向量方向的關(guān)系圖

1）計(jì)算向量River Vector到向量Contour Vector的方向，采用二者的叉積判斷，如果為叉積小于0，則為逆時(shí)針方向，需要將待定谷底點(diǎn)集合逆序排列。

2）對處理后的待定谷底點(diǎn)集合求曲率，除首、末點(diǎn)P1，Pn外任意點(diǎn)Pi的曲率Curi可以根據(jù)式（2）求得

其中，θi為向量Pi－1Pi和PiPi＋1的夾角；di為弧段Pi－1PiPi＋1的長度。當(dāng)θ一定時(shí)，其對應(yīng)的弧長d越小則曲率越大，由此可以計(jì)算出弧段內(nèi)的最大曲率點(diǎn)，即谷底點(diǎn)。

3 強(qiáng)制位移量的確定

得到谷底點(diǎn)和沖突點(diǎn)信息后，下一步需要確定消除沖突部分所需的最小位移量，即沖突部分完全移動(dòng)到?jīng)_突線的另一側(cè)時(shí) 所有可能位移方向中距離最小的一個(gè)向量［7］。具體可以分為如圖4所示的3種情況，其中Pb為谷底點(diǎn)，Pc為沖突點(diǎn)。

1）當(dāng)沖突點(diǎn)位于河流線段的中間，強(qiáng)制位移量為谷底點(diǎn)到最近的河流線段的最小距離，方向垂直于河流線段，如圖4（a）所示。

2）當(dāng)沖突點(diǎn)位于河流線段的始端點(diǎn)，強(qiáng)制位移量為谷底點(diǎn)到該點(diǎn)的最小距離，方向?yàn)楣鹊c(diǎn)與該點(diǎn)的連線，如圖4（b）所示。

3）當(dāng)沖突點(diǎn)位于河流線段的末端點(diǎn)，強(qiáng)制位移量為谷底點(diǎn)到該點(diǎn)的最小距離，方向?yàn)楣鹊c(diǎn)與該點(diǎn)的連線，如圖4（c）所示。

圖4 計(jì)算強(qiáng)制位移量示意圖

當(dāng)強(qiáng)制位移量過大時(shí)，如果強(qiáng)行移動(dòng)會(huì)破壞整個(gè)彈性體的彈性，從而導(dǎo)致位移結(jié)果變形。因此對于超過閾值范圍的沖突點(diǎn)，不能用這種方法自動(dòng)糾正，需要記錄其坐標(biāo)，方便人工處理。

4 目標(biāo)的變形方法

4．1 建立單元?jiǎng)偠染仃?/h3>

其中，KG為考慮橫剪力的桿全局坐標(biāo)剛度單元，E為彈性系數(shù)，s＝sinα，c＝cosα。

4．2 確定并集合相關(guān)的變形目標(biāo)

在制圖綜合中，河流等級和精度高于等高線，因此在二者沖突時(shí)，應(yīng)當(dāng)改變等高線的形狀。等高線構(gòu)成了空間桿件結(jié)構(gòu)，改變一個(gè)頂點(diǎn)往往會(huì)引發(fā)其他相關(guān)頂點(diǎn)的相應(yīng)變動(dòng)，所以在操作過程中要對所有需要變形的地點(diǎn)進(jìn)行適當(dāng)處理，使相關(guān)頂點(diǎn)形成一個(gè)整體，然后對這個(gè)整體進(jìn)行變形操作，只有這樣才不會(huì)破壞原目標(biāo)的整體結(jié)構(gòu)。文中的相關(guān)頂點(diǎn)個(gè)數(shù)是個(gè)經(jīng)驗(yàn)值（20），與等高線采集的密度及其地貌特征相關(guān)。這些頂點(diǎn)屬于不同的單元，并且在總剛度矩陣中的位置相同。多個(gè)目標(biāo)公用一個(gè)結(jié)點(diǎn)，通過這個(gè)公用的結(jié)點(diǎn)，不同目標(biāo)的剛度矩陣集合到一起。把每一個(gè)有強(qiáng)制位移量的頂點(diǎn)看作一個(gè)平面桿狀目標(biāo)，這樣帶有強(qiáng)制位移量的頂點(diǎn)集合就構(gòu)成了所有變形目標(biāo)的集合。

4．3 求解方程

仔細(xì)觀察式（3），可以看出它是一個(gè)奇異矩陣，只有引入足夠的約束條件消除其奇異性，才能得到唯一解。在這里約束條件就是前文計(jì)算的強(qiáng)制位移量，它是通過沖突探測和制圖約束條件分析得到的。引入約束條件的方法有多種，在程序計(jì)算中可以采用能求得精確解的置1賦0法。

將方程中給定位移σ的行和列的主元改為1，其余全部置0，并將原來矩陣的第i行除對角線元素外乘以給定位移σ后移到等式另一端，對應(yīng)的第i行的右端項(xiàng)Fi改為σ，修改后方程變?yōu)?/p>

顯然方程第i行等價(jià)于σi＝σ。

由式3可知，對位移有影響的參數(shù)有彈性系數(shù)E、彎曲慣性矩I、橫截面A。不同參數(shù)配置得到不同的位移變形結(jié)果。E越大桿件越不易變形；A越大桿件的伸縮性就越好；I越大桿件就更易于彎曲。根據(jù)制圖綜合規(guī)則和等高線變形等級，本文實(shí)驗(yàn)中給它們賦值如下：E＝5，I＝2，A＝0．851。

5 實(shí)驗(yàn)與分析

圖5 試驗(yàn)效果

采用1∶5萬數(shù)字地形圖作為試驗(yàn)用圖，結(jié)果如圖5所示。其中灰色線為河流，黑色實(shí)線為位移后的等高線 黑色虛線為位移前等高線 從圖5中可以看出，只有產(chǎn)生了沖突的地方得到了修正，等高線形態(tài)保持較好，并且等高線與水系的關(guān)系保持較好，處理結(jié)果基本滿足制圖綜合約束條件的要求。

表1列出了實(shí)驗(yàn)使用的3幅1∶5萬地形圖中河流等高線沖突的檢測點(diǎn)數(shù)以及進(jìn)行位移操作的各項(xiàng)參數(shù)。其中位移點(diǎn)數(shù)表示有沖突的點(diǎn)數(shù)，最大角度變形指所有相鄰線段的夾角的最大變化值。從表1中可以看出 對沖突點(diǎn)的修正率達(dá)到80%以上。在檢測出來的待位移點(diǎn)中，有一部分沖突是河流爬坡，還有一些是超過最大位移量的沖突點(diǎn)，這類沖突需要人工解決。經(jīng)過該算法糾正的沖突點(diǎn)，無論x軸方向還是y軸方向，位移量都未超過1 mm；且最大角度變形和位移傳播范圍都能滿足制圖綜合的要求。位移后的等高線也能夠保持基本形態(tài)。

表1 1∶5萬地形圖中河流等高線沖突檢測及糾正結(jié)果表

6 結(jié)束語

本文提出的基于彈性力學(xué)思想的河流等高線沖突處理方法具有幾何不變性、差異性和使用方便的特點(diǎn)，綜合后等高線和河流的形態(tài)及相互關(guān)系保持較好，應(yīng)用方便。實(shí)驗(yàn)證明該方法處理后的結(jié)果能夠達(dá)到生產(chǎn)精度要求，可以推廣使用。該算法的缺點(diǎn)是計(jì)算較為復(fù)雜，時(shí)間耗費(fèi)較長。本文研究僅適用于單線河與等高線發(fā)生沖突的情況，對于河流穿同根等高線、河流爬坡等沖突的自動(dòng)檢測與修正問題，需進(jìn)一步研究。

［1］ 武芳，侯璇，錢海忠，等．自動(dòng)制圖綜合中的線目標(biāo)位移模型［J］．測繪學(xué)報(bào)，2005，35（3）：269－276．

［2］ 徐芝綸．彈性力學(xué)［M］．北京：高等教育出版社，1990：210－254．

［3］ 李人憲．有限元算法基礎(chǔ)［M］．北京：國防工業(yè)出版社，2002：1－4；188－190．

［4］ 侯璇．基于彈性力學(xué)原理的自動(dòng)綜合位移模型［D］．鄭州：信息工程大學(xué)，2004：5－34．

［5］ 王強(qiáng)，曹輝．?dāng)?shù)字地形圖中河流線與谷底線空間沖突自動(dòng)檢測及糾正［J］．測繪通報(bào)，2010（12）：58－61．

［6］ GALANDA M．Automated Polygon Generalization in a Multi Agent System［D］．Zurich：Depart ment of Geography，University of Zurich．2003：13－18．

［7］ 劉芳，錢海忠，侯璇．基于彈性力學(xué)思想的GIS多源數(shù)據(jù)誤差糾正方法［J］．測繪工程，2009，16（1）：1－5．

［8］ 楚彬，范東明．改進(jìn)的多元線性回歸模型及其應(yīng)用［J］．測繪工程，2014，23（6）：63－66．

［9］ 蒙印，艾廷華，楊井源．1∶250 000水系要素綜合縮編技術(shù)方法［J］．測繪與空間地理信息，2014，37（3）：201－203．

［10］夏永亮．基于復(fù)雜網(wǎng)絡(luò)理論的城市道路網(wǎng)絡(luò)自動(dòng)綜合方法［J］．測繪與空間地理信息，2014，37（8）：155－156．

［11］宋少輝，魏東嵐，王雪．基于Map Basic的等高線賦值設(shè)計(jì)與實(shí)現(xiàn)［J］．測繪與空間地理信息，2014，37（11）：121－123．

［12］郭薇，郭菁，胡志勇．空間數(shù)據(jù)庫索引技術(shù)［M］．上海：交通大學(xué)出版社，2006：4－43．

［13］賈奮勵(lì)．電子地圖多尺度表達(dá)的研究與實(shí)踐［D］．鄭州：信息工程大學(xué)，2010：6－18．

［14］黃麗娜，費(fèi)立凡．采用3維Douglas－Peucker算法的等高線 綜 合［J］．測 繪 科 學(xué) 技 術(shù) 學(xué) 報(bào)，2009，26（6）：444－448．

［15］安曉亞，孫群，肖強(qiáng)，等．一種基于啟發(fā)式算法的等高線局部內(nèi)插方法［J］．測繪科學(xué)技術(shù)學(xué)報(bào)，2008，25（1）：50－53．

［16］王家耀．空間數(shù)據(jù)自動(dòng)綜合研究進(jìn)展及趨勢分析［J］．測繪科學(xué)技術(shù)學(xué)報(bào)，2008，25（1）：1－7．