[發明專利]一種基于掩碼技術和剖分編碼的位置信息快速檢索方法

有效

• 申請號: 201410373107.0
• 申請日: 2014-07-31
• 公開（公告）號: CN104182475A
• 公開（公告）日: 2014-12-03
• 發明（設計）人: 程承旗;濮國梁;王慧玲
• 申請（專利權）人: 北京大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京理工大學專利中心 11120
• 代理人: 高燕燕;仇蕾安

1.一種基于掩碼技術和剖分編碼的位置信息快速檢索方法，其特征在于，在GeoSOT剖分和編碼方案中，對應每個層級j創建層級掩碼C_j，C_j與第32層級的GeoSOT編碼長度一致，且對應層級1～j的位均為1、剩余位為0；1≤j≤32；

針對檢索區域，在GeoSOT剖分和編碼方案中選定與所述檢索區域有關聯關系的剖分面片集，剖分面片集中剖分面片p的GeoSOT編碼為Gd_p；

針對剖分面片集中的每一個剖分面片p獲取檢索結果：將剖分面片p的層級掩碼進行邏輯非的位操作之后與Gd_p進行邏輯或運算，獲得剖分面片p范圍內所包含的GeoSOT編碼數值最大的第32級剖分面片的編碼G_maxp；采用位比較方式，檢索獲得GeoSOT編碼大于或等于Gd_p且小于或等于G_maxp的所有剖分面片，檢索獲得的剖分面片的位置信息作為檢索結果；

匯總剖分面片集中各剖分面片對應的檢索結果。

2.如權利要求1所述的一種基于掩碼技術的剖分編碼的位置信息快速檢索方法，其特征在于，所述在GeoSOT剖分和編碼方案中選定與所述檢索區域有關聯關系的剖分面片集為：選定完全覆蓋所述檢索區域的一個剖分面片A。

3.如權利要求1所述的一種基于掩碼技術的剖分編碼的位置信息快速檢索方法，其特征在于，所述在GeoSOT剖分和編碼方案中選定與所述檢索區域有關聯關系的剖分面片集為：以GeoSOT剖分和編碼方案中覆蓋所述檢索區域的最小剖分面片A₀，A₀層級為k，找到該最小剖分面片周邊8個相鄰且層級為k的剖分面片A₁～A₈，由A₀～A₈組成剖分面片集。

4.如權利要求3所述的一種基于掩碼技術的剖分編碼的位置信息快速檢索方法，其特征在于，選定剖分面片集后，進一步對選定的剖分面片集進行優化，得到優化剖分面片集；

設剖分面片A₀～A₈對應的GeoSOT編碼為Gd₀～Gd₈，所述優化具體為：

S1、去掉Gd₀的最后一位獲得編碼Gd’，Gd’具體為Gd₁d₂d₃…d_k-1，Gd’對應第k-1層，其層級掩碼為C_k-1；

S2、將Gd₁～Gd₈分別與Gd’進行匹配運算，匹配運算如下：其中符號∧是位與操作，符號是位異或操作；其中i取值為1～8；

S3、若對于Gd_i，當上述匹配運算結果為1，則將Gd_i存入集合X中；若匹配運算結果為0，則舍棄Gd_i，同時將Gd’存入編碼集合X中；

則所述針對剖分面片集中的每一個剖分面片p獲取檢索結果時，針對編碼集合X對應的剖分面片集執行。

5.如權利要求1或2或3或4所述的一種基于掩碼技術的剖分編碼的位置信息快速檢索方法，其特征在于，所述檢索獲得的剖分面片的位置信息作為檢索結果具體為：

在索引表中查找并獲取剖分面片對應的位置信息；

所述索引表為針對各地理區域的位置信息建立的檢索表格，對于一個地理區域，在GeoSOT剖分方案中選擇包含該地理區域的最小的剖分面片，獲取其GeoSOT編碼作為索引號，將索引號和該地理區域的位置信息對應寫入索引表中。