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

有效

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

技術(shù)領(lǐng)域

本發(fā)明屬于地理信息技術(shù)領(lǐng)域，尤其涉及一種基于二維分塊結(jié)構(gòu)地圖空間索引的方法和系統(tǒng)。

背景技術(shù)

空間索引是指依據(jù)空間對(duì)象的位置和形狀或空間對(duì)象之間的某種空間關(guān)系按一定的順序排列的一種數(shù)據(jù)結(jié)構(gòu)，其中包含空間對(duì)象的概要信息，如對(duì)象的標(biāo)識(shí)、外接矩形及指向空間對(duì)象實(shí)體的指針。作為一種輔助性的空間數(shù)據(jù)結(jié)構(gòu)，空間索引介于空間操作算法和空間對(duì)象之間，它通過(guò)篩選作用，大量與特定空間操作無(wú)關(guān)的空間對(duì)象被排除，從而提高空間操作的速度和效率。

現(xiàn)有最常用的空間索引技術(shù)為R樹(shù)系列(R樹(shù))和四叉樹(shù)系列(CELLQ樹(shù))。

在R樹(shù)中，兄弟結(jié)點(diǎn)對(duì)應(yīng)的空間區(qū)域存在重疊產(chǎn)生了“死區(qū)域”(一個(gè)結(jié)點(diǎn)內(nèi)不含本結(jié)點(diǎn)數(shù)據(jù)的空白區(qū)域)，導(dǎo)致了無(wú)效查詢。盡管許多R樹(shù)的變種被開(kāi)發(fā)出來(lái)，如R+樹(shù)，它的空間劃分消除了R樹(shù)中的“死區(qū)域”問(wèn)題，減少了無(wú)效查詢數(shù)，提高了空間索引的效率。但對(duì)于插入、刪除空間對(duì)象的操作，則由于操作要保證空間區(qū)域無(wú)重疊而效率降低。同時(shí)R+樹(shù)對(duì)跨區(qū)域的空間物體的數(shù)據(jù)的存儲(chǔ)是有冗余的，而且隨著數(shù)據(jù)庫(kù)中數(shù)據(jù)的增多，冗余信息會(huì)不斷增長(zhǎng)。

四叉樹(shù)是一種結(jié)構(gòu)清晰、構(gòu)造簡(jiǎn)單的層次數(shù)據(jù)結(jié)構(gòu)。它遞歸地對(duì)地理空間進(jìn)行四分，直到自行設(shè)定的終止條件。與R樹(shù)相比，四叉樹(shù)更新計(jì)算量要小很多，但同樣存在一個(gè)圖元標(biāo)識(shí)被多個(gè)區(qū)域所關(guān)聯(lián)，相應(yīng)地存儲(chǔ)在多個(gè)葉子節(jié)點(diǎn)上。這樣，就存在索引的冗余，遞歸查詢效率也不高。

綜上所述，現(xiàn)有的空間索引技術(shù)存在重疊存儲(chǔ)、索引冗余以及查詢效率低等問(wèn)題。

發(fā)明內(nèi)容

本發(fā)明實(shí)施例的目的在于提供一種基于二維分塊結(jié)構(gòu)地圖空間索引的方法和系統(tǒng)，旨在解決現(xiàn)有空間索引技術(shù)存在的重疊存儲(chǔ)、索引冗余以及查詢效率低的問(wèn)題。

本發(fā)明實(shí)施例是這樣實(shí)現(xiàn)的，一種基于二維分塊結(jié)構(gòu)地圖空間索引的方法，所述方法包括以下步驟：

將地圖劃分為若干相等的方塊，記錄每個(gè)方塊的坐標(biāo)范圍，并為每個(gè)方塊建立對(duì)應(yīng)的ID標(biāo)識(shí)；

將空間對(duì)象的坐標(biāo)映射到所述地圖上，確定并記錄所述空間對(duì)象所在的方塊，為每個(gè)空間對(duì)象標(biāo)識(shí)方塊ID；

設(shè)置索引點(diǎn)坐標(biāo)，計(jì)算所述索引點(diǎn)所在的方塊，根據(jù)索引點(diǎn)所在的方塊、索引方案，獲取所述索引點(diǎn)所在的方塊周邊方塊內(nèi)空間對(duì)象的坐標(biāo)。

本發(fā)明實(shí)施例的另一目的在于提供基于二維分塊結(jié)構(gòu)地圖空間索引的系統(tǒng)，所述系統(tǒng)包括：

地圖分塊單元，用于將地圖劃分為若干相等的方塊，記錄每個(gè)方塊的坐標(biāo)范圍，并為每個(gè)方塊標(biāo)識(shí)不同的ID；

空間對(duì)象計(jì)算單元，用于根據(jù)空間對(duì)象的坐標(biāo)計(jì)算并記錄所述空間對(duì)象所在的方塊，并為每個(gè)空間對(duì)象標(biāo)識(shí)方塊ID；

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

本發(fā)明實(shí)施例，將地圖分為多個(gè)方塊，為每個(gè)方塊設(shè)置ID標(biāo)識(shí)，將空間對(duì)象映射到不同的方塊上，記錄每個(gè)空間對(duì)象所在的方塊，每次索引時(shí)，只需確定索引點(diǎn)坐標(biāo)，計(jì)算索引點(diǎn)坐標(biāo)所在的方塊，獲取索引點(diǎn)所在方塊周邊的方塊內(nèi)空間對(duì)象的坐標(biāo)，實(shí)現(xiàn)了一種簡(jiǎn)單方便的索引方法。

附圖說(shuō)明

圖1是本發(fā)明實(shí)施例提供的基于二維分塊結(jié)構(gòu)地圖空間索引方法的流程圖；

圖2是本發(fā)明實(shí)施例提供的線空間對(duì)象與方塊相交情況圖；

圖3是本發(fā)明實(shí)施例提供的索引方案圖；

圖4是本發(fā)明實(shí)施例提供的基于二維分塊結(jié)構(gòu)地圖空間索引系統(tǒng)的結(jié)構(gòu)圖。

具體實(shí)施方式

為了使本發(fā)明的目的、技術(shù)方案及優(yōu)點(diǎn)更加清楚明白，以下結(jié)合附圖及實(shí)施例，對(duì)本發(fā)明進(jìn)行進(jìn)一步詳細(xì)說(shuō)明。應(yīng)當(dāng)理解，此處所描述的具體實(shí)施例僅僅用以解釋本發(fā)明，并不用于限定本發(fā)明。

本發(fā)明實(shí)施例，將地圖分為多個(gè)方塊，為每個(gè)方塊設(shè)置ID標(biāo)識(shí)，將空間對(duì)象映射到不同的方塊上，記錄每個(gè)空間對(duì)象所在的方塊，每次索引時(shí)，只需確定索引點(diǎn)坐標(biāo)，計(jì)算索引點(diǎn)坐標(biāo)所在的方塊，獲取索引點(diǎn)所在方塊周邊的方塊內(nèi)空間對(duì)象的坐標(biāo)，實(shí)現(xiàn)了一種簡(jiǎn)單方便的索引方法。

實(shí)施例一

如圖1所示為本發(fā)明實(shí)施例提供的基于二維分塊結(jié)構(gòu)地圖空間索引方法的流程圖，詳述如下：

在步驟S101中，將地圖劃分為若干相等的方塊，記錄每個(gè)方塊的坐標(biāo)范圍，并為每個(gè)方塊建立對(duì)應(yīng)的ID標(biāo)識(shí)。

在本發(fā)明實(shí)施例中，對(duì)一張地圖進(jìn)行劃分，劃分為若干方塊，建立坐標(biāo)系，記錄每個(gè)方塊對(duì)應(yīng)的坐標(biāo)范圍，并為每個(gè)方塊建立對(duì)應(yīng)的ID標(biāo)識(shí)。

舉例說(shuō)明：