(57)【要約】【課題】リンク内の小区間の位置情報を維持したまま地図データのデータ量を低減できる技術の提供。【解決手段】地図データ加工システムは、互いの長さが等しいＭ個（Ｍは自然数）の小区間を有する第１リンクと、一端に存在するノードにて前記第１リンクと接続し、かつ、互いの長さが等しいＮ個（Ｎは自然数）の小区間を有する第２リンクとを取得するリンク取得部と、前記第１リンクと前記第２リンクとを接続するノードを削除することにより前記第１リンクと前記第２リンクとが結合した結合リンクを生成するリンク結合部と、前記第１リンクのリンクデータと前記第２リンクのリンクデータとに基づいて前記結合リンクのリンクデータを生成するとともに、削除したノードの位置である基準位置を示す情報と、ＭとＮとを示す情報を、前記結合リンクのリンクデータに記録するリンクデータ生成部と、を備える。【選択図】図２
2019074548.tif 000002
【特許請求の範囲】
【請求項１】
互いの長さが等しいＭ個（Ｍは自然数）の小区間を有する第１リンクと、一端に存在するノードにて前記第１リンクと接続し、かつ、互いの長さが等しいＮ個（Ｎは自然数）の小区間を有する第２リンクとを取得するリンク取得部と、
前記第１リンクと前記第２リンクとを接続するノードを削除することにより前記第１リンクと前記第２リンクとが結合した結合リンクを生成するリンク結合部と、
前記第１リンクのリンクデータと前記第２リンクのリンクデータとに基づいて前記結合リンクのリンクデータを生成するとともに、削除したノードの位置である基準位置を示す情報と、ＭとＮとを示す情報を、前記結合リンクのリンクデータに記録するリンクデータ生成部と、
を備える地図データ加工システム。
【請求項２】
前記リンクデータ生成部は、前記第１リンクの小区間と前記第２リンクの小区間の長さが等しい場合、前記基準位置を示す情報を付加することなく、（Ｍ＋Ｎ）を示す情報を、前記結合リンクのリンクデータに記録する、
請求項１に記載の地図データ加工システム。
【請求項３】
前記第１リンクは、前記第２リンクと共通するストリート名を有するとともに、
前記第１リンクと前記第２リンクとに跨って、前記小区間を区別する番地が連番となっている、
請求項１または請求項２のいずれかに記載の地図データ加工システム。
【請求項４】
前記リンク結合部は、前記結合リンクと、一端に存在するノードにて前記結合リンクと接続し、かつ、互いの長さが等しいＨ個（Ｈは自然数）の小区間を有する第３リンクとを結合した再結合リンクを生成する、
請求項１から請求項３のいずれか一項に記載の地図データ加工システム。
【請求項５】
リンクに対応付けられたリンクデータに基づいて、単一の前記リンク内の基準位置と、前記基準位置から前記リンクの始点までの区間である第１区間に存在する小区間の数であるＭと、前記基準位置から前記リンクの終点までの区間である第２区間に存在する小区間の数であるＮと、を取得するリンクデータ取得部と、
前記第１区間をＭ等分することによって導出した小区間と、前記第２区間をＮ等分することによって導出した小区間と、を表示する小区間表示部と、
を備え、
前記第１区間に存在する小区間の長さと、前記第２区間に存在する小区間の長さとが異なる、
地図表示システム。
【請求項６】
コンピュータを、
互いの長さが等しいＭ個（Ｍは自然数）の小区間を有する第１リンクと、一端に存在するノードにて前記第１リンクと接続し、かつ、互いの長さが等しいＮ個（Ｎは自然数）の小区間を有する第２リンクとを取得するリンク取得部、
前記第１リンクと前記第２リンクとを接続するノードを削除することにより前記第１リンクと前記第２リンクとが結合した結合リンクを生成するリンク結合部、
前記第１リンクのリンクデータと前記第２リンクのリンクデータとに基づいて前記結合リンクのリンクデータを生成するとともに、削除したノードの位置である基準位置を示す情報と、ＭとＮとを示す情報を、前記結合リンクのリンクデータに記録するリンクデータ生成部、
として機能させる地図データ加工プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図データ加工システム、地図表示システムおよび地図データ加工プログラムに関する。
【背景技術】
【０００２】
ノードで区切られたリンクごとにリンクデータが用意された地図データが知られている（特許文献１、参照。）。特許文献１において、ストリート名が共通する複数のリンクに跨って連続するようにハウスナンバーが定義されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００８−１４５２３４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところで、リンクとリンクとを接続しているノードが必ずしもナビゲーション装置等において有効に利用されるとは限らない。特に、リンクの分岐がないノード（リンクを一対一で接続するノード）は、ナビゲーション装置等において有効に利用される可能性が低くなる。このようなノードによってリンクが分割されていると、地図データのデータ量が不必要に大きくなるという問題があった。その一方で、分岐がない地点のノードを削除してリンクを結合すると、当該ノードの位置の情報が失われ、当該ノードの位置を基準に区分されていたリンク内の小区間の位置の情報も失われることとなる。例えば、特許文献１において、単純にノードを削除してリンクを結合すると、結合後のリンクにおいてどのようにハウスナンバーが付されているのかが不明となってしまう。
本発明は、前記課題にかんがみてなされたもので、リンク内の小区間の位置情報を維持したまま地図データのデータ量を低減できる技術を提供することを目的とする。
【課題を解決するための手段】
【０００５】
前記の目的を達成するため、本発明の地図データ加工システムは、互いの長さが等しいＭ個（Ｍは自然数）の小区間を有する第１リンクと、一端に存在するノードにて第１リンクと接続し、かつ、互いの長さが等しいＮ個（Ｎは自然数）の小区間を有する第２リンクとを取得するリンク取得部と、第１リンクと第２リンクとを接続するノードを削除することにより第１リンクと第２リンクとが結合した結合リンクを生成するリンク結合部と、第１リンクのリンクデータと第２リンクのリンクデータとに基づいて結合リンクのリンクデータを生成するとともに、削除したノードの位置である基準位置を示す情報と、ＭとＮとを示す情報を、結合リンクのリンクデータに記録するリンクデータ生成部と、を備える。
【０００６】
前記の目的を達成するため、本発明の地図データ加工プログラムは、コンピュータを、コンピュータを、互いの長さが等しいＭ個（Ｍは自然数）の小区間を有する第１リンクと、一端に存在するノードにて第１リンクと接続し、かつ、互いの長さが等しいＮ個（Ｎは自然数）の小区間を有する第２リンクとを取得するリンク取得部、第１リンクと第２リンクとを接続するノードを削除することにより第１リンクと第２リンクとが結合した結合リンクを生成するリンク結合部、第１リンクのリンクデータと第２リンクのリンクデータとに基づいて結合リンクのリンクデータを生成するとともに、削除したノードの位置である基準位置を示す情報と、ＭとＮとを示す情報を、結合リンクのリンクデータに記録するリンクデータ生成部、として機能させる。
【０００７】
前記の目的を達成するため、本発明の地図表示システムは、リンクに対応付けられたリンクデータに基づいて、単一のリンク内の基準位置と、基準位置からリンクの始点までの区間である第１区間に存在する小区間の数であるＭと、基準位置からリンクの終点までの区間である第２区間に存在する小区間の数であるＮと、を取得するリンクデータ取得部と、第１区間をＭ等分することによって導出した小区間と、第２区間をＮ等分することによって導出した小区間と、を表示する小区間表示部と、を備え、第１区間に存在する小区間の長さと、第２区間に存在する小区間の長さとが異なる。
【０００８】
本発明の地図データ加工システム、地図表示システムおよび地図データ加工プログラムによれば、基準位置に基づいて、削除したノードの位置を結合リンク内において再現できる。さらに再現したノードの位置の両側の区間（もとの第１リンクと第２リンク）をＭ個とＮ個に均等に分割することにより、小区間の位置を再現できる。すなわち、リンクを結合しても、リンク内の小区間の位置情報を維持することができる。ノードの個数とリンクの個数とを減少させることができるため、地図データのデータ量を低減できる。
【図面の簡単な説明】
【０００９】
【図１】車両システムのブロック図である。
【図２】リンクデータの説明図である。
【図３】リンクデータの説明図である。
【図４】地図データ加工処理のフローチャートである。
【発明を実施するための形態】
【００１０】
ここでは、下記の順序に従って本発明の実施の形態について説明する。
（１）車両システムの構成：
（１−１）地図データ加工システムの構成：
（１−２）地図表示システムの構成：
（２）地図データ加工処理：
（３）他の実施形態：
【００１１】
（１）車両システムの構成：
図１は、車両システムのブロック図である。車両システムは、互いに通信可能な地図データ加工システム１０と地図表示システム１１０と車両５０によって構成されている。地図データ加工システム１０は、車両５０に配信する地図データを作成するためのサーバである。地図表示システム１１０は車両５０に搭載された車載器である。図示しないが、多数の車両５０のそれぞれに地図表示システム１１０が搭載されており、地図表示システム１１０のそれぞれが地図データ加工システム１０と通信可能となっている。
【００１２】
（１−１）地図データ加工システムの構成：
地図データ加工システム１０は、制御部２０と記録媒体３０と通信部４０とを備えている。制御部２０は、ＣＰＵとＲＡＭとＲＯＭ等を備え、記録媒体３０やＲＯＭに記憶された地図データ加工プログラム２１を実行する。通信部４０は、車両５０と無線通信をするための無線通信回路である。
【００１３】
記録媒体３０は、加工前地図データ３０ａと加工後地図データ３０ｂとを記録している。加工前地図データ３０ａと加工後地図データ３０ｂとは、いずれもノードデータとリンクデータとを含む。ノードデータは、おもに交差点についての情報を示す。具体的に、ノードデータは、ノードの座標やノードの形状を示す。道路区間は、長さ方向に連続するノードで区切った道路の単位であり、リンクの両端にはノードが存在する。なお、３個以上のリンクが接続しているノードが交差点に対応する。リンクデータは、リンクごとにリンクの属性を示す。リンクの属性とは、リンクの区間長や旅行時間や制限速度や幅員やレーン数等である。
【００１４】
図２Ａは、加工前地図データ３０ａが示すリンクの模式図である。図２Ａにおいて、太い実線がリンクを示し、白丸がノードを示す。リンクデータが示す属性には、上述したものの他に、リンクに付された通りの名称と番地が含まれる。図２Ａにおいて、通りの名称としてStreet（ストリート）名が例示されているが、Boulevard名やAvenue名であってもよい。番地とは、通りの名称と組み合わせて住所を特定する番号である。
【００１５】
図２Ａにおいて、白丸の中の数字は番地を意味する。例えば、リンクＬ１に沿って、ＸＸストリート１番地からＸＸストリート４番地の住所が存在している。リンクデータが示す属性には、各リンクＬ１〜Ｌ４に沿って存在する番地の番号と、当該番地の個数とが含まれる。各番地は単一のリンクを均等に分割した小区間であり、例えば４個の番地を有するリンクＬ１の全体の区間長である１２００ｍを４等分した３００ｍの長さの区間が１〜４番地のそれぞれに対応する小区間となる。
【００１６】
なお、ノードＮ１〜Ｎ５のうち２個のノードＮ１，Ｎ５に対して３個以上のリンクが接続しているため、当該ノードＮ１，Ｎ５は交差点を構成する。一方、他のノードＮ２〜Ｎ４に対して２個のリンクＬ１〜Ｌ４のみが接続しており、ノードＮ２〜Ｎ４は交差点を構成しない。ノードＮ２〜Ｎ４を走行する際に退出可能なリンクは一意に定まる。加工後地図データ３０ｂは、加工前地図データ３０ａのノードデータとリンクデータに加工を行ったものであるが、当該加工の内容については後述する。
【００１７】
地図データ加工プログラム２１は、リンク取得モジュール２１ａとリンク結合モジュール２１ｂとリンクデータ生成モジュール２１ｃとを含む。リンク取得モジュール２１ａとリンク結合モジュール２１ｂとリンクデータ生成モジュール２１ｃとは、それぞれコンピュータとしての制御部２０をリンク取得部とリンク結合部とリンクデータ生成部として機能させるプログラムモジュールである。
【００１８】
リンク取得モジュール２１ａの機能により制御部２０は、互いの長さが等しいＭ個（Ｍは自然数）の小区間を有する第１リンクと、一端に存在するノードにて第１リンクと接続し、かつ、互いの長さが等しいＮ個（Ｎは自然数）の小区間を有する第２リンクとを取得する。リンク取得モジュール２１ａの機能により制御部２０は、加工前地図データ３０ａのリンクデータにおいて、結合可能条件を満足する属性を有する第１リンクと第２リンクとを取得する。本実施形態において、結合可能条件を満足するためには、第１リンクと第２リンクとが、他のリンクが接続していないノードにて接続していることが必要となる。さらに、結合可能条件を満足するには、第１リンクが第２リンクと共通するストリート名を有するとともに、第１リンクと第２リンクとに跨って、小区間を区別する番地が連番となっていていることが必要となる。
【００１９】
図２ＡのリンクＬ１とリンクＬ２は、他のリンクが接続していないノードＮ２にて接続し、共通するストリート名"ＸＸストリート"を有し、かつ、番地が１〜４番地，５〜７番地と連番になっている。リンクＬ１は互いの長さが等しいＭ個（Ｍ＝４）の小区間を有し、リンクＬ２は互いの長さが等しいＮ個（Ｎ＝３）の小区間を有する。そのため、リンク取得モジュール２１ａの機能により制御部２０は、図２ＡのリンクＬ１とリンクＬ２を、それぞれ第１リンクと第２リンクとして取得する。
【００２０】
リンク結合モジュール２１ｂの機能により制御部２０は、第１リンクと第２リンクとを接続するノードを削除することにより第１リンクと第２リンクとが結合した結合リンクを生成する。リンク結合モジュール２１ｂの機能により制御部２０は、結合可能条件を満足する第１リンクと第２リンクとが接続しているノードについての情報をノードデータから削除する。なお、制御部２０は、結合可能条件を満足する第１リンクと第２リンクとを接続するノードが削除された加工後のノードデータを加工後地図データ３０ｂに格納する。
【００２１】
図２Ｂは、加工後地図データ３０ｂが示すリンクの模式図である。同図に示すように、結合可能条件を満足する第１リンクと第２リンクとしてのリンクＬ１，Ｌ２を接続するノードＮ２が削除されており、リンクＬ１，Ｌ２が結合した結合リンクとしてのリンクＬ１２が生成されている。リンクＬ１２は、リンクＬ１，Ｌ２が接続するノードＮ１〜Ｎ３のうち削除されていないノードＮ１，Ｎ３が両端に存在するリンクである。
【００２２】
リンクデータ生成モジュール２１ｃの機能により制御部２０は、第１リンクのリンクデータと第２リンクのリンクデータとに基づいて結合リンクのリンクデータを生成するとともに、削除したノードの位置である基準位置を示す情報と、ＭとＮとを示す情報を、結合リンクのリンクデータに記録する。リンクデータ生成モジュール２１ｃの機能により制御部２０は、第１リンクと第２リンクの属性の各項目を合計したり平均したり一方を破棄することにより結合後の属性を取得する。例えば、制御部２０は、第１リンクと第２リンクの区間長や旅行時間等の合計値を結合リンクの区間長や旅行時間等として取得する。また、制御部２０は、第１リンクと第２リンクの幅員や制限速度やレーン数等の平均値を結合リンクの幅員や制限速度やレーン数等として取得する。なお、ストリート名は第１リンクと第２リンクとで共通するため、制御部２０は、当該共通するストリート名を結合リンクのストリート名としてそのまま取得する。
【００２３】
さらに、リンクデータ生成モジュール２１ｃの機能により制御部２０は、もともとの第１リンクと第２区間とが存在していた区間と、これらのそれぞれにおいて存在していた番地の個数であるＭとＮとを示す情報を、結合リンクの属性として記録する情報として取得する。図２Ｂにおいてグレーで示すように、リンクＬ１２の属性として、ノードＮ１を始点として０〜１２００ｍの区間に１〜４番地（Ｍ＝４）が存在し、ノードＮ１を始点として１２００〜２１００ｍの区間に５〜７番地（Ｎ＝３）が存在することが示されている。ノードＮ１を始点として１２００ｍだけ進んだ位置は、削除したノードＮ２の位置であり、基準位置Ｋ２（黒四角）を意味する。従って、結合リンクのリンクデータは、基準位置Ｋ２を示すこととなる。
【００２４】
リンクデータ生成モジュール２１ｃの機能により制御部２０は、上述したように取得した結合リンクの属性を示すリンクデータを加工後地図データ３０ｂに格納する。このとき、制御部２０は、もとの第１リンクと第２リンクのリンクデータを削除する。以上により、リンクデータとノードデータとが加工された加工後地図データ３０ｂが生成できたこととなる。
【００２５】
リンクデータ生成モジュール２１ｃの機能により制御部２０は、第１リンクの小区間と第２リンクの小区間の長さが等しい場合、削除したノードの位置である基準位置を示す情報を付加することなく、（Ｍ＋Ｎ）を示す情報を、結合リンクのリンクデータに記録する。図２Ａに示すように、第１リンクとしてのリンクＬ１の各小区間の長さは１２００／４＝３００ｍであり、同じく第２リンクとしてのリンクＬ２の各小区間の長さも９００／３＝３００ｍである。このような場合、図２ＢのリンクＬ１２の属性にて矢印で示すように、リンクデータ生成モジュール２１ｃの機能により制御部２０は、もとのリンクＬ１，Ｌ２の区間長の長さを示す情報を記録することなく、単に番地の個数の合計値（Ｍ＋Ｎ＝７）を、結合リンクとしてのリンクＬ１２のリンクデータに記録する。図２Ｂにおいてグレーで示す情報は、一旦リンクデータに記録された後、削除されてもよいし、最初から記録されないようにしてもよい。
【００２６】
リンク結合モジュール２１ｂの機能により制御部２０は、結合リンクと、一端に存在するノードにて結合リンクと接続し、かつ、互いの長さが等しいＨ個（Ｈは自然数）の小区間を有する第３リンクとを結合した再結合リンクを生成する。図２Ｂに示すように、リンクＬ１２は結合リンクであるが、さらに当該リンクＬ１２はリンクＬ３（Ｈ＝２）と結合される。なお、結合リンクと第３リンクとを結合するための結合可能条件は、第１リンクと第２リンクとを結合するための結合可能条件と同じである。図２Ｃは、リンクＬ１２とリンクＬ３とが結合したリンクＬ１２３が再結合リンクとして生成された状態を示す。図２Ｃにおいて、リンクＬ１２とリンクＬ３とを接続していたノードＮ３が削除されている。
【００２７】
図２Ｃに示すように、再結合リンクとしてのリンクＬ１２３の属性は、図２Ｂに示す結合リンクとしてのリンクＬ１２の属性と、第３リンクとしてのリンクＬ３の属性とに基づいて生成されている。例えば、リンクＬ１２３の区間長は、リンクＬ１２の区間長とリンクＬ３の区間長の合計値となっている。
【００２８】
なお、リンクＬ１２における小区間の長さは３００ｍであるのに対して、リンクＬ３における小区間の長さは３００／２＝１５０ｍであり、両者は等しくない。そのため、リンクＬ１２３の属性として、ノードＮ１を始点として０〜２１００ｍの区間に１〜７番地（Ｍ＋Ｎ＝７）が存在し、ノードＮ１を始点として２１００〜２４００ｍの区間に８〜９番地（Ｈ＝２）が存在することが示されている。つまり、再結合リンクのリンクデータに、削除したノードＮ３の位置である基準位置を示す情報が含まれている。
【００２９】
図２Ｂ，図２Ｃの例では、基準位置を含まない結合リンクを第３リンクと結合する状態を説明した。しかし、基準位置を含む結合リンクを第３リンクと結合する場合もあり得る。図３Ａは、第１リンクと第２リンクとを結合した結合リンクとしてのリンクＬ１２において小区間の長さがすべて均等ではなく、第１リンクと第２リンクの間に存在していたノードＮ２の位置である基準位置Ｋ２を示す情報がリンクデータに含まれている例を示している。
【００３０】
図３Ｂは、図３ＡのリンクＬ１２に第３リンクとしてのリンクＬ３を結合した状態を示す。同図に示すように、図３ＡのリンクＬ１２に第３リンクとしてのリンクＬ３を結合した再結合リンクとしてのリンクＬ１２３が生成されるとともに、当該リンクＬ１２３の属性として、ノードＮ１を始点として０〜９００ｍの区間に１〜３番地（Ｍ＝３）が存在し、ノードＮ１を始点として９００〜１５００ｍの区間に４〜６番地（Ｎ＝３）が存在し、ノードＮ１を始点として１５００〜２４００ｍの区間に７〜９番地（Ｈ＝３）が存在することが示されている。ノードＮ１から９００ｍだけ進んだ位置が基準位置Ｋ２であり、ノードＮ１から１５００ｍだけ進んだ位置が基準位置Ｋ３である。制御部２０は、もともと結合リンクに基準位置Ｋ２が含まれている場合、当該基準位置Ｋ２を示す情報を維持して、第３リンクを結合する。
【００３１】
なお、結合の繰り返し回数は特に限定されず、制御部２０は、結合可能条件が満足される限り、隣接するリンクを順次結合する。なお、図２Ａ〜図２Ｃおよび図３Ａ，図３Ｂの例において、リンクＬ４のストリート名は、リンク１〜Ｌ３と共通しない。従って、リンクＬ４は結合されず、リンクＬ１２３まで結合したところでリンクを結合する処理は終了することとなる。
【００３２】
（１−２）地図表示システムの構成：
地図表示システム１１０は、車両５０に搭載される。この車両５０は、測位部５１とユーザＩ／Ｆ部５２と通信部５３とを備える。測位部５１は、車両５０の現在地を測位するためのＧＰＳ受信部や車速センサやジャイロセンサ等を含む。ユーザＩ／Ｆ部５２は、地図を表示するディスプレイを含む。通信部５３は、地図データ加工システム１０と無線通信を行うための通信回路である。
【００３３】
地図表示システム１１０は、制御部１２０と記録媒体１３０とを備えている。制御部１２０は、ＣＰＵとＲＡＭとＲＯＭ等を備え、記録媒体１３０やＲＯＭに記憶された地図表示プログラム１２１を実行する。記録媒体１３０は、加工後地図データ１３０ｂを記録している。加工後地図データ１３０ｂは、地図データ加工システム１０の加工後地図データ３０ｂを当該地図データ加工システム１０から受信したものである。
【００３４】
地図表示プログラム１２１は、リンクデータ取得モジュール１２１ａと小区間表示モジュール１２１ｂとを含む。リンクデータ取得モジュール１２１ａと小区間表示モジュール１２１ｂとは、それぞれコンピュータとしての制御部１２０をリンクデータ取得部と小区間表示部として機能させるプログラムモジュールである。
【００３５】
リンクデータ取得モジュール１２１ａの機能により制御部２０は、単一のリンク内の基準位置と、基準位置からリンクの始点までの区間である第１区間に存在する小区間の数であるＭと、基準位置からリンクの終点までの区間である第２区間に存在する小区間の数であるＮと、を取得する。すなわち、リンクデータ取得モジュール１２１ａの機能により制御部２０は、加工後地図データ１３０ｂのリンクデータを取得する。例えば、制御部１２０は、図２ＣのリンクＬ１２３のリンクデータを取得した場合、基準位置Ｋ３（ノードＮ１から２１００ｍ）と、基準位置Ｋ３からリンクの始点のノードＮ１までの第１区間に存在する小区間の数（Ｍ＝７個）と、基準位置Ｋ３からリンクの終点のノードＮ４までの第２区間に存在する小区間の数（Ｎ＝２個）とを取得する。なお、基準位置Ｋ３は削除したノードＮ３の位置である。
【００３６】
小区間表示モジュール１２１ｂの機能により制御部２０は、第１区間をＭ等分することによって導出した小区間と、第２区間をＮ等分することによって導出した小区間と、を表示する。例えば、制御部２０は、リンクＬ１２３を示す線図を形状補間点等に基づいて描画し、"ＸＸストリート"の名称を当該線図に沿って表示する。さらに、制御部２０は、当該線図のうち第１区間に対応する部分を均等に７分割し、当該分割した部分のそれぞれの中点に番地を示す１〜７の数字を配置するとともに、第２区間に対応する部分を均等に２分割し、当該分割した部分のそれぞれの中点に番地を示す８，９の数字を配置する。なお、図３ＢのリンクＬ１２３のように複数の基準位置Ｋ２，Ｋ３が存在する場合、制御部２０は、リンクＬ１２３をノードＮ１から基準位置Ｋ２までの区間と基準位置Ｋ２から基準位置Ｋ３までの区間と基準位置Ｋ３からノードＮ５までの区間に分割し、さらに分割した３個の区間のそれぞれを小区間の個数（Ｍ，Ｎ，Ｈ）で均等に分割することにより、小区間の位置を再現する。
【００３７】
以上説明した本実施形態によれば、基準位置に基づいて、削除したノードの位置を結合リンク内にて再現できる。さらに再現したノードの位置の両側の区間（もとの第１リンクと第２リンク）をＭ個とＮ個に均等に分割することにより、小区間の位置を再現できる。すなわち、リンクを結合しても、リンク内の小区間の位置情報を維持することができる。ノードの個数とリンクの個数とを減少させることができるため、加工後地図データ３０ｂのデータ量を低減できる。
【００３８】
ここで、図２Ａ，図２Ｂに示すように、第１リンクとしてのリンクＬ１の小区間と第２リンクとしてのリンクＬ２の小区間の長さが等しい場合には、結合リンクとしてのリンクＬ１２を（Ｍ＋Ｎ）個に均等に分割することにより、すべての小区間の位置を再現できる。削除したノードの位置である基準位置を示す情報（図２Ｂにてグレーで示す部分）を結合リンクのリンクデータに付加しなくても済むため、加工後地図データ３０ｂのデータ量を低減できる。
【００３９】
また、第１リンクは、第２リンクと共通するストリート名を有するとともに、第１リンクと第２リンクとに跨って、小区間を区別する番地が連番となっていている。これにより、ストリート名と番地との組み合わせによって各小区間のアドレスを再現できる。また、連番であれば、各小区間について番地を個別に記録しなくてもよいため、加工後地図データ３０ｂのデータ量を低減できる。結合リンクにさらに第３リンクを結合することにより、加工後地図データ３０ｂのデータ量を低減できる。
【００４０】
（２）地図データ加工処理：
図４は、地図データ加工処理のフローチャートである。地図データ加工処理は、例えば加工前地図データ３０ａが新たに作成されたり、バージョンアップされたりした際に、地図データ加工システム１０が実行する処理である。まず、リンク取得モジュール２１ａの機能により制御部２０は、非分岐リンク列を抽出する（ステップＳ１００）。非分岐リンク列とは、交差点（分岐地点）を含まない一連のリンクによって構成されるリンク列であり、リンクが２個のみ接続しているノードのみによって連続的に連結されたリンク列である。図２Ａの例において、リンクＬ１〜Ｌ４が非分岐リンク列として抽出される。なお、非分岐リンク列の両端のノードＮ１，Ｎ５は３個以上のリンクが接続する交差点となる。制御部２０は、加工前地図データ３０ａに規定されているすべてのリンクから、非分岐リンク列を抽出する。
【００４１】
次に、リンク取得モジュール２１ａの機能により制御部２０は、処理対象の非分岐リンク列を選択する（ステップＳ１１０）。すなわち、ステップＳ１００にて抽出した非分岐リンク列のなかから１個を処理対象として選択する。次に、リンク取得モジュール２１ａの機能により制御部２０は、始点リンクの属性を取得する（ステップＳ１２０）。すなわち、制御部２０は、始点リンクの属性を加工前地図データ３０ａのリンクデータから取得する。ここで、始点リンクとは、非分岐リンク列の一方の端である始点端に近い順に選択される非分岐リンク列のリンクであり、結合リンク（再結合リンク）も始点リンクとなり得る。図２Ａ〜図２Ｃ，図３Ａ，図３Ｂにおいて左端が始点端であることとする。
【００４２】
次に、リンク取得モジュール２１ａの機能により制御部２０は、隣接リンクがあるか否かを判定する（ステップＳ１３０）。隣接リンクとは、始点リンクの次に始点端に近い非分岐リンク列のリンクである。図２Ａにおいて、非分岐リンク列の左端のリンクＬ１が始点リンクとして選択され、当該リンクＬ１の次に左端に近いリンクＬ２が隣接リンクとなる。
【００４３】
隣接リンクがあると判定した場合（ステップＳ１３０：Ｙ）、リンク取得モジュール２１ａの機能により制御部２０は、隣接リンクの属性を取得する（ステップＳ１４０）。すなわち、制御部２０は、隣接リンクの属性を加工前地図データ３０ａのリンクデータから取得する。
【００４４】
次に、リンク取得モジュール２１ａの機能により制御部２０は、始点リンクと隣接リンクとが結合可能であるか否かを判定する（ステップＳ１５０）。すなわち、制御部２０は、始点リンクと隣接リンクの属性が結合可能条件を満足するか否かを判定する。結合可能条件を満足するには、始点リンクが隣接リンクと共通するストリート名を有するとともに、始点リンクが隣接リンクとに跨って、小区間を区別する番地が連番となっていていることが必要となる。
【００４５】
ここで、始点リンクと隣接リンクとが結合可能あるとは、始点リンクと隣接リンクとが結合する対象のリンクとして取得されたこと、すなわち本発明の第１リンクと第２リンク（または結合リンクと第３リンク）として取得されたことを意味する。始点リンクと隣接リンクとが結合可能であると判定した場合（ステップＳ１５０：Ｙ）、リンク結合モジュール２１ｂとリンクデータ生成モジュール２１ｃの機能により制御部２０は、始点リンクと隣接リンクとを結合する（ステップＳ１６０）。
【００４６】
すなわち、リンク結合モジュール２１ｂの機能により制御部２０は、始点リンクと隣接リンクとを接続するノードを削除することにより、始点リンクと隣接リンクとが結合した結合リンク（または再結合リンク）を生成する。さらに、リンクデータ生成モジュール２１ｃの機能により制御部２０は、始点リンクのリンクデータと隣接リンクのリンクデータとに基づいて結合リンク（または再結合リンク）のリンクデータを生成するとともに、削除したノードの位置である基準位置を示す情報と、ＭとＮとを示す情報を、結合リンク（または再結合リンク）のリンクデータに記録する。第１リンクと第２リンクがリンクＬ１，Ｌ２である場合、図２Ｂにてグレーで示す情報（基準位置を示す情報）がリンクデータに記録する情報として取得されることとなる。
【００４７】
次に、リンクデータ生成モジュール２１ｃの機能により制御部２０は、小区間の区間長が均一であるか否かを判定する（ステップＳ１７０）。すなわち、制御部２０は、結合した結合リンク（または再結合リンク）が有する小区間の区間長がすべて等しいか否かを判定する。小区間の区間長が均一であると判定した場合（ステップＳ１７０：Ｙ）、基準位置を示す情報を破棄する（ステップＳ１８０）。
【００４８】
すなわち、ステップＳ１６０にて生成した基準位置を示す情報を、リンクデータとして記録する情報から除外する。このとき、制御部２０は、結合したリンクに含まれる小区間の合計の個数（Ｍ＋Ｎ）をリンクデータとして記録する情報として取得する。結果として、図２ＢのリンクＬ１２の属性にて矢印で示すように、単に番地の個数の合計値（Ｍ＋Ｎ＝７）を、結合リンクとしてのリンクＬ１２のリンクデータに記録する情報として取得することとなる。一方、小区間の区間長が均一であると判定しなかった場合（ステップＳ１７０：Ｎ）、ステップＳ１８０をスキップする。
【００４９】
ステップＳ１８０を実行またはスキップすると、制御部２０は、ステップＳ１３０に戻る。すなわち、制御部２０は、結合したリンクを新たな始点リンクとするとともに、当該新たな始点リンクの次に始点端に近い隣接リンクが、処理対象の非分岐リンク列に存在するか否かを判定する。ここで、前回の隣接リンクとして扱ったリンクが、非分岐リンク列のリンクのうち始点端から最も遠いリンクであった場合には、ステップＳ１３０にて隣接リンクがあると判定されないこととなる。隣接リンクがあると判定された場合（ステップＳ１３０：Ｙ）、ステップＳ１４０以降において、当該隣接リンクをさらに結合するための処理が実行されることとなる。
【００５０】
一方、隣接リンクがあると判定されなかった場合（ステップＳ１３０：Ｎ）、リンクデータ生成モジュール２１ｃの機能により制御部２０は、始点リンクを確定する（ステップＳ１９０）。すなわち、制御部２０は、ステップＳ１６０やステップＳ１８０にて始点リンクの情報として取得されていた情報を含むリンクデータを、加工後地図データ３０ｂのリンクデータとして確定的に記録する。ステップＳ１９０は、非分岐リンク列のリンクのうち始点端から最も遠いリンクの結合が完了した場合に実行される処理である。
【００５１】
ステップＳ１９０が完了すると、制御部２０は、未処理の非分岐リンク列があるか否かを判定する（ステップＳ２００）。未処理の非分岐リンク列があると判定した場合（ステップＳ２００：Ｙ）、制御部２０は、ステップＳ１１０に戻る。すなわち、次の非分岐リンク列を処理対象としてステップＳ１２０以降の処理を実行する。一方、未処理の非分岐リンク列があると判定しなかった場合（ステップＳ２００：Ｎ）、制御部２０は、地図データ加工処理を終了する。すなわち、制御部２０は、加工後地図データ３０ｂの作成を完了させる。これにより、加工後地図データ３０ｂを地図表示システム１１０に配信することが可能となる。
【００５２】
ところで、始点リンクと隣接リンクとが結合可能であると判定しなかった場合にも（ステップＳ１５０：Ｎ）、リンクデータ生成モジュール２１ｃの機能により制御部２０は、始点リンクを確定する（ステップＳ２１０）。すなわち、制御部２０は、ステップＳ１６０やステップＳ１８０にて始点リンクの情報として取得されていた情報を含むリンクデータを、加工後地図データ３０ｂのリンクデータとして確定的に記録する。なお、現在の始点リンクについてステップＳ１６０やステップＳ１８０が一度も実行されていなかった場合、すなわち始点リンクが隣接リンクと一度も結合されなかった場合、始点リンクのもともとの属性をそのまま確定する。ステップＳ２１０は、結合可能なリンク列のうち最も始点端から遠いリンク（例えば図２ＡのリンクＬ３）の結合が完了した場合に実行される処理である。
【００５３】
ステップＳ２１０にて始点リンクを確定すると、制御部２０は、次の始点リンクがあるか否かを判定する（ステップＳ２２０）。すなわち、制御部２０は、非分岐リンク列のリンクのうち、確定したリンクの次に始点端から近いリンクを始点リンクとしてステップＳ１２０以降の処理を実行する。
【００５４】
（３）他の実施形態：
なお、制御部２０は、第１リンクの小区間と第２リンクの小区間の長さが等しい場合においても、削除したノードの位置である基準位置を示す情報と、ＭとＮとを示す情報を、結合リンクのリンクデータに記録してもよい。すなわち、図４のステップＳ１７０〜Ｓ１８０が省略されてもよい。このようにしても、加工後地図データ３０ｂのデータ量の低減を実現できるとともに、地図表示システム１１０における小区間の表示も可能である。さらに、制御部２０は、必ずしも再結合リンクを生成しなくてもよく、結合するリンクの数を２個までに限定してもよい。このようにしても、加工前地図データ３０ａよりも加工後地図データ３０ｂのデータ量の低減することができる。加工後地図データ３０ｂの用途は、小区間の位置を利用する用途であればよく、地図の表示に限られない。例えば、加工後地図データ３０ｂは、ユーザ等によって指定された座標がどの住所（番地）に属するかを検索するために使用されてもよい。
【００５５】
地図データ加工システムは、地図データ加工する手段を備えていればよく、加工後の地図データを地図表示システムやナビゲーションシステム等の他の装置に配信する手段を備えてもよい。むろん、地図データ加工システムは、地図表示システムやナビゲーションシステム等の他の装置が読み取り可能な記録媒体に加工後の地図データを記録する手段を備えてもよい。さらに、地図データ加工システムは地図を表示する手段を備えてもよい。リンク取得部は、地図データのリンクデータが示すリンクの属性に基づいて、第１リンクと第２リンクとを取得してもよい。
【００５６】
リンク取得部は、予め決められた結合可能条件を満足する属性を有する第１リンクと第２リンクとを取得してもよく、結合可能条件は種々考えられる。結合可能条件は、予め決められた属性が一致または類似することであってもよい。予め決められた属性とは、例えば道路種別であってもよいし、幅員であってもよいし、レーン数であってもよいし、制限速度であってもよい。さらに、結合可能条件は、第１リンクと第２リンクとの間のノードに他のリンクが接続していないことであってもよい。第１リンクと第２リンクとの間のノードに他のリンクが接続していないことには、第１リンクと第２リンク以外に実質的に通行不能な他のリンクのみが当該ノードに接続していることであってもよい。
【００５７】
リンク結合部は、第１リンクと第２リンクとを接続するノードを削除することにより第１リンクと第２リンクとが結合した結合リンクを生成すればよく、もとの第２リンクを削除し、第１リンクの属性を示すリンクデータを結合リンクの内容に書き換えてもよい。さらに、リンク結合部は、リンク結合部は、第１リンクと第２リンクの双方を削除し、これらの代わりに結合リンクを新たに生成してもよい。
【００５８】
削除したノードの位置である基準位置を示す情報とは、必ずしも第１リンクや第２リンクの長さを示す情報でなくてもよく、削除されたノードの座標を示す情報であってもよい。ＭとＮとを示す情報とは、ＭとＮの数値を示す情報であり、ＭとＮを導出可能な数値を示す情報であればよい。
【００５９】
ここで、リンクデータ生成部は、第１リンクの小区間と第２リンクの小区間の長さが等しい場合、削除したノードの位置である基準位置を示す情報を付加することなく、（Ｍ＋Ｎ）を示す情報を、結合リンクのリンクデータに記録してもよい。ここで、第１リンクの小区間と第２リンクの小区間の長さが等しい場合には、結合リンク全体を（Ｍ＋Ｎ）個に均等に分割することにより、すべての小区間の位置を再現できる。削除したノードの位置である基準位置を示す情報を結合リンクのリンクデータに付加しなくても済むため、地図データのデータ量を低減できる。
【００６０】
さらに、第１リンクは、第２リンクと共通するストリート名を有するとともに、第１リンクと第２リンクとに跨って、小区間を区別する番地が連番となっていてもよい。さらに、予め決められた属性とは、リンクの名称であってもよい。すなわち、第１リンクと第２リンクとを結合するための結合可能条件は、共通するストリート名を有し、かつ、第１リンクと第２リンクとに跨って小区間の名称が連続した番号であることであってもよい。これにより、ストリート名と番地との組み合わせによって各小区間のアドレスを再現できる。また、連番であれば、各小区間について番地を個別に記録しなくてもよいため、地図データのデータ量を低減できる。
【００６１】
さらに、リンク結合部は、結合リンクと、一端に存在するノードにて結合リンクと接続し、かつ、互いの長さが等しいＨ個（Ｈは自然数）の小区間を有する第３リンクとを結合した再結合リンクを生成してもよい。このように、結合リンクにさらに第３リンクを結合することにより、地図データのデータ量を低減できる。
【００６２】
さらに、本発明のように、小区間を有するリンク同士を結合する手法は、プログラムや方法としても適用可能である。また、以上のようなシステム、プログラム、方法は、単独の装置として実現される場合もあれば、車両に備えられる各部と共有の部品を利用して実現される場合もあり、各種の態様を含むものである。例えば、以上のような装置を備えたナビゲーションシステム、地図データ加工システムや方法、プログラムを提供することが可能である。また、一部がソフトウェアであり一部がハードウェアであったりするなど、適宜、変更可能である。さらに、装置を制御するプログラムの記録媒体としても発明は成立する。むろん、そのソフトウェアの記録媒体は、磁気記録媒体であってもよいし光磁気記録媒体であってもよいし、今後開発されるいかなる記録媒体においても全く同様に考えることができる。
【符号の説明】
【００６３】
１０…地図データ加工システム、２０…制御部、２１…地図データ加工プログラム、２１ａ…リンク取得モジュール、２１ｂ…リンク結合モジュール、２１ｃ…リンクデータ生成モジュール、３０…記録媒体、３０ａ…加工前地図データ、３０ｂ…加工後地図データ、４０…通信部、５０…車両、５１…測位部、５２…ユーザＩ／Ｆ部、５３…通信部、１１０…地図表示システム、１２０…制御部、１２１…地図表示プログラム、１２１ａ…リンクデータ取得モジュール、１２１ｂ…小区間表示モジュール、１３０…記録媒体、１３０ｂ…加工後地図データ、Ｋ２，Ｋ３…基準位置、Ｌ１〜Ｌ４…リンク、Ｌ１２…結合リンク、Ｌ１２３…再結合リンク、Ｎ１〜Ｎ５…ノード
【図１】
2019074548.tif 000003
【図２】
2019074548.tif 000004
【図３】
2019074548.tif 000005
【図４】
2019074548.tif 000006