一種改進(jìn)的接圖表生成算法

郭 霄 薛 睿 武慧琳 荀張媛

(1. 61363部隊(duì), 陜西 西安 710000; 2. 自然資源部第一大地測(cè)量隊(duì), 陜西 西安 710054;3. 自然資源部測(cè)繪標(biāo)準(zhǔn)化研究所, 陜西 西安 710054; 4. 中煤航測(cè)遙感集團(tuán)公司, 陜西 西安 710199)

0 引言

標(biāo)準(zhǔn)經(jīng)緯度分幅地形圖接圖表作為一種項(xiàng)目管理不可缺少的重要數(shù)據(jù),在測(cè)繪生產(chǎn)領(lǐng)域有著十分重要的作用。當(dāng)前地方數(shù)據(jù)格式管理不一,實(shí)際工作中可能遇見數(shù)據(jù)分別采用新舊編號(hào)規(guī)則管理的圖幅,導(dǎo)致在數(shù)據(jù)匯交管理時(shí),需重新修改接圖表數(shù)據(jù)屬性或重新生成接圖表,現(xiàn)有的制作接圖表方法操作復(fù)雜效率低。因此本文提出一種快速生成接圖表的算法就具有十分重要的意義。

目前主流制作接圖表方法依據(jù)目的分為兩類:一是通過(guò)經(jīng)緯度范圍生成接圖表,主要通過(guò)ArcGIS中ArcToolbox提供的“創(chuàng)建漁網(wǎng)”工具,生成接圖表的骨架,使用者需要提供漁網(wǎng)的起始樞軸點(diǎn),要生成對(duì)應(yīng)比例尺的經(jīng)差與緯差等參數(shù)共11項(xiàng)[1]。該方法處理不夠自動(dòng)化,圖號(hào)等屬性需要后續(xù)通過(guò)字段計(jì)算器添加,費(fèi)時(shí)費(fèi)力,對(duì)操作者專業(yè)水平要求較高,容易出現(xiàn)操作失誤導(dǎo)致的漁網(wǎng)位置錯(cuò)位等問題。二是通過(guò)圖號(hào)創(chuàng)建接圖表,主要通過(guò)Arcpy實(shí)現(xiàn),分為3步：①根據(jù)文件名獲取圖幅號(hào)列表;②按照?qǐng)D幅名計(jì)算坐標(biāo);③依照計(jì)算出的坐標(biāo)生成接圖表多邊形,主要用到的函數(shù)有arcpy.Point()、arcpy. Array()、arcpy. Polygon()[2]。此方法一定程度的提高了生成接圖表的效率,但后續(xù)依舊需要通過(guò)字段計(jì)算器添加圖號(hào)信息,不能一步完成。

為更好地解決以上問題,本文提出了一種新的算法模型,該模型在部分以往的計(jì)算基礎(chǔ)上,借鑒了圖像處理深度優(yōu)先搜索(depth first search,DFS)算法邏輯,減少了操作者干預(yù)接圖表骨架的生成,提高了準(zhǔn)確度,將圖號(hào)信息在算法中直接添加,避免了后續(xù)操作,并將該算法與傳統(tǒng)方法進(jìn)行對(duì)比實(shí)驗(yàn)進(jìn)行驗(yàn)證。

1 接圖表生成算法

1.1 地形圖經(jīng)緯度分幅與編號(hào)

1.1.1地形圖經(jīng)緯度分幅

地形圖經(jīng)緯度分幅指地圖的圖廓由經(jīng)緯線構(gòu)成,我國(guó)的基本比例尺就是以經(jīng)緯線分幅制作的[3]。它們是以1∶1 000 000地圖為基礎(chǔ),按規(guī)定的經(jīng)差和緯差劃分圖幅,行列數(shù)和圖幅數(shù)成簡(jiǎn)單的倍數(shù)關(guān)系[4]。

1.1.2新舊圖幅編號(hào)

新舊圖幅編號(hào)規(guī)則都是在標(biāo)準(zhǔn)經(jīng)緯度分幅的基礎(chǔ)上設(shè)計(jì),新圖幅號(hào)由10位碼組成,以1∶50 000圖號(hào)為例,J50E001002中J代表該圖幅所屬1∶1 000 000圖幅行號(hào)數(shù)字碼、50代表其所屬1∶1 000 000圖幅列號(hào)數(shù)字碼、E代表所屬比例尺代碼、001與002分表代表圖幅行號(hào)與列號(hào)數(shù)字碼[5]。舊圖幅編號(hào)系統(tǒng)按圖1編碼。

所有比例尺都可實(shí)現(xiàn)新舊圖號(hào)轉(zhuǎn)換,以1∶50 000比例尺為例,其對(duì)應(yīng)公式如表1所示,其中H代表新圖幅中的行號(hào),L代表新圖幅中的列號(hào),X代表舊圖號(hào)中的地圖代碼值,[]代表取整,()代表取余。此為靈活生成不同編碼規(guī)則的圖號(hào)接圖表奠定了算法基礎(chǔ)。

圖1 我國(guó)舊式地形圖編號(hào)系統(tǒng)

表1 新舊圖號(hào)轉(zhuǎn)換

1.2 整體計(jì)算流程

本文提出算法將根據(jù)經(jīng)緯度范圍生成接圖表與根據(jù)圖號(hào)生成接圖表結(jié)合,整體流程如圖2所示。圖號(hào)文件可根據(jù)需求輸出為新編碼規(guī)則圖號(hào)與舊編碼規(guī)則圖號(hào)txt文件。

1.3 搜索計(jì)算圖號(hào)

1.3.1深度優(yōu)先搜索(DFS)[6]

DFS是計(jì)算機(jī)術(shù)語(yǔ),是一種在開發(fā)爬蟲早期使用較多的方法,是搜索算法的一種。它的目的是要達(dá)到被搜索結(jié)構(gòu)的葉結(jié)點(diǎn)。

深度優(yōu)先遍歷圖的算法是,假定給定圖G的初始狀態(tài)是所有頂點(diǎn)均未被訪問過(guò),在G中任選一個(gè)頂點(diǎn)i作為遍歷的初始點(diǎn),則深度優(yōu)先搜索遞歸調(diào)用步驟[7-8]。①訪問搜索到的未被訪問的鄰接點(diǎn);②將此頂點(diǎn)標(biāo)記為已訪問節(jié)點(diǎn);③搜索該頂點(diǎn)的未被訪問的鄰接點(diǎn),若該鄰接點(diǎn)存在,則從此鄰接點(diǎn)開始進(jìn)行同樣的訪問和搜索,反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問為止[9]。

圖2 整體算法流程

1.3.2計(jì)算圖號(hào)

本文將經(jīng)緯度范圍圍成的矩形四角頂點(diǎn)類比作圖G的頂點(diǎn)i,這里稱為基點(diǎn),以基點(diǎn)為根結(jié)點(diǎn)搜索與其相鄰的圖幅,相鄰圖幅作為其子節(jié)點(diǎn)[10-11]。

當(dāng)輸入數(shù)據(jù)為經(jīng)緯度范圍時(shí),根據(jù)下式計(jì)算四角其對(duì)應(yīng)的新式圖號(hào)編號(hào),a為1∶1 000 000圖幅所在經(jīng)度帶的字符所對(duì)應(yīng)的數(shù)字碼;b為1∶1 000 000圖幅所在緯度帶的字符所對(duì)應(yīng)的數(shù)字碼[12];c為所求比例尺地形圖在1∶1 000 000地形圖編號(hào)后的行號(hào);d為所求比例尺地形圖在1∶1 000 000地形圖編號(hào)后的列號(hào);λ為某點(diǎn)的經(jīng)度;φ為某點(diǎn)的緯度;Δλ為所求比例尺的經(jīng)差;Δφ為所求比例尺的緯差[13-14]。

以矩形4個(gè)交點(diǎn)圖號(hào)為控制搜索生成邊框圖號(hào),當(dāng)搜索結(jié)束后,計(jì)算四角點(diǎn)圖號(hào)內(nèi)對(duì)角圖號(hào),再以內(nèi)對(duì)角圖號(hào)為基準(zhǔn)再次進(jìn)行搜索。當(dāng)搜索進(jìn)行到最后一個(gè)循環(huán)時(shí)會(huì)有6種情況,分別為(a)田字分布(b)豎向一字分布(c)橫向一字分布(d)單幅分布(e)豎向兩行分布(f)橫向兩行分布。

針對(duì)(a)情況,當(dāng)四角圖號(hào)的對(duì)角圖號(hào)為其本身,則跳出搜索;針對(duì)(b)、(c)情況以兩邊圖幅為基準(zhǔn)向下或向右搜索圖號(hào)至完畢;(d)中當(dāng)四角圖號(hào)的對(duì)角圖號(hào)為同一圖號(hào)時(shí)跳出循環(huán),結(jié)束搜索;(e)(f)判斷向下或向右搜索是否右圖幅如果沒有,結(jié)束搜索。

1.4 通過(guò)圖號(hào)生成接圖表

在已知新圖號(hào)的前提下,通過(guò)(5)(6)式可計(jì)算出該圖幅在西南圖廓點(diǎn)的經(jīng)緯度坐標(biāo)[4]。

通過(guò)該比例尺所屬經(jīng)差與緯差可計(jì)算出其他3個(gè)角點(diǎn)的經(jīng)緯度坐標(biāo),獲取的XY坐標(biāo),寫出文件時(shí)將四角點(diǎn)坐標(biāo)與其對(duì)應(yīng)圖號(hào)一起寫出,為后續(xù)直接在接圖表面數(shù)據(jù)中增加圖號(hào)信息做準(zhǔn)備。根據(jù)實(shí)際需求轉(zhuǎn)換圖號(hào)編碼實(shí)現(xiàn)需要圖號(hào)的直接輸入。

將XY坐標(biāo)轉(zhuǎn)為點(diǎn)要素并通過(guò)spatRef = arcpy.SpatialReference(4326)設(shè)置其空間參考,再將點(diǎn)要素生成線,線轉(zhuǎn)面時(shí)將之前寫出的圖號(hào)寫入面要素屬性中。完成接圖表制作,具體流程如圖3所示。

圖3 通過(guò)圖號(hào)計(jì)算接圖表算法

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

2.1 算法的實(shí)現(xiàn)

2.1.1計(jì)算對(duì)角圖號(hào)實(shí)現(xiàn)

搜索計(jì)算四角圖號(hào)由4個(gè)主要函數(shù)組成,分別是ldown(string number)計(jì)算基準(zhǔn)圖幅左下角圖號(hào);lup(string number)計(jì)算基準(zhǔn)圖幅左上角圖號(hào);rdown(string number)計(jì)算基準(zhǔn)圖幅右下角圖號(hào);rup(string number)計(jì)算基準(zhǔn)圖幅右上角圖號(hào)。每一個(gè)計(jì)算方法都有4種情況：(1)a變b不變；(2)a不變b變；(3)a、b同時(shí)變化；(4)a、b都不變,最后返回計(jì)算圖號(hào)。

2.1.2循環(huán)獲取邊框圖號(hào)

循環(huán)獲取圖號(hào)主要借助toright(string num, string destination);todown(string num,string destination),采用while(true)死循環(huán),當(dāng)搜索圖號(hào)num與目標(biāo)圖號(hào)destination相等,或num圖號(hào)排在destination下方和左方時(shí)循環(huán)跳出,搜索結(jié)束。

最后一個(gè)循環(huán)借助hashset結(jié)構(gòu),在預(yù)先存儲(chǔ)了搜索基準(zhǔn)圖號(hào)的前提下,hashset的長(zhǎng)度為4,hashset主要特點(diǎn)為無(wú)序的不重復(fù),因此借助hashset可以了解最后一個(gè)循環(huán)屬于上文6種情況中的哪一種,利用while(true)死循環(huán),當(dāng)為(a)情況時(shí)添加其對(duì)角圖號(hào)后hashset長(zhǎng)度為仍為4,跳出循環(huán);(b)(c)情況時(shí)hashset長(zhǎng)度為6,借助todown(string num,string destination)、toright(string num, string destination)完成搜索后跳出;(d)情況時(shí)長(zhǎng)度為5,break跳出循環(huán)。

所有圖號(hào)最終都存儲(chǔ)在hashset中通過(guò)foreach循環(huán)遍歷借助stream類寫出。通過(guò)python實(shí)現(xiàn)角點(diǎn)圖號(hào)與邊框圖號(hào)函數(shù)編寫,并將腳本插入Arctoolbox中,方便加入modelbuilder使用。

2.1.3圖號(hào)生成接圖表實(shí)現(xiàn)

借助modelbuilder,實(shí)現(xiàn)圖3流程如圖4所示。其中“計(jì)算xy坐標(biāo)”與“xy轉(zhuǎn)為點(diǎn)要素”工具為插入的腳本工具。

圖4 Modelbuilder實(shí)現(xiàn)算法

2.2 與傳統(tǒng)方法對(duì)比分析

2.2.1參數(shù)對(duì)比

本文計(jì)算經(jīng)緯度范圍內(nèi)的圖號(hào),只需輸入上下緯度與左右經(jīng)度值,與保存路徑。也可以將該腳本拖入的Model中,一步實(shí)現(xiàn)生成。

依據(jù)圖號(hào)生成接圖表界面參數(shù)包括存儲(chǔ)圖號(hào)文件的路徑,判斷是否為一條線上的點(diǎn)的字段name,以及輸出路徑。

而傳統(tǒng)方法所需參數(shù)繁雜,后續(xù)還需要在屬性表中創(chuàng)建字段,使用字段計(jì)算器,計(jì)算幾何還有投影設(shè)置等設(shè)置接圖表圖號(hào)、投影屬性[15]。

2.2.2實(shí)驗(yàn)結(jié)果對(duì)比

以生成1∶50 000數(shù)據(jù)接圖表為例,假定使用傳統(tǒng)方法熟練的情況下,與本文方法對(duì)比如圖5所示，其中粗線為本文方法,細(xì)線為傳統(tǒng)方法。

從圖5可以看出傳統(tǒng)方法人工操作執(zhí)行時(shí)間受操作者的影響較大,且基本運(yùn)行時(shí)間是本文方法的1～2倍。

圖5 整體對(duì)比分析

3 結(jié)束語(yǔ)

本文借鑒深度優(yōu)先搜索算法邏輯,類比接圖表格網(wǎng)為柵格數(shù)據(jù)的像素格網(wǎng),以接圖表四頂點(diǎn)開始搜索經(jīng)緯度范圍內(nèi)的所有圖號(hào),并在通過(guò)圖號(hào)生成接圖表的過(guò)程中將圖號(hào)屬性寫入接圖表矢量數(shù)據(jù)中,與現(xiàn)有制作接圖表的方法相比減少了處理步驟與人工操作,克服了因人工誤操作導(dǎo)致的誤差問題。通過(guò)多次對(duì)比實(shí)驗(yàn)分析證明,該方法大大提高了接圖表生成的效率,有效地降低了制作的復(fù)雜度。但該方法還存在識(shí)別圖號(hào)格式不夠靈活的限制,例如在圖號(hào)中如果出現(xiàn)其他連接符需更改為標(biāo)準(zhǔn)圖號(hào)格式算法才可使用,未來(lái)將對(duì)算法進(jìn)行改進(jìn)使其更加靈活適應(yīng)圖號(hào)的不同格式,擴(kuò)大其適用領(lǐng)域。