(57)【要約】【課題】更新データファイルによる更新後の前記地図データの前記道路ネットワークの中で、一部の道路が他の道路から孤立することを防止し、当該一部の道路を含む経路の探索が可能な状態を保証できる地図データ供給装置等を提供する。【解決手段】対象地図データの一又は二以上の更新対象区画を更新用地図データＭａに基づいて更新することにより、前記対象地図データの道路ネットワークの中で、一部の道路が他の道路から孤立した状態となる孤立状態の有無を検出する孤立検出手段８と、孤立状態が有ることが検出された場合に、当該孤立した一部の道路に接続する道路を有する前記更新対象区画以外の更新用地図データＭａの区画を、更新必要区画として抽出する抽出手段９と、更新用地図データＭａに基づいて前記更新対象区画及び前記更新必要区画についての更新データファイルｆａを生成する更新データファイル生成手段１０と、を備える。【選択図】図１
2008249798.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも道路ネットワークの情報を含み、複数の区画に分割された対象地図データの各区画についての更新データファイルを供給する地図更新データ供給装置であって、
前記対象地図データと同じく複数の区画に分割された更新用地図データが格納された更新用地図データベースと、
前記対象地図データの一又は二以上の更新対象区画を前記更新用地図データに基づいて更新することにより、前記対象地図データの前記道路ネットワークの中で、一部の道路が他の道路から孤立した状態となる孤立状態の有無を検出する孤立検出手段と、
前記孤立状態が有ることが検出された場合に、当該孤立した一部の道路に接続する道路を有する前記更新対象区画以外の前記更新用地図データの区画を、更新必要区画として抽出する抽出手段と、
前記更新用地図データに基づいて、前記更新対象区画及び前記更新必要区画についての更新データファイルを生成する更新データファイル生成手段と、
を備える地図更新データ供給装置。
【請求項２】
前記孤立検出手段は、前記更新対象区画について、前記対象地図データに対する前記更新用地図データの更新内容に道路の削除があった場合に、当該削除された道路に接続していた道路に関して前記孤立状態の有無の検出を行う請求項１に記載の地図更新データ供給装置。
【請求項３】
前記孤立検出手段による前記孤立状態の検出は、前記対象地図データの前記更新対象区画を前記更新用地図データに基づいて更新した後に相当する状態で、前記削除された道路の一端と他端とを結ぶ経路の探索を行い、当該経路が存在しない場合に前記孤立状態が有ることを検出する請求項２に記載の地図更新データ供給装置。
【請求項４】
前記抽出手段は、前記対象地図データに対する前記更新用地図データの更新内容に道路の追加があった場合に、当該追加された道路を含む区画の中から前記更新必要区画を抽出する請求項１から３のいずれか一項に記載の地図更新データ供給装置。
【請求項５】
前記抽出手段による前記更新必要区画の抽出は、前記対象地図データの前記更新対象区画と前記追加された道路を含む少なくとも一つの区画とを前記更新用地図データに基づいて更新した後に相当する状態で、前記削除された道路の一端と他端とを結ぶ経路の探索を行い、前記追加された道路を通る前記経路が存在する場合には、前記経路を構成する前記追加された道路を含む区画を更新必要区画として抽出する請求項４に記載の地図更新データ供給装置。
【請求項６】
請求項１から５のいずれか一項に記載の地図更新データ供給装置と、ナビゲーション装置とを有して構成され、
前記ナビゲーション装置は、前記対象地図データとしてのナビゲーション用地図データが格納されたナビゲーション用地図データベースと、前記更新対象区画についての更新要求データファイルを生成する更新要求生成手段と、前記地図更新データ供給装置から供給された前記更新データファイルを取得する更新データファイル取得手段と、前記更新データファイルに基づいて、前記ナビゲーション用地図データの更新を行う地図データ更新手段と、を備える地図データ更新システム。
【請求項７】
少なくとも道路ネットワークの情報を含み、複数の区画に分割された対象地図データの各区画についての更新データファイルを供給する地図更新データ供給方法であって、
前記対象地図データと同じく複数の区画に分割された更新用地図データを用い、
前記対象地図データの一又は二以上の更新対象区画を前記更新用地図データに基づいて更新することにより、前記対象地図データの前記道路ネットワークの中で、一部の道路が他の道路から孤立した状態となる孤立状態の有無を検出する孤立検出ステップと、
前記孤立状態が有ることが検出された場合に、当該孤立した一部の道路に接続する道路を有する前記更新対象区画以外の前記更新用地図データの区画を、更新必要区画として抽出する抽出ステップと、
前記更新用地図データに基づいて、前記更新対象区画及び前記更新必要区画についての更新データファイルを生成する更新データファイル生成ステップと、
を実行する地図更新データ供給方法。
【請求項８】
前記孤立検出ステップとして、前記更新対象区画について、前記対象地図データに対する前記更新用地図データの更新内容に道路の削除があった場合に、前記対象地図データの前記更新対象区画を前記更新用地図データに基づいて更新した後に相当する状態で、前記削除された道路の一端と他端とを結ぶ経路の探索を行い、当該経路が存在しない場合に前記孤立状態が有ることを検出する請求項７に記載の地図更新データ供給方法。
【請求項９】
前記抽出ステップとして、前記対象地図データに対する前記更新用地図データの更新内容に道路の追加があった場合に、前記対象地図データの前記更新対象区画と前記追加された道路を含む少なくとも一つの区画とを前記更新用地図データに基づいて更新した後に相当する状態で、前記削除された道路の一端と他端とを結ぶ経路の探索を行い、前記追加された道路を通る前記経路が存在する場合には、前記経路を構成する前記追加された道路を含む区画を更新必要区画として抽出する請求項７又は８に記載の地図更新データ供給方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、少なくとも道路ネットワークの情報を含み、複数の区画に分割された対象地図データの各区画についての更新データファイルを供給する地図更新データ供給装置、この地図更新データ供給装置を用いた地図データ更新システム、及び地図更新データ供給方法に関する。
【背景技術】
【０００２】
これまでにも、ナビゲーション装置に使用される道路地図等の地図データの内容を部分的に更新する技術が知られている。例えば、下記の特許文献１に記載の装置では、新たに造られた道路について、当該新設道路が既存の幹線道路と繋がる部分までを１つのデータ群として保持するために、当該新設道路を構成する一連のリンク番号を格納したデータ群テーブルを備えている。そして、ナビゲーション装置から、複数の区画に分割された地図データの一部の区画の更新要求があった場合であって、前記データ群テーブルに格納された新設道路が当該更新要求のあった区画以外にも延びている場合には、前記データ群テーブルを参照して当該新設道路の全体の更新情報をナビゲーション装置に提供する構成となっている。
【０００３】
これにより、ナビゲーション装置から指定された地図データの一部の区画について更新情報を提供した場合であっても、隣接する区画との間で前記新設道路が途切れることを防止し、前記新設道路が既存の幹線道路に接続することを保証できる。したがって、一部の区画についての更新後にも、当該新設道路を通る経路の探索が可能となっている。
【０００４】
【特許文献１】特開２００４−１７８２４８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、一部の区画の更新により生じる地図データの不具合は上記のような新設道路に関するものに限られず、例えば、新設道路以外の既存の道路が、他の道路から孤立した状態となる場合がある。具体的には、一例として、地図更新データ供給装置側の地図データについて、ある道路（「道路Ａ」とする）に唯一接続する道路（「道路Ｂ」とする）が削除され、当該削除された道路Ｂを含む区画とは異なる区画に道路Ａに接続する道路（「道路Ｃ」とする）が追加される更新が行われた場合について説明する。このような場合に、ナビゲーション装置側の地図データの一部の区画の更新を行う際、削除された道路Ｂを含む区画が更新対象区画とされ、追加された道路Ｃの全体が更新対象区画でない場合には、地図データの更新後に、道路Ａはいずれの道路にも接続しない孤立状態となる。地図データが更新によりこのような状態となった場合には、当該孤立した道路を出発地や目的地に設定した際に、経路探索を適切に行うことができないという問題が生じる。
【０００６】
本発明は、上記の課題に鑑みてなされたものであり、その目的は、更新対象の地図データの一部の区画についての更新データファイルを供給する場合に、当該更新データファイルによる更新後の前記地図データの前記道路ネットワークの中で、一部の道路が他の道路から孤立することを防止し、当該一部の道路を含む経路の探索が可能な状態を保証できる地図データ供給装置、この地図更新データ供給装置を用いた地図データ更新システム、及び地図更新データ供給方法を提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するための本発明に係る、少なくとも道路ネットワークの情報を含み、複数の区画に分割された対象地図データの各区画についての更新データファイルを供給する地図更新データ供給装置の特徴構成は、前記対象地図データと同じく複数の区画に分割された更新用地図データが格納された更新用地図データベースと、前記対象地図データの一又は二以上の更新対象区画を前記更新用地図データに基づいて更新することにより、前記対象地図データの前記道路ネットワークの中で、一部の道路が他の道路から孤立した状態となる孤立状態の有無を検出する孤立検出手段と、前記孤立状態が有ることが検出された場合に、当該孤立した一部の道路に接続する道路を有する前記更新対象区画以外の前記更新用地図データの区画を、更新必要区画として抽出する抽出手段と、前記更新用地図データに基づいて、前記更新対象区画及び前記更新必要区画についての更新データファイルを生成する更新データファイル生成手段と、を備える点にある。
【０００８】
なお、本願において「一部の道路が他の道路から孤立した状態（孤立状態）」とは、前記一部の道路としての一の道路又は閉じた経路を形成する二以上の道路が、周囲の他の道路に接続していない状態のことである。
【０００９】
この特徴構成によれば、前記対象地図データの一又は二以上の更新対象区画を前記更新用地図データに基づいて更新することにより、前記対象地図データの前記道路ネットワークの中で、一部の道路が他の道路から孤立した状態となる場合には、当該孤立した一部の道路に接続する道路を有する前記更新対象区画以外の前記更新用地図データの区画を更新必要区画として抽出する。そして、前記対象地図データの前記更新対象区画に加えて前記更新必要区画についても前記更新用地図データに基づいて更新データファイルを生成することになる。したがって、この更新データファイルによる更新後の前記対象地図データの中で、一部の道路が他の道路から孤立した状態となることを防止することができる。これにより、当該一部の道路を含む経路の探索が可能な状態を保証することができる。
【００１０】
ここで、前記孤立検出手段は、前記更新対象区画について、前記対象地図データに対する前記更新用地図データの更新内容に道路の削除があった場合に、当該削除された道路に接続していた道路に関して前記孤立状態の有無の検出を行う構成とすると好適である。
【００１１】
通常、前記対象地図データの更新による一部の道路の孤立状態は、前記対象地図データの更新により削除された道路に接続していた道路及び当該道路と共に閉じた経路を形成する一又は二以上の道路に関して生じる。したがって、この構成によれば、このような前記対象地図データの更新による前記一部の道路の孤立状態の有無を、効率的に検出することが可能となる。
【００１２】
また、この際、前記孤立検出手段による前記孤立状態の検出は、前記対象地図データの前記更新対象区画を前記更新用地図データに基づいて更新した後に相当する状態で、前記削除された道路の一端と他端とを結ぶ経路の探索を行い、当該経路が存在しない場合に前記孤立状態が有ることを検出する構成とすると好適である。
【００１３】
この構成によれば、前記対象地図データの更新により削除された道路に接続していた道路に関する孤立状態の有無を、確実に検出することができる。
【００１４】
また、前記抽出手段は、前記対象地図データに対する前記更新用地図データの更新内容に道路の追加があった場合に、当該追加された道路を含む区画の中から前記更新必要区画を抽出する構成とすると好適である。
【００１５】
通常、現実の道路の状態を反映している更新用地図データにおいて、道路ネットワークの中の一部の道路が孤立状態となることはなく、当該一部の道路に接続する道路の削除がされた場合には、それに代わる道路が新たに追加されているはずである。そのため、前記対象地図データの更新対象区画の更新により一部の道路の孤立状態が生じる場合には、前記更新対象区画以外の区画に前記孤立した道路に接続する道路が新たに追加されている可能性が高い。この構成によれば、前記孤立状態が有ることが検出された場合に、新たに追加された道路を含む一又は二以上の区画の中から更新必要区画を抽出するので、前記孤立した一部の道路に接続する道路を有する前記更新対象区画以外の前記更新用地図データの区画を効率的に抽出することが可能となる。
【００１６】
また、この際、前記抽出手段による前記更新必要区画の抽出は、前記対象地図データの前記更新対象区画と前記追加された道路を含む少なくとも一つの区画とを前記更新用地図データに基づいて更新した後に相当する状態で、前記削除された道路の一端と他端とを結ぶ経路の探索を行い、前記追加された道路を通る前記経路が存在する場合には、前記経路を構成する前記追加された道路を含む区画を更新必要区画として抽出する構成とすると好適である。
【００１７】
この構成によれば、前記孤立した一部の道路に接続する道路を有する更新必要区画を、確実に検出することができる。
【００１８】
また、本発明に係る地図データ更新システムの特徴構成は、上記特徴構成を備えた地図更新データ供給装置と、ナビゲーション装置とを有して構成され、前記ナビゲーション装置は、前記対象地図データとしてのナビゲーション用地図データが格納されたナビゲーション用地図データベースと、前記更新対象区画についての更新要求データファイルを生成する更新要求生成手段と、前記地図更新データ供給装置から供給された前記更新データファイルを取得する更新データファイル取得手段と、前記更新データファイルに基づいて、前記ナビゲーション用地図データの更新を行う地図データ更新手段と、を備える点にある。
【００１９】
この特徴構成によれば、前記ナビゲーション装置側からナビゲーション用地図データの更新が必要な更新対象区画についての更新要求データを送信し、それに基づいて前記地図データ供給装置から供給される更新データファイルにより前記ナビゲーション用地図データの更新を行うことができる。それにより、ナビゲーション装置側では、前記更新対象区画と、当該更新対象区画の更新に伴い一部の道路が他の道路から孤立した状態となることを防止するために更新が必要となる更新必要区画とについての更新データファイルを受信し、ナビゲーション用地図データの一部の区画について更新することができる。したがって、ナビゲーション用地図データの必要最小限の区画を更新することが可能となり、前記ナビゲーション用地図データの全体を更新する場合と比較して、前記更新データファイルを送受信する際の通信データ量及び通信コストを低く抑えることが可能となる。
【００２０】
また、本発明に係る、少なくとも道路ネットワークの情報を含み、複数の区画に分割された対象地図データの各区画についての更新データファイルを供給する地図更新データ供給方法の特徴構成は、前記対象地図データと同じく複数の区画に分割された更新用地図データを用い、前記対象地図データの一又は二以上の更新対象区画を前記更新用地図データに基づいて更新することにより、前記対象地図データの前記道路ネットワークの中で、一部の道路が他の道路から孤立した状態となる孤立状態の有無を検出する孤立検出ステップと、前記孤立状態が有ることが検出された場合に、当該孤立した一部の道路に接続する道路を有する前記更新対象区画以外の前記更新用地図データの区画を、更新必要区画として抽出する抽出ステップと、前記更新用地図データに基づいて、前記更新対象区画及び前記更新必要区画についての更新データファイルを生成する更新データファイル生成ステップと、を実行する点にある。
【００２１】
この特徴構成によれば、前記対象地図データの一又は二以上の更新対象区画を前記更新用地図データに基づいて更新することにより、前記対象地図データの前記道路ネットワークの中で、一部の道路が他の道路から孤立した状態となる場合には、当該孤立した一部の道路に接続する道路を有する前記更新対象区画以外の前記更新用地図データの区画を更新必要区画として抽出する。そして、前記対象地図データの前記更新対象区画に加えて前記更新必要区画についても前記更新用地図データに基づいて更新データファイルを生成することになる。したがって、この更新データファイルによる更新後の前記対象地図データの中で、一部の道路が他の道路から孤立した状態となることを防止することができる。これにより、当該一部の道路を含む経路の探索が可能な状態を保証することができる。
【００２２】
ここで、前記孤立検出ステップとして、前記更新対象区画について、前記対象地図データに対する前記更新用地図データの更新内容に道路の削除があった場合に、前記対象地図データの前記更新対象区画を前記更新用地図データに基づいて更新した後に相当する状態で、前記削除された道路の一端と他端とを結ぶ経路の探索を行い、当該経路が存在しない場合に前記孤立状態が有ることを検出する構成とすると好適である。
【００２３】
この構成によれば、このような前記対象地図データの更新による前記一部の道路の孤立状態の有無を、効率的且つ確実に検出することが可能となる。
【００２４】
また、前記抽出ステップとして、前記対象地図データに対する前記更新用地図データの更新内容に道路の追加があった場合に、前記対象地図データの前記更新対象区画と前記追加された道路を含む少なくとも一つの区画とを前記更新用地図データに基づいて更新した後に相当する状態で、前記削除された道路の一端と他端とを結ぶ経路の探索を行い、前記追加された道路を通る前記経路が存在する場合には、前記経路を構成する前記追加された道路を含む区画を更新必要区画として抽出する構成とすると好適である。
【００２５】
この構成によれば、前記孤立状態が有ることが検出された場合に、新たに追加された道路を含む一又は二以上の区画の中から更新必要区画を抽出するので、前記孤立した一部の道路に接続する道路を有する前記更新対象区画以外の前記更新用地図データの区画を効率的且つ確実に抽出することが可能となる。
【発明を実施するための最良の形態】
【００２６】
本発明の実施形態について図面に基づいて説明する。図１は、本実施形態に係る地図更新データ供給装置１の構成を模式的に示すブロック図である。また、図２は、本実施形態に係るナビゲーション装置２の構成を模式的に示すブロック図である。本実施形態では、地図更新データ供給装置１とナビゲーション装置２とは、それぞれに通信装置６、２６を備え、各種の通信ネットワークを介してデータの送受信が可能に構成されており、全体として地図データ更新システムを構成している。そして、地図更新データ供給装置１は、ナビゲーション装置２に対して、ナビゲーション用地図データＭｂの更新用の更新データファイルｆａを供給する。更新データファイルｆａの供給を受けたナビゲーション装置２は、この更新データファイルｆａに基づいてナビゲーション用地図データＭｂの更新を行う。すなわち、本実施形態においては、ナビゲーション装置２のナビゲーション用地図データＭｂが本発明における「対象地図データ」に相当する。以下、本実施形態に係る地図更新データ供給装置１及びナビゲーション装置２の構成について詳細に説明する。
【００２７】
１．地図更新データ供給装置１
図１に示すように、地図更新データ供給装置１は、更新用地図データベースＤＢ１、制御装置３、入力装置４、表示装置５、及び通信装置６を備えている。また、制御装置３は、データベース更新手段７、孤立検出手段８、抽出手段９、更新データファイル生成手段１０、及び通信制御手段１１を備えている。ここで、制御装置３は、ＣＰＵ等の演算処理装置、及びソフトウエア（プログラム）やデータ等を格納するためのＲＡＭやＲＯＭ等の記憶媒体等を備えて構成されている。そして、制御装置３が備える各手段７〜１１は、この制御装置３の演算処理装置を中核部材として、入力されたデータに対して種々の処理を行うための機能部がハードウエア又はソフトウエア或いはその両方により実装されて構成されている。また、更新用地図データベースＤＢ１は、例えば、ハードディスクドライブやフラッシュメモリ等の書き換え可能な記憶媒体に格納されている。以下、地図更新データ供給装置１の各部の構成について順に説明する。
【００２８】
１−１．更新用地図データベースＤＢ１
図３は、更新用地図データベースＤＢ１内に格納された更新用地図データＭａの構成を説明するための説明図である。この図に示すように、更新用地図データベースＤＢ１には、複数の区画ｐに分割された更新用地図データＭａが複数の更新バージョンを有して格納されている。本例では、最初に作成された最も古い更新用地図データＭａをバージョン１とし、新たな情報に基づいて更新用地図データＭａを更新する毎にバージョン２、バージョン３と順にバージョンアップし、現時点で３つの更新バージョンの更新用地図データＭａが更新用地図データベースＤＢ１に格納されている。なお、本願の実施形態の説明において、各バージョン１〜３の更新用地図データＭａを区別する場合には、例えば「バージョン１の更新用地図データＭａ１」のように、更新用地図データの符号として、バージョン番号を付したＭａ１〜Ｍａ３の符号を用いる。一方、単に「更新用地図データＭａ」というときは、各バージョンの更新用地図データＭａ１〜Ｍａ３を総称するものとする。また、本願の実施形態の説明において、「区画ｐ」というときは、更新用地図データＭａ及び後述するナビゲーション用地図データＭｂの複数の区画を総称するものとし、個別の区画を指定する場合には、区画１、区画２、・・・等（図５〜８参照）のような区画番号を用いることとする。また、後述するように、複数の区画ｐの中から特に選択された区画が「更新対象区画ｐａ」又は「更新必要区画ｐｂ」となる。
【００２９】
また、本例では、更新用地図データＭａを構成する複数の区画ｐは、各区画ｐが同じ大きさの矩形となるように分割されている。例えば、日本全土の地図データを対象とする場合、更新用地図データＭａは、全体として日本全土を含む範囲を有し、それをｍ×ｎ（ｍ、ｎは自然数）分割して各区画ｐを構成する。この更新用地図データＭａの各区画ｐは、後述するナビゲーション用地図データＭｂの最下位のレイヤ１の区画ｐに対応して設けられている。図４は、更新用地図データＭａが有する情報の内容を説明するための説明図である。この図に示すように、更新用地図データＭａは、各区画ｐ内及び複数の区画ｐ間にわたって存在する多数の道路に相当するリンクや交差点に相当するノード等によって道路の接続関係を表す道路ネットワークＲｎの情報を有している。また、図示は省略するが、更新用地図データＭａは、道路ネットワークＲｎの情報以外にも、道路に沿って設けられる標識や信号機等、建築物（家屋やビル等）や橋梁やトンネル等の建造物、河川や海岸線等の自然物、及び行政区域等の各種の地物の配置及び形状等の情報を有している。但し、以下では説明の簡略化のため、更新用地図データＭａ、及びナビゲーション用地図データＭｂが有する地図としての情報の中で、特に重要な道路ネットワークＲｎの情報に関して説明を行う。
【００３０】
１−２．入力装置４、表示装置５、及び通信装置６
次に、図１に戻り、地図更新データ供給装置１の入力装置４、表示装置５、及び通信装置６について説明する。入力装置４は、キーボード、マウス、タッチパネル、スキャナ等の各種の入力用機器を有して構成されている。そして、作業者が、この入力装置４を用いて、更新用地図データＭａのバージョンアップのための地図情報の追加、変更、削除といった更新入力等を行うことができるようになっている。表示装置５は、液晶ディスプレイやＣＲＴディスプレイ等を有して構成されている。そして、作業者が、入力装置４を用いた作業を行う場合等に、更新用地図データＭａの状態やその更新作業の内容等の表示を行うことができるようになっている。通信装置６は、有線又は無線の公知の各種の通信ネットワークを介して、ナビゲーション装置２の通信装置２６との間で通信してデータの送受信を行うことができる構成となっている。このような通信ネットワークとしては、例えば、インターネット、有線又は無線の公衆電話網、有線又は無線ＬＡＮ（Local Area Network）、専用回線等を用いることができる。
【００３１】
１−３．制御装置３
上記のとおり、制御装置３は、データベース更新手段７、孤立検出手段８、抽出手段９、更新データファイル生成手段１０、及び通信制御手段１１を備えている。ここで、データベース更新手段７は、入力装置４を用いた更新用地図データＭａのバージョンアップのための地図情報の追加、変更、削除といった更新入力の処理、及び当該更新入力に基づいた新しいバージョンの更新用地図データＭａの生成及びその更新用地図データベースＤＢ１への格納の処理を行う手段である。このデータベース更新手段７の処理により、更新用地図データベースＤＢ１内の更新用地図データＭａは、現実の状況に追従して適宜更新される。そして、このデータベース更新手段７による更新用地図データＭａの更新の度に、更新用地図データベースＤＢ１には、各区画ｐについての新たなバージョンの更新用地図データＭａが格納される。
【００３２】
孤立検出手段８は、後述する更新データファイル生成手段による更新データファイルｆａの生成の前に、ナビゲーション用地図データＭｂの一又は二以上の更新対象区画ｐａを更新用地図データＭａに基づいて更新することにより生じる孤立状態の有無を検出する手段である。ここで、孤立状態とは、道路ネットワークＲｎ（図４参照）の中で、一部の道路が他の道路から孤立した状態となることであり、当該一部の道路としての一の道路又は閉じた経路を形成する二以上の道路（一部の道路）が、周囲の他の道路に接続していない状態のことである。換言すれば、孤立状態がない状態とは、道路ネットワークＲｎの中のいずれの位置に出発点と目的点とを設定したとしても、当該出発点と目的点とを結ぶ経路が存在する状態のことである。なお、更新対象区画ｐａとは、後述するナビゲーション装置２からの更新要求データファイルｆｂにより指定されるナビゲーション用地図データＭｂの更新対象となる区画ｐである。
【００３３】
ここで、図５〜７の地図データに示す道路ネットワークＲｎの例を用いて、一部の道路の孤立状態について説明する。これらの図５〜７は、更新用地図データベースＤＢ１に格納されている複数の更新バージョンの更新用地図データＭａに基づく地図データの、区画１〜４の道路ネットワークＲｎの各種の状態を示している。具体的には、図５は、区画１〜４の全てがバージョン２である場合の道路ネットワークＲｎの例を示し、図６は、区画１〜４の全てがバージョン３である場合の道路ネットワークＲｎの例を示している。また、図７は、区画１及び２のみがバージョン３に更新され、区画３及び４がバージョン２のままである場合の道路ネットワークＲｎの例を示している。なお、これらの図において、四角形で囲んだ数字は各区画ｐの更新バージョンを示している。これらの図に示す道路ネットワークＲｎにおいて、道路ｒ４〜ｒ７で構成される周回路ｒ４〜７は、図５に示すバージョン２の道路ネットワークＲｎでは道路ｒ１により、図６に示すバージョン３の道路ネットワークＲｎでは道路ｒ２により、それぞれ他の道路に接続されており、孤立状態とはなっていない。一方、図７に示す道路ネットワークＲｎでは、周回路ｒ４〜７は、閉じた経路を形成し、周囲の他の道路に接続していない孤立状態となる。孤立検出手段８は、このような孤立状態を検出する処理を行う。
【００３４】
通常、ナビゲーション用地図データＭｂの更新による一部の道路の孤立状態は、ナビゲーション用地図データＭｂの更新により削除された道路に接続していた道路及び当該道路と共に閉じた経路を形成する一又は二以上の道路に関して生じる。そこで、孤立検出手段８は、更新対象区画ｐａについて、ナビゲーション用地図データＭｂに対する最新バージョンの更新用地図データＭａの更新内容に道路の削除があった場合に、当該削除された道路に接続していた道路に関して孤立状態の有無の検出を行う。この際、孤立検出手段８は、ナビゲーション用地図データＭｂの更新対象区画ｐａを最新バージョンの更新用地図データＭａに基づいて更新した後に相当する状態で、削除された道路の一端と他端とを結ぶ経路（以下「接続経路ｋ」（図８参照）という。）の探索を行い、当該接続経路ｋが存在しない場合に孤立状態が有ることを検出する。なお、この孤立検出手段８による孤立状態の検出処理方法については、後に図１１に示すフローチャートにより詳細に説明する。
【００３５】
抽出手段９は、孤立検出手段８により孤立状態が有ることが検出された場合に、当該孤立した一部の道路に接続する道路を有する更新対象区画ｐａ以外の更新用地図データＭａの区画ｐを、更新必要区画ｐｂとして抽出する手段である。すなわち、抽出手段９は、ビゲーション装置２からの更新要求データファイルｆｂにより指定される更新対象区画ｐａの更新に伴い生じる一部の道路の孤立状態を防止するために更新を行う必要がある区画ｐとして、更新必要区画ｐｂを抽出する処理を行う。
【００３６】
通常、現実の道路の状態を反映している更新用地図データＭａにおいて、道路ネットワークＲｎの中の一部の道路が孤立状態となることはなく、当該一部の道路に接続する道路の削除がされた場合には、それに代わる道路が新たに追加されているはずである。そのため、ナビゲーション用地図データＭｂの更新対象区画ｐａの更新により一部の道路の孤立状態が生じる場合には、更新対象区画ｐａ以外の区画ｐに孤立した道路に接続する道路が新たに追加されている可能性が高い。そこで抽出手段９は、孤立検出手段８により孤立状態が有ることが検出された場合であって、ナビゲーション用地図データＭｂに対する最新バージョンの更新用地図データＭａの更新内容に道路の追加があった場合には、当該追加された道路を含む区画ｐの中から更新必要区画ｐｂを抽出する処理を行う。
【００３７】
この際、抽出手段９は、例えば図８に示すように、ナビゲーション用地図データＭｂの更新対象区画ｐａと追加された道路を含む少なくとも一つの区画ｐとを最新バージョンの更新用地図データＭａに基づいて更新した後に相当する状態の地図データの道路ネットワークＲｎにおいて、削除された道路の一端と他端とを結ぶ接続経路ｋの探索を行う。ここで、図８は、図７に示すように更新対象区画ｐａとしての区画１及び２をバージョン３に更新した状態から更に、追加された道路ｒ２を含む区画４についてもバージョン３に更新した状態の道路ネットワークＲｎを示している。そして、追加された道路を通る接続経路ｋが存在する場合には、抽出手段９は、当該接続経路ｋを構成する追加された道路（図８の例では道路ｒ２）を含む区画ｐ（図８の例では区画４）を更新必要区画ｐｂとして抽出する。なお、この抽出手段９による更新必要区画ｐｂの抽出処理方法については、後に図１２に示すフローチャートにより詳細に説明する。
【００３８】
更新データファイル生成手段１０は、更新用地図データベースＤＢ１に格納された更新用地図データＭａに基づいて、更新対象区画ｐａ及び抽出手段９により抽出された更新必要区画ｐｂについての更新データファイルｆａを生成する手段である。この際、更新データファイル生成手段１０は、更新対象区画ｐａ及び更新必要区画ｐｂに相当する全ての区画ｐについて、最新の更新バージョン（本例ではバージョン３）の更新データファイルｆａを生成する。本例では、各更新データファイルｆａは、更新対象区画ｐａ及び更新必要区画ｐｂについての最新の更新バージョンの地図データ、及び当該更新データファイルｆａに含まれる地図データの区画ｐ（更新対象区画ｐａ及び更新必要区画ｐｂに相当する全ての区画ｐ）を特定するための情報、例えばナビゲーション装置２のナビゲーション用地図データＭｂと共通で使用する区画ＩＤ情報等を含んだデータファイルとして生成される。
【００３９】
通信制御手段１１は、通信装置６の動作制御を行う手段である。具体的には、通信制御手段１１は、通信装置６による地図更新データ供給装置１とナビゲーション装置２との通信を制御し、ナビゲーション装置２から送信される更新要求データファイルｆｂの受信、及びナビゲーション装置２への更新データファイルｆａの送信等のための動作を通信装置６に行わせる。よって、本実施形態においては、この通信制御手段１１及び通信装置６が、ナビゲーション装置２に更新データファイルｆａを供給する「更新データファイル供給手段」を構成する。
【００４０】
２．ナビゲーション装置２
図２に示すように、ナビゲーション装置２は、ナビゲーション用地図データベースＤＢ２、制御装置２１、自位置検出装置２２、表示装置２３、音声出力装置２４、入力装置２５、及び通信装置２６を備えている。また、制御装置２１は、ナビゲーション用演算手段２７、更新要求生成手段２８、地図データ更新手段２９、及び通信制御手段３０を備えている。ここで、ナビゲーション用演算手段２７は、ナビゲーション装置２としての基本的なナビゲーション機能を実現するための演算手段である。このナビゲーション装置２のナビゲーション機能としては、例えば、自位置や指定した位置の周辺の地図表示、出発地から目的地までの経路探索、目的地までの経路誘導、自位置を道路上に補正するマップマッチング、目的地の検索等の機能がある。このナビゲーション装置２の制御装置２１は、ＣＰＵ等の演算処理装置、及びソフトウエア（プログラム）やデータ等を格納するためのＲＡＭやＲＯＭ等の記憶媒体等を備えて構成されている。そして、制御装置２１が備える各手段２７〜３０は、この制御装置２１の演算処理装置を中核部材として、入力されたデータに対して種々の処理を行うための機能部がハードウエア又はソフトウエア或いはその両方により実装されて構成されている。また、ナビゲーション用地図データベースＤＢ２は、例えば、ハードディスクドライブやフラッシュメモリ等の書き換え可能な記憶媒体に格納されている。以下、ナビゲーション装置２の各部の構成について順に説明する。
【００４１】
２−１．ナビゲーション用地図データベースＤＢ２
ナビゲーション用地図データベースＤＢ２には、ナビゲーション装置２のナビゲーション機能を実現するために、ナビゲーション用演算手段２７により参照される地図データであるナビゲーション用地図データＭｂが格納されている。図９は、ナビゲーション用地図データベースＤＢ２に格納されたナビゲーション用地図データＭｂの構成を説明するための説明図である。この図に示すように、ナビゲーション用地図データＭｂは、主要地図データＭｂ１、経路探索データＭｂ２、及び経路誘導データＭｂ３を備えている。ここで、主要地図データＭｂ１は、格納される道路等の地物の情報の詳細度に応じて複数のレイヤ（階層）に分けられている。本例では、主要地図データＭｂ１は、下位から上位に向かって順に、レイヤ１、レイヤ２、レイヤ３の３つのレイヤを有している。ここで、下位のレイヤほど詳細な道路等の地物の情報を含んでいる。また、主要地図データＭｂ１の各レイヤは、複数の区画ｐに分割されている。この際、上位のレイヤほど、広い領域に対応した区画ｐが設定されている。したがって、上位のレイヤの一つの区画ｐには、それより下位のレイヤの複数の区画ｐに対応する領域が含まれる。主要地図データＭｂ１の各レイヤには、道路に相当するリンクや交差点に相当するノード等によって道路の接続関係を表す道路ネットワークＲｎの情報が含まれる。この主要地図データＭｂ１は、自位置や指定した位置の周辺の地図表示や、自位置を道路上に補正するマップマッチング等に際して、ナビゲーション用演算手段２７により参照される。
【００４２】
経路探索データＭｂ２は、主要地図データＭｂ１に関連付けられており、前記道路ネットワークＲｎを構成する各リンクのコスト、通行条件、上位レイヤとの間でのノードの対応関係等の情報を有して構成されている。この経路探索データＭｂ２は、出発地から目的地までの経路探索に際して、ナビゲーション用演算手段２７により参照される。経路誘導データＭｂ３は、主要地図データＭｂ１に関連付けられており、目的地までの経路誘導に際して必要となる画像や音声等の情報を有して構成されている。したがって、この経路誘導データＭｂ３は、目的地までの経路誘導に際して、ナビゲーション用演算手段２７により参照される。
【００４３】
以上のように、ナビゲーション用地図データＭｂの主要地図データＭｂ１では、各レイヤより一つの区画ｐに対応する現実世界の領域の大きさが異なっている。本例では、主要地図データＭｂ１の最下位のレイヤ１の各区画ｐに含まれる領域の大きさが、更新用地図データＭａの各区画ｐの領域の大きさに対応している。したがって、地図更新データ供給装置１から供給される更新データファイルｆａは、主要地図データＭｂ１のレイヤ１の区画ｐに対応する区画単位のデータファイルとなる。そして、主要地図データＭｂ１のレイヤ２及びレイヤ３、並びに経路探索データＭｂ２及び経路誘導データＭｂ３は、この更新データファイルｆａによる更新後の主要地図データＭｂ１のレイヤ１のデータに基づいて、地図データ更新手段により生成されて更新される。
【００４４】
２−２．自位置検出装置２２
自位置検出装置２２は、ナビゲーション装置２の現在位置を検出するための装置である。そのため、自位置検出装置２２は、図示は省略するが、例えば、ＧＰＳ受信機、方位センサ、及び距離センサ等を有して構成されている。そして、これらにより取得された情報に基づいて現在の位置を示す座標や進行方位等の情報を取得して、制御装置２１に出力する。制御装置２１では、ナビゲーション用演算手段２７が、この自位置検出装置２２により検出された自位置情報とナビゲーション用地図データＭｂとに基づいて、自位置表示やマップマッチング等の処理を行う。
【００４５】
２−３．表示装置２３、音声出力装置２４、入力装置２５、及び通信装置２６
表示装置２３は、液晶ディスプレイ等を有して構成されている。音声出力装置２４は、スピーカ及びアンプ等を備えて構成される。これらの表示装置２３及び音声出力装置２４は、ナビゲーション用演算手段２７により制御されて動作し、自位置表示、２地点間の経路探索、進路案内、目的地検索等のための表示や音声出力等を行う。入力装置２５は、表示装置２３と一体的に配置されたタッチパネル、操作スイッチ、リモートコントローラ等を備えて構成されている。この入力装置２５は、ユーザによる操作入力を受け付け、その内容を制御装置２１へ出力する。通信装置６は、有線又は無線の公知の各種の通信ネットワークを介して、地図更新データ供給装置１の通信装置６との間で通信してデータの送受信を行うことができる構成となっている。
【００４６】
２−４．制御装置２１
上記のとおり、制御装置２１は、ナビゲーション用演算手段２７、更新要求生成手段２８、地図データ更新手段２９、及び通信制御手段３０を備えている。ナビゲーション用演算手段２７は、上記のとおり、例えば、自位置や指定した位置の周辺の地図表示、出発地から目的地までの経路探索、目的地までの経路誘導、自位置を道路上に補正するマップマッチング、目的地の検索等のナビゲーション装置２としての基本的なナビゲーション機能を実現するための演算手段である。本例では、ナビゲーション用演算手段２７は、図示は省略するが、ナビゲーション用の動作プログラムとして、表示プログラム、マップマッチングプログラム、経路探索プログラム、経路誘導プログラム、及び検索プログラムの５つのアプリケーションプログラムを有している。ここで、表示プログラムは、表示装置２３の表示画面に自位置や目的地等の周辺の地図表示や当該地図上への自位置表示等を行うためのプログラムである。マップマッチングプログラム、自位置検出装置２２により検出された自位置を地図の道路上に合わせるマップマッチング処理を行うためのプログラムである。経路探索プログラムは、例えば自位置等の出発地から入力装置２５により入力された目的地までの案内経路等を探索する経路探索を行うためのプログラムである。経路誘導プログラムは、経路探索プログラムにより決定された目的地までの経路に従って、表示装置２３の表示画面による案内表示や音声出力装置２４による音声案内等により、ユーザに対して適切な経路を案内して誘導する処理を行うためのプログラムである。検索プログラムは、目的地や地図表示のための地点等を、住所、電話番号、施設名称、ジャンル等に基づいて検索するためのプログラムである。またその他の各アプリケーションプログラムによるナビゲーション装置２の動作処理は公知であるので詳細な説明は省略する。そして、これらの各アプリケーションプログラムにおいて、ナビゲーション用地図データＭｂが参照されて用いられる。
【００４７】
更新要求生成手段２８は、更新対象区画ｐａについての更新要求データファイルｆｂを生成する手段である。ここでは、更新要求生成手段２８は、更新対象区画ｐａを決定し、当該更新対象区画ｐａについての更新データファイルｆａを地図更新データ供給装置１に要求するための更新要求データファイルｆｂを生成する。本例では、更新対象区画ｐａは、ナビゲーション装置２のナビゲーション用演算手段２７が参照するために必要なナビゲーション用地図データＭｂの区画ｐであり、主要地図データＭｂ１のレイヤ１の区画ｐの中から一又は二以上が選択される。ここで、ナビゲーション用演算手段２７が参照するために必要な区画ｐとしては、現に必要な区画ｐ及び将来必要となる可能性が高い区画が含まれる。したがって、更新対象区画ｐａとしては、例えば、自宅として登録している位置周辺、自位置検出装置２２により検出される現在の自位置周辺、目的地周辺、設定された目的地までの経路周辺等を含む区画ｐが該当する。また、このような更新対象区画ｐａを決定するに際して、例えば、自宅位置周辺については更新する領域を広くして多くの区画ｐを選択し、目的地までの経路周辺については更新する領域を狭くして必要最小限の区画ｐを選択する構成としても好適である。また、ナビゲーション装置２の使用者による地域を指定した地図更新処理の要求を受け付ける場合には、その際に指定された地域に含まれる区画ｐを更新対象区画ｐａとする。そして、更新要求データファイルｆｂは、決定された一又は二以上の更新対象区画ｐａを特定するための情報、並びに、更新対象区画ｐａ及び少なくとも更新対象区画ｐａの周辺の所定範囲内の区画ｐについてのナビゲーション用地図データＭｂの各区画ｐの更新状態を特定するための情報等を含んだデータファイルとして生成される。ここで、更新対象区画ｐａを特定するための情報としては、例えば地図更新データ供給装置１の更新用地図データＭａと共通で使用する区画ＩＤ情報が用いられる。また、各区画ｐの更新状態を特定するための更新状態情報としては、例えば各区画ｐの更新バージョン情報が用いられる。本例では、上記のとおり、区画１〜４について更新バージョンがバージョン２であることを示す情報が、更新要求データファイルｆｂに含まれた状態で地図更新データ供給装置１へ送信される。
【００４８】
地図データ更新手段２９は、地図更新データ供給装置１から供給された更新データファイルｆａに基づいて、ナビゲーション用地図データＭｂの更新を行う手段である。上記のとおり、本例では、各更新データファイルｆａは、更新対象区画ｐａ又は更新必要区画ｐｂについての地図データを含むファイルとなっている。したがって、地図データ更新手段２９は、ナビゲーション用地図データＭｂの主要地図データＭｂ１のレイヤ１における、更新対象区画ｐａ及び更新必要区画ｐｂに対応する区画ｐの地図データを、更新データファイルｆａに含まれる更新対象区画ｐａ及び更新必要区画ｐｂの地図データに変更することにより、ナビゲーション用地図データＭｂの更新を行う。
【００４９】
通信制御手段３０は、通信装置２６の動作制御を行う手段である。具体的には、通信制御手段３０は、通信装置２６による地図更新データ供給装置１とナビゲーション装置２との通信を制御し、地図更新データ供給装置１への更新要求データファイルｆｂの送信、及び地図更新データ供給装置１から送信される更新データファイルｆａの受信等のための動作を通信装置２６に行わせる。したがって、本実施形態においては、この通信制御手段３０及び通信装置２６が、地図更新データ供給装置から供給された前記更新データファイルを取得する「更新データファイル取得手段」を構成する。
【００５０】
３．地図更新データ供給装置１の動作処理
次に、地図更新データ供給装置１の動作処理について図１０〜１２に示すフローチャートに基づいて詳細に説明する。また、この際、孤立検出手段８による孤立状態の検出処理及び抽出手段９による更新必要区画ｐｂの抽出処理について、図５〜８に示す道路ネットワークＲｎの例を用いて具体的に説明する。これらの図５〜８は、更新用地図データベースＤＢ１に格納されている複数の更新バージョンの更新用地図データＭａに基づく地図データの、区画１〜４の道路ネットワークＲｎの各種の状態を示している。これらの図において、四角形で囲んだ数字は各区画ｐの更新バージョンを示している。また、これらの図において、ｒ１〜ｒ１５はそれぞれの道路を区別する符号であり、各道路ｒ１〜ｒ１５はそれぞれ交差点で区切られている。なお、これらの図５〜８では、説明の簡略化のために一部の区画ｐ（区画１〜４）のみを示しているが、実際にはこれより多数の区画ｐが処理対象として取り扱われる場合が多い。
【００５１】
３−１．地図更新データ供給方法の全体の処理
この地図更新データ供給装置１は、ナビゲーション装置２からの更新要求に基づいて更新対象区画ｐａ及び必要に応じて更新必要区画ｐｂについての更新データファイルｆａを生成し、送信する処理を行う。図１０は、このような地図更新データ供給装置１による地図更新データ供給方法の全体の処理を示すフローチャートである。この図に示すように、地図更新データ供給装置１は、ナビゲーション装置２からの更新要求があった場合、すなわち更新要求データファイルｆｂを受信した場合には（ステップ＃０１：Ｙｅｓ）、制御装置３は、更新要求データファイルｆｂから更新対象区画ｐａ及びナビゲーション用地図データＭｂの更新状態の情報を取得する（ステップ＃０２）。
【００５２】
次に、制御装置３は、孤立検出手段８により、ナビゲーション用地図データＭｂのステップ＃０２で取得した更新対象区画ｐａを更新用地図データＭａに基づいて更新することで生じる孤立状態の有無を検出する（ステップ＃０３）。この孤立検出手段８による孤立状態検出処理については、後に図１１のフローチャートに基づいて詳細に説明する。そして、孤立状態が有ることが検出された場合には（ステップ＃０４：Ｙｅｓ）、制御装置３は、抽出手段９により、当該孤立状態を防止するための更新必要区画ｐｂを抽出する（ステップ＃０５）。一方、孤立状態が無いことが検出された場合には（ステップ＃０４：Ｎｏ）、ステップ＃０５の処理は行わない。
【００５３】
その後、制御装置３は、更新データファイル生成手段１０により、更新データファイルｆａを生成する（ステップ＃０６）。この際、更新データファイル生成手段１０は、ステップ＃０４で孤立状態が無いことが検出されたために（ステップ＃０４：Ｎｏ）、ステップ＃０５で更新必要区画ｐｂが抽出されなかった場合には、ステップ＃０２で取得された更新対象区画ｐａのみについて更新データファイルｆａを生成し、ステップ＃０５で更新必要区画ｐｂが抽出された場合には、ステップ＃０２で取得された更新対象区画ｐａ及びステップ＃０５で抽出された更新必要区画ｐｂのそれぞれについて更新データファイルｆａを生成する。そして、制御装置３は、通信制御手段１１により、通信装置６を制御して、ステップ＃０６で生成された更新データファイルｆａをナビゲーション装置２に送信する（ステップ＃０７）。以上の処理により、更新データファイルｆａがナビゲーション装置２（対象地図データ側）に供給される。
【００５４】
３−２．孤立状態の検出処理方法
次に、上記ステップ＃０３の孤立検出手段８による孤立状態の検出処理方法について説明する。図１１は、この孤立検出手段８による孤立状態の検出処理方法を示すフローチャートである。この図に示すように、孤立検出手段８は、まず、ステップ＃０２で取得したナビゲーション用地図データＭｂの更新状態に基づいて、ナビゲーション用地図データＭｂと同じ更新状態の地図データを生成する（ステップ＃１１）。すなわち、孤立検出手段８は、更新要求データファイルｆｂに含まれる、更新対象区画ｐａ及び少なくともその周辺の所定範囲内の区画ｐについてのナビゲーション用地図データＭｂの各区画ｐの更新状態の情報に基づいて、ナビゲーション用地図データＭｂと同じ更新バージョンの更新用地図データＭａを更新用地図データベースＤＢ１から読み出して、更新データファイルｆａによる更新前のナビゲーション用地図データＭｂと同じ更新状態の地図データを生成する。本例では、ステップ＃０２において、更新要求データファイルｆｂから、更新対象区画ｐａとして区画１及び２、ナビゲーション用地図データＭｂの更新状態として区画１〜４の全てがバージョン２であることを示す情報を取得したものとする。図５は、この情報に基づいて生成したナビゲーション用地図データＭｂと同じ更新状態、すなわち区画１〜４の全てがバージョン２である地図データにおける道路ネットワークＲｎの状態を示している。また、図６は、本例における最新バージョンの更新用地図データＭａ、すなわち区画１〜４の全てがバージョン３である地図データにおける道路ネットワークＲｎの状態を示している。
【００５５】
次に、孤立検出手段８は、ステップ＃０２で取得した更新対象区画ｐａについて、ナビゲーション用地図データＭｂに対する最新バージョンの更新用地図データＭａの更新内容に道路の削除が有るか否かの判定を行う（ステップ＃１２）。この判定は、ステップ＃１１で生成したナビゲーション用地図データＭｂと同じ更新状態の地図データ（図５）と、最新バージョンの更新用地図データＭａ（図６）とを、更新対象区画ｐａについて比較することにより行う。すなわち、孤立検出手段８は、更新対象区画ｐａについて、ナビゲーション用地図データＭｂと同じ更新状態の地図データ（図５）の道路ネットワークＲｎに対する、最新バージョンの更新用地図データＭａ（図６）の道路ネットワークＲｎの更新内容（変更点）を抽出し、当該更新内容に道路の削除があるか否かを判定する。本例では、図５に示すナビゲーション用地図データＭｂと同じ更新状態の地図データの道路ネットワークＲｎに対して、図６に示す最新バージョンの更新用地図データＭａの道路ネットワークＲｎでは、区画１及び２にまたがる道路ｒ１が削除され、区画４に道路ｒ２が追加され、区画３に道路ｒ３が追加されている。また、道路ｒ３の追加により、バージョン３の道路ネットワークＲｎでは、道路ｒ８が道路ｒ８とｒ１４に分けられ、道路ｒ１２が道路ｒ１２とｒ１５に分けられている。そして、上記のとおり、本例では更新対象区画ｐａは区画１及び２であり、これらの区画１及び２では、道路ｒ１が削除されている。したがって、本例では、孤立検出手段８は、更新対象区画ｐａに道路の削除が有ると判定する（ステップ＃１２：Ｙｅｓ）。
【００５６】
このように、更新対象区画ｐａに道路の削除が有ると判定した場合には（ステップ＃１２：Ｙｅｓ）、孤立検出手段８は、次に、ナビゲーション用地図データＭｂの更新対象区画ｐａを最新バージョンの更新用地図データＭａにより更新した後に相当する状態の地図データを生成する（ステップ＃１３）。すなわち、孤立検出手段８は、ステップ＃１１で生成したナビゲーション用地図データＭｂと同じ更新状態の地図データ（図５）に対して、更新対象区画ｐａを最新バージョンの更新用地図データＭａ（図６）に置き換えることにより、ナビゲーション用地図データＭｂの更新対象区画ｐａの更新後に相当する状態の地図データを生成する。本例では、更新対象区画ｐａが区画１及び２であるので、図５に示す地図データの区画１及び２を、図６に示す最新バージョンの更新用地図データＭａの区画１及び２に置き換える。図７は、このナビゲーション用地図データＭｂの更新対象区画ｐａの更新後に相当する状態の地図データにおける道路ネットワークＲｎの状態を示している。
【００５７】
次に、孤立検出手段８は、ステップ＃１３で生成した、ナビゲーション用地図データＭｂの更新対象区画ｐａを最新バージョンの更新用地図データＭａにより更新した後に相当する状態の地図データにおいて、更新対象区画ｐａについての削除された道路の一端と他端とを結ぶ接続経路ｋを探索する処理を行う（ステップ＃１４）。この処理により、孤立検出手段８は、ステップ＃１２で、更新対象区画ｐａについてナビゲーション用地図データＭｂに対する最新バージョンの更新用地図データＭａの更新内容に道路の削除が有ると判定した場合における、当該削除された道路に接続していた道路に関して孤立状態の有無の検出を行う。本例では、孤立検出手段８は、図７に示すナビゲーション用地図データＭｂの更新対象区画ｐａの更新後に相当する状態の地図データの道路ネットワークＲｎにおいて、更新対象区画ｐａである区画１及び２内の削除された道路ｒ１（図５及び６参照）の一端の交差点ｃ１と他端の交差点ｃ２とを結ぶ接続経路ｋの探索を行う。ここでは、孤立検出手段８は、図７に細線矢印で示すように、一端の交差点ｃ１と他端の交差点ｃ２とのそれぞれから互いに他方へ向かう接続経路ｋ（図８参照）の探索を行う。
【００５８】
その後、孤立検出手段８は、ステップ＃１４の探索の結果、接続経路ｋが有るか否かについて判定する（ステップ＃１５）。そして、例えば図８に示すように、接続経路ｋが有る場合には（ステップ＃１５：Ｙｅｓ）、孤立検出手段８は、道路ネットワークＲｎの中に、一部の道路が他の道路から孤立した状態となる孤立状態が無いことを検出し、その検出結果を出力する（ステップ＃１６）。また、上述のステップ＃１２において、更新対象区画ｐａに道路の削除が無いと判定した場合にも（ステップ＃１２：Ｎｏ）、孤立検出手段８は、道路ネットワークＲｎの中に孤立状態が無いことを検出する（ステップ＃１６）。一方、ステップ＃１４の探索の結果、接続経路ｋが無い場合には（ステップ＃１５：Ｎｏ）、孤立検出手段８は、前記孤立状態が有ることを検出し、その検出結果を出力する（ステップ＃１７）。図７に示す例では、道路ｒ４〜ｒ７は閉じた周回路ｒ４〜７を形成しているため、一端の交差点ｃ１と他端の交差点ｃ２とを結ぶ接続経路ｋは存在しない（ステップ＃１５：Ｎｏ）。よって、本例では、孤立検出手段８は、ナビゲーション用地図データＭｂの更新対象区画ｐａである区画１及び２の更新後に相当する状態の地図データの道路ネットワークＲｎの中に、孤立状態が有ることを検出する。
【００５９】
３−３．更新必要区画ｐｂの抽出処理方法
次に、上記ステップ＃０５の抽出手段９による更新必要区画ｐｂの抽出処理方法について説明する。図１２は、この抽出手段９による更新必要区画ｐｂの抽出処理方法を示すフローチャートである。この図に示すように、抽出手段９は、まず、更新対象区画ｐａの周辺の追加された道路を含む区画ｐを、更新必要区画ｐｂの候補区画として選択する（ステップ＃２１）。本実施形態においては、抽出手段９は、候補区画として一つの区画ｐを選択する。この候補区画としては、更新対象区画ｐａに隣接する区画の中から選択すると好適である。具体的には、本例では、図５に示すナビゲーション用地図データＭｂと同じ更新状態の地図データの道路ネットワークＲｎに対して、図６に示す最新バージョンの更新用地図データＭａの道路ネットワークＲｎでは、区画４に道路ｒ２が追加され、区画３に道路ｒ３が追加されている。そこで、抽出手段９は、追加された道路ｒ２又はｒ３を含む区画３及び４の中から一つの候補区画を選択する。以下では、まず区画４を候補区画として選択した場合の例について説明する。
【００６０】
抽出手段９は、候補区画を選択した後（ステップ＃２１）、ナビゲーション用地図データＭｂの更新対象区画ｐａと、ステップ＃２１で選択した候補区画とを、最新バージョンの更新用地図データＭａにより更新した後に相当する状態の地図データを生成する（ステップ＃２２）。すなわち、抽出手段９は、図１１のステップ＃１１で生成したナビゲーション用地図データＭｂと同じ更新状態の地図データ（図５）に対して、更新対象区画ｐａ及びステップ＃２１で選択した候補区画を最新バージョンの更新用地図データＭａ（図６）に置き換えることにより、ナビゲーション用地図データＭｂの更新対象区画ｐａ及び候補区画の更新後に相当する状態の地図データを生成する。本例では、上記のとおり、更新対象区画ｐａが区画１及び２であり候補区画が区画４であるので、図５に示す地図データの区画１、２、及び４を、図６に示す最新バージョンの更新用地図データＭａの区画１、２、及び４に置き換える。図８は、このナビゲーション用地図データＭｂの更新対象区画ｐａ及び候補区画の更新後に相当する状態の地図データにおける道路ネットワークＲｎの状態を示している。
【００６１】
次に、抽出手段９は、ステップ＃２２で生成した、ナビゲーション用地図データＭｂの更新対象区画ｐａ及び候補区画を最新バージョンの更新用地図データＭａにより更新した後に相当する状態の地図データにおいて、孤立検出手段８による孤立状態の検出の際と同様に、更新対象区画ｐａについての削除された道路の一端と他端とを結ぶ接続経路ｋを探索する処理を行う（ステップ＃２３）。すなわち、本例では、抽出手段９は、図８に示すナビゲーション用地図データＭｂの更新対象区画ｐａ及び候補区画の更新後に相当する状態の地図データの道路ネットワークＲｎにおいて、削除された道路ｒ１（図５及び６参照）の一端の交差点ｃ１と他端の交差点ｃ２とを結ぶ接続経路ｋの探索を行う。ここでは、抽出手段９は、図８の細線矢印で示すように、一端の交差点ｃ１と他端の交差点ｃ２とのそれぞれから互いに他方へ向かう接続経路ｋの探索を行う。
【００６２】
その後、抽出手段９は、ステップ＃２３の探索の結果、接続経路ｋが有るか否かについて判定する（ステップ＃２４）。そして、接続経路ｋが有る場合には（ステップ＃２４：Ｙｅｓ）、抽出手段９は、この接続経路ｋが存在するときのステップ＃２１で選択した候補区画を更新必要区画ｐｂとして抽出する（ステップ＃２５）。本例では、図８に示すように、一端の交差点ｃ１から、道路ｒ８、ｒ９、ｒ１０、ｒ２、ｒ６、及びｒ７を通り、他端の交差点ｃ２に到達する接続経路ｋが存在する。したがって、抽出手段９は、追加された道路ｒ２を含む区画４を更新必要区画ｐｂとして抽出する。
【００６３】
一方、ステップ＃２３の探索の結果、接続経路ｋが無い場合には（ステップ＃２４：Ｎｏ）、当該候補区画は更新必要区画ｐｂとはしない。そして、処理はステップ＃２１へ戻り、抽出手段９は、他の候補区画を選択し、上記と同様の処理を行う。例えば、図示は省略するが、追加された道路ｒ３を含む区画３を更新必要区画ｐｂの候補区画として選択した（ステップ＃２１）場合には、抽出手段９は、ナビゲーション用地図データＭｂの更新対象区画ｐａと、ステップ＃２１で選択した候補区画とを、最新バージョンの更新用地図データＭａにより更新した後に相当する状態の地図データとして、図５に示す地図データの区画１、２、及び３を、図６に示す最新バージョンの更新用地図データＭａの区画１、２、及び３に置き換えた地図データを生成する。この場合、削除された道路ｒ１の一端の交差点ｃ１と他端の交差点ｃ２とを結ぶ接続経路ｋは存在しない（ステップ＃２４：Ｎｏ）。よって、抽出手段９は、この場合の候補区画である区画３は、更新必要区画ｐｂとはしない。なお、抽出手段９は、更新必要区画ｐｂが少なくとも一つ抽出されるまで、追加された道路を含む区画ｐを候補区画として順次同様の処理を行う。
【００６４】
４．ナビゲーション装置２における地図更新のための動作処理方法
次に、ナビゲーション装置２における地図更新のための動作処理方法について図１３に示すフローチャートに基づいて詳細に説明する。この図に示すように、ナビゲーション装置２は、ナビゲーション用地図データＭｂの更新に際して、更新要求生成手段２８による更新要求データファイルｆｂを生成して地図更新データ供給装置１へ送信し、当該更新要求データファイルｆｂを受けた地図更新データ供給装置１により生成された更新データファイルｆａを取得し、当該更新データファイルｆａに基づいて、ナビゲーション用地図データＭｂの更新を行う。
【００６５】
具体的には、図１３に示すように、ナビゲーション装置２は、まず、地図更新処理が開始されたか否かを判定する（ステップ＃３１）。この地図更新処理の開始は、例えば、ナビゲーション装置２が予め定められた期間で定期的に地図更新処理を行う場合、ナビゲーション用演算手段２７により所定の条件を満たす形態でのナビゲーション用地図データＭｂの参照があった場合、或いは、ナビゲーション装置２の使用者による地図更新処理の開始要求操作があった場合等に開始される。
【００６６】
そして、地図更新処理が開始された場合には（ステップ＃３１：Ｙｅｓ）、ナビゲーション装置２は、更新要求生成手段２８により、更新対象区画ｐａを決定する（ステップ＃３２）。ここで、更新対象区画ｐａとしては、上記のとおり、ナビゲーション用演算手段２７による処理のために現に必要な区画ｐ及び将来必要となる可能性が高い区画が含まれる。本例では、更新対象区画ｐａは、主要地図データＭｂ１のレイヤ１の区画ｐの中から一又は二以上が選択される。
【００６７】
次に、ナビゲーション装置２は、更新要求生成手段２８により、更新要求データファイルｆｂを生成する（ステップ＃３３）。ここで、更新要求データファイルｆｂは、上記のとおり、決定された一又は二以上の更新対象区画ｐａを特定するための情報、並びに、更新対象区画ｐａ及び少なくとも更新対象区画ｐａの周辺の所定範囲内の区画ｐについてのナビゲーション用地図データＭｂの各区画ｐの更新状態を特定するための情報等を含んだデータファイルとして生成される。そして、ナビゲーション装置２は、通信制御手段３０により通信装置２６を制御して、ステップ＃３３で生成された更新要求データファイルｆｂを地図更新データ供給装置１に送信する（ステップ＃３４）。この更新要求データファイルｆｂを受信した地図更新データ供給装置１では、上記のとおり、更新データファイルｆａを生成してナビゲーション装置２に送信する処理が行われる。ナビゲーション装置２は、所定の時間を経過しても地図更新データ供給装置１からの更新データファイルｆａを受信できない場合には（ステップ＃３５：Ｎｏ）、通信異常と判断して更新要求データファイルｆｂの送信（ステップ＃３４）を再度行う。
【００６８】
そして、ナビゲーション装置２は、地図更新データ供給装置１からの更新データファイルｆａを受信した場合には（ステップ＃３５：Ｙｅｓ）、更新データファイルｆａを取得し（ステップ＃３６）、地図データ更新手段２９により、当該更新データファイルｆａに基づいて、ナビゲーション用地図データＭｂの更新を行う（ステップ＃３７）。本例では、上記のとおり、各更新データファイルｆａは、更新対象区画ｐａ及び抽出手段９により更新必要区画ｐｂが抽出された場合には当該更新必要区画ｐｂについての最新バージョンの地図データを含むファイルとなっている。したがって、地図データ更新手段２９は、ナビゲーション用地図データＭｂの主要地図データＭｂ１のレイヤ１における、更新対象区画ｐａ及び更新必要区画ｐｂに対応する区画ｐの地図データを、更新データファイルｆａに含まれる更新対象区画ｐａ及び更新必要区画ｐｂの地図データに変更することにより、ステップ＃３７のナビゲーション用地図データＭｂの更新を行う。以上により、ナビゲーション装置２における地図更新のための動作処理が終了する。
【００６９】
〔その他の実施形態〕
（１）上記の実施形態では、孤立検出手段８が、ナビゲーション用地図データＭｂの更新対象区画ｐａを更新用地図データＭａに基づいて更新した後に相当する状態で、削除された道路の一端と他端とを結ぶ接続経路ｋの探索を行い、当該接続経路ｋが存在しない場合に孤立状態が有ることを検出する構成である場合について説明した。しかし、孤立検出手段８の構成はこれに限定されない。すなわち、孤立検出手段８は、道路ネットワークの中で、一部の道路が他の道路から孤立した状態となる孤立状態の有無を検出することができる構成であれば良く、例えば、道路形状等に基づいて、一部の道路が他の道路から孤立した状態となっていることを検出する構成とすることも、本発明の好適な実施形態の一つである。
【００７０】
（２）上記の実施形態では、抽出手段９が、ナビゲーション用地図データＭｂの更新対象区画ｐａと追加された道路を含む少なくとも一つの区画ｐとを最新バージョンの更新用地図データＭａに基づいて更新した後に相当する状態で、削除された道路の一端と他端とを結ぶ接続経路ｋの探索を行い、当該接続経路ｋが有る場合に、当該接続経路ｋを構成する追加された道路を含む区画ｐを更新必要区画ｐｂとして抽出する構成である場合について説明した。しかし、抽出手段９の構成はこれに限定されない。すなわち、抽出手段９は、孤立状態が有ることが検出された場合に、当該孤立した一部の道路に接続する道路を有する更新対象区画ｐａ以外の更新用地図データＭａの区画ｐを、更新必要区画ｐｂとして抽出する構成であれば良く、例えば、道路形状等に基づいて、当該孤立した一部の道路に接続する道路を有する区画ｐを抽出する構成とすることも、本発明の好適な実施形態の一つである。
【００７１】
（３）上記の実施形態では、抽出手段９が、ナビゲーション用地図データＭｂの更新対象区画ｐａと追加された道路を含む一つの区画ｐ（上記例では区画４）とを最新バージョンの更新用地図データＭａに基づいて更新した後に相当する状態で、接続経路ｋの探索を行う場合を例として説明した。しかし、本発明の適用範囲はこれに限定されるものではなく、抽出手段９が、ナビゲーション用地図データＭｂの更新対象区画ｐａ（上記例では区画１及び２）と追加された道路を含む複数の区画ｐ（上記例では区画３及び４）とを最新バージョンの更新用地図データＭａに基づいて更新した後に相当する状態で、接続経路ｋの探索を行う構成とすることも、本発明の好適な実施形態の一つである。
【００７２】
（４）上記の実施形態では、更新対象区画ｐａを、ナビゲーション装置２からの更新要求データファイルｆｂにより指定される区画ｐとする場合を例として説明した。しかし、更新対象区画ｐａの決定方法はこれに限定されるものではなく、例えば地図更新データ供給装置１が決定する構成とすることも可能である。
【００７３】
（５）上記の実施形態では、更新用地図データベースＤＢ１内の更新用地図データＭａは、図３に示すように、各更新バージョンについて、更新用地図データＭａを構成する全ての区画ｐの地図データが格納される場合を例として説明した。しかし、更新用地図データＭａの構成はこれに限定されない。すなわち、例えば、区画ｐ毎に更新があったものをバージョンアップし、内容に変更がない区画については新たな更新バージョンのデータを生成しない構成とすることにより、区画ｐ毎に最新の更新バージョンが異なる構成とすることも好適な実施形態の一つである。このように構成すれば、更新用地図データベースＤＢ１の全体のデータ量を少なく抑えることが可能となる。
【００７４】
（６）上記の実施形態では、更新データファイルｆａは、区画ｐ毎の地図データのファイルとする場合を例として説明した。しかし、更新データファイルｆａの構成はこれに限定されない。例えば、この更新データファイルｆａを、更新前のナビゲーション用地図データＭｂの内容に対して変更すべき内容を表す区画ｐ毎の差分データとすることも好適な実施形態の一つである。このような構成とすれば、更新データファイルｆａとして各区画ｐの地図データを全て含む場合と比較して、ファイルのデータ量を少なくすることができる。
【００７５】
（７）また、上記の実施形態では、更新データファイルｆａを、更新対象区画ｐａ又は更新必要区画ｐｂの区画ｐ毎に、それぞれ生成する場合を例として説明した。しかし、更新データファイルｆａの構成はこれに限定されるものではなく、一つのナビゲーション装置２に対して送信する複数の区画ｐについての更新データを一つのファイルにまとめた構成とすることも好適な実施形態の一つである。
【００７６】
（８）上記の実施形態では、地図更新データ供給装置１は、更新データファイルｆａを通信ネットワークを介してナビゲーション装置２に送信する場合の例について説明した。しかし、更新データファイルｆａの供給方法はこれに限定されるものではない。したがって、例えば、地図更新データ供給装置１は、更新データファイルｆａを、通信手段を介さず、記録媒体記録手段を用いて所定の記録媒体に更新データファイルｆａを記録し、郵送等によりナビゲーション装置２の使用者に提供する構成とすることも好適な実施形態の一つである。この場合、地図更新データ供給装置１は、ナビゲーション装置２からの更新要求を、上記の各実施形態と同様の通信の他、郵送等の他の手段を用いて取得する構成とできる。
【００７７】
（９）上記の実施形態では、地図更新データ供給装置１により供給される更新データファイルｆａが、ナビゲーション装置２のナビゲーション用地図データＭｂを更新対象とする場合を例として説明した。しかし、更新データファイルｆａが更新対象とする対象地図データは、ナビゲーション用地図データＭｂに限定されるものではなく、複数の区画に分割された地図データであれば、各種の用途の地図データを更新対象とすることができる。また、対象地図データは、上記の実施形態のように、地図更新データ供給装置１から離れた装置に備えられるものに限られず、例えば、地図更新データ供給装置１と一体的に設けられた装置が対象地図データを備える構成とすることも可能である。
【産業上の利用可能性】
【００７８】
本発明は、少なくとも道路ネットワークの情報を含み、複数の区画に分割された対象地図データの各区画についての更新データファイルを供給する地図更新データ供給装置、この地図更新データ供給装置を用いた地図データ更新システム、及び地図更新データ供給方法等に利用することが可能である。
【図面の簡単な説明】
【００７９】
【図１】本発明の実施形態に係る地図更新データ供給装置の構成を示すブロック図
【図２】本発明の実施形態に係るナビゲーション装置の構成を示すブロック図
【図３】更新用地図データの構成を説明するための説明図
【図４】更新用地図データが有する情報の内容を説明するための説明図
【図５】ナビゲーション用地図データと同じ更新状態の地図データにおける道路ネットワークの状態を示す図
【図６】最新バージョンの更新用地図データにおける道路ネットワークの状態を示す図
【図７】ナビゲーション用地図データの更新対象区画の更新後に相当する状態の地図データにおける道路ネットワークの状態を示す図
【図８】ナビゲーション用地図データの更新対象区画及び候補区画の更新後に相当する状態の地図データにおける道路ネットワークの状態を示す図
【図９】ナビゲーション用地図データの構成を説明するための説明図
【図１０】本発明の実施形態に係る地図更新データ供給装置による地図更新データ供給方法の全体の処理を示すフローチャート
【図１１】孤立検出手段による孤立状態の検出処理方法を示すフローチャート
【図１２】抽出手段による更新必要区画の抽出処理方法を示すフローチャート
【図１３】ナビゲーション装置における地図更新のための動作処理方法を示すフローチャート
【符号の説明】
【００８０】
１：地図更新データ供給装置
２：ナビゲーション装置
８：孤立検出手段
９：抽出手段
１０：更新データファイル生成手段
２６：通信装置（更新データファイル取得手段）
２８：更新要求生成手段
２９：地図データ更新手段
３０：通信制御手段（更新データファイル取得手段）
Ｒｎ：道路ネットワーク
ｐ：区画
ＤＢ１：更新用地図データベース
Ｍａ：更新用地図データ
ＤＢ２：ナビゲーション用地図データベース
Ｍｂ：ナビゲーション用地図データ（対象地図データ）
ｆａ：更新データファイル
ｐａ：更新対象区画
ｐｂ：更新必要区画
ｆｂ：更新要求データファイル
ｋ：接続経路
【図１】
2008249798.tif 000003
【図２】
2008249798.tif 000004
【図３】
2008249798.tif 000005
【図４】
2008249798.tif 000006
【図５】
2008249798.tif 000007
【図６】
2008249798.tif 000008
【図７】
2008249798.tif 000009
【図８】
2008249798.tif 000010
【図９】
2008249798.tif 000011
【図１０】
2008249798.tif 000012
【図１１】
2008249798.tif 000013
【図１２】
2008249798.tif 000014
【図１３】
2008249798.tif 000015