數(shù)字等高線邊界問題處理算法優(yōu)化研究

勾朝陽

(忻州師范學(xué)院地理系，山西忻州034000)

0 引言

數(shù)字化等高線的過程中，會出現(xiàn)等高線首尾節(jié)點與區(qū)域邊界不連接，或等高線首尾節(jié)點超出區(qū)域邊界外(圖1)，使后期處理工作量增加，一般在原有矢量等高線上直接手工校正，但工作量非常大.因此，利用原有矢量化等高線直接自動處理的方法是值得研究的課題［1］.

圖1 未處理等高線邊界

1 數(shù)據(jù)結(jié)構(gòu)

算法的執(zhí)行效率與數(shù)據(jù)結(jié)構(gòu)之間存在密切的關(guān)系.一個良好的數(shù)據(jù)結(jié)構(gòu)有利于對數(shù)據(jù)進(jìn)行高效的管理，從而提高算法的執(zhí)行效率［2］.數(shù)據(jù)結(jié)構(gòu)如下:

2 算法思想

2.1 算法原理

第一步，判斷等高線是閉合曲線還是開放曲線.如果為閉合曲線則繼續(xù)判斷下一條，如果為開放曲線則進(jìn)入第二步.

第二步，搜索等高線首節(jié)點和尾節(jié)點，判斷首節(jié)點或尾節(jié)點是否在邊界上.如果在邊界上則繼續(xù)判斷下一條等高線，如果不在邊界上則進(jìn)入第三步.

第三步，判斷等高線首節(jié)點或尾節(jié)點是在區(qū)域邊界內(nèi)還是在區(qū)域邊界外.［3］如果在區(qū)域邊界內(nèi)，則轉(zhuǎn)入第四步，否則轉(zhuǎn)入第五步.

第四步，(1)線頭的延長.等高線第一點和第二點所在直線與相應(yīng)邊界區(qū)域求交點并記錄，將此交點作為等高線的首節(jié)點.

(2)線尾的延長.把等高線倒數(shù)第一點和倒數(shù)第二點所在直線與相應(yīng)邊界區(qū)域求交點并記錄，將此交點作為等高線的尾節(jié)點.

第五步，(1)線頭的裁剪.繼續(xù)判斷等高線第二點和第三點等等直至找到出現(xiàn)在區(qū)域邊界內(nèi)的一點為止并記為(xi，yi)，求線段(xi-1，yi-1)(xi，yi)與相應(yīng)區(qū)域邊界的交點并記錄，用此交點作為等高線的首節(jié)點，重新生成等高線.

(2)線尾的裁剪.繼續(xù)判斷等高線倒數(shù)第二點和倒數(shù)第三點等等直至找到出現(xiàn)在區(qū)域邊界內(nèi)的一點為止并記為(xi，yi)，求線段(xi-1，yi-1)(xi，yi)與相應(yīng)區(qū)域邊界的交點并記錄，用此交點作為等高線的尾節(jié)點，重新生成等高線.

2.2 算法流程圖

圖2 算法流程圖

3 算法實現(xiàn)

3.1 判斷等高線是否為閉合曲線

3.2 判斷首節(jié)點和尾節(jié)點是否在區(qū)域邊界上

3.3 判斷首節(jié)點和尾節(jié)點是否在區(qū)域邊界內(nèi)

3.3.1 判斷首節(jié)點是否在區(qū)域邊界內(nèi)

圖3 首尾節(jié)點均在邊界內(nèi)

圖4 首節(jié)點在超出邊界，尾節(jié)點在邊界內(nèi)

圖5 首節(jié)點延長至邊界上

3.3.2 判斷尾節(jié)點是否在區(qū)域邊界內(nèi)

尾節(jié)點處理方法與首節(jié)點相同.

3.4 判斷每個節(jié)點是否在區(qū)域邊界外

圖6 首節(jié)點均超出邊界

圖7 第i個節(jié)點在邊界內(nèi)

3.4.1 從第二個節(jié)點開始向后判斷

3.4.2 從倒數(shù)第二個節(jié)點開始向前判斷

圖8 尾節(jié)點超出邊界

圖9 第i個節(jié)點在邊界內(nèi)

4 實例應(yīng)用

圖10 處理前等高線

圖11 處理后等高線

本文很好地解決了引言中所提出的問題，程序不僅適用于所有矩形邊界的同類問題，而且通過邊界的變換，可以推廣至不規(guī)則復(fù)雜邊界的同類問題.

5 結(jié)語

本文算法結(jié)構(gòu)簡單明了，內(nèi)外共兩層for循環(huán)，外層為等高線條數(shù)，內(nèi)層為區(qū)域邊界數(shù)，因而時間復(fù)雜度為O(1)，運(yùn)行效率較高.但隨著等高線數(shù)據(jù)量的增大，需要的內(nèi)存空間會有所增加.

［1］李峰婷，陳性義，趙禮劍，等.矢量等高線自動內(nèi)插加密分析［J］.工程地球物理學(xué)報，2004，(1):183-185.

［2］沈雷，李翔，邵培南.C/C++軟件測試工具的元數(shù)據(jù)結(jié)構(gòu)設(shè)計與實現(xiàn)［J］.計算機(jī)工程，2008，34(13):43-48.

［3］張宏，溫永寧，劉愛利.地理信息系統(tǒng)算法基礎(chǔ)［M］.北京:科學(xué)出版社，2006.30-32.

［4］劉勇奎.圖形裁剪算法研究［J］.計算機(jī)工程與應(yīng)用，2005，(21):18-23.

［5］李雪，石廣田.任意多邊形窗口的有效線裁剪算法［J］.蘭州交通大學(xué)學(xué)報(自然科學(xué)版)，2007，26(3):41-47.