[發(fā)明專利]一種在電子地圖中記錄交通限制信息的方法和裝置

有效

• 申請(qǐng)?zhí)枺?/td>: 200910090869.9
• 申請(qǐng)日: 2009-08-11
• 公開（公告）號(hào): CN101620803A
• 公開（公告）日: 2010-01-06
• 發(fā)明（設(shè)計(jì)）人: 周猛;陳丹;顏凱;徐晉暉
• 申請(qǐng)（專利權(quán)）人: 北京四維圖新科技股份有限公司
• 主分類號(hào): G09B29/00
• 分類號(hào): G09B29/00;G01C21/26
• 代理公司: 北京銀龍知識(shí)產(chǎn)權(quán)代理有限公司
• 代理人: 許 靜

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

本發(fā)明涉及電子地圖技術(shù)，特別是指一種在電子地圖中記錄交通限制信息 的方法和裝置。

背景技術(shù)

電子地圖是對(duì)現(xiàn)實(shí)世界的描述，但又不同于現(xiàn)實(shí)世界，例如，現(xiàn)實(shí)世界中 的一條道路，在導(dǎo)航電子地圖中使用兩條邊表示，一個(gè)十字路口，在導(dǎo)航電子 地圖中可以由一個(gè)多條邊和點(diǎn)組成的有向圖表示。

在計(jì)算導(dǎo)航路徑的過程中，交通限制信息有著重要的作用。現(xiàn)實(shí)道路數(shù)字 化后采用矢量地圖表示導(dǎo)航信息，其中對(duì)交通限制信息，例如在導(dǎo)航電子地圖 中的路口有向子圖中，通常是采用邊的序列記錄交通限制信息，包括永久禁止 通行和時(shí)間段禁止通行。

發(fā)明人在實(shí)現(xiàn)本發(fā)明的過程中，發(fā)現(xiàn)現(xiàn)有技術(shù)中至少存在如下問題：在采 用邊的序列記錄交通限制信息時(shí)，需要記錄涉及到的較多邊甚至每一個(gè)邊序 號(hào)，產(chǎn)生了大量的冗余數(shù)據(jù)，造成電子地圖存儲(chǔ)介質(zhì)的空間浪費(fèi)，尤其對(duì)于手 機(jī)用戶更為明顯；冗余數(shù)據(jù)使得導(dǎo)航儀廠商只能采用高配置硬件，否則極易產(chǎn) 生內(nèi)存溢出等事故；由于交通限制信息是導(dǎo)航設(shè)備計(jì)算可行路徑時(shí)的必要依 據(jù)，上述冗余影響到設(shè)備的計(jì)算速度，使得導(dǎo)航設(shè)備響應(yīng)遲鈍，造成了計(jì)算資 源的浪費(fèi)。

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

本發(fā)明的目的是提供一種在電子地圖中記錄交通限制信息的方法和裝置， 用于消除電子地圖中所存放的交通限制信息的冗余數(shù)據(jù)。

本發(fā)明實(shí)施例提供一種在電子地圖中記錄交通限制信息的方法，在生成電 子地圖的過程中，包括：步驟一，獲取一路口的有向網(wǎng)絡(luò)圖；步驟二，獲取所 述有向網(wǎng)絡(luò)圖的可通行序列集，所述可通行序列集中的每一個(gè)可通行序列是由 所述有向網(wǎng)絡(luò)圖中的邊序號(hào)組成的有序組合，表示從前一邊到后一邊可通行； 獲取所述有向網(wǎng)絡(luò)圖的交限序列集，所述交限序列集中的每一個(gè)交限序列是由 所述有向網(wǎng)絡(luò)圖中的邊序號(hào)組成的有序組合，表示從前一邊到后一邊限制通 行；其中，前一邊是指所述有序組合中的第一個(gè)邊序號(hào)所對(duì)應(yīng)的邊，后一邊是 指所述有序組合中的最后一個(gè)邊序號(hào)所對(duì)應(yīng)的邊，且均是所述有向網(wǎng)絡(luò)圖中的 任意邊；步驟三，對(duì)于一個(gè)交限序列，如果判定該交限序列包含在一個(gè)可通行 序列中，則從所述交限序列集中剔除該交限序列；交限序列集中剩余的所有交 限序列形成一交限序列中間集；步驟四，根據(jù)預(yù)定的優(yōu)先級(jí)標(biāo)準(zhǔn)對(duì)所述交限序 列中間集中的各個(gè)交限序列進(jìn)行排序；所述優(yōu)先級(jí)標(biāo)準(zhǔn)包括：序列長(zhǎng)度u或者 等價(jià)序列個(gè)數(shù)v；其中，序列長(zhǎng)度u，是指該交限序列所包含的邊序號(hào)的個(gè)數(shù)； 等價(jià)序列個(gè)數(shù)v，是指交限序列中間集中的一個(gè)交限序列與交限序列集中的至 少一個(gè)交限序列等價(jià)時(shí)，所述交限序列集中的至少一個(gè)交限序列的數(shù)目；每一 個(gè)所述交限序列均應(yīng)至少對(duì)應(yīng)一序列長(zhǎng)度u和一等價(jià)序列個(gè)數(shù)v；步驟五，當(dāng) 根據(jù)所述等價(jià)序列個(gè)數(shù)v對(duì)所述交限序列中間集中的各個(gè)所述交限序列進(jìn)行 排序時(shí)，v1+v2+......vi＝C，其中C是一個(gè)定值，i是交限序列的序號(hào)，vi表示 該交限序列的等價(jià)序列個(gè)數(shù)；在所述交限序列中間集中，選取i個(gè)交限序列作 為結(jié)果輸出，所述i個(gè)交限序列滿足：使得i的取值最小，且使得i個(gè)所述交 限序列的序列長(zhǎng)度u的和值最小。

所述的方法中，所述步驟二之后，還包括：計(jì)算出各個(gè)所述交限序列的全 部子序列，放入一交限子序列集合；則在步驟三中，所述一個(gè)交限序列具體為 所述交限子序列集合中的一個(gè)子序列。

所述的方法中，所述步驟二中，所述可通行序列分為永久可通行序列和分 時(shí)間段可通行序列，則所述可通行序列集包括第一列表和第二列表：所述第一 列表存放所述永久可通行序列，所述第二列表存放所述分時(shí)間段可通行序列； 所述交限序列分為永久限制通行序列和分時(shí)間段限制通行序列，則所述交限序 列集包括第三列表和第四列表：所述第三列表存放所述永久限制通行序列，所 述第四列表存放所述分時(shí)間段限制通行序列。

所述的方法中，對(duì)于所述第三列表中的序列a1，當(dāng)a1包含在第一列表中， 剔除該a1；a1包含在第二列表中，剔除該a1；對(duì)于第四列表中的一個(gè)序列a2， 當(dāng)：a2包含在第一列表中，剔除該a2；a2包含在第二列表中，且兩者所在時(shí) 間段相同，不再剔除該a2；時(shí)間段不同則剔除a2。

所述的方法中，形成一交限序列中間集之后，還包括：對(duì)所述交限序列中 間集中的各個(gè)交限序列，遍歷該交限序列的各個(gè)邊序號(hào)，判斷該交限序列是否 是從前一邊到后一邊的邊序號(hào)的有序組合，且前一邊到后一邊可通行；如果是 則從所述交限序列中間集中剔除該交限序列，否則保留。