孤立道路抽出装置
【課題】少ないメモリ消費で、道路ネットワークデータ内に存在する孤立した道路を抽出することのできる孤立道路抽出装置を提供する。
【解決手段】グループ化部１３は、１つのメッシュから読み出された道路ネットワークについてグループ化処理を実行する。次に、フラグ情報付与部１４は、グループにフラグ情報である接続確定フラグ情報または孤立フラグ情報を付与するフラグ情報付与処理を実行する。すべてのメッシュについて処理が実行されたと判定した場合、制御部１７は、すべてのメッシュにおいて生成されたグループを結合する処理を実行する。そして、孤立道路抽出部１６は、グループが複数存在する場合、孤立フラグ情報が付与されているグループに対応する孤立道路を抽出する。
【解決手段】グループ化部１３は、１つのメッシュから読み出された道路ネットワークについてグループ化処理を実行する。次に、フラグ情報付与部１４は、グループにフラグ情報である接続確定フラグ情報または孤立フラグ情報を付与するフラグ情報付与処理を実行する。すべてのメッシュについて処理が実行されたと判定した場合、制御部１７は、すべてのメッシュにおいて生成されたグループを結合する処理を実行する。そして、孤立道路抽出部１６は、グループが複数存在する場合、孤立フラグ情報が付与されているグループに対応する孤立道路を抽出する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、道路ネットワークデータを含む地図データから、孤立した道路に対応する道路ネットワークデータを抽出する技術に関連したものである。
【背景技術】
【０００２】
従来から、ナビゲーション装置等に使用される電子地図の一部を更新する技術が知られている。例えば、特許文献１に記載の技術は、既存の地図データを更新用地図データに基づいて更新したときに、一部の道路が他の道路から孤立した状態となる孤立状態の有無を検出している。具体的には、例えば、削除された道路があった場合に、削除された道路の一端と他端とを結ぶ経路の探索を行って、経路が存在しない場合に更新された地図データに孤立状態が存在していることを検出している。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００８−２４９７９８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、この特許文献１に記載の技術では、道路データが削除された場合に、その道路に接続していた道路の孤立状態を検出するだけであり、もともと孤立していた道路の一部が削除された場合には、当該道路が孤立状態であることを検出することができない場合がある。そもそも、特許文献１に記載の技術は、局所的に道路の接続状態に矛盾が生じないかを判断しているだけであり、道路ネットワーク全体の中から孤立状態にある道路を抽出することを意図した技術ではない。
【０００５】
特許文献１に記載の技術で道路ネットワーク全体における孤立状態の有無の判定処理を実行する場合、通常の経路探索アルゴリズムでは多大なメモリを要することになり、現実的でない。なぜならば、削除された道路の一端と他端とを結ぶ経路を探索する場合、その候補となる道路が多数存在するからである。
本発明は、上記の問題点を解決するためになされた発明である。その目的は、少ないメモリ消費で、道路ネットワークデータ内に存在する孤立した道路を抽出することのできる孤立道路抽出装置を提供することである。
【課題を解決するための手段】
【０００６】
上記課題を解決するために、本発明は、複数のメッシュで区分されるとともに該メッシュ単位で管理されている、ノードおよびリンクで表わされた道路ネットワークデータおよびメッシュの境界に存在する境界ノードに設定されているフラグ情報を記憶するネットワークデータ記憶部と、前記メッシュに含まれる道路ネットワークデータおよび境界ノードに設定されているフラグ情報を読み出すデータ読出部と、前記道路ネットワークデータを構成するノードおよびリンクのうち、接続されているリンクおよびノードをグループ化するグループ化部と、幹線道路に該当する幹線リンク、または幹線道路に接続していることを表わす接続確定フラグ情報が設定されている境界ノードが含まれているグループに接続確定フラグ情報を付与するとともに、前記幹線リンクが含まれないグループおよび単一のメッシュ内に独立して存在するグループに孤立の可能性を表わす孤立フラグ情報を付与するフラグ情報付与部と、フラグ情報が付与されたグループに含まれる境界ノードに、該グループに付与されたフラグ情報を設定するとともに、該フラグ情報を前記ネットワークデータ記憶部に記憶するフラグ情報設定部と、前記孤立フラグ情報が付与されているグループに対応する道路を孤立道路として抽出する孤立道路抽出部とを備えることを特徴とする。
なお、上述した特徴は、本発明の特徴のすべてを列挙したものではなく、これらを要部とする構成（または方法）もまた発明となり得る。
【発明の効果】
【０００７】
本発明によれば、少ないメモリ消費で、道路ネットワークデータ全体から孤立する道路を抽出することができる。
【図面の簡単な説明】
【０００８】
【図１】孤立道路抽出装置の構成図。
【図２】道路ネットワークデータの一部の説明図。
【図３】孤立道路抽出処理のフローチャート。
【図４】グループ化処理のフローチャート。
【図５】グループ化処理の説明図。
【図６】フラグ情報付与処理のフローチャート。
【発明を実施するための形態】
【０００９】
以下、本発明を具体化した実施例について説明する。
図１に示すように、本実施例における孤立道路抽出装置は、ハードディスクやフラッシュメモリ等で構成されているネットワークデータ記憶部１１と、データ読出部１２と、グループ化部１３と、フラグ情報付与部１４と、フラグ情報設定部１５と、孤立道路抽出部１６と、制御部１７とを備える。
【００１０】
ネットワークデータ記憶部１１には、道路ネットワークデータが記憶されている。道路ネットワークデータは、図２に示すように、地図２１における道路２２を表現したリンク２３と交差点２４を表現したノード２５とを含んで構成されている。また、道路ネットワークデータは、矩形状をなすメッシュ２６で区分されている。メッシュとは全領域に対応する地図２１を緯度経度等で構成される所定の区画で細分化した領域である。リンク２３が、隣接するメッシュ２６を跨る場合、そのメッシュ２６の境界地点には、境界ノード２５が付与されている。この境界ノード２５もノード２５と同様に道路ネットワークデータを構成している。通常、地図データは、メッシュ単位で管理されている。例えば、地図データが修正・更新等される場合には、このメッシュ２６毎に実行される。
【００１１】
リンク２３、ノード２５、境界ノード２５には、各種の属性情報が付与されている。属性情報は、そのリンクやノードに対応する路線の特徴を表す情報であり、ネットワークデータ記憶部１１に、リンクやノードと関連付けられた状態で記憶されている。例えば、リンクの属性情報のひとつであるリンクコストは、一般的にはそのリンクを通行する際にユーザにかかる負荷を表している。そのほかにも、リンクの属性情報としては、当該リンクを特定する固有のＩＤ番号、リンクの長さを示すリンク長、リンクの始端および終端に存在するノードの緯度・経度座標、高度情報、リンクにおける複数地点の緯度・経度座標、高度情報、路線名称、路線種別等がある。
【００１２】
また、ノードに対応付けられている属性情報としては、ノードを特定する固有のＩＤ番号、ノード座標、高度情報、ノード名称、ノードに接続するリンクのリンクＩＤが記述される接続リンクＩＤ等がある。リンクおよびノードの高度情報は、基準位置における高さとの相対的な高さに関する情報であってもよいし、海抜であってもよい。
さらに、境界ノードには、属性情報として、フラグ情報が設定されている。このフラグ情報には、接続確定フラグ情報と孤立フラグ情報とがある。接続確定フラグ情報は、当該境界ノードに直接的もしくは間接的に接続しているリンクに、幹線道路に該当する幹線リンクが存在する場合に設定される。
【００１３】
ここで、幹線道路とは主要地点間を結び網の骨格をなす重要路線のことである。例えば、高速道路や、国道が該当する。なお、本実施例では、当該幹線道路と一体となって高速交通体系の役割を果たし、地域構造を強化する規格の高い地域高規格道路についても、幹線道路に含めてよい。こうした地域高規格道路は、通常高速道路や国道に接続しているからである。
つまり、接続確定フラグ情報が設定されている境界ノードは、幹線道路に接続されている、孤立したノードでないことを表わす情報である。
本実施例において、「孤立」とは、幹線道路と直接的もしくは間接的に接続していない道路ネットワークに対応する道路の状態のことをいう。
【００１４】
一方、孤立フラグ情報は、当該境界ノードに直接的もしくは間接的に接続しているリンクに、幹線道路に該当する幹線リンクが存在しない場合に設定される。つまり、孤立フラグ情報が設定されている境界ノードは、幹線道路に接続されておらず、孤立したノードであるか、または孤立している可能性があるノードであることを表わす情報である。
【００１５】
データ読出部１２は、ネットワークデータ記憶部１１に記憶されている各種データを読み出す機能を有する。例えば、データ読出部１２は、メッシュで管理されている道路ネットワークデータや境界ノードに設定されているフラグ情報を読み出す。
グループ化部１３は、メッシュにおける道路ネットワークデータを構成するノードおよびリンクのうち、直接的もしくは間接的に接続されているリンクおよびノードを１つのグループとしてまとめていく機能を有する。例えば、接続関係にあるリンクおよびノードについてはグループに固有のＩＤを属性情報として付与するなどして、どのリンクおよびノードが１つのグループに属するかを判別可能な状態にする。
【００１６】
フラグ情報付与部１４は、グループを構成するリンクに、幹線道路に該当する幹線リンクが含まれているか否かを判定する。幹線リンクが含まれている場合には、当該幹線リンクを含むグループに対して接続確定フラグ情報を付与する。当該グループを構成している道路ネットワークは、本実施例で規定する孤立した道路には該当しないからである。一方、幹線リンクが含まれていない場合には、当該幹線リンクを含まないグループに対して孤立フラグ情報を付与する。幹線リンクが含まれていない、細道路の道路ネットワークでのみ構成されるグループは、孤立した道路に該当する可能性があるからである。
【００１７】
また、フラグ情報付与部１４は、グループを構成する道路ネットワークに境界ノードが含まれている場合であって、その境界ノードに接続確定フラグ情報が設定されている場合には、そのグループに対して接続確定フラグ情報を付与する。接続確定フラグ情報が設定されている境界ノードは、隣接するメッシュにおいて幹線道路に該当する幹線リンクに直接的もしくは間接的に接続していることから、その境界ノードを含むグループも孤立状態ではないとして、確定させることができるからである。
【００１８】
一方、グループを構成する道路ネットワークに境界ノードが含まれていない場合には、フラグ情報付与部１４は当該グループに孤立フラグ情報を付与する。当該グループは、孤立状態である可能性があるからである。また、単一のメッシュ内に独立して存在するグループに対しても、フラグ情報付与部１４は孤立フラグ情報を付与する。単一のメッシュ内に独立して存在するグループは、仮に幹線リンクを含んでいたとしても、単一のメッシュ内でしかグループ化できなかった道路ネットワークは、データの誤入力等によって孤立した状態にあるからである。したがって、フラグ情報付与部１４が、幹線リンクが含まれているとして一旦接続確定フラグ情報を当該グループに付与したとしても、この条件を満たすグループについては接続確定フラグ情報が孤立フラグ情報に変更されることになる。
【００１９】
フラグ情報設定部１５は、フラグ情報が付与されたグループに含まれている境界ノードを抽出するとともに、当該境界ノードに対してグループに付与されたフラグ情報と同一のフラグ情報を設定する。フラグ情報設定部１５は、境界ノードに設定されたフラグ情報をネットワークデータ記憶部１１に記憶する。つまり、境界ノードの属性情報が更新されることになる。
【００２０】
孤立道路抽出部１６は、すべてのメッシュに対してグループ化処理が実行されるとともに、すべてのグループおよび境界ノードにフラグ情報が付与された場合に、孤立フラグ情報が付与されているグループに対応する道路を孤立道路として抽出する。最終的に幹線道路に直接的もしくは間接的に接続されていない道路ネットワークに対応する道路は、孤立道路であると認定することができるからである。
【００２１】
制御部１７は、孤立道路抽出装置が備える各部１１〜１６の動作を、メモリ等に記録されている所定のプログラムに基づいて制御する機能を有する。
なお、各部１２〜１７の機能は、実際には孤立道路抽出装置に備えられている図示しないＣＰＵ（Central Processing Unit ）がメモリ等に記憶されている各種プログラムを実行することにより実現される。
【００２２】
以上のように構成される孤立道路抽出装置を用いて、地図データ全体の中に存在している孤立道路を抽出する孤立道路抽出処理について説明する。
図３に示すように、まず、データ読出部１２は、ネットワークデータ記憶部１１に記憶されている道路ネットワークデータのうち、１つのメッシュで管理されている道路ネットワークデータを読み出す（ステップＳ３１）。
【００２３】
次に、グループ化部１３は、読み出された道路ネットワークについてグループ化処理を実行する（ステップＳ３２）。具体的なグループ化処理は後述する。
次に、フラグ情報付与部１４は、グループにフラグ情報である接続確定フラグ情報または孤立フラグ情報を付与するフラグ情報付与処理を実行する（ステップＳ３３）。具体的なフラグ情報付与処理は後述する。
【００２４】
次に、フラグ情報設定部１５は、メッシュ内のすべての境界ノードを抽出するとともに、当該境界ノードの属性情報としてフラグ情報を設定する（ステップＳ３４）。具体的には、境界ノードが属するグループに付与されたフラグ情報と同じフラグ情報を、当該境界ノードの属性情報として設定する。境界ノードに、孤立フラグ情報が設定されていたとしても、当該境界ノードの属するグループに接続確定フラグ情報が付与されている場合には、フラグ情報は、孤立フラグ情報から接続確定フラグ情報に変更されることになる。その後に、フラグ情報設定部１５は、フラグ情報が設定された境界ノードをネットワークデータ記憶部１１に記憶する。
【００２５】
次に、制御部１７は、すべてのメッシュについて、グループ化処理およびフラグ情報付与処理が実行されたか否かを判定する（ステップＳ３５）。すべてのメッシュについて処理が実行されていないと判定された場合、制御部１７は、実行されていないメッシュについて、グループ化処理、フラグ情報付与処理等（ステップＳ３１〜Ｓ３４）を実行する。その一方で、すべてのメッシュについて処理が実行されたと判定した場合、制御部１７は、すべてのメッシュにおいて生成されたグループを結合する処理を実行する（ステップＳ３６）。この処理は、メッシュを跨いで接続されているグループを１つのグループとする処理である。具体的には、境界メッシュで接続されている隣接するメッシュのグループについて、これらのグループの属性情報であるＩＤを同一のＩＤとする。
【００２６】
次に、孤立道路抽出部１６は、孤立道路を抽出する（ステップＳ３７）。
グループが１つしか存在しない場合、換言すれば、すべての道路ネットワークデータが接続されている場合には、孤立フラグ情報が付与されているグループが存在し得ないため、孤立道路抽出部１６は、孤立道路が存在しないと判断して、処理を終了する。
一方、グループが複数存在する場合、孤立道路抽出部１６は、孤立フラグ情報が付与されているグループに対応する道路を抽出する。
【００２７】
孤立道路抽出部１６によって抽出された道路は、幹線道路に接続されていない孤立道路である。実際には、こうした孤立道路が存在することはほとんどない。したがって、孤立道路に対応する道路ネットワークの接続関係を検査することで、道路ネットワークの整備漏れや誤整備などの存在を効率的に見つけることができる。また、整備漏れ等がない場合には、当該孤立道路から幹線道路へと接続する道路であって、道路ネットワークとして整備されてない道路を決定して道路ネットワークデータとして整備することで道路ネットワークデータを充実させることが可能となる。
【００２８】
次に、グループ化処理（ステップＳ３２）の一例について図４，図５を用いて説明する。
図４に示すように、まず、グループ化部１３は任意の１つのリンクを選択する（ステップＳ４１）。図５に示す例では、リンクＬ２が選択される。次に、グループ化部１３は当該リンクに直接的もしくは間接的に接続されているノードおよびリンクを順次探索して選択する（ステップＳ４２）。図５に示す例では、リンクＬ２に直接的に接続しているノードＮ１，Ｎ２および間接的に接続しているリンクＬ１，Ｌ３〜Ｌ６が選択される。さらに、リンクが接続している境界ノードＮ５〜Ｎ９についても選択される。
【００２９】
次に、グループ化部１３は、これらリンクＬ１〜Ｌ６およびノードＮ１，Ｎ２，Ｎ５〜Ｎ９について、１つのグループであることを示すグループＩＤを付与する（ステップＳ４３）。グループＩＤは、各リンクおよびノードの属性情報として付与してもよい。また、グループＩＤと、グループ化されたリンクおよびノードとを対応付けたテーブルを作成してもよい。
【００３０】
次に、グループ化部１３は、メッシュ内に、グループ化されていないリンクおよびノードが存在するか否かを判定する（ステップＳ４４）。メッシュ内のすべてのリンクおよびノードがグループ化されている場合には、グループ化部１３は、グループ化処理を終了する。一方、メッシュ内にグループ化されていないリンクまたはノードが存在する場合、グループ化部１３は、当該グループ化されていないリンクまたはノードのうち任意のリンクまたはノードを選択する（ステップＳ４５）。そして、グループ化部１３は、当該リンクまたはノードについて、グループ化処理を実行する。
【００３１】
図５に示す例の場合、グループ化されていないリンクとして、リンクＬ７，Ｌ８が存在する。したがって、グループ化部１３は、リンクＬ７を選択するとともに、当該リンクＬ７に直接接続しているノードＮ３，Ｎ４を選択する。そして、これらリンクＬ７、ノードＮ３，Ｎ４をグループ化するとともに、同一のグループＩＤを付与する。同じく、グループ化部１３は、リンクＬ８を選択するとともに、当該リンクＬ８に直接接続しているノードＮ１０，Ｎ１１を選択する。そして、これらリンクＬ８、ノードＮ１０，Ｎ１１をグループ化するとともに、同一のグループＩＤを付与する。
【００３２】
次に、フラグ情報付与化処理（ステップＳ３３）の一例について説明する。
図６に示すように、まず、フラグ情報付与部１４は、メッシュ内の１つのグループに着目するとともに、当該グループ内に存在するリンクの属性情報である路線種別情報を参照する。そして、高速道路や国道等の幹線道路に該当する幹線リンクがあるか否かを判定する（ステップＳ６１）。幹線リンクが存在すると判定した場合、フラグ情報付与部１４は、当該幹線リンクを含むグループに接続確定フラグ情報を付与する（ステップＳ６２）。一方、幹線リンクが存在しないと判定した場合、フラグ情報付与部１４は、当該幹線リンクが含まれないグループに孤立フラグ情報を付与する（ステップＳ６３）。
【００３３】
次に、フラグ情報付与部１４は、孤立フラグ情報が付与されたグループ内に境界ノードが含まれており、当該境界ノードにフラグ情報が設定されている場合には、当該フラグ情報をグループのフラグ情報に反映させる（ステップＳ６４）。具体的には、グループ内に含まれている境界ノードのうち、少なくともいずれか１つの境界ノードに接続確定フラグ情報が設定されている場合には、そのグループを構成する道路ネットワークは間接的に幹線リンクと接続されていることになる。したがって、こうしたグループには、フラグ情報付与部１４によって接続確定フラグ情報が付与される。一方、グループ内に含まれているすべての境界ノードにフラグ情報が設定されていないか、あるいは孤立フラグ情報が設定されている場合には、当該グループのフラグ情報は孤立フラグ情報のまま変更されない。
【００３４】
次に、フラグ情報付与部１４は、グループが、他のメッシュに接続しているか否かを判定する（ステップＳ６５）。例えば、グループに境界ノードが含まれていない場合には、当該グループは１つのメッシュ内に含まれる道路ネットワークでのみ構成されている、換言すれば単一のメッシュ内に独立して存在するグループということになる。この場合、グループを構成する道路ネットワークは幹線リンクに接続していない。また、仮に幹線リンクに接続していたとしても他の道路ネットワークからは孤立したネットワークであることは明らかである。したがって、グループが他のメッシュに接続していない場合には、フラグ情報付与部１４は、孤立フラグ情報を付与する（ステップＳ６６）。
【００３５】
次に、フラグ情報付与部１４は、メッシュ内のすべてのグループに対してフラグ情報を付与したか否かを判定する（ステップＳ６７）。すべてのグループに対してフラグ情報が付与されていないと判定した場合には、フラグ情報付与部１４は、フラグ情報が付与されていないグループを選択するとともに、ステップＳ６１に戻って、当該グループに対してフラグ情報を付与する処理を実行する。その一方で、メッシュに含まれるすべてのグループに対してフラグ情報を付与したと判定した場合には、制御部１７は、フラグ情報付与化処理を終了する。
【００３６】
本実施例の孤立道路抽出装置によれば、複数のメッシュに跨るような比較的広範囲の道路であっても高速道路や国道に接続していない孤立した道路であると判定して抽出することができる。また、境界ノードの属性情報としてフラグ情報を設定するとともに、このフラグ情報を利用してメッシュ毎の孤立状態を把握するようにしたことで、１つのメッシュを処理するだけのメモリ容量があれば、地図データ全体にわたって孤立状態にある道路を抽出する処理を実現することができる。
【符号の説明】
【００３７】
１１…ネットワークデータ記憶部
１２…データ読出部
１３…グループ化部
１４…フラグ情報付与部
１５…フラグ情報設定部
１６…孤立道路抽出部
【技術分野】
【０００１】
本発明は、道路ネットワークデータを含む地図データから、孤立した道路に対応する道路ネットワークデータを抽出する技術に関連したものである。
【背景技術】
【０００２】
従来から、ナビゲーション装置等に使用される電子地図の一部を更新する技術が知られている。例えば、特許文献１に記載の技術は、既存の地図データを更新用地図データに基づいて更新したときに、一部の道路が他の道路から孤立した状態となる孤立状態の有無を検出している。具体的には、例えば、削除された道路があった場合に、削除された道路の一端と他端とを結ぶ経路の探索を行って、経路が存在しない場合に更新された地図データに孤立状態が存在していることを検出している。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００８−２４９７９８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、この特許文献１に記載の技術では、道路データが削除された場合に、その道路に接続していた道路の孤立状態を検出するだけであり、もともと孤立していた道路の一部が削除された場合には、当該道路が孤立状態であることを検出することができない場合がある。そもそも、特許文献１に記載の技術は、局所的に道路の接続状態に矛盾が生じないかを判断しているだけであり、道路ネットワーク全体の中から孤立状態にある道路を抽出することを意図した技術ではない。
【０００５】
特許文献１に記載の技術で道路ネットワーク全体における孤立状態の有無の判定処理を実行する場合、通常の経路探索アルゴリズムでは多大なメモリを要することになり、現実的でない。なぜならば、削除された道路の一端と他端とを結ぶ経路を探索する場合、その候補となる道路が多数存在するからである。
本発明は、上記の問題点を解決するためになされた発明である。その目的は、少ないメモリ消費で、道路ネットワークデータ内に存在する孤立した道路を抽出することのできる孤立道路抽出装置を提供することである。
【課題を解決するための手段】
【０００６】
上記課題を解決するために、本発明は、複数のメッシュで区分されるとともに該メッシュ単位で管理されている、ノードおよびリンクで表わされた道路ネットワークデータおよびメッシュの境界に存在する境界ノードに設定されているフラグ情報を記憶するネットワークデータ記憶部と、前記メッシュに含まれる道路ネットワークデータおよび境界ノードに設定されているフラグ情報を読み出すデータ読出部と、前記道路ネットワークデータを構成するノードおよびリンクのうち、接続されているリンクおよびノードをグループ化するグループ化部と、幹線道路に該当する幹線リンク、または幹線道路に接続していることを表わす接続確定フラグ情報が設定されている境界ノードが含まれているグループに接続確定フラグ情報を付与するとともに、前記幹線リンクが含まれないグループおよび単一のメッシュ内に独立して存在するグループに孤立の可能性を表わす孤立フラグ情報を付与するフラグ情報付与部と、フラグ情報が付与されたグループに含まれる境界ノードに、該グループに付与されたフラグ情報を設定するとともに、該フラグ情報を前記ネットワークデータ記憶部に記憶するフラグ情報設定部と、前記孤立フラグ情報が付与されているグループに対応する道路を孤立道路として抽出する孤立道路抽出部とを備えることを特徴とする。
なお、上述した特徴は、本発明の特徴のすべてを列挙したものではなく、これらを要部とする構成（または方法）もまた発明となり得る。
【発明の効果】
【０００７】
本発明によれば、少ないメモリ消費で、道路ネットワークデータ全体から孤立する道路を抽出することができる。
【図面の簡単な説明】
【０００８】
【図１】孤立道路抽出装置の構成図。
【図２】道路ネットワークデータの一部の説明図。
【図３】孤立道路抽出処理のフローチャート。
【図４】グループ化処理のフローチャート。
【図５】グループ化処理の説明図。
【図６】フラグ情報付与処理のフローチャート。
【発明を実施するための形態】
【０００９】
以下、本発明を具体化した実施例について説明する。
図１に示すように、本実施例における孤立道路抽出装置は、ハードディスクやフラッシュメモリ等で構成されているネットワークデータ記憶部１１と、データ読出部１２と、グループ化部１３と、フラグ情報付与部１４と、フラグ情報設定部１５と、孤立道路抽出部１６と、制御部１７とを備える。
【００１０】
ネットワークデータ記憶部１１には、道路ネットワークデータが記憶されている。道路ネットワークデータは、図２に示すように、地図２１における道路２２を表現したリンク２３と交差点２４を表現したノード２５とを含んで構成されている。また、道路ネットワークデータは、矩形状をなすメッシュ２６で区分されている。メッシュとは全領域に対応する地図２１を緯度経度等で構成される所定の区画で細分化した領域である。リンク２３が、隣接するメッシュ２６を跨る場合、そのメッシュ２６の境界地点には、境界ノード２５が付与されている。この境界ノード２５もノード２５と同様に道路ネットワークデータを構成している。通常、地図データは、メッシュ単位で管理されている。例えば、地図データが修正・更新等される場合には、このメッシュ２６毎に実行される。
【００１１】
リンク２３、ノード２５、境界ノード２５には、各種の属性情報が付与されている。属性情報は、そのリンクやノードに対応する路線の特徴を表す情報であり、ネットワークデータ記憶部１１に、リンクやノードと関連付けられた状態で記憶されている。例えば、リンクの属性情報のひとつであるリンクコストは、一般的にはそのリンクを通行する際にユーザにかかる負荷を表している。そのほかにも、リンクの属性情報としては、当該リンクを特定する固有のＩＤ番号、リンクの長さを示すリンク長、リンクの始端および終端に存在するノードの緯度・経度座標、高度情報、リンクにおける複数地点の緯度・経度座標、高度情報、路線名称、路線種別等がある。
【００１２】
また、ノードに対応付けられている属性情報としては、ノードを特定する固有のＩＤ番号、ノード座標、高度情報、ノード名称、ノードに接続するリンクのリンクＩＤが記述される接続リンクＩＤ等がある。リンクおよびノードの高度情報は、基準位置における高さとの相対的な高さに関する情報であってもよいし、海抜であってもよい。
さらに、境界ノードには、属性情報として、フラグ情報が設定されている。このフラグ情報には、接続確定フラグ情報と孤立フラグ情報とがある。接続確定フラグ情報は、当該境界ノードに直接的もしくは間接的に接続しているリンクに、幹線道路に該当する幹線リンクが存在する場合に設定される。
【００１３】
ここで、幹線道路とは主要地点間を結び網の骨格をなす重要路線のことである。例えば、高速道路や、国道が該当する。なお、本実施例では、当該幹線道路と一体となって高速交通体系の役割を果たし、地域構造を強化する規格の高い地域高規格道路についても、幹線道路に含めてよい。こうした地域高規格道路は、通常高速道路や国道に接続しているからである。
つまり、接続確定フラグ情報が設定されている境界ノードは、幹線道路に接続されている、孤立したノードでないことを表わす情報である。
本実施例において、「孤立」とは、幹線道路と直接的もしくは間接的に接続していない道路ネットワークに対応する道路の状態のことをいう。
【００１４】
一方、孤立フラグ情報は、当該境界ノードに直接的もしくは間接的に接続しているリンクに、幹線道路に該当する幹線リンクが存在しない場合に設定される。つまり、孤立フラグ情報が設定されている境界ノードは、幹線道路に接続されておらず、孤立したノードであるか、または孤立している可能性があるノードであることを表わす情報である。
【００１５】
データ読出部１２は、ネットワークデータ記憶部１１に記憶されている各種データを読み出す機能を有する。例えば、データ読出部１２は、メッシュで管理されている道路ネットワークデータや境界ノードに設定されているフラグ情報を読み出す。
グループ化部１３は、メッシュにおける道路ネットワークデータを構成するノードおよびリンクのうち、直接的もしくは間接的に接続されているリンクおよびノードを１つのグループとしてまとめていく機能を有する。例えば、接続関係にあるリンクおよびノードについてはグループに固有のＩＤを属性情報として付与するなどして、どのリンクおよびノードが１つのグループに属するかを判別可能な状態にする。
【００１６】
フラグ情報付与部１４は、グループを構成するリンクに、幹線道路に該当する幹線リンクが含まれているか否かを判定する。幹線リンクが含まれている場合には、当該幹線リンクを含むグループに対して接続確定フラグ情報を付与する。当該グループを構成している道路ネットワークは、本実施例で規定する孤立した道路には該当しないからである。一方、幹線リンクが含まれていない場合には、当該幹線リンクを含まないグループに対して孤立フラグ情報を付与する。幹線リンクが含まれていない、細道路の道路ネットワークでのみ構成されるグループは、孤立した道路に該当する可能性があるからである。
【００１７】
また、フラグ情報付与部１４は、グループを構成する道路ネットワークに境界ノードが含まれている場合であって、その境界ノードに接続確定フラグ情報が設定されている場合には、そのグループに対して接続確定フラグ情報を付与する。接続確定フラグ情報が設定されている境界ノードは、隣接するメッシュにおいて幹線道路に該当する幹線リンクに直接的もしくは間接的に接続していることから、その境界ノードを含むグループも孤立状態ではないとして、確定させることができるからである。
【００１８】
一方、グループを構成する道路ネットワークに境界ノードが含まれていない場合には、フラグ情報付与部１４は当該グループに孤立フラグ情報を付与する。当該グループは、孤立状態である可能性があるからである。また、単一のメッシュ内に独立して存在するグループに対しても、フラグ情報付与部１４は孤立フラグ情報を付与する。単一のメッシュ内に独立して存在するグループは、仮に幹線リンクを含んでいたとしても、単一のメッシュ内でしかグループ化できなかった道路ネットワークは、データの誤入力等によって孤立した状態にあるからである。したがって、フラグ情報付与部１４が、幹線リンクが含まれているとして一旦接続確定フラグ情報を当該グループに付与したとしても、この条件を満たすグループについては接続確定フラグ情報が孤立フラグ情報に変更されることになる。
【００１９】
フラグ情報設定部１５は、フラグ情報が付与されたグループに含まれている境界ノードを抽出するとともに、当該境界ノードに対してグループに付与されたフラグ情報と同一のフラグ情報を設定する。フラグ情報設定部１５は、境界ノードに設定されたフラグ情報をネットワークデータ記憶部１１に記憶する。つまり、境界ノードの属性情報が更新されることになる。
【００２０】
孤立道路抽出部１６は、すべてのメッシュに対してグループ化処理が実行されるとともに、すべてのグループおよび境界ノードにフラグ情報が付与された場合に、孤立フラグ情報が付与されているグループに対応する道路を孤立道路として抽出する。最終的に幹線道路に直接的もしくは間接的に接続されていない道路ネットワークに対応する道路は、孤立道路であると認定することができるからである。
【００２１】
制御部１７は、孤立道路抽出装置が備える各部１１〜１６の動作を、メモリ等に記録されている所定のプログラムに基づいて制御する機能を有する。
なお、各部１２〜１７の機能は、実際には孤立道路抽出装置に備えられている図示しないＣＰＵ（Central Processing Unit ）がメモリ等に記憶されている各種プログラムを実行することにより実現される。
【００２２】
以上のように構成される孤立道路抽出装置を用いて、地図データ全体の中に存在している孤立道路を抽出する孤立道路抽出処理について説明する。
図３に示すように、まず、データ読出部１２は、ネットワークデータ記憶部１１に記憶されている道路ネットワークデータのうち、１つのメッシュで管理されている道路ネットワークデータを読み出す（ステップＳ３１）。
【００２３】
次に、グループ化部１３は、読み出された道路ネットワークについてグループ化処理を実行する（ステップＳ３２）。具体的なグループ化処理は後述する。
次に、フラグ情報付与部１４は、グループにフラグ情報である接続確定フラグ情報または孤立フラグ情報を付与するフラグ情報付与処理を実行する（ステップＳ３３）。具体的なフラグ情報付与処理は後述する。
【００２４】
次に、フラグ情報設定部１５は、メッシュ内のすべての境界ノードを抽出するとともに、当該境界ノードの属性情報としてフラグ情報を設定する（ステップＳ３４）。具体的には、境界ノードが属するグループに付与されたフラグ情報と同じフラグ情報を、当該境界ノードの属性情報として設定する。境界ノードに、孤立フラグ情報が設定されていたとしても、当該境界ノードの属するグループに接続確定フラグ情報が付与されている場合には、フラグ情報は、孤立フラグ情報から接続確定フラグ情報に変更されることになる。その後に、フラグ情報設定部１５は、フラグ情報が設定された境界ノードをネットワークデータ記憶部１１に記憶する。
【００２５】
次に、制御部１７は、すべてのメッシュについて、グループ化処理およびフラグ情報付与処理が実行されたか否かを判定する（ステップＳ３５）。すべてのメッシュについて処理が実行されていないと判定された場合、制御部１７は、実行されていないメッシュについて、グループ化処理、フラグ情報付与処理等（ステップＳ３１〜Ｓ３４）を実行する。その一方で、すべてのメッシュについて処理が実行されたと判定した場合、制御部１７は、すべてのメッシュにおいて生成されたグループを結合する処理を実行する（ステップＳ３６）。この処理は、メッシュを跨いで接続されているグループを１つのグループとする処理である。具体的には、境界メッシュで接続されている隣接するメッシュのグループについて、これらのグループの属性情報であるＩＤを同一のＩＤとする。
【００２６】
次に、孤立道路抽出部１６は、孤立道路を抽出する（ステップＳ３７）。
グループが１つしか存在しない場合、換言すれば、すべての道路ネットワークデータが接続されている場合には、孤立フラグ情報が付与されているグループが存在し得ないため、孤立道路抽出部１６は、孤立道路が存在しないと判断して、処理を終了する。
一方、グループが複数存在する場合、孤立道路抽出部１６は、孤立フラグ情報が付与されているグループに対応する道路を抽出する。
【００２７】
孤立道路抽出部１６によって抽出された道路は、幹線道路に接続されていない孤立道路である。実際には、こうした孤立道路が存在することはほとんどない。したがって、孤立道路に対応する道路ネットワークの接続関係を検査することで、道路ネットワークの整備漏れや誤整備などの存在を効率的に見つけることができる。また、整備漏れ等がない場合には、当該孤立道路から幹線道路へと接続する道路であって、道路ネットワークとして整備されてない道路を決定して道路ネットワークデータとして整備することで道路ネットワークデータを充実させることが可能となる。
【００２８】
次に、グループ化処理（ステップＳ３２）の一例について図４，図５を用いて説明する。
図４に示すように、まず、グループ化部１３は任意の１つのリンクを選択する（ステップＳ４１）。図５に示す例では、リンクＬ２が選択される。次に、グループ化部１３は当該リンクに直接的もしくは間接的に接続されているノードおよびリンクを順次探索して選択する（ステップＳ４２）。図５に示す例では、リンクＬ２に直接的に接続しているノードＮ１，Ｎ２および間接的に接続しているリンクＬ１，Ｌ３〜Ｌ６が選択される。さらに、リンクが接続している境界ノードＮ５〜Ｎ９についても選択される。
【００２９】
次に、グループ化部１３は、これらリンクＬ１〜Ｌ６およびノードＮ１，Ｎ２，Ｎ５〜Ｎ９について、１つのグループであることを示すグループＩＤを付与する（ステップＳ４３）。グループＩＤは、各リンクおよびノードの属性情報として付与してもよい。また、グループＩＤと、グループ化されたリンクおよびノードとを対応付けたテーブルを作成してもよい。
【００３０】
次に、グループ化部１３は、メッシュ内に、グループ化されていないリンクおよびノードが存在するか否かを判定する（ステップＳ４４）。メッシュ内のすべてのリンクおよびノードがグループ化されている場合には、グループ化部１３は、グループ化処理を終了する。一方、メッシュ内にグループ化されていないリンクまたはノードが存在する場合、グループ化部１３は、当該グループ化されていないリンクまたはノードのうち任意のリンクまたはノードを選択する（ステップＳ４５）。そして、グループ化部１３は、当該リンクまたはノードについて、グループ化処理を実行する。
【００３１】
図５に示す例の場合、グループ化されていないリンクとして、リンクＬ７，Ｌ８が存在する。したがって、グループ化部１３は、リンクＬ７を選択するとともに、当該リンクＬ７に直接接続しているノードＮ３，Ｎ４を選択する。そして、これらリンクＬ７、ノードＮ３，Ｎ４をグループ化するとともに、同一のグループＩＤを付与する。同じく、グループ化部１３は、リンクＬ８を選択するとともに、当該リンクＬ８に直接接続しているノードＮ１０，Ｎ１１を選択する。そして、これらリンクＬ８、ノードＮ１０，Ｎ１１をグループ化するとともに、同一のグループＩＤを付与する。
【００３２】
次に、フラグ情報付与化処理（ステップＳ３３）の一例について説明する。
図６に示すように、まず、フラグ情報付与部１４は、メッシュ内の１つのグループに着目するとともに、当該グループ内に存在するリンクの属性情報である路線種別情報を参照する。そして、高速道路や国道等の幹線道路に該当する幹線リンクがあるか否かを判定する（ステップＳ６１）。幹線リンクが存在すると判定した場合、フラグ情報付与部１４は、当該幹線リンクを含むグループに接続確定フラグ情報を付与する（ステップＳ６２）。一方、幹線リンクが存在しないと判定した場合、フラグ情報付与部１４は、当該幹線リンクが含まれないグループに孤立フラグ情報を付与する（ステップＳ６３）。
【００３３】
次に、フラグ情報付与部１４は、孤立フラグ情報が付与されたグループ内に境界ノードが含まれており、当該境界ノードにフラグ情報が設定されている場合には、当該フラグ情報をグループのフラグ情報に反映させる（ステップＳ６４）。具体的には、グループ内に含まれている境界ノードのうち、少なくともいずれか１つの境界ノードに接続確定フラグ情報が設定されている場合には、そのグループを構成する道路ネットワークは間接的に幹線リンクと接続されていることになる。したがって、こうしたグループには、フラグ情報付与部１４によって接続確定フラグ情報が付与される。一方、グループ内に含まれているすべての境界ノードにフラグ情報が設定されていないか、あるいは孤立フラグ情報が設定されている場合には、当該グループのフラグ情報は孤立フラグ情報のまま変更されない。
【００３４】
次に、フラグ情報付与部１４は、グループが、他のメッシュに接続しているか否かを判定する（ステップＳ６５）。例えば、グループに境界ノードが含まれていない場合には、当該グループは１つのメッシュ内に含まれる道路ネットワークでのみ構成されている、換言すれば単一のメッシュ内に独立して存在するグループということになる。この場合、グループを構成する道路ネットワークは幹線リンクに接続していない。また、仮に幹線リンクに接続していたとしても他の道路ネットワークからは孤立したネットワークであることは明らかである。したがって、グループが他のメッシュに接続していない場合には、フラグ情報付与部１４は、孤立フラグ情報を付与する（ステップＳ６６）。
【００３５】
次に、フラグ情報付与部１４は、メッシュ内のすべてのグループに対してフラグ情報を付与したか否かを判定する（ステップＳ６７）。すべてのグループに対してフラグ情報が付与されていないと判定した場合には、フラグ情報付与部１４は、フラグ情報が付与されていないグループを選択するとともに、ステップＳ６１に戻って、当該グループに対してフラグ情報を付与する処理を実行する。その一方で、メッシュに含まれるすべてのグループに対してフラグ情報を付与したと判定した場合には、制御部１７は、フラグ情報付与化処理を終了する。
【００３６】
本実施例の孤立道路抽出装置によれば、複数のメッシュに跨るような比較的広範囲の道路であっても高速道路や国道に接続していない孤立した道路であると判定して抽出することができる。また、境界ノードの属性情報としてフラグ情報を設定するとともに、このフラグ情報を利用してメッシュ毎の孤立状態を把握するようにしたことで、１つのメッシュを処理するだけのメモリ容量があれば、地図データ全体にわたって孤立状態にある道路を抽出する処理を実現することができる。
【符号の説明】
【００３７】
１１…ネットワークデータ記憶部
１２…データ読出部
１３…グループ化部
１４…フラグ情報付与部
１５…フラグ情報設定部
１６…孤立道路抽出部
【特許請求の範囲】
【請求項１】
複数のメッシュで区分されるとともに該メッシュ単位で管理されている、ノードおよびリンクで表わされた道路ネットワークデータおよびメッシュの境界に存在する境界ノードに設定されているフラグ情報を記憶するネットワークデータ記憶部と、
前記メッシュに含まれる道路ネットワークデータおよび境界ノードに設定されているフラグ情報を読み出すデータ読出部と、
前記道路ネットワークデータを構成するノードおよびリンクのうち、接続されているリンクおよびノードをグループ化するグループ化部と、
幹線道路に該当する幹線リンク、または幹線道路に接続していることを表わす接続確定フラグ情報が設定されている境界ノードが含まれているグループに接続確定フラグ情報を付与するとともに、前記幹線リンクが含まれないグループおよび単一のメッシュ内に独立して存在するグループに孤立の可能性を表わす孤立フラグ情報を付与するフラグ情報付与部と、
フラグ情報が付与されたグループに含まれる境界ノードに、該グループに付与されたフラグ情報を設定するとともに、該フラグ情報を前記ネットワークデータ記憶部に記憶するフラグ情報設定部と、
前記孤立フラグ情報が付与されているグループに対応する道路を孤立道路として抽出する孤立道路抽出部と
を備えることを特徴とする孤立道路抽出装置。
【請求項１】
複数のメッシュで区分されるとともに該メッシュ単位で管理されている、ノードおよびリンクで表わされた道路ネットワークデータおよびメッシュの境界に存在する境界ノードに設定されているフラグ情報を記憶するネットワークデータ記憶部と、
前記メッシュに含まれる道路ネットワークデータおよび境界ノードに設定されているフラグ情報を読み出すデータ読出部と、
前記道路ネットワークデータを構成するノードおよびリンクのうち、接続されているリンクおよびノードをグループ化するグループ化部と、
幹線道路に該当する幹線リンク、または幹線道路に接続していることを表わす接続確定フラグ情報が設定されている境界ノードが含まれているグループに接続確定フラグ情報を付与するとともに、前記幹線リンクが含まれないグループおよび単一のメッシュ内に独立して存在するグループに孤立の可能性を表わす孤立フラグ情報を付与するフラグ情報付与部と、
フラグ情報が付与されたグループに含まれる境界ノードに、該グループに付与されたフラグ情報を設定するとともに、該フラグ情報を前記ネットワークデータ記憶部に記憶するフラグ情報設定部と、
前記孤立フラグ情報が付与されているグループに対応する道路を孤立道路として抽出する孤立道路抽出部と
を備えることを特徴とする孤立道路抽出装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１１−２１５２１９（Ｐ２０１１−２１５２１９Ａ）
【公開日】平成２３年１０月２７日（２０１１．１０．２７）
【国際特許分類】
【出願番号】特願２０１０−８１０８３（Ｐ２０１０−８１０８３）
【出願日】平成２２年３月３１日（２０１０．３．３１）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
【公開日】平成２３年１０月２７日（２０１１．１０．２７）
【国際特許分類】
【出願日】平成２２年３月３１日（２０１０．３．３１）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
[ Back to top ]