王曉穎

(鐵嶺市測(cè)繪管理辦公室，遼寧 鐵嶺 112000)

?

建立于可視化地圖組件的數(shù)據(jù)空間索引研究

王曉穎

(鐵嶺市測(cè)繪管理辦公室，遼寧 鐵嶺 112000)

摘要：根據(jù)地理空間要素的空間對(duì)象、地理位置或形狀之間空間關(guān)系，按特定規(guī)律組合的空間數(shù)據(jù)結(jié)構(gòu)，通過排除篩選不相干的對(duì)象，提升空間操作的效率和速度。此等空間索引建立了多種方法，各有不同。文章對(duì)規(guī)則網(wǎng)格索引進(jìn)行改進(jìn)，在首層劃分的基礎(chǔ)上，以相鄰四個(gè)網(wǎng)格的對(duì)角線點(diǎn)為中心，逐級(jí)格網(wǎng)劃分，形成多級(jí)交錯(cuò)式格網(wǎng)劃分方法的空間索引。此種方法，在定位點(diǎn)匹配時(shí)間和精度上有一定進(jìn)步，從實(shí)驗(yàn)結(jié)果中可以看出，采用基于多級(jí)交錯(cuò)式格網(wǎng)劃分方法的空間索引方法，充分的使用空間信息，舒緩了格網(wǎng)劃分密集導(dǎo)致的數(shù)據(jù)量增加和檢索用時(shí)過長(zhǎng)等矛盾，使實(shí)時(shí)路段搜索更加快捷高效，具有一定的優(yōu)越性。

關(guān)鍵詞：可視化；地圖組件；空間索引；劃分方法

0引言

目前，隨著經(jīng)濟(jì)社會(huì)的迅猛發(fā)展，人們的生活水平不斷提高，汽車這個(gè)交通工具已悄然走進(jìn)千家萬戶，致使城市交通壓力不斷加大，為使人們利用私家交通工具快速搜索路徑，車載導(dǎo)航必不可少。本文研究的就是車載導(dǎo)航的地圖匹配。因單點(diǎn)定位的精度較低，為解決精度低的問題，就要對(duì)單層規(guī)則網(wǎng)格建立空間索引，在基礎(chǔ)網(wǎng)格劃分上繼續(xù)劃分，使搜索區(qū)域逐漸變小而提高精度。以鐵嶺市地圖數(shù)據(jù)為例進(jìn)行了實(shí)驗(yàn)，結(jié)果表明搜索更加簡(jiǎn)捷高效。

1分析空間索引建立方法

1.1數(shù)據(jù)空間索引設(shè)計(jì)

在已有資料的道路層上，均勻的將圖層實(shí)際圖幅尺寸劃分為a×b個(gè)網(wǎng)格，使各個(gè)網(wǎng)格為正方形，設(shè)計(jì)網(wǎng)格邊長(zhǎng)為500 m×500 m。在此基礎(chǔ)上，以每個(gè)網(wǎng)格對(duì)角線交點(diǎn)為中心，再次進(jìn)行500 m×500 m的網(wǎng)格劃分，按照此等方法依次劃分。即多級(jí)交錯(cuò)式劃分方法。

如果設(shè)圖幅尺寸為A×B，a，b分別為A方向和B方向的網(wǎng)格數(shù)量，定位點(diǎn)坐標(biāo)為(x，y),得到如下計(jì)算過程，假設(shè)定位點(diǎn)在第一次網(wǎng)格劃分中的索引塊號(hào)為D，二次劃分網(wǎng)格索引塊號(hào)為(D1，D2，D3，D4)，則D1，D2，D3，D4的計(jì)算過程如公式1：

a=[A/50q]+1

b=[B/50q]+1

D=[x/50q]+[y/50q]×a+1

D1=a×b+[x/50q]+([y/50q-1])×(a-1)

D2=D1+1

D3=D1+(a-1)

D4=D3+1

(1)

式中：[ ]表示取整。

定位點(diǎn)的路段匹配區(qū)域(a=10)。此時(shí)的網(wǎng)格索引塊號(hào)[D，D1，D2，D3，D4]=[6，18，19，31，32]，對(duì)尺寸確定、坐標(biāo)參數(shù)已知的正方形，經(jīng)過數(shù)據(jù)比較，可明確定位點(diǎn)在250 m×250 m格網(wǎng)中的位置。

單點(diǎn)定位精度較差，默認(rèn)誤差為100 m，以定位點(diǎn)為圓心，以100 m為半徑的區(qū)域內(nèi)，在首層格網(wǎng)中區(qū)域可能覆蓋了其它網(wǎng)格，首層網(wǎng)格局限性被忽視，使定位點(diǎn)在某條道路上時(shí)產(chǎn)生重大的錯(cuò)誤。從上述說明可看出，定位點(diǎn)按上述過程進(jìn)行單元格邏輯判斷，匹配道路范圍始終在500 m×500 m的區(qū)域內(nèi)。大大的減小單點(diǎn)定位誤差帶來的影響，高標(biāo)準(zhǔn)的提取待匹配路段信息[1]。

1.2建立多級(jí)劃分流程

取得地圖最弱外接矩形的右上角和左下角的坐標(biāo)，算出高度和寬度；依據(jù)高度與寬度計(jì)算首層格網(wǎng)縱向和橫向上的網(wǎng)格數(shù)b和a；明確首層網(wǎng)格右上角坐標(biāo)，首層網(wǎng)格的標(biāo)識(shí)從01開始；順次計(jì)算各層網(wǎng)格的右上角和左下角坐標(biāo)，根據(jù)算得的坐標(biāo)取得處于該區(qū)域內(nèi)的數(shù)量及其路徑，將得到的信息數(shù)據(jù)存入數(shù)據(jù)庫中，直到每單層網(wǎng)格結(jié)束循環(huán)；計(jì)算二層網(wǎng)格縱向和橫向的格網(wǎng)數(shù)b-1和a-1； 依次計(jì)算多層級(jí)網(wǎng)格的右上角和左下角坐標(biāo)，獲取該區(qū)域的數(shù)量和路徑，并將得到的信息數(shù)據(jù)存入數(shù)據(jù)庫中，所有的層級(jí)格網(wǎng)循環(huán)結(jié)束即可[2]。

2實(shí)現(xiàn)多級(jí)劃分的方法

2.1建立空間索引

2.1.1設(shè)定坐標(biāo)系

使用1980年西安坐標(biāo)系，設(shè)置成高斯-克呂格投影，取得圖形坐標(biāo)系統(tǒng)，按照坐標(biāo)系要求的標(biāo)準(zhǔn)設(shè)置對(duì)應(yīng)的坐標(biāo)系。

2.1.2道路圖層獲取

各幅地圖含有很多圖層，本文的研究只要道路層即可，測(cè)出道路層全部圖元的數(shù)量。

2.1.3數(shù)據(jù)控制

鑒定后臺(tái)服務(wù)數(shù)據(jù)中是否存在數(shù)據(jù)，存在則刪除，不存在則保留。使用指針刪掉首條信息記錄，然后挪動(dòng)到第二個(gè)，依次循環(huán)，直到刪掉最后一條記錄再返回，清空原數(shù)據(jù)庫。

2.1.4確定空間索引

確定最弱外接正方形對(duì)象，獲取右上角和左下角的坐標(biāo)，算得正方形的高和寬，以500為單位計(jì)算縱向上的格網(wǎng)數(shù)b：

int mb=int(Height /wgwz)+1;

bool mb =false;

for(int i=0;i<= mb;i++)

{

if(Height -i* wgwz ==0)

{

m=int(Height / wgwz);

mb =true;

break;

}

}

if(! mb)

{

b=int(Height / wgwz)+1;

}

使用相同的計(jì)算方法得到橫向的格網(wǎng)數(shù)a。

2.1.5描繪多層格網(wǎng)

得到需要圖層，不得自動(dòng)刷新，設(shè)置圖層為可讀寫狀態(tài)并描繪，使用循環(huán)語句，在縱向和橫向上隔500 m繪出一條橫線和豎線。對(duì)每層格網(wǎng)編號(hào)，首層格網(wǎng)編號(hào)從01開始，第二層網(wǎng)格編號(hào)從b×a+1開始，依次類推。最終讓圖層自動(dòng)刷新后不可讀寫[3]。

2.1.6數(shù)據(jù)庫入庫

算出多層格網(wǎng)中全部格網(wǎng)的右上角和左下角坐標(biāo)，獲取每個(gè)格網(wǎng)通過的標(biāo)識(shí)號(hào)和道路數(shù)后入庫。

2.2分析數(shù)據(jù)獲取的經(jīng)過

通過單點(diǎn)定位點(diǎn)坐標(biāo)，計(jì)算確定其所在的多級(jí)網(wǎng)格號(hào)，網(wǎng)格編號(hào)位置如圖1所示：

圖1　兩層網(wǎng)格編號(hào)標(biāo)識(shí)

N級(jí)網(wǎng)格劃分如圖2所示，將第一層D號(hào)網(wǎng)格再次劃分成4×4格網(wǎng)，得到D格網(wǎng)中的各個(gè)小網(wǎng)格的右上角坐標(biāo)。當(dāng)定位點(diǎn)在D網(wǎng)格的不同位置時(shí)，有可能屬于{D，D1，D2，D3，D4}不同的網(wǎng)格內(nèi)，要經(jīng)過計(jì)算確定定位點(diǎn)在D號(hào)格網(wǎng)中的小格網(wǎng)的編碼而數(shù)據(jù)。

if(i_D==6 || i_D==7 || i_D==10 || i_D==11)

{

ListDu m=LiDeDu m_D;

LiDeIDGridArray=Dew iDt[ListDu m];

m_CalBase.striDg_to_array(LiDeIDGrid_D,LiDeDu m_D,LiDeIDGridArray);

}

定位點(diǎn)在5、9或14、15或8、12或2、3位置時(shí)，經(jīng)過計(jì)算來劃定定位點(diǎn)所處的500 m×500 m區(qū)域，保證獲取數(shù)據(jù)準(zhǔn)確的前提下，減少獲取量，可提高效率。

圖2N級(jí)網(wǎng)格劃分

3方法實(shí)驗(yàn)

3.1實(shí)驗(yàn)經(jīng)過

選取鐵嶺市地圖數(shù)據(jù)進(jìn)行了實(shí)驗(yàn)。

3.1.1準(zhǔn)備數(shù)據(jù)

創(chuàng)建新表，確定1980年西安坐標(biāo)系，設(shè)置投影。打開地圖，在控制界面上增加dl圖層，使其處于可編緝狀態(tài)，把dl圖層中增加的線段存在dl表中。在可視化地圖組件中找到dl表并將其保存成.gst文件。

3.1.2建立索引

啟動(dòng)程序，打開地圖，點(diǎn)選建立索引響應(yīng)，系統(tǒng)自動(dòng)建立空間索引，清空數(shù)據(jù)庫后，生成新的數(shù)據(jù)庫表，如圖3所示。

圖3數(shù)據(jù)庫表

3.2結(jié)果驗(yàn)證

1)準(zhǔn)確性方面，原方法對(duì)單個(gè)網(wǎng)格檢索，準(zhǔn)確性為57%，而采用多級(jí)交錯(cuò)式格網(wǎng)劃分方法，其準(zhǔn)確性為100%，可見本文研究的準(zhǔn)確性很高。

2)數(shù)據(jù)量方面，傳統(tǒng)格網(wǎng)劃分方法有2680個(gè)網(wǎng)格單元，多級(jí)交錯(cuò)式格網(wǎng)劃分方法則有1183個(gè)網(wǎng)格單元，數(shù)據(jù)庫中存儲(chǔ)的記錄數(shù)大幅度減少。

3)檢索方面，通過單元格的檢索變化，也可看出數(shù)據(jù)檢索效率大大提高。

4結(jié)論

通過對(duì)空間索引方法的研究，分析各自的優(yōu)缺點(diǎn)，文章對(duì)規(guī)則網(wǎng)格索引進(jìn)行改進(jìn)，在首層劃分的基礎(chǔ)上，以相鄰四個(gè)網(wǎng)格的對(duì)角線點(diǎn)為中心，逐級(jí)格網(wǎng)劃分，形成多級(jí)交錯(cuò)式格網(wǎng)劃分方法的空間索引。此種方法，在定位點(diǎn)匹配時(shí)間和精度上有一定進(jìn)步，從實(shí)驗(yàn)結(jié)果中可以看出，采用基于多級(jí)交錯(cuò)式格網(wǎng)劃分方法的空間索引方法，充分的使用空間信息，舒緩了格網(wǎng)劃分密集導(dǎo)致的數(shù)據(jù)量增加和檢索用時(shí)過長(zhǎng)等矛盾，使實(shí)時(shí)路段搜索更加快捷高效，具有一定的優(yōu)越性。

參考文獻(xiàn)：

[1]隋心．GPS車輛導(dǎo)航系統(tǒng)中地圖匹配算法研究[D].沈陽：遼寧工程技術(shù)大學(xué)，2007.

[2]龔強(qiáng).GIS及空間數(shù)據(jù)組織管理[M].哈爾濱:哈爾濱地圖出版社,2004:157-169.

[3]尹旭日，張武軍.Visual C++環(huán)境下mapX 的開發(fā)技術(shù)[M].北京: 冶金工業(yè)出版社，2009：21-36．

中圖分類號(hào)：P208

文獻(xiàn)標(biāo)識(shí)碼：B

[作者簡(jiǎn)介]王曉穎(1979-)，女，遼寧鐵嶺人，工程師，從事測(cè)繪業(yè)務(wù)工作。

[收稿日期]2016-01-14

文章編號(hào)：1007-7596(2016)03-0041-03