[發(fā)明專利]一種基于二維分塊結構地圖空間索引的方法和系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201210099851.7
• 申請日: 2012-04-06
• 公開（公告）號: CN103365911B
• 公開（公告）日: 2017-05-24
• 發(fā)明（設計）人: 劉錦標;鐘艷春;江紅英
• 申請（專利權）人: 騰訊科技（深圳）有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30;G09B29/00
• 代理公司: 深圳市深佳知識產(chǎn)權代理事務所(普通合伙)44285
• 代理人: 王仲凱

1.一種基于二維分塊結構地圖空間索引的方法，其特征在于，所述方法包括以下步驟：

將地圖劃分為若干相等的方塊，記錄每個方塊的坐標范圍，并為每個方塊建立對應的ID標識；

將空間對象的坐標映射到所述地圖上，確定并記錄所述空間對象所在的方塊，為每個空間對象標識方塊ID；

設置索引點坐標，計算所述索引點所在的方塊，根據(jù)索引點所在的方塊、索引方案，獲取所述索引點所在的方塊周邊方塊內(nèi)空間對象的坐標；

所述索引方案由空間對象類型和地圖方塊決定；所述空間對象類型包括點空間對象和線空間對象。

2.如權利要求1所述的方法，其特征在于，所述將空間對象的坐標映射到所述地圖上，確定并記錄所述空間對象所在的方塊，為每個空間對象標識方塊ID具體包括：

點空間對象，直接根據(jù)點空間對象的坐標確定該點空間對象所在的方塊；

線空間對象，根據(jù)線空間對象與方塊的交點以及線空間對象的端點，將線空間對象分割為線段，計算線空間對象與方塊的交點，根據(jù)所述交點與線空間對象的端點計算每條線段所在的方塊。

3.如權利要求2所述的方法，其特征在于，對于線空間對象具體為：

與方塊邊緣帶角度相交的線段，通過計算斜率的方法計算交點坐標，根據(jù)交點坐標與兩個端點坐標確定每段線段所在的方塊；

與方塊垂直相交的，根據(jù)交點的Y軸坐標確定線段所在的方塊；

與方塊水平相交的，根據(jù)交點的X軸坐標確定線段所在的方塊。

4.一種基于二維分塊結構地圖空間索引的系統(tǒng)，其特征在于，所述系統(tǒng)包括：

地圖分塊單元，用于將地圖劃分為若干相等的方塊，記錄每個方塊的坐標范圍，并為每個方塊標識不同的ID；

空間對象計算單元，用于根據(jù)空間對象的坐標計算并記錄所述空間對象所在的方塊，并為每個空間對象標識方塊ID；

空間索引單元，用于根據(jù)索引點的坐標確定索引點所在的方塊，并根據(jù)索引方案獲取所述索引點所在的方塊周邊方塊內(nèi)空間對象的坐標；

所述索引方案由空間對象類型和地圖方塊決定；所述空間對象類型包括點空間對象和線空間對象。

5.如權利要求4所述的系統(tǒng)，其特征在于，所述空間對象計算單元具體包括：

點空間對象計算單元，用于根據(jù)點空間對象的坐標確定該點空間對象所在的方塊；

線空間對象計算單元，用于根據(jù)線空間對象與方塊的交點以及線空間對象的端點，將線空間對象分割為線段，計算線空間對象與方塊的交點，根據(jù)所述交點與線空間對象的端點計算每條線段所在的方塊。

6.如權利要求5所述的系統(tǒng)，其特征在于，所述線空間對象計算單元具體包括：

帶角度線段交點計算單元，用于計算帶角度線段的斜率的計算交點的坐標；

與方塊垂直相交線段計算單元，用于根據(jù)交點的Y軸坐標確定線段所在的方塊；

與方塊水平相交線段計算單元，用于根據(jù)交點的X軸坐標確定線段所在的方塊。