(57)【要約】【課題】道路ネットワーク全体における一部の道路若しくは道路網について孤立状態を判定することのできる地図データ検査装置を提供する。【解決手段】  グループ分割部は、道路ネットワークデータから一方通行のリンクを除外した仮道路ネットワークデータを生成する。そして、互いに接続状態である道路ネットワーク群を１つのグループとして抽出する。次に、グループ結合部は、グループ結合処理により、複数のグループを１つのグループに結合する。孤立道路判定部は、道路ネットワークデータに複数の独立したグループが存在するか否かを判定する。具体的に、道路ネットワークデータを構成する全てのリンクのグループ識別ＩＤを参照して、全てのリンクにおけるグループ識別ＩＤが同一である場合には、独立したグループは１つしか存在しないため、孤立道路ネットワークが存在しないと判定する。【選択図】図２
2010237487.tif 000002
【特許請求の範囲】
【請求項１】
道路を表現したリンク及び該リンクの端部に位置するノードを含んで構成される道路ネットワークデータが記憶されている道路ネットワークデータ記憶部と、
前記道路ネットワークデータを、リンク及びノードで構成されるグループであって、互いに一方通行を表す一方通行情報が付与されている一方通行リンクで接続される複数のグループに分割するグループ分割部と、
分割されたグループのうち、前記一方通行リンクを通って巡回可能な状態にある複数のグループを結合することで新たなグループを生成するグループ結合部と、
全てのグループの組み合わせについて前記グループ結合部における結合処理を実行した場合において、なお複数の独立した独立グループが存在する場合、前記道路ネットワークデータには孤立した道路ネットワークが存在すると判定する孤立道路判定部と
を備えることを特徴とする地図データ検査装置。
【請求項２】
前記グループ分割部は、
前記道路ネットワークデータから、前記一方通行リンクを除去した仮道路ネットワークデータを生成する仮道路ネットワークデータ生成機能と、
前記仮道路ネットワークデータから、互いに接続状態である道路ネットワーク群で構成されるグループを抽出するグループ抽出機能と
を有することを特徴とする請求項１に記載の地図データ検査装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置等で用いられる道路ネットワークデータにおいて、孤立した道路ネットワークを検出する技術に関するものである。
【背景技術】
【０００２】
新しい道路が開通した場合など、道路ネットワークデータは当該道路が反映された最新のデータに更新される。この道路ネットワークデータのデータ更新作業は、通常オペレータが現地の撮影画像や地図等を参照しつつ手作業で行う。そのため、従来から道路を表すリンクの接続ミスや入力漏れ等によって、ある道路若しくは道路網が他の道路から孤立した状態となる場合がある。
【０００３】
こうしたデータ更新時の入力ミスをチェックするための技術が提案されている。例えば、特許文献１に記載の技術では地図データが複数の区画で構成されており、当該区画ごとに地図データが更新される。そして、削除された道路が存在する区画において削除された道路の一端と他端とを結ぶ経路の探索を行い、経路が存在しない場合に孤立状態であることを検出している。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−２４９７９８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、特許文献１に記載の技術では、削除された道路にのみ着目して孤立状態の有無を検出するものであるため、局所的な孤立道路を検出することはできても、道路ネットワーク全体における孤立道路を検出することはできなかった。
本発明は、上記従来技術が有する課題を解決するためになされた発明である。その目的は、道路ネットワーク全体における一部の道路若しくは道路網について孤立状態を判定することのできる地図データ検査装置を提供することにある。
【課題を解決するための手段】
【０００６】
上記課題を解決するために、本発明は、道路を表現したリンク及び該リンクの端部に位置するノードを含んで構成される道路ネットワークデータが記憶されている道路ネットワークデータ記憶部と、前記道路ネットワークデータを、リンク及びノードで構成されるグループであって、互いに一方通行を表す一方通行情報が付与されている一方通行リンクで接続される複数のグループに分割するグループ分割部と、分割されたグループのうち、前記一方通行リンクを通って巡回可能な状態にある複数のグループを結合することで新たなグループを生成するグループ結合部と、全てのグループの組み合わせについて前記グループ結合部における結合処理を実行した場合において、なお複数の独立した独立グループが存在する場合、前記道路ネットワークデータには孤立した道路ネットワークが存在すると判定する孤立道路判定部とを備えることを特徴とする。
なお、上述した特徴は、本発明の特徴の全てを列挙したものではなく、これらを要部とする構成もまた発明となり得る。
【発明の効果】
【０００７】
本発明によれば、道路ネットワーク全体における一部の道路若しくは道路網について孤立状態を判定することができる。
【図面の簡単な説明】
【０００８】
【図１】孤立道路チェック装置の構成図。
【図２】孤立道路チェック処理のフローチャート。
【図３】道路ネットワークの説明図。
【図４】分割された仮道路ネットワークの説明図。
【図５】グループ結合処理のフローチャート。
【図６】グループ結合処理に用いるグループの概要図。
【図７】グループにおける木構造データの説明図。
【図８】グループ結合処理結果の概要図。
【発明を実施するための形態】
【０００９】
以下、本発明を具体化した孤立道路チェック装置における実施例を説明する。
図１に示すように、本実施例における孤立道路チェック装置は、コンピュータで構成されている。孤立道路チェック装置は、表示部としてのディスプレイ１１、道路ネットワークデータ記憶部としてのハードディスク１２、一時記憶部としてのメモリ１３、所定のプログラムに基づいて各種制御を実行するＣＰＵ１４を備える。各部１１〜１３はＣＰＵ１４によって動作制御される。
【００１０】
ハードディスク１２には、道路を表現したリンクと、当該リンクの端点に存在しており交差点等の位置を表すノードとを含んで構成される道路ネットワークデータが記憶されている。リンクには、当該リンクの属性等を表す各種属性情報が付与されている。属性情報には、リンクを特定する固有のＩＤ番号、リンクの長さを示すリンク長、リンクの始端及び終端に存在するノードの緯度・経度座標、リンクにおける複数地点の緯度・経度座標、道路名称、道路種別、道路幅員、一方通行、車線数、右折・左折専用車線の有無とその専用車線の数、及び制限速度等がある。
【００１１】
メモリ１３には、ＣＰＵ１４によってハードディスク１２等から読み出された各種データ、プログラム等が一時的に記憶される。
図１に示すように、ＣＰＵ１４は、グループ分割部１５及びグループ結合部１６及び孤立道路判定部１７を有する。
グループ分割部１５は、道路ネットワークデータを、互いに一方通行を表す一方通行情報が付与されている一方通行リンクで接続される複数のグループ（ネットワーク領域）に分割する。各グループは、互いにノードを介して接続関係にある複数のリンクで構成されている。
【００１２】
具体的に、グループ分割部１５は、仮道路ネットワークデータ生成機能と、グループ抽出機能とを有しており、これらの機能によって道路ネットワークデータを複数のグループに分割する。仮道路ネットワークデータ生成機能は、道路ネットワークデータから、属性情報としての一方通行情報が付与されているリンクを除去した仮道路ネットワークデータを生成する機能である。また、グループ抽出機能は、生成された仮道路ネットワークデータから、互いに接続状態である道路ネットワーク群で構成されるグループを抽出する機能である。グループ抽出機能によって抽出された複数のグループは、それぞれ他のグループとは非接続状態にある。
【００１３】
グループ結合部１６は、グループ分割部１５で分割された各グループのうち、一方通行リンクを通って巡回可能な状態にある複数のグループを結合することで新たなグループを生成する。
孤立道路判定部１７は、孤立道路ネットワークが存在するか否かを判定する。ここで、道路ネットワークで孤立道路ネットワークが存在しない状態とは、任意の地点から全ての地点まで辿り着くことができ、かつ元の地点に戻ることができる状態であると定義できる。なお、往路と復路とは経路が異なってもよい。
具体的に、孤立道路判定部１７は、全てのグループの組み合わせについてグループ結合処理が終了した場合であって、なお複数の独立したグループが存在する場合、道路ネットワークデータには孤立道路ネットワークが存在すると判定する。
【００１４】
グループ結合処理が終了した場合においてもなお複数の独立した道路ネットワークのグループが存在する状態とは、道路ネットワークにおける所定の出発地から所定の目的地まで辿り着くことができない（経路が存在しない）か、あるいは、辿り着くことはできたとしても、逆に目的地から出発地まで辿り着くことができない状態を意味している。したがって、孤立道路判定部１７は、複数の独立グループのうち、最も多くのリンクを含んで構成される独立したグループを除外した他の独立グループに含まれるリンクに対応する道路が孤立道路であると判定する。
【００１５】
ここで、最も多くのリンクを含んで構成されている独立したグループとは、最終的に道路ネットワークにおける主要な道路（高速道路や国道等）に対応するリンクを全て含んでいるグループであることが想定される。一方、それ以外のグループは、本来存在するはずのリンクが整備されていない場合や、一方通行に関する属性情報が誤って付与されているリンクが存在する場合など、道路ネットワークデータに整備ミスがある可能性の高いエリアに相当する。
【００１６】
次に、このように構成される孤立道路チェック装置を用いて、道路ネットワークに含まれる孤立道路ネットワークを検出する方法について説明する。
図２に示すように、まず、ＣＰＵ１４は、ハードディスク１２に記憶されている、リンク３２及びノード３３で構成される道路ネットワークデータ３１（図３）をメモリ１３に読み込む（ステップＳ２１）。次に、グループ分割部１５は、道路ネットワークデータ３１を複数のグループに分割する（ステップＳ２２）。
【００１７】
グループ分割部１５は、図３に示すように、道路ネットワークデータ３１を構成するリンク３２の属性情報である一方通行情報３４に着目して、当該一方通行情報３４が付与されているリンク３２ａについて道路ネットワークデータ３１から除外した状態の仮道路ネットワークデータ３５を新たに生成する。
図４に示すように、例えば、この仮道路ネットワークデータ３５には、互いに非接続状態である３つの道路ネットワーク群３６ａ〜３６ｃが存在している。グループ分割部１５は、これら３つの道路ネットワーク群３６ａ〜３６ｃをそれぞれ個別のグループとして抽出する。
【００１８】
具体的なグループの抽出方法としては、仮道路ネットワークデータ３５において任意に選択されたリンクとノードやリンクを介して直接的若しくは間接的に接続されている全てのリンクについて、ＣＰＵ１４が属性情報としての同一のグループ識別ＩＤを付与する。そして接続されている全てのリンクにグループ識別ＩＤが付与されたら、次に、ＣＰＵ１４はグループ識別ＩＤが付与されていない別のリンクを任意に選択して、同様にグループ識別ＩＤを付与する。こうしたグループ識別ＩＤの付与処理を道路ネットワークデータにおける一方通行ではない全てのリンクに対して実行することで、複数のグループが抽出される。
【００１９】
次に、グループ結合部１６は、後述するグループ結合処理を実行する（ステップＳ２３）。そして、孤立道路判定部１７は、道路ネットワークデータに複数の独立したグループが存在するか否かを判定する（ステップＳ２４）。
孤立道路判定部１７は、道路ネットワークデータ３１を構成する全てのリンクのグループ識別ＩＤを参照する。そして、全てのリンクにおけるグループ識別ＩＤが同一である場合には、独立したグループは１つしか存在しないため、孤立道路判定部１７は、孤立した道路ネットワークが存在しないと判定する（ステップＳ２５）。
【００２０】
一方、全てのリンクにおけるグループ識別ＩＤが複数存在する場合には、独立したグループは複数存在するため、孤立道路判定部１７は、孤立した道路ネットワークが存在すると判定する（ステップＳ２６）。このとき、孤立道路判定部１７は、最も多くのリンクを含んで構成される独立したグループを除外した他の独立グループに含まれる道路ネットワークが孤立した道路ネットワークであると判定する。
【００２１】
次に、上述したグループ結合処理（ステップＳ２３）について、図５〜図９を参考に具体的に説明する。
なお本処理については、図６に示すように、６つのグループ６１ａ〜６１ｆに分割されており、かつ一方通行のリンク６２ａ〜６２ｇで接続されている道路ネットワークを例に説明する。なお、リンク６２ａ〜６２ｇは、矢印方向にのみ通行することができるものとする。
【００２２】
図５に示すように、まず、グループ結合部１６は、全ての一方通行のリンク６２ａ〜６２ｇの両端がどのグループに接続しているかを決定するとともに、これらのリンク６２ａ〜６２ｇと端部が属するグループとの関係をリスト化する（ステップＳ５１）。リストの一例は、表１のとおりである。表１によれば、例えばリンク６２ａは進入側の端部がグループ６１ｃに接続しており、退出側の端部がグループ６１ａに接続していることがわかる。なお、リンク６２ａ〜６２ｇ及びグループ６１ａ〜６１ｆについては、固有のＩＤ番号で表現してもよい。
【００２３】
【表１】
2010237487.tif 000003
【００２４】
次に、グループ結合部１６は、生成されたリストに登録されていないグループを抽出する（ステップＳ５２）。道路ネットワークデータに含まれるグループであって、かつリストに登録されていないグループは、他のグループと一方通行のリンクを介して接続されていないグループであるため、完全に他のグループとは孤立している完全孤立グループであると判定することができるからである。グループ結合部１６は、抽出された完全孤立グループをハードディスク１２に記憶する。図６の例では、グループ６１ｂが完全孤立グループとして抽出される。
【００２５】
次に、グループ結合部１６は、リストに登録されたグループを節点及び頂点とするとともに、一方通行のリンクを枝とする木構造データを生成する（ステップＳ５３）。なお、頂点には任意のグループが設定される。例えば、図７に示すように、最もリンクの数が多いグループ６１ａを頂点７１とした木構造データが生成される。なお、各枝には、便宜上一方通行のリンクの番号を付してある。
【００２６】
次に、グループ結合部１６は、生成された木構造データを参照して複数のグループを結合する（ステップＳ５４）。具体的には、頂点に設定されているグループと同じグループが節点に存在する場合、同グループ間に存在する節点のグループは、頂点に設定されているグループと結合されて同じグループとなる。換言すれば、分割されたグループのうち、一方通行リンクを通って巡回可能な状態にある複数のグループが存在する場合には、当該複数のグループを結合する。これは、任意のグループを表す節点（頂点）から枝を辿って同じグループを表す節点に行き着くということは、その間に存在するグループが頂点に設定されているグループに対して孤立状態ではないということを表しているからである。
【００２７】
図６、７に示す例の場合、頂点７１と節点７３とが同じグループであり、グループ６１ａ→６１ｃ→６１ａと巡回可能である。したがって、頂点７１と節点７３との間に存在する節点７２に対応するグループ６１ｃは、グループ６１ａから孤立していないと判断されてグループ結合部１６によって結合される。
また頂点７１と節点７６とについても同じグループであり、グループ６１ａ→６１ｆ→６１ｅ→６１ａと巡回可能である。したがって、頂点７１と節点７６との間に存在する節点７４，７５にそれぞれ対応するグループ６１ｆ，６１ｅは、グループ６１ａから孤立していないと判断されてグループ結合部１６によって結合される。
【００２８】
すなわち、グループ６１ａ，６１ｃ，６１ｆ，６１ｅは、同じグループとして結合されて、図８に示すように新たなグループ６３ａとなる。なおグループ６３ａには、一方通行のリンク６２ａ，６２ｂ，６２ｄ〜６２ｇも含まれる。
次に、グループ結合部１６は、複数のグループの結合処理（ステップＳ５４）の結果、結合されたグループが存在するか否かを判定する（ステップＳ５５）。本実施例において、上述したとおり、グループ６１ａ，６１ｃ，６１ｆ，６１ｅは結合されていることから、再度一方通行のリンクについて、リスト化処理が実行される（ステップＳ５１）。一方、複数のグループの結合処理（ステップＳ５４）の結果、結合されたグループが存在しないと判定した場合には、グループ結合部１６は、グループ結合処理を終了する。
【００２９】
以上説明したとおり、本実施例の孤立道路チェック装置は以下の効果を奏する。
・道路ネットワーク全体において、孤立した道路ネットワークが存在するか否かを判定することができるため、領域にとらわれず、換言すれば道路ネットワークの規模に制限されることなく、孤立した道路ネットワークの抽出が可能となる。
・孤立した道路ネットワークが存在するということは、道路ネットワークデータにリンクの整備忘れ等のミスが存在する可能性もある。したがって、最新の道路ネットワークデータに更新された際の誤り判定等に利用することも可能である。
【００３０】
・一方通行リンクを除いてグループ化する処理と一方通行リンクに着目してグループ結合を行う処理とを採用したことで、ロジックを簡略化することができる。
・結合できたグループ内のリンクをメモリ上から除去し、一方通行リンクにおける接続部分に着目して処理を実行することで無駄なメモリの消費を軽減することができる。
・一方通行情報が付与されているリンクを除去して、互いに接続状態である道路ネットワーク群を１つのグループとして抽出するようにしたことで、ある程度まとまったネットワーク群がグループ化される。したがって、グループ結合処理の処理回数を抑制することができる。
【００３１】
（別例）
・道路ネットワークデータには、本来的に孤立した道路ネットワークが存在する場合もあり得る。例えば、道路ネットワークにリンクとして整備されていないような細い道路でのみ主要道路と接続されている道路ネットワークのグループについては孤立した道路ネットワークであると判定される。こうした道路ネットワークのグループについては、予め道路ネットワークデータから除外しておくことで、無用な孤立道路ネットワークの検出を回避するようにしてもよい。
【００３２】
・グループ分割部１５が道路ネットワークデータ３１を複数のグループに分割する方法は、上記実施例の手法に限られない。例えば、１つのリンクを１つのグループとして定義してもよい。
・孤立道路ネットワークを検出するための道路ネットワークデータは、全国規模の道路ネットワークデータは勿論のこと、九州地方や関東地方、福岡県といった所定の領域における道路ネットワークデータであってもよい。
【符号の説明】
【００３３】
１２…道路ネットワークデータ記憶部としてのハードディスク、１５…グループ分割部、１６…グループ結合部、１７…孤立道路判定部。
【図１】
2010237487.tif 000004
【図２】
2010237487.tif 000005
【図３】
2010237487.tif 000006
【図４】
2010237487.tif 000007
【図５】
2010237487.tif 000008
【図６】
2010237487.tif 000009
【図７】
2010237487.tif 000010
【図８】
2010237487.tif 000011