王曉穎

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

?

建立于可視化地圖組件的數據空間索引研究

王曉穎

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

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

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

0引言

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

1分析空間索引建立方法

1.1數據空間索引設計

在已有資料的道路層上，均勻的將圖層實際圖幅尺寸劃分為a×b個網格，使各個網格為正方形，設計網格邊長為500 m×500 m。在此基礎上，以每個網格對角線交點為中心，再次進行500 m×500 m的網格劃分，按照此等方法依次劃分。即多級交錯式劃分方法。

如果設圖幅尺寸為A×B，a，b分別為A方向和B方向的網格數量，定位點坐標為(x，y),得到如下計算過程，假設定位點在第一次網格劃分中的索引塊號為D，二次劃分網格索引塊號為(D1，D2，D3，D4)，則D1，D2，D3，D4的計算過程如公式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)

式中：[ ]表示取整。

定位點的路段匹配區(qū)域(a=10)。此時的網格索引塊號[D，D1，D2，D3，D4]=[6，18，19，31，32]，對尺寸確定、坐標參數已知的正方形，經過數據比較，可明確定位點在250 m×250 m格網中的位置。

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

1.2建立多級劃分流程

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

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

2.1建立空間索引

2.1.1設定坐標系

使用1980年西安坐標系，設置成高斯-克呂格投影，取得圖形坐標系統(tǒng)，按照坐標系要求的標準設置對應的坐標系。

2.1.2道路圖層獲取

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

2.1.3數據控制

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

2.1.4確定空間索引

確定最弱外接正方形對象，獲取右上角和左下角的坐標，算得正方形的高和寬，以500為單位計算縱向上的格網數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;

}

使用相同的計算方法得到橫向的格網數a。

2.1.5描繪多層格網

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

2.1.6數據庫入庫

算出多層格網中全部格網的右上角和左下角坐標，獲取每個格網通過的標識號和道路數后入庫。

2.2分析數據獲取的經過

通過單點定位點坐標，計算確定其所在的多級網格號，網格編號位置如圖1所示：

圖1　兩層網格編號標識

N級網格劃分如圖2所示，將第一層D號網格再次劃分成4×4格網，得到D格網中的各個小網格的右上角坐標。當定位點在D網格的不同位置時，有可能屬于{D，D1，D2，D3，D4}不同的網格內，要經過計算確定定位點在D號格網中的小格網的編碼而數據。

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);

}

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

圖2N級網格劃分

3方法實驗

3.1實驗經過

選取鐵嶺市地圖數據進行了實驗。

3.1.1準備數據

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

3.1.2建立索引

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

圖3數據庫表

3.2結果驗證

1)準確性方面，原方法對單個網格檢索，準確性為57%，而采用多級交錯式格網劃分方法，其準確性為100%，可見本文研究的準確性很高。

2)數據量方面，傳統(tǒng)格網劃分方法有2680個網格單元，多級交錯式格網劃分方法則有1183個網格單元，數據庫中存儲的記錄數大幅度減少。

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

4結論

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

參考文獻：

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

[2]龔強.GIS及空間數據組織管理[M].哈爾濱:哈爾濱地圖出版社,2004:157-169.

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

中圖分類號：P208

文獻標識碼：B

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

[收稿日期]2016-01-14

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