説明

地図データ検査装置

【課題】道路ネットワーク全体における一部の道路若しくは道路網について孤立状態を判定することのできる地図データ検査装置を提供する。
【解決手段】
グループ分割部は、道路ネットワークデータから一方通行のリンクを除外した仮道路ネットワークデータを生成する。そして、互いに接続状態である道路ネットワーク群を1つのグループとして抽出する。次に、グループ結合部は、グループ結合処理により、複数のグループを1つのグループに結合する。孤立道路判定部は、道路ネットワークデータに複数の独立したグループが存在するか否かを判定する。具体的に、道路ネットワークデータを構成する全てのリンクのグループ識別IDを参照して、全てのリンクにおけるグループ識別IDが同一である場合には、独立したグループは1つしか存在しないため、孤立道路ネットワークが存在しないと判定する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、ナビゲーション装置等で用いられる道路ネットワークデータにおいて、孤立した道路ネットワークを検出する技術に関するものである。
【背景技術】
【0002】
新しい道路が開通した場合など、道路ネットワークデータは当該道路が反映された最新のデータに更新される。この道路ネットワークデータのデータ更新作業は、通常オペレータが現地の撮影画像や地図等を参照しつつ手作業で行う。そのため、従来から道路を表すリンクの接続ミスや入力漏れ等によって、ある道路若しくは道路網が他の道路から孤立した状態となる場合がある。
【0003】
こうしたデータ更新時の入力ミスをチェックするための技術が提案されている。例えば、特許文献1に記載の技術では地図データが複数の区画で構成されており、当該区画ごとに地図データが更新される。そして、削除された道路が存在する区画において削除された道路の一端と他端とを結ぶ経路の探索を行い、経路が存在しない場合に孤立状態であることを検出している。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】特開2008−249798号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
しかしながら、特許文献1に記載の技術では、削除された道路にのみ着目して孤立状態の有無を検出するものであるため、局所的な孤立道路を検出することはできても、道路ネットワーク全体における孤立道路を検出することはできなかった。
本発明は、上記従来技術が有する課題を解決するためになされた発明である。その目的は、道路ネットワーク全体における一部の道路若しくは道路網について孤立状態を判定することのできる地図データ検査装置を提供することにある。
【課題を解決するための手段】
【0006】
上記課題を解決するために、本発明は、道路を表現したリンク及び該リンクの端部に位置するノードを含んで構成される道路ネットワークデータが記憶されている道路ネットワークデータ記憶部と、前記道路ネットワークデータを、リンク及びノードで構成されるグループであって、互いに一方通行を表す一方通行情報が付与されている一方通行リンクで接続される複数のグループに分割するグループ分割部と、分割されたグループのうち、前記一方通行リンクを通って巡回可能な状態にある複数のグループを結合することで新たなグループを生成するグループ結合部と、全てのグループの組み合わせについて前記グループ結合部における結合処理を実行した場合において、なお複数の独立した独立グループが存在する場合、前記道路ネットワークデータには孤立した道路ネットワークが存在すると判定する孤立道路判定部とを備えることを特徴とする。
なお、上述した特徴は、本発明の特徴の全てを列挙したものではなく、これらを要部とする構成もまた発明となり得る。
【発明の効果】
【0007】
本発明によれば、道路ネットワーク全体における一部の道路若しくは道路網について孤立状態を判定することができる。
【図面の簡単な説明】
【0008】
【図1】孤立道路チェック装置の構成図。
【図2】孤立道路チェック処理のフローチャート。
【図3】道路ネットワークの説明図。
【図4】分割された仮道路ネットワークの説明図。
【図5】グループ結合処理のフローチャート。
【図6】グループ結合処理に用いるグループの概要図。
【図7】グループにおける木構造データの説明図。
【図8】グループ結合処理結果の概要図。
【発明を実施するための形態】
【0009】
以下、本発明を具体化した孤立道路チェック装置における実施例を説明する。
図1に示すように、本実施例における孤立道路チェック装置は、コンピュータで構成されている。孤立道路チェック装置は、表示部としてのディスプレイ11、道路ネットワークデータ記憶部としてのハードディスク12、一時記憶部としてのメモリ13、所定のプログラムに基づいて各種制御を実行するCPU14を備える。各部11〜13はCPU14によって動作制御される。
【0010】
ハードディスク12には、道路を表現したリンクと、当該リンクの端点に存在しており交差点等の位置を表すノードとを含んで構成される道路ネットワークデータが記憶されている。リンクには、当該リンクの属性等を表す各種属性情報が付与されている。属性情報には、リンクを特定する固有のID番号、リンクの長さを示すリンク長、リンクの始端及び終端に存在するノードの緯度・経度座標、リンクにおける複数地点の緯度・経度座標、道路名称、道路種別、道路幅員、一方通行、車線数、右折・左折専用車線の有無とその専用車線の数、及び制限速度等がある。
【0011】
メモリ13には、CPU14によってハードディスク12等から読み出された各種データ、プログラム等が一時的に記憶される。
図1に示すように、CPU14は、グループ分割部15及びグループ結合部16及び孤立道路判定部17を有する。
グループ分割部15は、道路ネットワークデータを、互いに一方通行を表す一方通行情報が付与されている一方通行リンクで接続される複数のグループ(ネットワーク領域)に分割する。各グループは、互いにノードを介して接続関係にある複数のリンクで構成されている。
【0012】
具体的に、グループ分割部15は、仮道路ネットワークデータ生成機能と、グループ抽出機能とを有しており、これらの機能によって道路ネットワークデータを複数のグループに分割する。仮道路ネットワークデータ生成機能は、道路ネットワークデータから、属性情報としての一方通行情報が付与されているリンクを除去した仮道路ネットワークデータを生成する機能である。また、グループ抽出機能は、生成された仮道路ネットワークデータから、互いに接続状態である道路ネットワーク群で構成されるグループを抽出する機能である。グループ抽出機能によって抽出された複数のグループは、それぞれ他のグループとは非接続状態にある。
【0013】
グループ結合部16は、グループ分割部15で分割された各グループのうち、一方通行リンクを通って巡回可能な状態にある複数のグループを結合することで新たなグループを生成する。
孤立道路判定部17は、孤立道路ネットワークが存在するか否かを判定する。ここで、道路ネットワークで孤立道路ネットワークが存在しない状態とは、任意の地点から全ての地点まで辿り着くことができ、かつ元の地点に戻ることができる状態であると定義できる。なお、往路と復路とは経路が異なってもよい。
具体的に、孤立道路判定部17は、全てのグループの組み合わせについてグループ結合処理が終了した場合であって、なお複数の独立したグループが存在する場合、道路ネットワークデータには孤立道路ネットワークが存在すると判定する。
【0014】
グループ結合処理が終了した場合においてもなお複数の独立した道路ネットワークのグループが存在する状態とは、道路ネットワークにおける所定の出発地から所定の目的地まで辿り着くことができない(経路が存在しない)か、あるいは、辿り着くことはできたとしても、逆に目的地から出発地まで辿り着くことができない状態を意味している。したがって、孤立道路判定部17は、複数の独立グループのうち、最も多くのリンクを含んで構成される独立したグループを除外した他の独立グループに含まれるリンクに対応する道路が孤立道路であると判定する。
【0015】
ここで、最も多くのリンクを含んで構成されている独立したグループとは、最終的に道路ネットワークにおける主要な道路(高速道路や国道等)に対応するリンクを全て含んでいるグループであることが想定される。一方、それ以外のグループは、本来存在するはずのリンクが整備されていない場合や、一方通行に関する属性情報が誤って付与されているリンクが存在する場合など、道路ネットワークデータに整備ミスがある可能性の高いエリアに相当する。
【0016】
次に、このように構成される孤立道路チェック装置を用いて、道路ネットワークに含まれる孤立道路ネットワークを検出する方法について説明する。
図2に示すように、まず、CPU14は、ハードディスク12に記憶されている、リンク32及びノード33で構成される道路ネットワークデータ31(図3)をメモリ13に読み込む(ステップS21)。次に、グループ分割部15は、道路ネットワークデータ31を複数のグループに分割する(ステップS22)。
【0017】
グループ分割部15は、図3に示すように、道路ネットワークデータ31を構成するリンク32の属性情報である一方通行情報34に着目して、当該一方通行情報34が付与されているリンク32aについて道路ネットワークデータ31から除外した状態の仮道路ネットワークデータ35を新たに生成する。
図4に示すように、例えば、この仮道路ネットワークデータ35には、互いに非接続状態である3つの道路ネットワーク群36a〜36cが存在している。グループ分割部15は、これら3つの道路ネットワーク群36a〜36cをそれぞれ個別のグループとして抽出する。
【0018】
具体的なグループの抽出方法としては、仮道路ネットワークデータ35において任意に選択されたリンクとノードやリンクを介して直接的若しくは間接的に接続されている全てのリンクについて、CPU14が属性情報としての同一のグループ識別IDを付与する。そして接続されている全てのリンクにグループ識別IDが付与されたら、次に、CPU14はグループ識別IDが付与されていない別のリンクを任意に選択して、同様にグループ識別IDを付与する。こうしたグループ識別IDの付与処理を道路ネットワークデータにおける一方通行ではない全てのリンクに対して実行することで、複数のグループが抽出される。
【0019】
次に、グループ結合部16は、後述するグループ結合処理を実行する(ステップS23)。そして、孤立道路判定部17は、道路ネットワークデータに複数の独立したグループが存在するか否かを判定する(ステップS24)。
孤立道路判定部17は、道路ネットワークデータ31を構成する全てのリンクのグループ識別IDを参照する。そして、全てのリンクにおけるグループ識別IDが同一である場合には、独立したグループは1つしか存在しないため、孤立道路判定部17は、孤立した道路ネットワークが存在しないと判定する(ステップS25)。
【0020】
一方、全てのリンクにおけるグループ識別IDが複数存在する場合には、独立したグループは複数存在するため、孤立道路判定部17は、孤立した道路ネットワークが存在すると判定する(ステップS26)。このとき、孤立道路判定部17は、最も多くのリンクを含んで構成される独立したグループを除外した他の独立グループに含まれる道路ネットワークが孤立した道路ネットワークであると判定する。
【0021】
次に、上述したグループ結合処理(ステップS23)について、図5〜図9を参考に具体的に説明する。
なお本処理については、図6に示すように、6つのグループ61a〜61fに分割されており、かつ一方通行のリンク62a〜62gで接続されている道路ネットワークを例に説明する。なお、リンク62a〜62gは、矢印方向にのみ通行することができるものとする。
【0022】
図5に示すように、まず、グループ結合部16は、全ての一方通行のリンク62a〜62gの両端がどのグループに接続しているかを決定するとともに、これらのリンク62a〜62gと端部が属するグループとの関係をリスト化する(ステップS51)。リストの一例は、表1のとおりである。表1によれば、例えばリンク62aは進入側の端部がグループ61cに接続しており、退出側の端部がグループ61aに接続していることがわかる。なお、リンク62a〜62g及びグループ61a〜61fについては、固有のID番号で表現してもよい。
【0023】
【表1】

【0024】
次に、グループ結合部16は、生成されたリストに登録されていないグループを抽出する(ステップS52)。道路ネットワークデータに含まれるグループであって、かつリストに登録されていないグループは、他のグループと一方通行のリンクを介して接続されていないグループであるため、完全に他のグループとは孤立している完全孤立グループであると判定することができるからである。グループ結合部16は、抽出された完全孤立グループをハードディスク12に記憶する。図6の例では、グループ61bが完全孤立グループとして抽出される。
【0025】
次に、グループ結合部16は、リストに登録されたグループを節点及び頂点とするとともに、一方通行のリンクを枝とする木構造データを生成する(ステップS53)。なお、頂点には任意のグループが設定される。例えば、図7に示すように、最もリンクの数が多いグループ61aを頂点71とした木構造データが生成される。なお、各枝には、便宜上一方通行のリンクの番号を付してある。
【0026】
次に、グループ結合部16は、生成された木構造データを参照して複数のグループを結合する(ステップS54)。具体的には、頂点に設定されているグループと同じグループが節点に存在する場合、同グループ間に存在する節点のグループは、頂点に設定されているグループと結合されて同じグループとなる。換言すれば、分割されたグループのうち、一方通行リンクを通って巡回可能な状態にある複数のグループが存在する場合には、当該複数のグループを結合する。これは、任意のグループを表す節点(頂点)から枝を辿って同じグループを表す節点に行き着くということは、その間に存在するグループが頂点に設定されているグループに対して孤立状態ではないということを表しているからである。
【0027】
図6、7に示す例の場合、頂点71と節点73とが同じグループであり、グループ61a→61c→61aと巡回可能である。したがって、頂点71と節点73との間に存在する節点72に対応するグループ61cは、グループ61aから孤立していないと判断されてグループ結合部16によって結合される。
また頂点71と節点76とについても同じグループであり、グループ61a→61f→61e→61aと巡回可能である。したがって、頂点71と節点76との間に存在する節点74,75にそれぞれ対応するグループ61f,61eは、グループ61aから孤立していないと判断されてグループ結合部16によって結合される。
【0028】
すなわち、グループ61a,61c,61f,61eは、同じグループとして結合されて、図8に示すように新たなグループ63aとなる。なおグループ63aには、一方通行のリンク62a,62b,62d〜62gも含まれる。
次に、グループ結合部16は、複数のグループの結合処理(ステップS54)の結果、結合されたグループが存在するか否かを判定する(ステップS55)。本実施例において、上述したとおり、グループ61a,61c,61f,61eは結合されていることから、再度一方通行のリンクについて、リスト化処理が実行される(ステップS51)。一方、複数のグループの結合処理(ステップS54)の結果、結合されたグループが存在しないと判定した場合には、グループ結合部16は、グループ結合処理を終了する。
【0029】
以上説明したとおり、本実施例の孤立道路チェック装置は以下の効果を奏する。
・道路ネットワーク全体において、孤立した道路ネットワークが存在するか否かを判定することができるため、領域にとらわれず、換言すれば道路ネットワークの規模に制限されることなく、孤立した道路ネットワークの抽出が可能となる。
・孤立した道路ネットワークが存在するということは、道路ネットワークデータにリンクの整備忘れ等のミスが存在する可能性もある。したがって、最新の道路ネットワークデータに更新された際の誤り判定等に利用することも可能である。
【0030】
・一方通行リンクを除いてグループ化する処理と一方通行リンクに着目してグループ結合を行う処理とを採用したことで、ロジックを簡略化することができる。
・結合できたグループ内のリンクをメモリ上から除去し、一方通行リンクにおける接続部分に着目して処理を実行することで無駄なメモリの消費を軽減することができる。
・一方通行情報が付与されているリンクを除去して、互いに接続状態である道路ネットワーク群を1つのグループとして抽出するようにしたことで、ある程度まとまったネットワーク群がグループ化される。したがって、グループ結合処理の処理回数を抑制することができる。
【0031】
(別例)
・道路ネットワークデータには、本来的に孤立した道路ネットワークが存在する場合もあり得る。例えば、道路ネットワークにリンクとして整備されていないような細い道路でのみ主要道路と接続されている道路ネットワークのグループについては孤立した道路ネットワークであると判定される。こうした道路ネットワークのグループについては、予め道路ネットワークデータから除外しておくことで、無用な孤立道路ネットワークの検出を回避するようにしてもよい。
【0032】
・グループ分割部15が道路ネットワークデータ31を複数のグループに分割する方法は、上記実施例の手法に限られない。例えば、1つのリンクを1つのグループとして定義してもよい。
・孤立道路ネットワークを検出するための道路ネットワークデータは、全国規模の道路ネットワークデータは勿論のこと、九州地方や関東地方、福岡県といった所定の領域における道路ネットワークデータであってもよい。
【符号の説明】
【0033】
12…道路ネットワークデータ記憶部としてのハードディスク、15…グループ分割部、16…グループ結合部、17…孤立道路判定部。


【特許請求の範囲】
【請求項1】
道路を表現したリンク及び該リンクの端部に位置するノードを含んで構成される道路ネットワークデータが記憶されている道路ネットワークデータ記憶部と、
前記道路ネットワークデータを、リンク及びノードで構成されるグループであって、互いに一方通行を表す一方通行情報が付与されている一方通行リンクで接続される複数のグループに分割するグループ分割部と、
分割されたグループのうち、前記一方通行リンクを通って巡回可能な状態にある複数のグループを結合することで新たなグループを生成するグループ結合部と、
全てのグループの組み合わせについて前記グループ結合部における結合処理を実行した場合において、なお複数の独立した独立グループが存在する場合、前記道路ネットワークデータには孤立した道路ネットワークが存在すると判定する孤立道路判定部と
を備えることを特徴とする地図データ検査装置。
【請求項2】
前記グループ分割部は、
前記道路ネットワークデータから、前記一方通行リンクを除去した仮道路ネットワークデータを生成する仮道路ネットワークデータ生成機能と、
前記仮道路ネットワークデータから、互いに接続状態である道路ネットワーク群で構成されるグループを抽出するグループ抽出機能と
を有することを特徴とする請求項1に記載の地図データ検査装置。


【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate