[發明專利]線性要素空間索引構建方法、系統和檢索方法及其系統

有效

• 申請號: 201310356524.X
• 申請日: 2013-08-15
• 公開（公告）號: CN103473268A
• 公開（公告）日: 2013-12-25
• 發明（設計）人: 蔡越;王翔;王玫
• 申請（專利權）人: 北京恒達時訊科技開發有限責任公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京路浩知識產權代理有限公司 11002
• 代理人: 王瑩

技術領域

本發明涉及空間信息系統技術領域，尤其涉及一種線性要素空間索引構建方法、系統及其檢索方法和系統。

背景技術

R樹是一個高度平衡樹，它是B樹在k維上的自然擴展，用空間對象的MBR來近似表達空間對象，根據地物的MBR建立R樹，可以直接對空間中占據一定范圍的空間對象進行索引。R樹的每一個結點都對應著磁盤頁D和區域I，如果結點不是葉結點，則該結點的所有子結點的區域都在區域I的范圍之內，而且存儲在磁盤頁D中。如果結點是葉結點，那么磁盤頁D中存儲的將是區域I范圍內的一系列子區域，子區域緊緊圍繞空間對象，一般為空間對象的外接矩形。

由于建立索引的依據為幾何對象的外接多邊形，適應用面域要素，對于長度較長線性要素，特別是當線狀要素長度達到一定的長度時，其外接矩形的范圍就會比較大，在進行查詢的時候，尤其是小范圍區域查詢，導致查詢的空白區域也會返回大量數據，對后續空間分析帶來大量無效運算，降低了查詢準確度，從而整體上降低空間檢索的效率。

發明內容

（一）要解決的技術問題

本發明所要解決的技術問題是：如何提供一種線性要素空間索引構建方法、系統及其檢索方法和系統，以降低現有技術中由于查詢的外接矩形面積過大導致的查詢結果準確度低的技術問題。

（二）技術方案

為了解決上述技術問題，一方面，本發明提供了一種基于R樹的線性要素空間索引構建方法，該方法包括：

根據線性要素的坐標長度，計算出每個端點B_n到起始點A的距離，起始點A的坐標為（x₀，y₀）、端點（x_n+1，y_n+1）;

按如下公式計算：

Dis(n+1)=Dis(n)+(xn+1-xn)2+(yn+1-yn)2;]]>

式中，n為非負整數;Dis（n+1）表示第n+1個端點離起始點的距離；Dis（n）表示第n個端點離起始點的距離；x_n表示n個端點的x坐標；x_n+1表示n+1個端點的x坐標；y_n示n個端點的y坐標；y_n+1表示n+1個端點的y坐標；

判斷計算出每個端點到起始點的距離是否小于等于標準長度，如果是，以起始點到該端點的連線為對角線構建矩形，利用構建的各個矩形構建R樹空間索引。

優選地，如果一個端點到起始點的距離大于標準長度，該方法進一步包括：采用二分插入法對線段AB_n進行分段：

當n為0，則對線段AB_n進行插入點C₁；判斷AC₁的長度是否小于標準長度，如果是，則對線段CB_n進行插入；否則，則對線段AC₁進行插入；