[發(fā)明專(zhuān)利]一種移動(dòng)端矢量數(shù)據(jù)的空間索引和緩存構(gòu)建方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201610120863.1
• 申請(qǐng)日: 2016-03-03
• 公開(kāi)（公告）號(hào): CN105760529B
• 公開(kāi)（公告）日: 2018-12-25
• 發(fā)明（設(shè)計(jì)）人: 鄔群勇;汪洋
• 申請(qǐng)（專(zhuān)利權(quán)）人: 福州大學(xué)
• 主分類(lèi)號(hào): G06F17/30
• 分類(lèi)號(hào): G06F17/30
• 代理公司: 福州元?jiǎng)?chuàng)專(zhuān)利商標(biāo)代理有限公司 35100
• 代理人: 蔡學(xué)俊

1.一種移動(dòng)端矢量數(shù)據(jù)的空間索引和緩存構(gòu)建方法，其特征在于，包括以下步驟：

步驟S1：根據(jù)矢量地圖范圍、屏幕尺寸和像素精度，對(duì)移動(dòng)端矢量數(shù)據(jù)進(jìn)行基于四叉樹(shù)的多級(jí)網(wǎng)格劃分；

步驟S2：依據(jù)空間對(duì)象尺寸，確定各個(gè)空間對(duì)象所在的網(wǎng)格級(jí)別，并計(jì)算其所跨越的網(wǎng)格范圍，分別記錄空間對(duì)象的ID；

步驟S3：根據(jù)最高級(jí)網(wǎng)格中的空間對(duì)象的個(gè)數(shù)，結(jié)束網(wǎng)格劃分，確定網(wǎng)格的級(jí)別數(shù)；

步驟S4：通過(guò)網(wǎng)格的行列號(hào)，計(jì)算各個(gè)網(wǎng)格的網(wǎng)格編碼，并使用網(wǎng)格編碼建立索引表，每級(jí)網(wǎng)格分別建立索引，各級(jí)網(wǎng)格索引相互間獨(dú)立；

步驟S5：針對(duì)不同的網(wǎng)格級(jí)別，設(shè)置不同的顯示級(jí)別，實(shí)現(xiàn)分級(jí)顯示；

步驟S6：根據(jù)分塊、分級(jí)顯示的矢量地圖的特點(diǎn)，設(shè)置相應(yīng)的緩存參數(shù)；

步驟S7：在步驟S6基礎(chǔ)上，構(gòu)建面向分塊、分級(jí)顯示的矢量數(shù)據(jù)的緩存模型；

步驟S8：在步驟S6和S7基礎(chǔ)上，構(gòu)建合適的緩存淘汰更新策略；

步驟S9：當(dāng)對(duì)地圖進(jìn)行操作時(shí)，加載緩存數(shù)據(jù)，并統(tǒng)計(jì)緩沖區(qū)容量，適時(shí)執(zhí)行緩存淘汰更新策略；所述步驟S1中，基于四叉樹(shù)的多級(jí)網(wǎng)格劃分具體包括以下步驟：

步驟S11：分別以矢量地圖的橫坐標(biāo)范圍ΔX和縱坐標(biāo)范圍ΔY，除以在滿(mǎn)足數(shù)據(jù)編輯精度條件下，移動(dòng)設(shè)備可顯示的數(shù)據(jù)橫坐標(biāo)和縱坐標(biāo)的實(shí)際距離，得到兩個(gè)網(wǎng)格數(shù)L和H；若已知屏幕分辨率為L(zhǎng)_s×W_s像素，矢量地圖X坐標(biāo)覆蓋范圍X_max-X_min，Y坐標(biāo)覆蓋范圍Y_max-Y_min，地圖中一個(gè)像素代表的實(shí)際距離記為A，記地圖橫向劃分圖塊數(shù)量為L(zhǎng)，縱向劃分圖塊數(shù)量為H，則有以下公式：

L＝(X_max-X_min)/(A×L_s)

H＝(Y_max-Y_min)/(A×W_s)

通過(guò)上述公式求出最初的L和H；

步驟S12：根據(jù)四叉樹(shù)的特點(diǎn)，取L和H中的最大那個(gè)數(shù)，并求大于它的最鄰近的2的n次冪，即2^n-1≤max{L,H}≤2ⁿ，令這個(gè)2ⁿ的值為N；

步驟S13：以N×N塊來(lái)劃分矢量地圖，構(gòu)成第1級(jí)網(wǎng)格劃分；

步驟S14：以(N/2)×(N/2)塊來(lái)劃分矢量地圖，構(gòu)成第2級(jí)網(wǎng)格劃分；

步驟S15：依次類(lèi)推，構(gòu)成基于四叉樹(shù)的多級(jí)網(wǎng)格劃分；

所述步驟S8中，緩存淘汰更新策略具體包括以下步驟：

步驟S81：先不考慮當(dāng)前顯示級(jí)別網(wǎng)格，從比例尺最大的網(wǎng)格級(jí)別開(kāi)始，從底向上，依次根據(jù)網(wǎng)格的最后訪問(wèn)時(shí)間和訪問(wèn)熱度計(jì)算每個(gè)網(wǎng)格級(jí)別中的所有網(wǎng)格的綜合價(jià)值；網(wǎng)格綜合價(jià)值為：value_i＝μ_time×μ_hot；最近訪問(wèn)時(shí)間影響因子的計(jì)算如下：首先，計(jì)算出最近幾次網(wǎng)格被訪問(wèn)的時(shí)間間隔的平均值：其中，Δt表示相鄰兩次網(wǎng)格i被訪問(wèn)的時(shí)間間隔，Δt_i表示網(wǎng)格i相鄰兩次被訪問(wèn)的平均值，相當(dāng)于概率統(tǒng)計(jì)中的標(biāo)準(zhǔn)差；其次，計(jì)算出網(wǎng)格在緩存中未被訪問(wèn)的時(shí)間：t＝currentT-lastT，其中，currentT表示當(dāng)前時(shí)間，lastT表示網(wǎng)格i最后一次被訪問(wèn)的時(shí)間；最后，最近訪問(wèn)時(shí)間影響因子為：μ_time＝1/(|t-Δt_i|+1)，此公式表示的意義為：網(wǎng)格在緩存中未被訪問(wèn)的時(shí)間離網(wǎng)格相鄰兩次被訪問(wèn)的時(shí)間間隔的平均值越近，則越容易再次被訪問(wèn)；反之，則越難被訪問(wèn)；訪問(wèn)熱度影響因子的計(jì)算如下：其中times表示網(wǎng)格i的訪問(wèn)次數(shù)，currentT表示當(dāng)前時(shí)間，t₀表示網(wǎng)格i在緩存中的生成時(shí)間；

步驟S82：從最小級(jí)網(wǎng)格i開(kāi)始，將綜合價(jià)值小的網(wǎng)格從緩沖區(qū)中移去，直至緩沖區(qū)不再溢出，若第i級(jí)網(wǎng)格中的所有網(wǎng)格均被移除，而緩沖區(qū)還溢出，則將第i+1級(jí)網(wǎng)格中綜合價(jià)值小的網(wǎng)格從緩沖區(qū)中移去，依次類(lèi)推；

步驟S83：若除去當(dāng)前顯示級(jí)別網(wǎng)格外，其他級(jí)別的網(wǎng)格從緩沖區(qū)中移除，但緩沖區(qū)還是溢出，則對(duì)當(dāng)前顯示層，使用網(wǎng)格中心點(diǎn)坐標(biāo)到屏幕中心點(diǎn)坐標(biāo)的距離為依據(jù)計(jì)算出每個(gè)網(wǎng)格的綜合價(jià)值，并以此為依據(jù)，將綜合價(jià)值小的網(wǎng)格從緩沖區(qū)中移去，直至緩沖區(qū)不再溢出，使用網(wǎng)格中心點(diǎn)坐標(biāo)到屏幕中心點(diǎn)坐標(biāo)的距離作為綜合價(jià)值value的衡量指標(biāo)，進(jìn)一步簡(jiǎn)化為，使用網(wǎng)格與屏幕中心點(diǎn)所在網(wǎng)格行列號(hào)之差的絕對(duì)值進(jìn)行衡量，計(jì)算公式為：

value_i＝1/(|row_i-row₀|+|col_i-col₀|)其中，value_i表示網(wǎng)格i的綜合價(jià)值，row_i、col_i分別為網(wǎng)格i的行列號(hào)，row₀、col₀分別為屏幕中心點(diǎn)所在網(wǎng)格的行列號(hào)。