図面 (/)

この項目の情報は公開日時点(2001年2月27日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (20)

課題

ある1つが更新された場合に、隣接ユニット地図ファイルを更新する必要がない地図ファイルを読み出すための端末装置を提供することである。

解決手段

地図を複数の領域に分割して得られる各ユニットを表す地図ファイルは、ノード毎に作成されるノードレコードと、リンク毎に作成されるリンクレコードとを含む。所定のノードレコードには、ユニットとそれに隣接するユニットとの道路接続関係を規定する隣接ノード座標情報が記録される。以上の地図ファイルは、第1の記憶装置19に格納される。前記データ処理部13は、地図ファイルを利用して経路を探索する処理を実行する。データ処理部13は、経路探索処理の最中に、一方のユニットおよび他方の隣接ユニットの隣接ノードが有する座標情報に基づいて、当該一方のユニット内の道路から、当該他方の隣接ユニット内の道路への接続をたどる。

概要

背景

「第1の従来技術」近年、ナビゲーションシステムが搭載された車両が増加してきている。ナビゲーションシステムでは、当初は、画面上に地図を作成するファイル(以下、地図ファイルと称す)だけが提供されていた。しかし、近年は、地図ファイルに加えて、例えば交通情報および経路案内情報も提供されるようになった。かかる情報の多様化により、ナビゲーションシステムは、より便利になり、今後も急速に普及すると期待されている。

当初、ナビゲーションシステムには、CD−ROMに代表される読み出し専用記録媒体を有する記憶装置が搭載されていた。この記録媒体には、ユーザに提供されるべき地図ファイルと、その関連データとが予め記録されている。記憶装置は、記憶媒体に記録された地図ファイルを、必要に応じて読み出す。読み出された地図ファイルは、ユーザにより参照されたり、経路探索処理またはマップマッチング処理に利用されたりしていた。

一般的にディジタル地図ファイルは、互いに縮尺の異なる地図の階層構造を効率よく管理するために、当該各地図を経度方向および緯度方向に等間隔に分割した矩形領域毎に作成される。以下、「第1の従来技術」において、かかる矩形領域を以降ではユニットと呼ぶ。

かかる地図ファイルは、典型的には、カーナビゲーションシステムにおいて、経路探索処理または現在位置の補正処理マップマッチング)に用いられる。そのために、地図ファイルには、道路ネットワークデータが記録される。道路ネットワークデータは、少なくとも、各ノードおよび各リンク接続関係を示す接続情報とから構成される。ここで、ノードとは、主として、道路網に存在する交差点を表す情報であり、リンクとは、主として、2つの交差点間に存在する道路を表すベクトル情報である。かかるノードおよびリンクの集合によって、それぞれのユニット内の道路ネットワークを表す地図が表現される。

上記のノード、リンクおよびそれらの接続情報で最小限の道路網を表現することができるが、これだけでは地図を表示する用途には不十分である。例えば、山岳部や臨海部の道路では交差点間の道路が屈曲している場合が多い。そこで、道路ネットワークデータは、屈曲した道路の形状を表示するためにリンク形状を特定するための情報をさらに含む。以上から明らかなように、リンクはベクトルデータで表現されることが多い。また、道路には、国道および県道というように様々な種類がある。他にも、車線数相違または中央分離帯の有無等により道路を分類することができる。かかる道路の種類を区別するために、道路ネットワークデータは、道路の種別等を示す属性情報をさらに含んでいる。また、交差点には、交差点名称が付けられているものや、付けられていないものがある。さらには、信号機が設置されている交差点、信号機が設置されていない交差点がある。そこで、道路ネットワークデータはさらに、ノード毎に属性情報を有している。各属性情報には、対応する交差点の名称および信号機の有無等の情報が記録される。

また、ベクトルデータ構造を有する地図ファイルでは、複数のユニットに跨るような道路が存在する場合には、ユニットの境界に特別なノード(以降、隣接ノードと称す)が別途作成される。かかる隣接ノードを経由することによって、互いに隣接するユニットとの間で道路の接続関係を辿ることができるようになる。従来の地図ファイルでは、あるユニットの隣接ノードが、隣接するユニットのどの隣接ノードと対応するかを特定するために、オフセットアドレスおよびレコード番号が記録されていた。ここで、オフセットアドレスとは、基準アドレスからみて、隣接ノードがどのアドレス位置に記録されているかを示す。また、レコード番号とは、隣接ユニットの地図ファイルにおいて、先頭のノードから起算して隣接ノードが何番目の位置に記録されているかを示す。

「第2の従来技術」「第1の従来技術」で説明したように、従来のナビゲーションシステムは、当初、読み出し専用の記録媒体に記録された地図ファイルしか利用できなかったので、リアルタイム性の高い情報を提供することが困難であった。かかるリアルタイム性の高い情報としては、交通情報または気象情報が代表的である。そのため、リアルタイム性が要求される情報、さらには地図ファイルを提供できる地図提供システムが、例えば、「特開平7−262493号」公報に開示されている。この公報の地図提供システムでは、地図ファイルおよびリアルタイム性の高い情報が、情報提供センターから車載用端末装置へと通信メディアを介してダウンロードされる。

また、地図提供システムは、情報をリアルタイムに提供するために、移動体通信技術とデジタル放送技術とに基づいて構築される。このような地図提供システムでは、センタ局は、サービスエリア内に存在する移動体に対し、所定の放送用チャンネルを用いて情報を配信する。センタ局としては、通信衛星(いわゆるCS)、放送衛星(いわゆるBS)、または地上波ディジタル放送局が典型的である。この移動体通信技術とデジタル放送技術が利用された地図提供システムは、例えば、「特開平7−154350号」公報に開示されている。より具体的には、この公報には、ある情報の放送地域を限定するための技術的内容が開示されている。つまり、センタ局は、多重された情報を、放送メディアを介して送信する際に、各情報に郵便番号のような地域コードを付ける。端末装置は、自身の現在位置に対応する地域コードをIDとして予めメモリ登録しておく。端末装置の内部では、データ抽出回路が、放送局から放送される多重情報を分離して、各情報に付加された地域コードを取り出す。さらに、端末装置の内部では、取り出された地域コードと、登録されたIDとが比較される。両者が一致する場合に、端末装置は、対象となった地域コードが付された情報をユーザに参照させる。

以上のように、通信または放送により地図を提供するような地図提供システムの開発が近年盛んである。この地図提供システムにおいて、センタ局は、端末装置に送信すべき地図ファイルをユニット単位読み出して、当該端末装置に送信する。端末装置は、センタ局からの地図データを受信した後に、記憶装置に格納する。格納された地図ファイルは、必要に応じて、ユーザが参照するため、経路探索処理のため、またはマップマッチング処理のために用いられる。

概要

ある1つが更新された場合に、隣接ユニットの地図ファイルを更新する必要がない地図ファイルを読み出すための端末装置を提供することである。

地図を複数の領域に分割して得られる各ユニットを表す地図ファイルは、ノード毎に作成されるノードレコードと、リンク毎に作成されるリンクレコードとを含む。所定のノードレコードには、ユニットとそれに隣接するユニットとの道路の接続関係を規定する隣接ノードの座標情報が記録される。以上の地図ファイルは、第1の記憶装置19に格納される。前記データ処理部13は、地図ファイルを利用して経路を探索する処理を実行する。データ処理部13は、経路探索処理の最中に、一方のユニットおよび他方の隣接ユニットの隣接ノードが有する座標情報に基づいて、当該一方のユニット内の道路から、当該他方の隣接ユニット内の道路への接続をたどる。

目的

それゆえに、本発明の第1の目的は、ある1つが更新された場合に、隣接ユニットの地図ファイルを更新する必要がない地図ファイルのデータ構造を提供することである。また、本発明の第2の目的は、そのデータ量を圧縮可能な地図ファイルのデータ構造を提供することである。また、本発明の第3の目的は、端末装置内の記憶領域を効率的に利用し、しかもセンタ局と端末装置との間の伝送路を効率的に利用できる地図提供システムを提供することである。

効果

実績

技術文献被引用数
13件
牽制数
20件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

地図を複数の領域に分割して得られる各ユニットデジタルデータ化された地図ファイル記憶装置に格納されており、当該記憶装置から地図ファイルを読み出すための端末装置であって、各前記地図ファイルは、それぞれのユニット内に含まれる道路網ノードリンクとで表すべく、当該ノード毎に作成されるノードレコードと、当該リンク毎に作成されるリンクレコードとを含んでおり、各前記ノードレコードには、前記道路網上の交差点を表す非隣接ノードに関連する情報、または、ユニットとそれに隣接するユニットとの道路接続関係を規定する隣接ノードに関連する情報が記録されており、前記隣接ノードに関連する情報とは、当該隣接ノードの座標情報であり、ユーザの操作に応答して、地図の範囲を指定する情報を生成する入力装置と、前記入力装置により生成された情報に基づいて、必要な地図ファイルの記録領域を特定するデータ処理部と、前記データ処理部により特定された記録領域に基づいて、前記記憶装置から地図ファイルを読み出す読み出し制御部とを備え、前記データ処理部は、前記読み出し制御部により読み出された地図ファイルに記録されたノードレコードおよびリンクレコードを用いて、所定の処理を実行し、一方のユニットおよび他方の隣接ユニットの隣接ノードが有する座標情報に基づいて、当該一方のユニット内の道路から、当該他方の隣接ユニット内の道路への接続をたどる、端末装置。

請求項2

前記リンクレコードには、前記リンクが表す道路の属性を示す属性情報が記録されており、前記データ処理部は、さらに、一方のユニットおよび他方の隣接ユニットの隣接ノードに接続されたリンクの属性情報に基づいて、当該一方のユニット内の道路から、当該他方の隣接ユニット内の道路への接続をたどる、請求項1に記載の端末装置。

請求項3

各前記地図ファイルにおいて、前記隣接ノードに関連する情報を含む各ノードレコードは連続的に記録されている、請求項1に記載の端末装置。

請求項4

前記データ処理部は、他方の隣接ユニットを表す地図ファイルにおいて、隣接ノードに関連する情報を含む各ノードレコードのみを検索して、当該一方のユニット内の道路から、当該他方の隣接ユニット内の道路への接続をたどる、請求項3に記載の端末装置。

請求項5

各前記地図ファイルにおいて、前記隣接ノードに関連する情報を含む各ノードレコードは、連続的にかつ当該隣接ノードの座標昇順または降順になるように記録されている、請求項1に記載の端末装置。

請求項6

前記データ処理部は、他方の隣接ユニットを表す地図ファイルにおいて、隣接ノードに関連する情報を含む各ノードレコードのみを検索して、当該一方のユニット内の道路から、当該他方の隣接ユニット内の道路への接続をたどる、請求項5に記載の端末装置。

請求項7

各前記地図ファイルにおいて、前記隣接ノードに関連する情報を含む各ノードレコードは、連続的にかつ当該各隣接ノードが前記ユニットの境界上を一周するような順序で記録されている、請求項1に記載の端末装置。

請求項8

前記データ処理部は、他方の隣接ユニットを表す地図ファイルにおいて、一方のユニットとの境界上に位置する隣接ノードに関連する情報を含む各ノードレコードのみを、当該各ノードレコードの記録順序と逆方向に検索して、当該一方のユニット内の道路から、当該他方の隣接ユニット内の道路への接続をたどる、請求項7に記載の端末装置。

請求項9

各前記ユニットは、地図を多角形状の領域に分割されており、各前記地図ファイルにおいて、前記ユニットの各辺に位置する隣接ノードに関連する情報を含む各ノードレコードは連続的に記録されている、請求項3に記載の端末装置。

請求項10

前記データ処理部は、他方の隣接ユニットを表す地図ファイルにおいて、当該隣接ユニットの所定の一辺上に位置する隣接ノードに関連する情報を含む各ノードレコードのみを検索して、前記一方のユニット内の道路から、当該他方の隣接ユニット内の道路への接続をたどり、前記隣接ユニットの所定の一辺とは、前記一方のユニット内の隣接ノードが属する辺と接する、請求項9に記載の端末装置。

請求項11

前記ユニットの各辺に位置する隣接ノードに関連する情報を含む各ノードレコードは、当該各隣接ノードの座標情報が昇順または降順に記録されている、請求項9に記載の端末装置。

請求項12

前記データ処理部は、他方の隣接ユニットを表す地図ファイルにおいて、当該隣接ユニットの所定の一辺上に位置する隣接ノードに関連する情報を含む各ノードレコードのみを、当該各ノードレコードの記録順序に従って検索して、前記一方のユニット内の道路から、当該他方の隣接ユニット内の道路への接続をたどり、前記隣接ユニットの所定の一辺は、前記一方のユニット内の隣接ノードが属する辺と接する、請求項11に記載の端末装置。

請求項13

地図を複数の領域に分割して得られる各ユニットがデジタルデータ化された地図ファイルが記憶装置に格納されており、当該記憶装置から地図ファイルを読み出すための端末装置であって、各前記地図ファイルは、自身が表す地図の範囲を一意に対応するファイル名が付けられて前記記憶装置に格納されており、ユーザの操作に応答して、地図の範囲を指定する情報を生成する入力装置と、前記入力装置により生成された情報に基づいて、必要な地図ファイルの記録領域を特定するデータ処理部と、前記データ処理部により特定された記録領域に基づいて、前記記憶装置から地図ファイルを読み出す読み出し制御部とを備える、端末装置。

請求項14

各前記地図ファイルは、それぞれのユニット内に含まれる道路網をノードとリンクとで表すべく、当該ノード毎に作成されるノードレコードと、当該リンク毎に作成されるリンクレコードとを含んでおり、前記データ処理部は、前記読み出し制御部により今回読み出された地図ファイルに記録されたノードレコードおよびリンクレコードを用いて経路を探索する処理を実行し、今回読み出された地図ファイルが表す範囲において、経路の探索が終了すると、さらなる経路の探索に必要な地図の範囲を算出して、算出した地図の範囲に基づいて、次に読み出すべき地図ファイルの記録領域を特定する、請求項13に記載の端末装置。

請求項15

地図を複数の領域に分割して得られる各ユニットがデジタルデータ化された地図ファイルが記憶装置に格納されており、当該記憶装置から地図ファイルを読み出すための端末装置であって、各前記ユニット内に含まれる各背景は、一筆書き可能なオブジェクト単位で分割され、当該複数のオブジェクトは互いに同一の属性を有するもの毎にグループ化され、前記地図ファイルは、各前記グループ毎にオブジェクトに関連する情報が記録される背景レコードを含んでおり、ユーザの操作に応答して、地図の範囲を指定する情報を生成する入力装置と、前記入力装置により生成された情報に基づいて、必要な地図ファイルの記録領域を特定するデータ処理部と、前記データ処理部により特定された記録領域に基づいて、前記記憶装置から地図ファイルを読み出す読み出し制御部と、出力装置とを備え、前記データ処理部は、前記読み出し制御部により読み出された地図ファイルに含まれる背景レコードに基づいて、前記出力装置上に背景を表示させる、端末装置。

請求項16

各前記オブジェクトは、形状を示すための要素点からなっており、各前記背景レコードには、各前記オブジェクトの要素点の座標値が一筆書きされる順番に記録されており、前記要素点の座標値は、前記ユニットにおける原点を基準とした絶対座標値、および他の要素点の座標値を基準とした相対座標値のいずれかで表現される、請求項15に記載の端末装置。

請求項17

各前記オブジェクトにおいてペンダウン位置となる要素点は、所定の条件を満足する場合には相対座標値で表現される、請求項15に記載の端末装置。

請求項18

前記所定の条件は、直前ペンアップ位置からペンダウン位置までの距離が所定値以下である、請求項17に記載の端末装置。

請求項19

前記所定の条件は、ペンダウン位置となる要素点の相対座標値が予め定められたビット数以下で表現されることである、請求項17に記載の端末装置。

請求項20

各前記オブジェクトの要素点は、所定の条件を満足する場合には、直接座標値で表現される、請求項15に記載の端末装置。

請求項21

前記所定の条件は、要素点からその直前の要素点までの距離が所定値以上である、請求項19に記載の端末装置。

請求項22

前記所定の条件は、要素点の座標値を相対座標値で表現した場合に予め定められたビット数を超えることである、請求項19に記載の端末装置。

請求項23

コンピュータ装置による処理のために予め定められたデータ構造を有しており、地図を複数の領域に分割して得られる各ユニットがデジタルデータ化された地図ファイルが記録された記録媒体であって、各前記地図ファイルのユニット内に含まれる道路網を構成するノード毎に作成されるノードレコードと、各前記地図ファイルのユニット内に含まれる道路網を構成するリンク毎に作成されるリンクレコードとを含み、各前記ノードレコードには、前記道路網上の交差点を表す非隣接ノードに関連する情報、または、ユニットとそれに隣接するユニットとの道路の接続関係を規定する隣接ノードの座標を示す座標情報が記録される、前記コンピュータ装置が、ユーザの操作に応答して、地図の範囲を指定する範囲情報を生成し、生成された範囲情報に基づいて、必要な地図ファイルの記録領域を特定し、特定された記録領域に基づいて地図ファイルを読み出し、さらに、読み出された地図ファイルに記録されたノードレコードおよびリンクレコードを用いて経路を探索する処理を実行中に、一方のユニットおよび他方の隣接ユニットの隣接ノードの座標情報に基づいて、当該一方のユニット内の道路から、当該他方の隣接ユニット内の道路への接続をたどる、という処理を実現可能にする地図ファイルが記録された記録媒体。

請求項24

前記リンクレコードには、前記リンクが表す道路の属性を示す属性情報が記録されており、前記コンピュータ装置は、さらに、前記経路を探索する処理の実行中に、一方のユニットおよび他方の隣接ユニットの隣接ノードに接続されたリンクの属性情報に基づいて、当該一方のユニット内の道路から、当該他方の隣接ユニット内の道路への接続をたどる、請求項23に記載の地図ファイルが記録された記録媒体。

請求項25

前記隣接ノードに関連する情報を含む各ノードレコードは連続的に記録されている、請求項23に記載の地図ファイルが記録された記録媒体。

請求項26

前記隣接ノードに関連する情報を含む各ノードレコードは、連続的にかつ当該隣接ノードの座標が昇順または降順になるように記録されている、請求項23に記載の地図ファイルが記録された記録媒体。

請求項27

前記隣接ノードに関連する情報を含む各ノードレコードは、連続的にかつ当該各隣接ノードが前記ユニットの境界上を一周するような順番で記録されている、請求項23に記載の地図ファイルが記録された記録媒体。

請求項28

コンピュータ装置による処理のために予め定められたデータが記録された記録媒体であって、構造を有するしており、地図を複数の領域に分割して得られる各ユニットがデジタルデータ化された地図ファイルが記録された記録媒体であって、地図を複数の領域に分割して得られる各ユニットがデジタルデータ化された地図ファイルと、各前記地図ファイルの名前ツリー構造で表現して、当該各地図ファイルの記録領域を管理する管理情報とを含み、前記コンピュータ装置が、外部から地図の範囲を指定する範囲情報が入力されると、入力された範囲情報に基づいて、必要な地図ファイルの名前を特定し、さらに、前記管理情報を参照して、特定された地図ファイルの名前に一意に対応する記録領域から地図ファイルを読み出す、という処理を実現可能にする地図ファイルが記録された記録媒体。

請求項29

コンピュータ装置による処理のために予め定められたデータ構造を有しており、地図を複数の領域に分割して得られる各ユニットがデジタルデータ化された地図ファイルが記録された記録媒体であって、各前記ユニット内に含まれる各背景は、一筆書き可能なオブジェクト単位で分割されており、各背景の属性を示す情報と、各オブジェクトを描画するために必要な情報が記録されるオブジェクトレコードとを含み、前記背景の属性を示す情報と、当該属性を有するオブジェクトのオブジェクトレコードとが連続して記録され、これによって、複数のオブジェクトは互いに同一の属性を有するもの毎にグループ化され、前記コンピュータ装置が、各前記地図ファイルに含まれる各背景の属性情報とオブジェクトレコードとに基づいて地図を描画する、という処理を実現可能にする、地図ファイルが記録された記録媒体。

請求項30

各前記オブジェクトは、自身の形状を示すための要素点からなっており、各前記オブジェクトレコードには、各前記オブジェクトの要素点の座標値が一筆書きされる順番に記録されており、前記要素点の座標値は、前記ユニットにおける原点を基準とした絶対座標値、および他の要素点の座標値を基準とした相対座標値のいずれかで表現される、請求項29に記載の地図ファイルが記録された記録媒体。

請求項31

各前記オブジェクトにおいてペンダウン位置となる要素点は、所定の条件を満足する場合には相対座標値で表現される、請求項29に記載の地図ファイルが記録された記録媒体。

請求項32

各前記オブジェクトの要素点は、所定の条件を満足する場合には、直接座標値で表現される、請求項29に記載の端末装置。

請求項33

互いに縮尺が異なる複数の地図をそれぞれ、複数の領域に分割して得られる各ユニットがデジタルデータ化された地図ファイルが記憶装置に格納されており、当該記憶装置から地図ファイルを読み出すための端末装置であって、複数の前記地図ファイルは、前記縮尺に応じて階層的な構造を有しており、それぞれのユニット内に含まれる道路網をノードとリンクとで表すべく、当該ノード毎に作成されかつ当該ノードの座標情報が記録されるノードレコードと、当該リンク毎に作成されるリンクレコードとを少なくとも含んでおり、各前記地図ファイルには、ノードの座標情報が昇順または降順になるようにノードレコードが記録されており、地図の範囲を指定する情報を生成する入力装置と、前記入力装置により生成された情報に基づいて、必要な地図ファイルの記録領域を特定するデータ処理部と、前記データ処理部により特定された記録領域に基づいて、前記記憶装置から地図ファイルを読み出す読み出し制御部とを備え、前記データ処理部は、前記読み出し制御部により読み出された地図ファイルに記録された座標情報に基づいて、下位階層のユニットに含まれるノードに対応する上位階層のユニットのノードを検索する、端末装置。

請求項34

データ処理部はさらに、各前記ノードレコードの記録順序に基づいて、下位階層のユニットに含まれるノードに対応する上位階層のユニットのノードを検索する、請求項33に記載の端末装置。

請求項35

センタ局が端末装置に伝送路を通じて地図ファイルを提供するシステムであって、前記センタ局は、予め定められた範囲の地図を表す地図ファイルを記憶する第1の記憶装置と、前記第1の記憶装置から、地図ファイルの一部またはすべてを、地図データとして読み出す読み出し制御部と、前記読み出し制御部により読み出された地図データを用いて、前記伝送路にとって適切な形式パケットを組み立てるパケット組み立て部と、前記パケット組み立て部により組み立てられたパケットを、前記伝送路を通じて前記端末装置に送信する送信部とを備え、前記端末装置は、前記伝送路を通じて、前記送信部により送信されたパケットを受信する受信部と、前記受信部により受信されたパケットを分解して、地図データを復元する処理を実行するデータ処理部と、その内部の記憶媒体に、地図ファイルを記憶する第2の記憶装置とを備え、前記データ処理部は、今回復元した地図データに関連する地図ファイルが前記第2の記憶装置に既に格納されている場合には、当該第2の記憶装置から当該地図ファイルを読み出し、さらに、復元した地図データを、読み出された第2の地図ファイルに追加して、前記第2の記憶装置に格納する処理を実行する、地図提供システム

請求項36

前記データ処理部は、必要に応じて、地図ファイルを複数個作成する、請求項35に記載の地図提供システム。

請求項37

前記地図ファイルは、前記予め定められた範囲の地図が複数の領域に区画された複数のユニットと、各前記ユニットを管理するための管理情報とから構成されており、前記センタ局において、前記読み出し制御部は、前記第1の記憶装置に格納された地図ファイルから、ユニット単位の読み出しを実行し、前記パケット組み立て部は、前記読み出し制御部が読み出したユニットと、地図ファイルを特定するファイルID、当該ユニットを特定するユニットIDおよび当該ユニットのデータサイズとを用いて、パケットを組み立てる、請求項35に記載の地図提供システム。

請求項38

前記データ処理部はさらに、前記受信部により受信されたパケットから、ファイルID、ユニットIDおよびデータサイズを取り出し、取り出されたファイルID、ユニットIDおよびデータサイズを用いて、前記受信部により受信されたパケットを分解して地図データを復元する、請求項37に記載の地図提供システム。

請求項39

前記地図ファイルはさらに、前記予め定められた範囲を概略的に表す基本データと、当該範囲を詳細に表す詳細データとを含み、前記基本データと前記詳細データとは互いに分離可能なデータ構造を有する、請求項35に記載の地図提供システム。

請求項40

前記基本データはさらに、前記地図の背景を表す基本背景データと、当該地図に表示すべき文字および記号を概略的に表す基本文字記号データと、当該地図内に存在する主要幹線道路ネットワークを表す主要幹線ネットワークデータとを含み、前記詳細データはさらに、前記地図の詳細な背景を表す詳細背景データと、当該地図に表示すべき文字および記号を詳細に表す詳細文字記号データと、当該地図内に存在する細街路の道路ネットワークを表す細街路ネットワークデータとを含み、前記詳細背景データ、前記詳細文字記号データおよび細街路ネットワークデータは、前記基本背景データ、詳細文字記号データおよび細街路ネットワークデータの差分データとして構成されており、前記基本データと前記詳細データとが組み合わされることにより、相対的に詳細な地図が表される、請求項39に記載の地図提供システム。

請求項41

前記読み出し制御部はさらに、前記第1の記憶装置に格納された地図ファイルに含まれる基本データのみを、地図データとして読み出す、請求項39に記載の地図提供システム。

請求項42

前記読み出し制御部はさらに、前記記憶装置に格納された地図ファイルに含まれる詳細データのみを、地図データとして読み出す、請求項41に記載の地図提供システム。

請求項43

前記読み出し制御部はさらに、前記第1の記憶装置に格納された地図ファイルに含まれる基本データおよび詳細データを、地図データとして読み出す、請求項39に記載の地図提供システム。

請求項44

前記データ処理部はさらに、前記受信部により受信されたパケットを分解して、基本データを復元する、請求項41に記載の地図提供システム。

請求項45

前記センタ局の前記読み出し制御部はさらに、前記第1の記憶装置に格納された地図ファイルに含まれる詳細データのみを、地図データとして読み出し、前記移動局の前記データ処理部はさらに、前記受信部により受信されたパケットを組み立てて、詳細データを復元する、請求項44に記載の地図提供システム。

請求項46

前記データ処理部はさらに、前記受信部により受信されたパケットを分解して、基本データおよび詳細データを復元する、請求項43に記載の地図提供システム。

--

0001

本発明は、端末装置に関し、より特定的には、地図を複数の領域に分割して得られる各ユニットデジタルデータ化された地図ファイルが内部の記憶装置に格納されており、当該記憶装置から地図ファイルを読み出す端末装置に関する。

背景技術

0002

「第1の従来技術」近年、ナビゲーションシステムが搭載された車両が増加してきている。ナビゲーションシステムでは、当初は、画面上に地図を作成するファイル(以下、地図ファイルと称す)だけが提供されていた。しかし、近年は、地図ファイルに加えて、例えば交通情報および経路案内情報も提供されるようになった。かかる情報の多様化により、ナビゲーションシステムは、より便利になり、今後も急速に普及すると期待されている。

0003

当初、ナビゲーションシステムには、CD−ROMに代表される読み出し専用記録媒体を有する記憶装置が搭載されていた。この記録媒体には、ユーザに提供されるべき地図ファイルと、その関連データとが予め記録されている。記憶装置は、記憶媒体に記録された地図ファイルを、必要に応じて読み出す。読み出された地図ファイルは、ユーザにより参照されたり、経路探索処理またはマップマッチング処理に利用されたりしていた。

0004

一般的にディジタル地図ファイルは、互いに縮尺の異なる地図の階層構造を効率よく管理するために、当該各地図を経度方向および緯度方向に等間隔に分割した矩形領域毎に作成される。以下、「第1の従来技術」において、かかる矩形領域を以降ではユニットと呼ぶ。

0005

かかる地図ファイルは、典型的には、カーナビゲーションシステムにおいて、経路探索処理または現在位置の補正処理マップマッチング)に用いられる。そのために、地図ファイルには、道路ネットワークデータが記録される。道路ネットワークデータは、少なくとも、各ノードおよび各リンク接続関係を示す接続情報とから構成される。ここで、ノードとは、主として、道路網に存在する交差点を表す情報であり、リンクとは、主として、2つの交差点間に存在する道路を表すベクトル情報である。かかるノードおよびリンクの集合によって、それぞれのユニット内の道路ネットワークを表す地図が表現される。

0006

上記のノード、リンクおよびそれらの接続情報で最小限の道路網を表現することができるが、これだけでは地図を表示する用途には不十分である。例えば、山岳部や臨海部の道路では交差点間の道路が屈曲している場合が多い。そこで、道路ネットワークデータは、屈曲した道路の形状を表示するためにリンク形状を特定するための情報をさらに含む。以上から明らかなように、リンクはベクトルデータで表現されることが多い。また、道路には、国道および県道というように様々な種類がある。他にも、車線数相違または中央分離帯の有無等により道路を分類することができる。かかる道路の種類を区別するために、道路ネットワークデータは、道路の種別等を示す属性情報をさらに含んでいる。また、交差点には、交差点名称が付けられているものや、付けられていないものがある。さらには、信号機が設置されている交差点、信号機が設置されていない交差点がある。そこで、道路ネットワークデータはさらに、ノード毎に属性情報を有している。各属性情報には、対応する交差点の名称および信号機の有無等の情報が記録される。

0007

また、ベクトルデータ構造を有する地図ファイルでは、複数のユニットに跨るような道路が存在する場合には、ユニットの境界に特別なノード(以降、隣接ノードと称す)が別途作成される。かかる隣接ノードを経由することによって、互いに隣接するユニットとの間で道路の接続関係を辿ることができるようになる。従来の地図ファイルでは、あるユニットの隣接ノードが、隣接するユニットのどの隣接ノードと対応するかを特定するために、オフセットアドレスおよびレコード番号が記録されていた。ここで、オフセットアドレスとは、基準アドレスからみて、隣接ノードがどのアドレス位置に記録されているかを示す。また、レコード番号とは、隣接ユニットの地図ファイルにおいて、先頭のノードから起算して隣接ノードが何番目の位置に記録されているかを示す。

0008

「第2の従来技術」「第1の従来技術」で説明したように、従来のナビゲーションシステムは、当初、読み出し専用の記録媒体に記録された地図ファイルしか利用できなかったので、リアルタイム性の高い情報を提供することが困難であった。かかるリアルタイム性の高い情報としては、交通情報または気象情報が代表的である。そのため、リアルタイム性が要求される情報、さらには地図ファイルを提供できる地図提供システムが、例えば、「特開平7−262493号」公報に開示されている。この公報の地図提供システムでは、地図ファイルおよびリアルタイム性の高い情報が、情報提供センターから車載用の端末装置へと通信メディアを介してダウンロードされる。

0009

また、地図提供システムは、情報をリアルタイムに提供するために、移動体通信技術とデジタル放送技術とに基づいて構築される。このような地図提供システムでは、センタ局は、サービスエリア内に存在する移動体に対し、所定の放送用チャンネルを用いて情報を配信する。センタ局としては、通信衛星(いわゆるCS)、放送衛星(いわゆるBS)、または地上波ディジタル放送局が典型的である。この移動体通信技術とデジタル放送技術が利用された地図提供システムは、例えば、「特開平7−154350号」公報に開示されている。より具体的には、この公報には、ある情報の放送地域を限定するための技術的内容が開示されている。つまり、センタ局は、多重された情報を、放送メディアを介して送信する際に、各情報に郵便番号のような地域コードを付ける。端末装置は、自身の現在位置に対応する地域コードをIDとして予めメモリ登録しておく。端末装置の内部では、データ抽出回路が、放送局から放送される多重情報を分離して、各情報に付加された地域コードを取り出す。さらに、端末装置の内部では、取り出された地域コードと、登録されたIDとが比較される。両者が一致する場合に、端末装置は、対象となった地域コードが付された情報をユーザに参照させる。

0010

以上のように、通信または放送により地図を提供するような地図提供システムの開発が近年盛んである。この地図提供システムにおいて、センタ局は、端末装置に送信すべき地図ファイルをユニット単位読み出して、当該端末装置に送信する。端末装置は、センタ局からの地図データを受信した後に、記憶装置に格納する。格納された地図ファイルは、必要に応じて、ユーザが参照するため、経路探索処理のため、またはマップマッチング処理のために用いられる。

発明が解決しようとする課題

0011

「第1の従来技術の課題」「第1の従来技術」から明らかなように、従来では、あるユニットの地図ファイルには、隣接ユニットの地図ファイル内部のデータ構造を直接指示する情報(上述のオフセットアドレスまたはレコード番号)が記録されていた。例えば、あるユニット内の道路が新しく造成された場合には、当然、当該ユニットの地図ファイルは更新される。更新された地図ファイルでは、隣接ノードが記録される位置が変わる場合が多い。そのため、従来のような地図ファイル内部のデータ構造を直接指示する方法と採用していれば、隣接ユニットの地図ファイルに記録された隣接ノードから、更新された地図ファイルにおいて対応する隣接ノードを正確にたどれなくなる。つまり、ある1つの地図ファイルが更新されると、隣接ユニットの地図ファイルも更新しなければならない場合が多くなるという問題点があった。

0012

また、上述のディジタル地図ファイルの品質を評価する尺度として、地図の詳細度がある。しかしながら、地図ファイルは、リンクがベクトルデータで表現されることから、詳細な地図を表現しようとすればするほど、当該地図ファイルのデータ量が大きくなるという問題点があった。従来、かかる地図ファイルは、主として、カーナビゲーションシステムにて使用される。カーナビゲーションシステムでは、CD−ROM、DVD−ROMまたはハードディスク等の大容量の記憶媒体に、地図ファイルが記録される。しかし、今後、地図ファイルは、カーナビゲーションシステムだけでなく、人が携帯できるような情報機器においても使用されることが考えられる。かかる携帯型情報機器に、カーナビゲーションシステムのような大容量の記憶媒体を搭載することは難しい。かかる点から、地図ファイルのデータ量を圧縮する必要性は高い。

0013

「第2の従来技術の課題」ところで、「第2の従来技術」の欄で示した各公報は、端末装置が地図ファイルを記憶装置にどのようにして格納するかについて何ら開示していない。容易に想到できるのは、端末装置が、受信したユニット毎の地図ファイルを作成して、作成した地図ファイルを記憶装置に格納するという方法である。しかしながら、この方法では、記憶領域の利用効率が悪くなるという問題点があった。今、例えば、ある範囲を表す地図βが、図71のように、64個の矩形のユニットに区画化されると仮定する。さらに、端末装置が、4個のユニット71から74を受信し格納すると仮定する。また、周知のように、記憶装置の記憶領域は、クラスタ単位で管理される。また、各ユニットのデータサイズは、クラスタのサイズの整数倍に一致するとは限らない。そのため、端末装置が、受信した4個のユニット71〜74について、4個のファイル81〜84を作成すると、図72に示すように、空き領域を有する4個のクラスタ91〜94が発生する場合が多い。図72において、ドットが付された部分は、各ファイル81〜84が記録された領域を示す。また、斜線が付された部分は、空き領域を示す。各クラスタ91〜94に生じた空き領域は使用されない。つまり、たとえ、端末装置が、各ユニット71〜74以外のユニット75(図71参照)を受信したとしても、このユニット75を基に作成されたファイルは、各クラスタ91〜94の空き領域に格納されることはない。以上から明らかなように、端末装置が受信するユニットが多くなればなるほど、空き領域を有するクラスタが多くなる。つまり、記憶領域の利用効率が悪くなる。

0014

ところで、地図が相対的に少数のユニットに区画されれば、空き領域を有するクラスタを発生し難くすることができる。今、図71と同じ範囲の地図βが、図73のように、16個の矩形のユニットに区画されると仮定する。図73のユニット76が表す範囲は、図71のユニット71〜74を併せた範囲に相当する。さらに、端末装置が1個のユニット76を受信し格納すると仮定する。この仮定下では、端末装置は、受信した1個のユニット76について、1個のファイル86を作成すると、図74に示すように、空き領域を有するクラスタ96が1個しか発生しない。図74ドット部分は、ファイル86が記録された領域を示す。また、斜線部分は、空き領域を示す。

0015

以上から明らかなように、地図が小さいユニットに区画された場合(図71参照)、ある範囲を表す地図ファイルが記憶装置に格納されると、相対的に多く空き領域が発生する(図72参照)。しかしながら、地図が大きなユニットに区画された場合には(図73参照)、同じ範囲の地図データが記憶装置に格納されても、発生する空き領域は少ない(図74参照)。つまり、記憶領域の有効利用の観点からは、地図は少数のユニットに区画された方がよい。

0016

しかしながら、地図を少数のユニットに区画するということは、1ユニット当たりのデータ量が大きくなることを意味する。そのため、基地局は、1度に、大量のデータを端末装置に送信しなければならない。その結果、無線伝送路輻輳状態に陥り易くなる、つまり無線伝送路の利用効率が悪くなる、という別の問題点が生じる。つまり、記憶領域を重視すれば、無線伝送路の効率的な利用が難しく、無線伝送路を重視すれば、記憶領域の効率的な利用が難しくなるという問題点があった。

0017

それゆえに、本発明の第1の目的は、ある1つが更新された場合に、隣接ユニットの地図ファイルを更新する必要がない地図ファイルのデータ構造を提供することである。また、本発明の第2の目的は、そのデータ量を圧縮可能な地図ファイルのデータ構造を提供することである。また、本発明の第3の目的は、端末装置内の記憶領域を効率的に利用し、しかもセンタ局と端末装置との間の伝送路を効率的に利用できる地図提供システムを提供することである。

0018

ある1つの発明は、地図を複数の領域に分割して得られる各ユニットがデジタルデータ化された地図ファイルが記憶装置に格納されており、当該記憶装置から地図ファイルを読み出すための端末装置であって、各地図ファイルは、それぞれのユニット内に含まれる道路網をノードとリンクとで表すべく、当該ノード毎に作成されるノードレコードと、当該リンク毎に作成されるリンクレコードとを含んでおり、各ノードレコードには、道路網上の交差点を表す非隣接ノードに関連する情報、または、ユニットとそれに隣接するユニットとの道路の接続関係を規定する隣接ノードに関連する情報が記録されており、隣接ノードに関連する情報とは、当該隣接ノードの座標情報であり、ユーザの操作に応答して、地図の範囲を指定する情報を生成する入力装置と、入力装置により生成された情報に基づいて、必要な地図ファイルの記録領域を特定するデータ処理部と、データ処理部により特定された記録領域に基づいて、記憶装置から地図ファイルを読み出す読み出し制御部とを備え、データ処理部は、読み出し制御部により読み出された地図ファイルに記録されたノードレコードおよびリンクレコードを用いて所定の処理を実行し、一方のユニットおよび他方の隣接ユニットの隣接ノードが有する座標情報に基づいて、当該一方のユニット内の道路から、当該他方の隣接ユニット内の道路への接続をたどる。

0019

上記発明では、データ処理部は、経路探索処理を実行している最中に、ユニットおよび隣接ユニットの隣接ノードの座標情報を基に、当該ユニットおよび当該隣接ユニットの間をまたぐような道路の接続をたどる。このように、データ処理部は、各地図ファイル内部のデータ構造を直接指示する情報を参照することなく、データ処理部は、2つのユニットの間の道路の接続をたどることができる。これによって、記憶装置内のあるユニットの地図ファイルを更新する時、隣接ユニットの地図ファイルを更新する必要がなくなる。

0020

また、他の発明は、地図を複数の領域に分割して得られる各ユニットがデジタルデータ化された地図ファイルが記憶装置に格納されており、当該記憶装置から地図ファイルを読み出すための端末装置であって、各地図ファイルは、自身が表す地図の範囲を一意に特定するファイル名が付けられて記憶装置に格納されており、ユーザの操作に応答して、地図の範囲を指定する情報を生成する入力装置と、入力装置により生成された情報に基づいて、必要な地図ファイルの記録領域を特定するデータ処理部と、データ処理部により特定された記録領域に基づいて、記憶装置から地図ファイルを読み出す読み出し制御部とを備える。

0021

上記発明によれば、各地図ファイルは、自身が表す地図の範囲を一意に特定するファイル名が付けられる。そのため、データ処理部は、それぞれ名前から互いに隣接する地図ファイルを特定することができる。このように、上記発明によれば、各地図ファイルには、隣接するユニットの地図ファイルのデータ構造に関連する情報を記録する必要がなくなるので、複数の地図ファイル間の関係が薄くなる。これによって、ある1つの地図ファイルを更新した場合であっても、それ以外の地図ファイルを更新する必要がなくなる。

0022

また、他の発明は、地図を複数の領域に分割して得られる各ユニットがデジタルデータ化された地図ファイルが記憶装置に格納されており、当該記憶装置から地図ファイルを読み出すための端末装置であって、各ユニット内に含まれる各背景は、一筆書き可能なオブジェクト単位で分割され、当該複数のオブジェクトは互いに同一の属性を有するもの毎にグループ化され、地図ファイルは、各グループ毎にオブジェクトに関連する情報が記録される背景レコードを含んでおり、ユーザの操作に応答して、地図の範囲を指定する情報を生成する入力装置と、入力装置により生成された情報に基づいて、必要な地図ファイルの記録領域を特定するデータ処理部と、データ処理部により特定された記録領域に基づいて、記憶装置から地図ファイルを読み出す読み出し制御部と、出力装置とを備え、データ処理部は、読み出し制御部により読み出された地図ファイルに含まれる背景レコードに基づいて、出力装置上に背景を表示させる。

0023

上記発明によれば、地図ファイルには、同一属性のオブジェクトは同じ背景レコードにまとめて記録されるため、当該属性を示す情報を冗長に記録する必要がなくなるためは、各地図ファイルのデータ量を圧縮することが可能となる。

0024

また、他の発明は、互いに縮尺が異なる複数の地図をそれぞれ、複数の領域に分割して得られる各ユニットがデジタルデータ化された地図ファイルが記憶装置に格納されており、当該記憶装置から地図ファイルを読み出すための端末装置であって、複数の地図ファイルは、縮尺に応じて階層的な構造を有しており、それぞれのユニット内に含まれる道路網をノードとリンクとで表すべく、当該ノード毎に作成されかつ当該ノードの座標情報が記録されるノードレコードと、当該リンク毎に作成されるリンクレコードとを少なくとも含んでおり、各地図ファイルには、ノードの座標情報が昇順または降順になるようにノードレコードが記録されており、地図の範囲を指定する情報を生成する入力装置と、入力装置により生成された情報に基づいて、必要な地図ファイルの記録領域を特定するデータ処理部と、データ処理部により特定された記録領域に基づいて、記憶装置から地図ファイルを読み出す読み出し制御部とを備え、データ処理部は、読み出し制御部により読み出された地図ファイルに記録された座標情報に基づいて、下位階層のユニットに含まれるノードに対応する上位階層のユニットのノードを検索する。

0025

上記発明では、データ処理部は、ノードの座標情報を基に、読み出し制御部により読み出された地図ファイルに記録された座標情報に基づいて、下位階層のユニットに含まれるノードに対応する上位階層のユニットのノードを検索する。このように、データ処理部は、各地図ファイル内部のデータ構造を直接指示する情報を参照することなく、データ処理部は、異なる階層間において同じ座標を有するノードをたどることができる。これによって、記憶装置内のあるユニットの地図ファイルを更新する時、隣接ユニットの地図ファイルを更新する必要がなくなる。

0026

さらに、他の発明は、センタ局が端末装置に伝送路を通じて地図ファイルを提供するシステムであって、センタ局は、予め定められた範囲の地図を表す地図ファイルを記憶する第1の記憶装置と、第1の記憶装置から、地図ファイルの一部またはすべてを、地図データとして読み出す読み出し制御部と、読み出し制御部により読み出された地図データを用いて、伝送路にとって適切な形式パケットを組み立てるパケット組み立て部と、パケット組み立て部により組み立てられたパケットを、伝送路を通じて端末装置に送信する送信部とを備え、端末装置は、伝送路を通じて、送信部により送信されたパケットを受信する受信部と、受信部により受信されたパケットを分解して、地図データを復元する処理を実行するデータ処理部と、その内部の記憶媒体に、地図ファイルを記憶する第2の記憶装置とを備え、データ処理部は、今回復元した地図データに関連する地図ファイルが第2の記憶装置に既に格納されている場合には、当該第2の記憶装置から当該地図ファイルを読み出し、さらに、復元した地図データを、読み出された第2の地図ファイルに追加して、第2の記憶装置に格納する処理を実行する。

0027

上記発明では、データ処理部は、今回復元した地図データと、第2の記憶装置から読み出された地図ファイルとを一まとめにして当該第2の記憶装置に格納し、これによって、地図ファイルを更新する。このようにデータ処理部は、受信部が受信した地図データにのみ基づいて、地図ファイルを作成しない。データ処理部は、今回受信された地図データを、今回読み出された地図ファイルに追加する。そのため、第2の記憶装置は、データ量が小さな地図ファイルを多数格納せずに、あるまとまったデータ量の地図ファイルを格納するので、空き領域を有するクラスタが発生しにくくなる。これによって、端末装置側の記憶領域を効率的に利用できる地図提供システムを実現することができる。

0028

さらに、上記発明では、センタ局が小さいサイズの地図データを送信しても、端末装置がセンタ局から提供された地図データを1ファイルにまとめるので、空き領域を有するクラスタの発生を抑えることができる。このように、第35の発明では、センタ局が小さなサイズの地図データを送信できるので、伝送路が輻輳状態に陥りにくくなる。これによって、伝送路を効率的に利用できる地図提供システムを実現することができる。

発明を実施するための最良の形態

0029

「第1の実施形態」
システム構成図1は、本発明の一実施形態に係る地図提供システムの構成を示すブロック図である。図1において、本地図提供システムには、端末装置1とセンタ局2とが収容される。端末装置1とセンタ局2とは通信網3を通じて双方向通信可能に接続される。より具体的には、端末装置1とセンタ局2との間には、アップリンクULとダウンリンクDLとが張られる。アップリンクULとは、端末装置1からセンタ局2への通信路を意味し、ダウンリンクDLとは、センタ局2から端末装置1への通信路を意味する。ここで、通信網3の典型例としては、携帯電話に代表される移動体通信網ISDN(Integrated ServicesDigital Network)に代表される公衆回線、または専用回線がある。また、通信網3は、移動体通信網、公衆回線および専用回線の内のいずれか2つ以上により構成される場合もある。

0030

次に、端末装置1の構成について説明する。端末装置1は、典型的には、カーナビゲーションシステムにより相当し、入力装置11と、位置検出装置12と、データ処理部13と、要求生成部14と、第1の送受信部15と、アンテナ16と、パケット分解部17と、読み出し/書き込み制御部18と、第1の記憶装置19と、出力装置110とを備える。入力装置11は、カーナビゲーションシステムを遠隔から操作するリモートコントローラまたはカーナビゲーションシステム本体に配列されたキーによりハードウェア的に実現されたり、カーナビゲーションシステムのメニュー画面に表示されたボタンによりソフトウェア的に実現されたりする。さらには、入力装置11は、音声認識技術を駆使して実現される場合もある。端末装置1のユーザは、以上の入力装置11を操作して、端末装置1に対して、表示された地図のスクロールまたは縮尺変更経路探索情報検索、もしくはセンタ局2への接続等、様々な処理の要求を行う。さらに、入力装置11は、特徴的な動作として、ユーザが必要とする地図ファイルCFを特定するための情報をデータ処理部13に出力する。

0031

位置検出装置12は、速度センサジャイロセンサ、またはGPS(Global Positioning System)のアンテナおよび受信機により実現される。また、速度センサ、ジャイロセンサ、ならびにGPS(Global Positioning System)のアンテナおよび受信機のいずれか2つ以上の組み合わせにより、位置検出装置12は実現される場合もある。位置検出装置12は、速度センサにより端末装置1の移動速度を検出して、検出結果を基に走行距離を算出したり、ジャイロセンサにより端末装置1の進行方向を検出したり、アンテナおよび受信機により人工衛星からの電波を受信して、地球上における端末装置1の絶対的な位置を検出したりする。以上の検出結果を基に、位置検出装置12は端末装置1の現在位置を検出する。データ処理部13は、後述する各種のデータ処理を行う。データ処理部13の処理の一つに、入力装置11から入力された情報を基に、ユーザが必要とする地図の範囲を特定する座標を求めて、要求生成部14に出力するという処理がある。要求生成部14は、座標情報が入力されると、ユーザが必要とする地図ファイルCFの送信をセンタ局2に要求するための制御コマンドを生成する。以降、生成された制御コマンドを要求REQと称することとする。要求REQは、予め定められたフォーマットを有しており、要求生成部14に入力された座標情報を少なくとも含む。以上のような要求REQは、第1の送受信部15に出力される。第1の送受信部15は、典型的には、携帯電話に代表される移動体通信装置により実現される。第1の送受信部15は、入力された要求REQを、アンテナ16を通じてアップリンクULに送出する。

0032

要求REQは、アップリンクULを通じて、センタ局2により受信される。センタ局2は、要求REQを解析して、ユーザが必要とする地図ファイルCFを特定する。センタ局2は、特定した地図ファイルCFを第2の記憶装置24から取り出して、複数のパケットPを組み立てる(アセンブリする)。組み立てられたパケットPは、通信網3(ダウンリンクDL)を通じて、順次端末装置1に送信される。なお、センタ局2の処理は後で詳しく説明される。端末装置1において、第1の送受信部15はさらに、アンテナ16を通じてパケットPを受信して、パケット分解部17に出力する。パケット分解部17は、入力されたパケットPを、元の地図ファイルCFに分解(デアセンブリ)して、データ処理部13に出力する。データ処理部13は、地図ファイルCFが入力されると、予め定められた処理を実行して、所定の条件を満たす場合、入力された地図ファイルCFを基に第1のデータベース111を作成して読み出し/書き込み制御部18に出力する。読み出し/書き込み制御部18は、入力された地図ファイルCFを第1の記憶装置19にそのまま書き込んだり、既存の地図ファイルCFと書き換えたりする。なお、一連書き込み処理については後で説明する。第1の記憶装置19は、典型的には、ハードディスクドライブまたはフラッシュメモリに代表される、データの書き換えが可能な記憶装置からなる。第1の記憶装置19には、第1のデータベース111が蓄積される。第1のデータベース111は、本端末装置1がナビゲーションシステムとして機能するために必要な少なくとも1つの地図ファイルCFから構成されるデータの集合体である。また、出力装置110は、典型的には、ディスプレイおよびスピーカからなる。ディスプレイには、地図ファイルCFにより表される地図が現在位置とともに表示されたり、データ処理部13による経路探索処理の結果または経路案内処理の結果が表示されたりする。スピーカは、データ処理部13による経路案内処理の結果が音声によりユーザに提供する。

0033

ところで、データ処理部13は、第1のデータベース111を構成する地図ファイルCFを使って様々な処理を行う。例えば、データ処理部13は、端末装置1の現在位置の表示処理を実行する。この場合、データ処理部13は、位置検出装置12により検出された現在位置周辺の地図が必要となるので、読み出し/書き込み制御部18と協働して、第1のデータベース111から、当該地図を表す地図ファイルCFを検索して取り出す。データ処理部13は、取り出された地図ファイルCFを使って、マップマッチング等の位置補正処理を行う。位置補正処理後、データ処理部13は、取り出した地図ファイルCFが表す地図上に、検出された現在位置を視覚的に示すポインタを重ね合わせて、出力装置110に出力する。また、データ処理部13は、端末装置1のユーザが入力装置11を用いて経路探索処理等を要求した場合には、出発地および目的地付近の地図を表す地図ファイルCF、ならびに探索すべき経路を含む地図を表す地図ファイルCFを読み出して経路探索処理等を行う必要がある。この場合にも、データ処理部13は、読み出し/書き込み制御部18と協働して、第1のデータベース111から、経路探索処理等に必要となる地図ファイルCFを検索して取り出す。なお、一連の地図ファイルCFの読み出し処理については後で説明する。

0034

次に、センタ局2の構成について説明する。センタ局2は、第2の送受信部21と、受信要求解析部22と、読み出し制御部23と、第2の記憶装置24と、パケット組み立て部25とを備える。上述したように、センタ局2には、端末装置1により生成された要求REQが通信網3(アップリンクUL)を通じて送信されてくる。第2の送受信部21は、典型的には、モデムターミナルアダプタ、またはゲートウェイに代表される通信装置からなる。ここで、ゲートウェイとは、異なる通信プロトコルが使用される通信網3にセンタ局2を接続するための装置または機能を意味するだけでなく、他の局が当該センタ局2に不正アクセスすることを防止するための装置または機能を意味する。第2の送受信部21は、通信網3と接続されており、端末装置1からのデータ受信および端末装置1へのデータ送信を制御する。より具体的には、第1のデータ送受信部15は、その一つの機能として、アップリンクULを通じて送信されてきた要求REQを受信して受信要求解析部22に出力する。

0035

受信要求解析部22は、入力された要求REQを解析して、解析結果を読み出し制御部23に出力する。読み出し制御部23は、入力された解析結果を基に、端末装置1が必要とする地図ファイルCFを第2の記憶装置24から読み出す。ここで、第2の記憶装置24は、典型的には、ハードディスクドライブ、CD−ROMドライブまたはDVD−ROMドライブで構成されており、少なくとも蓄積されたデータの読み出しが可能な記録媒体とそのドライバとからなる。第2の記憶装置24は、第2のデータベース25を格納する。第2のデータベース25は、センタ局2が本端末装置1に地図を提供する局として機能するために必要な少なくとも1つの地図ファイルCFから構成されるデータの集合体である。つまり、地図ファイルCFは、端末装置1に提供可能な地図を表現したデジタルデータを意味する。端末装置1側の第1のデータベース111は、センタ局2により提供される地図ファイルCFから作成される。ここで、読み出し制御部23が読み出すのは、地図ファイルCFのすべてである場合もあれば、当該地図ファイルCFの一部である場合もある。読み出し制御部23は、読み出した地図ファイルCFを、パケット組み立て部25に出力する。パケット組み立て部25は、入力された地図ファイルCFを基にパケットPを組み立てて(アセンブリして)、第2の送受信部21に出力する。第3の送受信部21は、ダウンリンクDLを通じて、入力されたパケットPを端末装置1に送信する。

0036

以上、本実施形態に係る地図提供システムの全体構成、ならびに端末装置1およびセンタ局2の構成について説明した。次に、上述の地図ファイルCFの階層構造およびファイル名について詳細に説明する。

0037

「階層構造およびファイル名」図2は、本実施形態に係る地図ファイルCFにより表現される地図の階層構造を説明するための図である。図2に示すように、まず、互いに縮尺の異なる複数種類の地図が準備される。本実施形態では、便宜上、4段階の縮尺の地図が準備されると仮定する。以降の説明では、最大縮尺をレベル「0」、2番目に大きな縮尺をレベル「1」、3番目に大きな縮尺をレベル「2」、最小縮尺をレベル「3」と称する。以上から分かるように、地図データは、最大縮尺をレベル「0」として、レベル「0」〜「3」の4階層から構成される。さらに、レベルが高いものを上位階層の地図と称し、レベルが低いものを下位階層の地図と称する。したがって、図2に示すように、上位階層の地図ほど、広域でかつ詳細度が低い。逆に、下位階層の地図ほど、狭域でかつ詳細度が高い。また、各階層の地図は、経度方向および緯度方向に沿って等間隔に区切られる。

0038

ここで、図3は、最上位階層(レベル「3」)のユニットを説明するための図である。図3世界地図は、緯度0度を基準として、当該緯度方向に沿って5度20分毎に区切られる。さらに、この世界地図は、経度0度を基準として、当該経度方向に沿って約8度毎に区切られる。その結果、世界地図は、約640km四方の矩形領域に分割される。最上位階層(レベル「3」)においては、約640km四方の矩形領域をユニットと称する。レベル「3」においては、かかる約640km四方のユニットがデジタルデータ化されることにより、1つの地図ファイルCFが作成される。以上のような、最上位階層(レベル「3」)のユニットを代表して、ユニットU3 (ハッチングを付した部分)について説明する。最上位階層(レベル「3」)のユニットU3 は、日本の関西を含むユニットであり、緯度0度、経度0度の位置を原点として、東経方向に数えて16番目、北緯方向に数えて6番目に位置する(ただし、原点を含むユニットは0番目と数える)。以上のユニットU3 が、図2の最上段に示されている。

0039

図2に示すように、ユニットU3 の地図は、一つの頂点を基準として、点線で示すように、緯度方向に沿って40分毎に区切られる。さらに、ユニットU3 の地図は、上記と同じ頂点を基準として、点線で示すように、当該経度方向に沿って1度毎に区切られる。その結果、ユニットU3 の地図は、約80km四方の矩形領域に64分割される。約80km四方の各矩形領域を詳細に表した地図が、1階層下(つまり、レベル「2」の階層)における1つのユニットとなる。レベル「2」の階層のユニットを代表して、ユニットU2 (ハッチングを付した部分)について説明する。かかるユニットU2 は、ユニットU3 内の1つの頂点(便宜上、左下の頂点とする)の位置を原点として、東経方向に数えて4番目、北緯方向に数えて1番目に位置する(ただし、原点を含むユニットUは0番目と数える)。レベル「2」の階層のユニットU2 が、図2の2段目に示されている。

0040

同様に、ユニットU2 の地図は、一つの頂点を基準として、緯度方向に沿って5分毎に、さらに経度方向に沿って7分30秒毎に区切られ、その結果、約10km四方の矩形領域に64分割される。約10km四方の各矩形領域を詳細に表した地図が、1階層下(つまり、レベル「1」の階層)における1つのユニットとなる。その内の一つであるユニットU1 (ハッチングを付した部分)は、ユニットU2 の左下の頂点を原点として、東経方向に数えて5番目、北緯方向に数えて3番目に位置する(ただし、原点を含むユニットは0番目と数える)。レベル「1」のユニットU1 が、図2の上から3段目に示されている。

0041

同様に、ユニットU1 の地図は、約1.2km毎四方の矩形領域に64分割される。約1.2km四方を詳細に表した各地図が、1階層下(つまり、レベル「1」の階層)における1つのユニットUとなる。その内の一つであるユニットU0 (ハッチングを付した部分)は、ユニットU1 の左下の頂点を原点として、東経方向に2番目、北緯方向に1番目に位置する(ただし、原点を含むユニットは0番目と数える)。レベル「0」のユニットU0 が、図2の上から4段目に示されている。

0042

図4は、レベル「3」〜「0」のそれぞれの階層間におけるユニットUの親子関係を説明するための図である。まず、以下の説明において、子ユニットCUとは、ある1つのユニットUがカバーする範囲に包含される、下位階層の全てのユニットを意味する。言い換えれば、子ユニットCUとは、上位階層のある1つのユニットUが表す地図の一部分を表すユニットUの集合である。逆に、親ユニットPUとは、あるユニットUのカバーする範囲を包含する、上位階層の全てのユニットを意味する。言い換えれば、親ユニットPUとは、下位階層のある1つのユニットUが表す地図を、自身が表す地図の一部として含んでいるユニットUの集合である。ここで、図4中のユニットU3 は、図2に示すユニットU3 に相当しており、レベル「3」のユニットの一つである。ユニットU3 を親ユニットPU3 とするレベル「2」のユニットU、すなわちユニットU3 の子ユニットCUの内、レベル「2」に属するものは、ユニットU3 を経度および緯度方向にそれぞれ8等分してできる64個のユニットUとなる。

0043

このように、親ユニットPUに対しては、1階層下に64個の子ユニットCUができる。各子ユニットCUには位置コード割り当てられる。位置コードとは、子ユニットCUが表す地図が、親ユニットPUのどの部分に相当するかを特定するための情報である。言い換えれば、位置コードとは、親ユニットPUを基準とした子ユニットCUの位置を特定するための情報である。今、親ユニットPUが図4ユニットU3 であるとする。かかる場合、ユニットU3 の左下隅の地図を詳細に表す子ユニットCUには、位置コードとして「0000」が割り当てられる。この位置コード「0000」を基準値として、子ユニットCU(位置コード「0000」)に対して、東経方向に沿って隣接する子ユニットCUには「0100」が割り当てられる。以下同様に、子ユニットCUが東経方向に1つ移るたびに、位置コードは、「0100」だけ増加する.また、位置コード「0000」を基準値として、子ユニットCU(位置コード「0000」)に対して、北緯方向に沿って隣接する子ユニットCUには「0001」が割り当てられる。以下同様に、子ユニットCUが北緯方向に1つ移るたびに、位置コードは、「0001」だけ増加する。以上のように割り当てられる位置コードに従えば、ユニットU3 の子ユニットCUの一つであるユニットU2 の位置コードは「0401」である。

0044

次に、親ユニットPUがユニットU2 であると仮定する。このユニットU2 に対しても、1階層下(レベル「1」)には64個の子ユニットCUができる。レベル「1」の64個の子ユニットCUに対しても、図4に示すように、上述と同様の方法で位置コードが割り当てられる。例えば、ユニットU2 の子ユニットCUの一つであるユニットU1 の位置コードは「0503」である。また、親ユニットPUとしてのユニットU1 に対しても、1階層下(レベル「0」)には、64個の子ユニットCUができる。レベル「0」の各子ユニットCUに対しても、図4に示すように、同様に位置コードが割り当てられる。例えば、ユニットU1 の子ユニットCUの一つであるユニットU0 の位置コードは「0201」である。

0045

以上のように、本実施形態に係る位置コードでは、東経方向への値の増分および北緯方向への値の増分が予め定められている。そのため、子ユニットCU同士の隣接関係を簡単に把握することができる。

0046

ところで、図1に示す端末装置1およびセンタ局2にはそれぞれ、ファイルシステムが搭載される。端末装置1側のファイルシステムは、データ処理部13および読み出し/書き込み制御部18により構成される。端末装置1側のファイルシステムは、第1の記憶装置19内の第1のデータベース111を容易に管理すべく、第1の記憶装置19が有する記録領域を「ディレクトリ」と呼ばれるいくつかの論理領域に分割する。さらに、端末装置1側のファイルシステムは、第1のデータベース111を構成する地図ファイルCFの親子関係および隣接関係を、ツリー構造に基づくディレクトリ名およびファイル名により表す。また、センタ局2側のファイルシステムは、受信要求解析部22および読み出し制御部23により構成される。センタ局2側のファイルシステムは、第2の記憶装置24内の第2の地図ファイル24の記憶領域を「ディレクトリ」(論理領域)に分割し、さらに、第2のデータベース25を構成する地図ファイルCFの親子関係および隣接関係を、ツリー構造に基づくディレクトリ名およびファイル名により表す。

0047

以下、図5は、図2図4に示す地図ファイルCFを管理するためのツリー構造を示す図である。上述したように、各ファイルシステムの各ディレクトリは、図5に示すようなツリー構造をとり、「¥」マークにより表される。「¥」マークは、ディレクトリを識別するための識別子である。また、最上部のディレクトリは、ルートと呼ばれ、「¥MAP」で表される。ルートディレクトリ「¥MAP」の下のディレクトリには、地図ファイルCFそのものまたはサブディレクトリを格納することができる。ここで、ファイルシステムは、必要な地図ファイルCFを指定する際、ファイル名の前にルート「¥MAP」から当該地図ファイルCFが存在するディレクトリまでに介在するディレクトリ名を「パス」として記述する必要がある。したがって、2つの「¥」マークで挟まれた文字列がディレクトリ名を表すこととなる。サブディレクトリ名の頭文字は「D」と定義される。また、ファイル名の頭文字は「M」と定義される。さらに、ファイル名の拡張子は「.map」と定義される。

0048

さて、次に、本実施形態の一つの特徴である、ディレクトリ名およびファイル名を割り当て方法を説明する。まず、原則として、最上位階層の各ユニットがカバーする地図を表す地図ファイルCFは、所定の規則に従ってファイル名が付けられ、ルート(「¥map」)の直下のディレクトリ(論理領域)に格納される。例えば、図3に示すユニットU3 は、最上位の階層(レベル「3」)に属しており、原点(緯度0度、経度0度)を基準として、東経方向に数えて16番目、北緯方向に6番目(ただし、原点を含むユニットはそれぞれ0番目と数える)のユニットに該当する。そのため、ユニットU3 には、ファイル名の頭文字および拡張子を含めて「M1606.map」という名前が付けられる。さらに、最上位階層のユニットU3 は、ルート(「¥map」)の直下に格納されるので、パスは、「¥MAP¥M1606.map」となる。以上のユニットU3 のファイル名から分かるように、ファイル名の頭文字および拡張子の間には、4桁の数字が並ぶ。上位2桁の数字は、ユニットUが原点から東経方向に数えて何番目に位置するかを規定する。また、下位2桁の数字は、ユニットUが原点から北緯方向に数えて何番目に位置するかを規定する。このように、ファイル名は、ユニットUの位置を規定する。また、ユニットU3 のパスから分かるように、ルート(「¥map」)からファイル名に至るまでにはサブディレクトリが介在しない。このように、サブディレクトリの個数は、ユニットUがどの階層に属しているかを規定する。ユニットU3 の場合には、ルートとファイル名との間に介在するサブディレクトリの個数が「0」であることにより、ユニットU3 (M1606.map)が最上位階層に属することが分かる。以上の規則に従うと、他の最上位階層のユニットUのためのパスは、「¥MAP¥M0000.map」,「¥MAP¥M0001.map」,…「¥MAP¥M1606.map」…等のように表される。

0049

また、最上位階層のユニットUを親ユニットPUとするユニットのグループを格納するためのサブディレクトリがルートの直下に作成される。例えば、ユニットU3 を親ユニットPUとするユニットUのグループを格納するために、「¥D1606」と名付けられたサブディレクトリがルートの直下に作成される。以上のサブディレクトリ名から分かるように、サブディレクトリ名の頭文字には4桁の数字が続く。この4桁の数字は、ファイル名の場合と同様に、親ユニットPUが原点から東経方向および北緯方向に数えてそれぞれ何番目に位置するかを表す。そのため、ルート(「¥MAP」)の直下には、「¥D0000」、「¥D0001.map」,…,「¥1606」,…が作成される。

0050

次に、レベル「2」の階層に属する各ユニットUは、位置コードに基づくファイル名が付けられ、自身の親ユニットPUを表すサブディレクトリの直下のディレクトリ(論理領域)に格納される。例えば、ユニットU3 を親ユニットPUとするレベル「2」のユニットUは、図4等を参照すると64個ある。その内の一つであるユニットU2 は、位置コードが「0401」であるため、ファイル名の頭文字および拡張子を含めて「M0401.map」という名前が付けられる。さらに、レベル「2」のユニットU2 は、ユニットU3 (親ユニットPU)のサブディレクトリ(「¥map¥D1606」)の直下に格納されるので、パスは、「¥MAP¥D1606¥M0401.map」となる。以上のユニットU2 のファイル名から分かるように、レベル「2」のユニットUのファイル名の頭文字および拡張子の間には、上述した位置コードが並ぶ。そのため、レベル「2」のユニットUのファイル名もまた、当該ユニットUの位置を規定することとなる。また、ユニットU2 のパスから分かるように、ルート(「¥map」)からファイル名に至るまでにはサブディレクトリが1つだけ介在する。サブディレクトリの個数は、ユニットUがどの階層に属しているかを規定する。ユニットU2 の場合には、ルートとファイル名との間に介在するサブディレクトリの個数が「1」であることにより、当該ユニットU2 (M0401.map)がレベル「2」の階層に属することが分かる。以上の規則に従うと、他のレベル「2」のパスは、「¥MAP¥D0000¥M0000.map」,「¥MAP¥D0000¥M0001.map」,…,「¥MAP¥D0000¥M0007.map」,「¥MAP¥D0000¥M0100.map」,…「¥MAP¥D0000¥M0707.map」,「¥MAP¥D0001¥M0000.map」,…「¥MAP¥D1606¥M0001.map」,…,「¥MAP¥D1606¥M0401.map」,…「¥MAP¥D1606¥M0707.map」,…等のように表される。

0051

同様に、レベル「2」のユニットU2 を親ユニットPUとするユニットのグループは、サブディレクトリ「¥D0401」の下のディレクトリ(論理領域)の下に格納されることになる。例えば、ユニットU1 は、ユニットU2 の子ユニットCUの一つであって、当該ユニットU2 が64分割されたユニットUの内、位置コード「0503」に該当するユニットである。そのため、ユニットU1 のためのパスは、「¥MAP¥D1606¥D0401¥M0503.map」と表される。同様に、ユニットU2 を親ユニットPUとするレベル「1」の各ユニットのパスは、「¥MAP¥D1606¥D0401¥M0000.map」、「¥MAP¥D1606¥D0401¥M0001.map」,…,「¥MAP¥D1606¥D0401¥M0707.map」で表される。

0052

さらに、ユニットU1 を親ユニットPUとするユニットUのグループは、「¥MAP¥D1606¥D0401¥D0503」と表されるサブディレクトリの直下のディレクトリ(論理領域)に格納される。かかるグループに属するユニットU0 は、ユニットU1 が64分割されたユニットUの内、位置コード「0201」に該当するユニットである。そのため、ユニットU0 のパスは、「¥MAP¥D1606¥D0401¥D0503¥M0201.map」と表される。同様に、ユニットU1 を親ユニットPUとするレベル「0」の各ユニットのパスは、「¥MAP¥D1606¥D0401¥D0503¥M0000.map」,「¥MAP¥D1606¥D0401¥D0503¥M0001.map」,…「¥MAP¥D1606¥D0401¥D0503¥M0707.map」で表される。

0053

以上、地図ファイルCFにより実現される階層構造およびファイル名について説明した。ここで、以上のユニットUがデジタルデータ化され、必要な管理情報が付加されることにより、1つの地図ファイルCFが構成される(詳細は図7を参照)。以下の説明において、ユニットデータは、ユニットUをデジタルデータ化したものを意味する。つまり、1つの地図ファイルCFには、1つのユニットデータが含まれる。次に、地図ファイルCFのデータ構造について詳細に説明する。

0054

「地図ファイルCFのデータ構造」図6は、1つの地図ファイルCFを基に描かれる地図を説明するための図である。また、図7は、1つの地図ファイルCFのデータ構造を示している。図7において、地図ファイルCFは、大略的に、ユニットヘッダとユニットデータとから構成される。まず、ユニットデータから説明する。一般的に、地図は、用途に応じて、図7に示すように、背景、道路、地図記号および文字から構成される。しかし、地図ファイルCFは、主として、端末装置1のディスプレイ上への表示、マップマッチングまたは経路探索処理に使用される。例えば、経路探索処理では、道路のつながりが分かればよく、背景の必要性は薄い。そこで、1つのユニットデータは、図6に示すように、文字記号データと、道路ネットワークデータと、背景データとに分けてデータ化される。これによって、文字記号データ、道路ネットワークデータおよび背景データはそれぞれ、独立的に使用することができる。文字記号データとは、ユニットUがカバーする地図に記載されるべき文字列(地名および交差点名称等)からなるデータと、当該地図に記載されるべき地図記号からなるデータとを意味する。道路ネットワークデータとは、ユニットUがカバーする地図に表されるべき道路そのものおよび道路同士のつながりを表す図形データを意味する。背景データとは、水系、山系、建造物等、ユニットUがカバーする地図に表されるべき背景を表す図形データを意味する。背景の例としては、河川、山、緑地帯鉄道、建造物、橋、公園がある。以上の文字記号データ、道路ネットワークデータおよび背景データを重ねあわせて表示することにより、図6に示すように、ユニットデータは、背景、道路、地図記号および文字を表すことができる。

0055

次に、背景データの詳細なデータ構造を、図7および図8を参照して説明する。図7に示すように、背景データは、基本背景テーブルおよび詳細背景テーブルから構成される。基本背景テーブルは、図8(a)から明らかなように、河川、鉄道および緑地帯等、地図の背景を表示する際に概略となる図形データを集合である。一方、詳細背景テーブルは、図8(b)から明らかなように、橋および建造物等、地図の背景をより詳細に表示するための図形データの集合である。これら基本背景テーブルおよび詳細背景テーブルは、図7から明らかなように、ユニットデータにおいて互いに別々に記録される。さらに、基本背景テーブルおよび詳細背景テーブルには、相互に参照し合うような情報は記録されない。つまり、基本背景テーブルを構成する背景データを描いている際に、詳細背景テーブルの背景データは何一つ参照されない。逆に、詳細背景テーブルを構成する背景データを描いている際に、基本背景テーブルの背景データは何一つ参照されない。このように、基本背景テーブルおよび詳細背景テーブルは、相互に独立したデータ構造を有する。したがって、背景をディスプレイ上に表示する場合には、図8(a)に示すように、基本背景テーブルのみで表される背景を表示することが可能になる。これによって、端末装置1のユーザは、概略的な地図を見ることが可能になる。また、図8(c)に示すように、基本背景テーブルおよび詳細背景テーブルで表される背景を表示することもできる。この場合、所定の原点を基準として、基本背景テーブルから得られる概略的な背景の上に、詳細背景テーブルから得られる詳細な背景を重ねあわせることとなる。これによって、端末装置1のユーザは、詳細な地図を見ることが可能となる。なお、本実施形態では、背景データは基本背景テーブルおよび詳細背景テーブルとから構成されるとして説明したが、第1の記憶装置19または第2の記憶装置24に記憶容量の制限がある場合等には、第1のデータベース111または第2のデータベース25を小さいサイズにする観点から、背景データは基本背景テーブルのみから構成されてもよい。逆に、本実施形態で説明したように、背景データは基本背景テーブルおよび詳細背景テーブルとから構成される場合には、センタ局2は、詳細な地図を端末装置1に提供することが可能となり、当該端末装置1は詳細な地図をディスプレイに表示できるようになる。

0056

上述の基本背景テーブルおよび詳細背景テーブルの内部のデータ構造は互いに同じである。以下には、基本背景テーブルおよび詳細背景テーブルを背景テーブルと総称して、双方のデータ構造についてより詳細に説明する。上述したように、背景テーブルは、地図の背景をディスプレイ上に描画するために使用される図形データの集合である。各図形データによって、河川、公園、工場および鉄道等がディスプレイ上に描画される。以下、これら地図の背景の要素となる、河川、公園、工場および鉄道等を総称して「描画オブジェクト」と呼ぶこととする。ここで、図9は、描画オブジェクトの概念を示す図である。上述から明らかなように、描画オブジェクトは、公園または工場等のように、それ自体で意味のあるひとまとまり対象物のを表し、データ構造としては、対象物を折れ線で描画するための要素点の並びから構成される。例えば、図9には、矩形領域のユニットUが示されている。ユニットUがカバーする範囲には、2つの描画オブジェクトDO1およびDO2が存在する。描画オブジェクトDO1は、オブジェクトOBJ1とO2とから構成される。オブジェクトOBJ1は、要素点a→要素点b→要素点c→要素点d→要素点e→要素点aの順番に一筆書きした時に作成される折れ線で囲まれる領域である。また、オブジェクトOBJ2は、要素点f→要素点g→要素点h→要素点i→要素点fの順番に一筆書きした時に描かれる折れ線で囲まれる領域である。また、描画オブジェクトDO2は、オブジェクトOBJ3から構成される。オブジェクトOBJ3は、要素点j→要素点k→要素点l→要素点m→要素点n→要素点jの順番に一筆書きした時に描かれる折れ線で囲まれる領域である。以上から明らかなように、本実施形態の描画オブジェクトは、複数の要素点を一筆書きして得ることができる1つ以上のオブジェクトにより表される。

0057

ここで、図10は、背景テーブル、つまり基本背景テーブルまたは詳細背景テーブルの詳細なデータ構造を示す図である。図10において、背景テーブルには、背景レコード数Mと、M個の背景レコードBR1〜BRMとから構成される。ここで、Mは、1以上の自然数である。背景レコード数Mは、背景テーブルに含まれる背景レコードBR1〜BRMの個数を示す情報である。また、背景レコードBR1は、背景属性と、オブジェクト数Nと、オブジェクトOBJ1〜ONの要素点数N1〜NNと、オブジェクトレコードOR1〜ORNとから構成される。背景属性は、背景レコードBR1内に含まれる各オブジェクトOBJにより表される背景の属性を示す情報である。より具体的には、背景属性は、背景レコードBR1内に含まれる各オブジェクトOBJのカラーコードおよびテクスチャーマッピングコードである。ここで、本実施形態の一つの特徴として、背景属性には、1つのカラーコードまたはテクスチャマッピングコードのみが記述される。つまり、例えば、「青」を示すカラーコードと、「赤」を示すカラーコードとが一緒に背景属性に記述されることはない。「青」を示すカラーコードのみ、または「赤」を示すカラーコードのみが背景属性に記述される。

0058

また、オブジェクト数Nは、背景レコードBR1内に含まれるオブジェクトOBJの数を示す情報である。また、要素点数N1は、オブジェクトOBJ1を構成する要素点の数を示している。要素点数N2は、オブジェクトOBJ2を構成する要素点の数を示している。以降、同様に、要素点数NNは、オブジェクトOBJNの要素点の数を示す。このように、背景レコードBR1には、そこに含まれるN個のオブジェクトOを構成する要素点の数が並ぶ。ここで、Nは1以上の自然数である。

0059

さらに、オブジェクトレコードOR1は、1つのオブジェクトOBJ1を構成する要素点の座標を示す情報である。ここで注意を要するのは、オブジェクトOBJ1は複数の要素点を含むので、オブジェクトレコードOR1には複数の座標情報が並ぶこととなる。つまり、オブジェクトレコードOR1には座標列の情報が記述される。ここで、上述から明らかなように、オブジェクトレコードOR1には、要素点数N1に相当する個数の座標情報が記述される。また、オブジェクトレコードOR2は、オブジェクトOBJ2を構成する要素点の座標列を示す情報である。オブジェクトレコードOR2には、要素点数N2に相当する個数の座標情報が記述される。以降、同様に、オブジェクトレコードORNは、オブジェクトOBJNを構成するNN個の要素点の座標列を示す情報である。オブジェクトレコードORNには、要素点数NNに相当する個数の座標情報が記述される。

0060

以上のように、各オブジェクトレコードORには、オブジェクトOBJを構成する要素点の座標列が記述される。座標列の表現方法としては、ユニットU内での絶対座標で表現する方法と、ある要素点の座標と直前の要素点の座標との差分を用いた相対座標で表現する方法とがある。絶対座標は、ユニットU内の所定の原点を基準とした各要素点の座標であるため、多くのビット数を必要とする。そのため、座標列の表現方法として、相対座標が使用されることが、地図ファイルCFのデータサイズを小型化する観点から、好ましい。以下、絶対座標と相対座標とについて、詳細に説明する。

0061

図11は絶対座標が多くのビット数を必要とすることを説明するための図である。図11には、8個の要素点P0〜P7で構成される図形データが示されている。要素点P0の絶対座標は、予め定められた原点を基準として、(X0,Y0)である。以降、同様に、要素点P1〜P7の絶対座標は、(X1,Y1)〜(X7,Y7)である。また、図12は、以上のP0〜P7の各絶対座標情報をオブジェクトレコードORに記述した時の図である。今、要素点P0〜P7の絶対座標は、東経方向(x軸方向)および北緯方向(y軸方向)それぞれについて、例えば2バイトで表現すると、P0〜P7の各絶対座標情報をオブジェクトレコードORに記述するためには、32バイトが必要となる。

0062

一方、図13は、図11と同じ図形データの各要素点P0〜P7を相対座標で表現した時の図である。図12において、図形データは、要素点P0→P1→P2→P3→P4→P5→P6→P7の順番で一筆書きされる。相対座標表現であっても、一筆書きされる最初の要素点P0は、絶対座標表現と同様に、所定の原点を基準として、(X0,Y0)で表される。ただし、次の要素点P1は、絶対座標表現の場合には、(X1,Y1)と表される。しかし、相対座標表現では、要素点P1は(ΔX1,ΔY1)で表される。ここで、ΔX1は、ΔX1=X1−X0である。また、ΔY1は、ΔY1=Y1−Y0である。以降の要素点P2〜P7も、それぞれの要素点の絶対座標と、直前の要素点の絶対座標との差分により表現される。図14は、以上の要素点P0〜P7の各相対座標情報をオブジェクトレコードORに記述した時のデータ構造を示す図である。ここで注意を要するのは、相対座標表現は、それぞれの要素点の絶対座標と、直前の要素点の絶対座標との差分で表されるため、ΔX1≪X1,ΔX2≪X2,…ΔX7≪X7となる。同様に、ΔY1≪Y1,ΔY2≪Y2,…ΔY7≪Y7となる。そのため、要素点P1〜P7の相対座標は、東経方向(x軸方向)および北緯方向(y軸方向)それぞれについて2バイトで表現するのではなく、それぞれ1バイトで表現する。その結果、要素点P1〜P7の各相対座標情報をオブジェクトレコードORに記述するためには、14バイトが必要となる。ただし、最初の要素点P0は、絶対座標で記述される必要があるので、要素点P0〜P7の各座標情報をオブジェクトレコードORに記述するためには、差分数(「7」)の情報を含めて、19バイトが必要となる。

0063

以上、図11図14を参照して説明したように、オブジェクトOBJを構成する各要素点Pを相対座標を使って表現すると、絶対座標表現のみを用いた場合と比較して、オブジェクトレコードORのサイズが小さくなる。しかしながら、オブジェクトOBJを構成する各要素点を無条件に相対座標で表現すると、データサイズの小型化を実現できない場合が生じるという問題点が想定できる。かかる問題点を、図15を参照して説明する。図15には、要素点P0、P1およびPnで構成されるオブジェクトOBJが示されている。今、要素点P1は、相対座標では(ΔX1,ΔY1)で表される。ΔX1およびΔY1の双方は、1バイトで表現できるとする。同様に、要素点Pnは、相対座標では(ΔXn,デルタYn)で表される。しかしながら、ΔXnおよび/またはΔYnは、要素点Pnが直前の要素点P1から離れた位置にあるため、1バイトでは表現しきれない値であると仮定する。このような場合、図16に示すように、要素点P1およびPnを結ぶ直線上に、新しい要素点P2およびP3を作成する必要が生じる。これによって、要素点Pnの相対座標は、直前の要素点P3の絶対座標を基に、(ΔX4,ΔY4)で表すことができる。ΔX4およびΔY4は、要素点P3が要素点P1と比べて要素点Pnの近くに位置するため、1バイトで表現できる。以上の要素点P0,P1,P2,P3およびPnの各相対座標情報をオブジェクトレコードORに記述すると、図17に示すように、13バイト必要となる。

0064

以上、図15図17を参照して説明したように、2個の要素点Pが離れて位置している場合には、新しい要素点Pを補う必要が生じる。その結果、オブジェクトレコードORには、補った要素点Pの相対座標情報を記述しなければならない。このように、最初の要素点Pを除くすべての要素点Pを相対座標で表現しようとすると、要素点Pの数が不必要に多くなり、オブジェクトレコードORのデータサイズが不必要に大きくなるという問題点が顕在化してくる。そこで、図15の要素点P0およびPnを絶対座標で表現し、要素点P1を要素点P0を基準とした相対座標で表現することが有効となる。今、要素点Pnの絶対座標は、4バイトで表現できる(Xn,Yn)であると仮定して、要素点P0,P1およびPnの各座標情報をオブジェクトレコードORに記述すると、図18に示すようになる。図18において、要素点P0およびPnの絶対座標情報はそれぞれ4バイトであり、要素点P1の相対座標情報は2バイトである。さらに、絶対座標で表されたP0およびPnを基準として、いくつの相対座標が作成されているかを示す差分数の情報は2バイトである。以上の合計をとると、オブジェクトレコードORのデータサイズは12バイトとなる。このデータサイズは、相対座標だけで表現した場合のオブジェクトレコードORのデータサイズ13バイト(図17参照)よりも小さい。

0065

以上、図18を参照して説明したように、その直前の要素点と離れて位置する要素点は絶対座標で表現される。このように、本実施形態では、ある要素点は、主として相対座標で表現されるが、他の要素点は絶対座標で表現される。これによって、オブジェクトレコードORのデータサイズをより小さくすることが可能となる。

0066

また、上述したように、本実施形態では、オブジェクトの境界にも、相対座標表現が適用される。ここで、オブジェクトの境界とは、あるオブジェクトOBJを構成する1つの要素点Pからペンアップして、他のオブジェクトOBJを構成する1つの要素点Pにペンダウンする部分を意味する。かかる相対座標表現の適用によって、本実施形態は、背景テーブルのデータサイズを小型化できるという技術的効果を奏する。以下には、まず、かかる技術的効果を明確にするために、オブジェクトの境界に相対座標表現が適用されない場合について、図19および図20を参照して説明する。図19には、描画オブジェクトDO3が示されている。描画オブジェクトBO3は、オブジェクトOBJ3およびOBJ4から構成される。オブジェクトOBJ3は、6個の要素点P0〜P5から構成される。また、オブジェクトOBJ4は、4個の要素点P6〜P9から構成される。

0067

以上のオブジェクトOBJ3は、要素点P0→P1→P2→P3→P4→P5→P0という順番で一筆書きされる。その後、要素点P0でペンアップが行われ、要素点P6でペンダウンが行われる。そして、オブジェクトOBJ4は、要素点P6→P7→P8→P9→P6という順番で一筆書きされる。この時、オブジェクトの境界で相対座標が適用されないと仮定すると、要素点P0〜P5および要素点P6〜P9を表す座標のデータ構造は、図20に示すようになる。図20において、最初に、オブジェクトOBJ3の基準点となる要素点P0の絶対座標(X0,Y0)が4バイトで記述される。オブジェクトOBJ3の描画時には、要素点P0にペンダウンした後ペンアップするまでに、要素点P1〜P5を辿ることになるので、差分数(つまり相対座標の個数)は、5個となり、1バイトの情報である。今、要素点P1〜P5の相対座標は、前述と同様に2バイトで表され、(ΔX1,ΔY1)〜(ΔX5,ΔY5)である。また、オブジェクトの境界部分に相対座標が適用されないので、要素点P5の相対座標の後には、オブジェクトOBJ4の基準点となる要素点P6の絶対座標(X1,Y1)が4バイトで記述される。オブジェクトOBJ4の描画時には、要素点P6にペンダウンした後ペンアップするまでに、要素点P7〜P9を辿ることになるので、差分数(相対座標の個数)は、3個となり、1バイトの情報である。要素点P7〜P9の相対座標は、(ΔX6,ΔY6)〜(ΔX8,ΔY8)であり、2バイトで表される。したがって、両オブジェクトの境界に相対座標を適用することなく、オブジェクトOBJ3およびOBJ4を相対座標列は、26バイトで表現される。

0068

次に、オブジェクトの境界に相対座標表現が適用される場合について、図21および図22を参照して説明する。図21には、図19と同様に、2個のオブジェクトOBJ3およびOBJ4から構成される描画オブジェクトDO3が示されている。描画オブジェクトDO3は、要素点P0→P1→P2→P3→P4→P5という順番で一筆書きされる。その後、要素点P5から要素点P6へのペンアップおよびペンダウンが行われた後、描画オブジェクトDO3は、要素点P6→P7→P8→P9→P6という順番で一筆書きされる。ただし、描画時においては、一筆書きの開始点とペンアップした点とは必ず結ぶという原則があるので、要素点P5および要素点P0は線で結ばれる。以上の描画時において、オブジェクトの境界で相対座標が適用されると仮定すると、要素点P0〜P5および要素点P6〜P9を表す座標のデータ構造は、図22に示すようになる。図22において、最初に、オブジェクトOBJ3の基準点となる要素点P0の絶対座標(X0,Y0)が4バイトで記述される。描画オブジェクトDO3の描画時には、要素点P0から一筆書きを開始から終了までに、要素点P1〜P9を辿ることになるので、相対座標の個数、つまり差分数は、1バイトのデータであって、「9個」を示す。今、要素点P1〜P9の相対座標は、前述と同様に2バイトで表され、(ΔX1,ΔY1)〜(ΔX9,ΔY9)である。したがって、両オブジェクトの境界に相対座標を適用する場合には、オブジェクトOBJ3およびOBJ4を相対座標列は、23バイトで表現される。

0069

以上、図19図22を参照して説明したように、オブジェクトの境界に相対座標を適用すると、それを適用しない場合と比較して、背景テーブルのデータサイズを小型化することができる。

0070

ここで注意を要するのは、図20においてはオブジェクトの境界は、オブジェクトレコードORに記述された絶対座標により分かる。しかし、図22においては、オブジェクトの境界は、絶対座標からは見つけることはできない。図21に示すように、オブジェクトの境界を規定するペンアップする要素点Pおよびペンダウンする要素点Pはそれぞれ相対座標で示される場合があり、さらには、図18に示したように2点間の距離が離れている場合には、要素点Pが絶対座標で表現される場合があるからである。しかしながら、図22において、オブジェクトの境界は、図10に示された要素点数N1〜要素点数NNを参照すれば正確に規定できる。つまり、本実施形態では、要素点数N1〜要素点数NNはそれぞれ、ペンダウンしてからペンアップするまでに一筆書きで辿る要素点の個数を意味する。したがって、実際の描画時において、オブジェクトレコードORの先頭から座標の個数をカウントし、カウント値が要素点数N1と同じであれは、最初のオブジェクトの境界を正確に特定することができる。同様に、カウント値が要素点数N1およびN2の加算値と同じであれは、2回目のオブジェクトの境界を特定することができる。以降、同様に、カウント値が要素点数N1〜NNの加算値と同じであれは、N回目のオブジェクトの境界を特定することができる。

0071

「文字記号データの詳細なデータ構造」次に、図7に示す文字記号データについて説明する。なお、文字記号データは本願発明の特徴的な事項ではないため、簡単に説明する。文字記号データとは、前述したように、ユニットUがカバーする地図に記載されるべき文字列(地名、道路名称および交差点名称等)からなるデータと、当該地図に記載されるべき地図記号からなるデータとを意味する。さらに、文字記号データは、図7に示すように、基本文字記号テーブルと詳細文字記号テーブルとから構成される。基本文字記号テーブルは、ユニットUがカバーする地図に記載される文字列または地図記号の内、基本的な文字列および地図記号を表すデータを集合である。より具体的には、基本文字記号テーブルには、図23(a)から明らかなように、河川名称、道路名称および地図記号等、ユニットUがカバーする地図を表示する際に概略となる文字列および地図記号とが記録される。一方、詳細文字記号テーブルは、ユニットUがカバーする地図に記載される文字列または地図記号の内、基本文字記号テーブルには記録されない文字列および地図記号を表すデータを集合である。より具体的には、詳細文字記号テーブルには、図23(b)から明らかなように、公園、鉄道、橋および工場の名称等、ユニットUがカバーする地図をより詳細に表示するための文字列および地図記号とが記録される。

0072

ここで、本実施形態の端末装置1としては、上述したようにカーナビゲーションシステムが想定されている。かかる事情から、基本文字データテーブルには、カーナビゲーションに重要な河川名称、道路名称および地図記号等が記録されると説明した。しかし、他の用途の端末装置1も想定できる。そのため、基本文字記号テーブルにどのような文字列および地図記号が記録されるか、また、詳細文字記号テーブルにどのような文字列および地図記号が記録されるかについては、端末装置1の用途に依存する。それゆえに、本願発明の技術範囲は、基本文字データテーブルには、河川名称、道路名称および地図記号等が記録される、というように限定解釈されてはならない。

0073

さて、以上の基本文字記号テーブルおよび詳細文字記号テーブルは、図7から明らかなように、ユニットデータにおいて互いに別々のフィールドに記録される。さらに、基本文字記号テーブルおよび詳細文字記号テーブルには、相互に参照し合うような情報は一切記録されない。つまり、基本文字テーブルを構成する文字列または地図記号を描いている際に、詳細文字記号テーブルの文字列または地図記号は何一つ参照されない。逆に、詳細文字記号テーブルを構成する文字列および地図記号を描いている際に、基本文字記号テーブルの文字列および地図記号は何一つ参照されない。このように、基本文字記号テーブルおよび詳細文字記号テーブルは、相互に独立したデータ構造を有する。したがって、文字列および地図記号をディスプレイ上に表示する場合には、図23(a)に示すように、基本文字記号テーブルのみで表される文字列および地図記号を表示することが可能になる。これによって、端末装置1のユーザは、概略的な地図を見ることが可能になる。また、図23(c)に示すように、基本文字記号テーブルおよび詳細文字記号テーブルそれぞれを構成する文字列および地図記号を表示することもできる。この場合、所定の原点を基準として、基本文字記号テーブルから得られる概略的な文字列および地図記号に、詳細文字記号テーブルから得られる文字列および地図記号を重ねあわせることとなる。これによって、端末装置1のユーザは、詳細な地図を見ることが可能となる。なお、本実施形態では、文字記号データは基本文字記号テーブルおよび詳細文字記号テーブルとから構成されるとして説明したが、第1の記憶装置19または第2の記憶装置24に記憶容量の制限がある場合等には、第1のデータベース111または第2のデータベース25を小さいサイズにする観点から、文字記号データは基本文字記号テーブルのみから構成されてもよい。逆に、本実施形態で説明したように、文字記号データは基本文字記号テーブルおよび詳細文字記号テーブルとから構成される場合には、センタ局2は、詳細な地図を端末装置1に提供することが可能となり、当該端末装置1は詳細な地図をディスプレイに表示できるようになる。

0074

上述の基本文字記号テーブルおよび詳細文字記号テーブルの内部のデータ構造は互いに同じである。以下には、基本文字記号テーブルおよび詳細文字記号テーブルを文字記号テーブルと総称して、双方のデータ構造についてより詳細に説明する。

0075

上述したように、文字記号テーブルは、ユニットUがカバーする地図上の文字列および地図記号をディスプレイ上に表すためのデータの集合である。ここで、図24は、文字記号テーブル、つまり基本文字記号テーブルまたは詳細文字記号テーブルの詳細なデータ構造を示す図である。図24において、文字記号テーブルは、文字記号レコード数Pと、P個の文字記号レコードTSR1〜TSRPとから構成される。文字記号レコード数Pは、文字記号テーブルに含まれる文字記号レコードTSR1〜TSRPの個数を示す情報である。ここで、Pは、1以上の自然数であって、ユニットUがカバーする地図上の文字列および地図記号の総数である。文字記号レコードTSR1〜TSRPは、ユニットUがカバーする地図上の文字列または地図記号の数だけ作成される。文字記号レコードTSR1は、文字記号属性と、ポイント座標と、文字記号コードとから構成される。

0076

文字記号属性は、文字記号レコードTSR1により表されるべき文字列または地図記号の属性を示す情報である。文字記号属性には、文字列または当該地図記号のサイズと、文字列が並ぶ方向(縦/横)とを示す情報が記録される。ここで注意を要するのは、地図記号は、複数の記号により1つの対象物を表すことがほとんどなく、さらに、1つの文字で表される地名もある。かかる場合には、文字列が並ぶ方向(縦/横)を示す情報が文字記号属性に記録される必要性は特にない。ポイント座標は、文字記号レコードTSR1により表されるべき文字列または地図記号がユニットU上のどの位置に表示されるかを特定するための座標情報である。文字記号レコードTSR1により表されるべき文字列等は、ディスプレイ上において、ポイント座標により特定される位置に表示される。また、文字記号コードは、文字記号レコードTSR1により表されるべき文字列および地図記号のコード番号である。文字列のコード番号としては、日本国ではシフトJISコードが典型的であり、文字記号属性に記録された文字列の大小を表すサイズに該当する情報が記録される。ここで、地図記号は、シフトJIS等のように、それに関連する規格がないので、独自に作成される。さらに、作成された地図記号のコード番号としては、日本国ではシフトJISの空きコード番号が割り当てられる。割り当てられたコード番号が、文字記号コードとして記録される。なお、他の文字記号レコードTSR2〜TSRPは、文字記号レコードTSR1と同様のデータ構造を有するので、それぞれの説明を省略する。

0077

「道路ネットワークデータの詳細なデータ構造」次に、図7に示す道路ネットワークデータについて説明する。道路ネットワークデータは、カーナビゲーションシステムとしての端末装置1において、ディスプレイ上に道路を表示するために使用されるだけでなく、マップマッチング、経路探索処理または経路案内処理にも使用される。そのため、道路ネットワークデータは、前述したように、ユニットUがカバーする地図に表されるべき道路そのものを表す図形データ、および道路同士のつながりを表すデータの集合を意味する。より具体的には、道路ネットワークデータはマップマッチング等に使用されるため、当該道路ネットワークデータには、単に、道路網の形状を表す図形データが記録されるだけではなく、ユニットUがカバーする範囲の地図に表される道路同士の接続関係を示すデータも記録される。

0078

以上の道路ネットワークデータは、図7に示すように、第1のネットワークデータと第2のネットワークデータとから構成される。第1のネットワークデータには、主要幹線道路の道路ネットワークデータが記録される。主要幹線道路とは、例えば、以下の3つの条件のいずれかを満たすものを意味する。まず、第1の条件は、地方自治体およびそれよりも上位の行政機関が造った道路(高速道路、国道)であることである。第2の条件は、地方自治体よりも下位の行政機関が造った道路(高速道路、国道)および私道であって、かつその幅員が5.5m以上の道路であることである。第3の条件は、上記第1および第2の条件に該当する道路に接続された道路であることである。また、第2のネットワークデータには、細街路の道路ネットワークデータが記録される。細街路とは、その幅員が3.0m以上であって、主要幹線道路に該当しない道路(例えば、住宅の周辺に造られた道路)を意味する。ただし、上記の主要幹線道路および細街路の定義は単なる一例であって、他の定義を採用しても構わない。それゆえに、本願発明の技術範囲は、第1および第2の道路ネットワークデータには、上記定義にのみ該当する道路ネットワークデータが記録される、というように限定解釈されてはならない。

0079

次に、第1の道路ネットワークデータおよび第2の道路ネットワークデータの関係について、図25を参照して説明する。第1の道路ネットワークデータは、主要幹線道路の道路ネットワークデータである。そのため、第1の道路ネットワークデータが端末装置1のディスプレイに表示されると、図25(a)に示すように、主要幹線道路を表す図形が表示される。一方、第2の道路ネットワークデータは、細街路の道路ネットワークデータである。そのため、第2の道路ネットワークデータが端末装置1のディスプレイに表示されると、図25(b)に示すように、細街路を表す図形が表示される。これら第1および第2の道路ネットワークデータは、図7から明らかなように、ユニットデータにおいて互いに別々に記録される。したがって、図25(a)に示すように、第1の道路ネットワークデータを構成する主要幹線道路のみを端末装置1のディスプレイに表示することが可能になる。これによって、端末装置1のユーザは、概略的な道路ネットワークを見ることが可能になる。また、図25(c)に示すように、第1および第2の道路ネットワークデータを構成する主要幹線道路および細街路を表示することもできる。この場合、所定の原点を基準として、第1の道路ネットワークデータから得られる主要幹線道路網の上に、第2の道路ネットワークデータから得られる細街路の道路網を重ねあわせることとなる。これによって、端末装置1のユーザは、詳細な道路網を見ることが可能となる。なお、本実施形態では、道路ネットワークデータは、第1および第2の道路ネットワークデータから構成されるとして説明したが、第1の記憶装置19または第2の記憶装置24に記憶容量の制限がある場合等には、第1のデータベース111または第2のデータベース25を小さいサイズにする観点から、道路ネットワークデータは、第1の道路ネットワークデータのみから構成されてもよい。逆に、本実施形態で説明したように、道路ネットワークデータが第1および第2の道路ネットワークデータから構成される場合には、センタ局2は、詳細な道路網を端末装置1に提供することが可能となり、当該端末装置1は詳細な道路網をディスプレイに表示できるようになる。

0080

上述の第1および第2の道路ネットワークデータのデータ構造は互いに同じである。以下には、第1および第2の道路ネットワークデータのデータ構造についてより詳細に説明する。周知のように、道路ネットワークデータは、主として、ノードとリンクにより構成される。ノードとは、主として、交差点または道路の区切りを表現するためのデータを意味する。また、リンクとは、2個の交差点の間をつなぐ道路を表現するためのデータである。かかるノードとリンクを用いることにより、ユニットUがカバーする地図上に表されるべき道路(主要幹線道路または細街路)の形状および道路同士の接続関係が端末装置1のディスプレイ上に表示される。そのため、図7に示すように、第1の道路ネットワークデータは、第1のノードテーブルおよび第1のリンクテーブルから構成され、第2の道路ネットワークデータは、第2のノードテーブルおよび第2のリンクテーブルから構成される。以下には、まず、第1および第2のノードテーブルのデータ構造をまず説明する。

0081

ここで、図26は、ノードおよびリンクの概念を説明するための図である。図26には、1つのユニットUがカバーする範囲に存在する道路網が示されている。図26の道路網は、11個のノードN0〜N10と、11個のリンクL0〜L10とから構成される。11個のノードN0〜N10は、非隣接ノードと隣接ノードとに大別される。非隣接ノードとは、通常の交差点、もしくは道路の種別または属性が変わる点(上述の道路の区切りに相当する)に作成されるノードであり、ユニットU内での道路の接続関係を表す分岐点を意味する。ところで、図26のユニットUには、同じレベルに属しかつ隣接するユニットUがいくつかある(図2参照)。したがって、1本の道路が、互いに隣り合う複数のユニットUにまたがる場合がある。以下では、図26のユニットUに隣接するユニットUのことを、便宜上、隣接ユニットNUと称する。図26には、隣接ユニットNUの1つが点線にて示されている。隣接ノードは、図26のユニットUおよび隣接ユニットNUの間をまたがる道路が存在する場合に、当該ユニットUの境界(つまり矩形領域の辺)上に作成されるノードであり、当該ユニットUと隣接ユニットNUとの道路の接続関係を表す点を意味する。以上の定義に従うと、図26のノードN1、N2、N5およびN8の4つ(○印参照)が非隣接ノードに分類される。また、ノードN0、N3、N4、N6、N7、N9、N10の7つ(●印参照)が隣接ノードに分類される。ここで注意を要するのは、交差点または道路の区切りを表すノードNがユニットUの境界上に存在する場合には、当該ノードNを隣接ノードと分類するか、非隣接ノードと分類するかが問題となる。かかる場合、交差点または道路の区切りを表すノードNを境界上からずらして、新しい非隣接ノードを作成することが1つの対処方法である。他の対処方法として、ユニットUの境界上の交差点または道路の区切りと同じ座標上に非隣接ノードを作成することがある。以上から明らかなように、ユニットUの境界上には隣接ノードが作成されてはならない。

0082

図27は、第1のノードテーブルの詳細なデータ構造を示す図である。ここで、予め断っておくが、第1および第2のノードテーブルは、互いに同様のデータ構造を有しており、主要幹線道路および細街路について作成される点で相違する。そのため、説明の簡素化の観点から、第2のノードテーブルの詳細な説明を省略する。さて、図27において、第1のノードテーブルは、隣接ノード数Qと、非隣接ノード数Rと、(Q+R)個のノードレコードNR1〜NR(Q+R)とから構成される。隣接ノード数Qは、第1のノードテーブルに含まれる隣接ノードの個数を示す情報である。ここで、Qは、1以上の自然数であって、ユニットUにより表される地図上の道路網に隣接ノードがいくつ存在するかを示す。非隣接ノード数Rは、第1のノードテーブルに含まれる非隣接ノードの個数を示す情報である。ここで、Rは、1以上の自然数であって、ユニットUにより表される地図上の道路網に非隣接ノードがいくつ存在するかを示す。

0083

ノードレコードNR1〜NR(Q+R)は、ユニットUにより表される地図上の道路網に存在するノードNの数だけ作成される。ノードレコードNR1〜NR(Q+R)には、(Q+R)個のノードNに関連する情報が記録される。次に、本実施形態におけるノードレコードNR1〜NR(Q+R)の並べ方について説明する。第1のノードテーブルにおいて、最初のQ個のノードレコードNR1〜NRQには、Q個の隣接ノードに関連する情報が記録され、後のR個のノードレコードNR(Q+1)〜NRRには、R個の非隣接ノードに関連する情報が記録される。また、Q個のノードレコードNR1〜NRQにおいて、先頭から順番に、矩形領域(ユニットU)の左辺上に存在する隣接ノード(図26の参照)に関連する情報が記録される。次に、矩形領域の上辺上に存在する隣接ノード(図26の参照)に関連する情報が記録される。次に、矩形領域の右辺上に存在する隣接ノード(図26の参照)に関連する情報が記録される。最後に、矩形領域の下辺上に存在する隣接ノード(図26の参照)に関連する情報が記録される。また、上記右辺上または左辺上の隣接ノードのノードレコードNRは、当該隣接ノードの緯度が昇順になるよう並べられる。一方、上記右辺上または左辺上の隣接ノードのノードレコードNRは、当該隣接ノードの経度が昇順になるよう並べられる。

0084

さらに、非隣接ノードのノードレコードNRは、最初に、当該非隣接ノードの緯度が昇順になるように並べられる。この時、同じ緯度の非隣接ノードが複数存在した場合には、ノードレコードNRは、当該非隣接ノードの経度が昇順になるように並べられる。

0085

図26のノードN0〜N10に関して、上記の並べ方に従うと、図28に示すように、先頭のノードレコードNR1には、隣接ノードN6の情報が記録される。次のノードレコードNR2には、隣接ノードN0の情報が記録される。ノードレコードNR3、NR4、NR5、NR6およびNR7には、隣接ノードN4、N7、N10、N3およびN9の情報が記録される。ここで、図28中の〜は、図26の〜に対応しており、隣接ノードが並べられる順位を示している。次のノードレコードNR8には、非隣接ノードN8の情報が記録される。ノードレコードNR9、NR10およびNR11には、非隣接ノードN5、N2およびN1の情報が記録される。以上のように、本実施形態では、ユニットUに含まれるノードNの情報は、ランダムにではなく、上述した規則に従った順番でノードレコードNRに記録されていく。ここで、以下の説明において、ノードレコード番号とは、最初のノードレコードNR1を「0」として、各ノードレコードNR2以降が何番目に記録されているかを特定する番号を意味する。以上のノードレコード番号を図28のノードレコードNR1〜NR11に当てはめると、当該ノードレコードNR1〜NR11のノードレコード番号は「0」〜「10」となる。なお、以上のような並べ方は、ユニットUと隣接ユニットNUの間にまたがる道路の接続関係をたどる処理を高速に行ったり、ユニットUの親子間におけるノードやリンクの対応づけを的確に行ったりできるという効果を生むが、これらの具体的な処理および効果については後述する。

0086

さて、再度図27を参照して、ノードレコードNR1の内部データ構造を詳細に説明する。ノードレコードNR1は、ノード属性と、ノード座標と、ノード接続情報とから構成される。ノード属性は、ノードレコードNR1に記録されるノードの属性を表すための情報である。ノード属性の例としては、記録されたノードに交差点での交通規制されているか否かを示す情報、当該ノードにより表される交差点に名称があるか否かを示す情報、当該ノードにより表される交差点に信号機が存在するか否か等の情報がある。なお、ノード属性に交通規制または交差点名称の有無に関する情報を記録する場合には、本実施形態では説明しない交差点規制テーブルおよび交差点名称テーブル等のテーブルを別途作成し、該当する情報を記録するようにする。

0087

また、ノード座標は、ノードレコードNR1に記録されるノードの経度方向の座標および緯度方向の座標を表すための情報である。ノードの経度方向の座標および緯度方向の座標としては、絶対経度緯度座標を記録しても良いが、記録されるノードを含むユニットU(矩形領域)の左下隅を基準点として、当該ユニットUがカバーする範囲の経度幅および緯度幅を2バイト程度の値で正規化した座標で表すのが一般的である。例えば、図29に示すように、ユニットUの左下隅Naの座標を(0000h,0000h)と表現し(hは16進数の値を表す)、当該ユニットUの座標系を経度方向および緯度方向共に8000hで正規化する。この場合、ユニットの左上隅Nbの座標は(0000h,8000h)と表現される。また、ユニットの右下隅Ncの座標は(8000h,0000h)と表現される。さらに、ユニットの右上隅Ndの座標は(8000h,8000h)で表現される。また、ノード接続情報は、ノードレコードNR1に記録されるノードNと、後述するリンクレコードLRに記録されるリンクLとの接続関係を表す情報である。ノード接続情報の詳細については後述する。なお、他のノードレコードNR2〜NR(Q+R)の内部データ構造については、ノードレコードNR1と同様であるため説明を省略する。ただし、他のノードレコードNR2〜NR(Q+R)には、互いに異なるノードNの情報が記録される。

0088

次に、図7の第1のリンクテーブルのデータ構造を説明する。ここで、予め断っておくが、第1および第2のリンクテーブルは、同様のデータ構造を有しており、主要幹線道路および細街路について作成される点で相違する。そのため、以降では、第2のリンクテーブルの詳細な説明を省略する。図30は、第1のリンクテーブルの詳細なデータ構造を示す図である。図30において、第1のリンクテーブルは、道路数Sと、M個の道路レコードRR1〜RRMとから構成される。道路数Sは、第1のノードテーブルにより表される道路網に含まれる道路の本数を示す情報である。ここで、Sは、1以上の自然数であって、ユニットUにより表される地図上の道路網に道路が何本存在するかを示す。道路レコードRR1には、ある1つの道路属性が割り当てられ、当該道路属性が同じリンクLおよびノードNに関する情報が記録される。また、道路レコードRR2には、他の1つの道路属性が割り当てられ、当該道路属性が同じリンクLおよびノードNに関する情報が記録される。以降、同様に、道路レコードRRSには、他の道路レコードRR1〜RR(S−1)には割り当てられていない1つの道路属性が割り当てられ、当該道路属性が同じリンクLおよびノードNに関する情報が記録される。以上から明らかなように、道路レコードRR1〜RRSには、互いに異なる道路属性が割り当てられる。ここで、道路属性とは、道路の種別毎に分類するための情報である。典型的には、道路は、高速道路、国道、県道、市道、私道等といった区分で分類され、さらには、各道路の名称によってより詳細に分類される。なお、必要に応じて、道路の一方通行規制等を道路属性に採用してもよい。

0089

道路レコードRR1は、道路属性と、リンク数T1と、先頭ノードレコード番号と、T1個のリンクレコードLR1〜LRT1とから構成される。道路属性には、道路種別(高速道路、国道、県道等)、道路の一方通行規制等を示す情報が記録される。リンク数T1は、道路レコードRR1に記録されるリンクLの個数を示す情報である。ここで、T1は、1以上の自然数であって、ユニットUにより表される地図上の道路網において、道路属性の情報に該当するリンクLが何個存在するかを示す情報である。先頭ノードレコード番号は、所定のノードレコードNRを特定するためのノードレコード番号を意味する。このノードレコード番号は、図28等を参照して上述したように、最初のノードレコードNR1を「0」として、各ノードレコードNR2以降が何番目に記録されているかを特定する番号である。さらに、所定のノードレコードNRとは、道路レコードRR1により表される道路網の先頭に位置するノードNが記録されたものを意味する。また、リンクレコードLR1には、ユニットUにより表される地図上の道路網において、道路属性により分類されるリンクLの内のある1つに関する情報が記録される。そのために、リンクレコードLR1は、リンク属性と、リンク接続情報とから構成される。リンク属性とは、リンクレコードLR1により表されるリンクLの属性を示す情報である。リンク属性の典型例としては、リンク種別本線リンクであるか、側道リンクであるか等)または車線数等がある。また、リンク接続情報は、リンクレコードLR1により表されるリンクLに接続されたノードN、またはリンクレコードLR1により表されるリンクLとノードNを介してつながっているリンクLの情報である。また、リンクレコードLR2には、道路属性により分類されるリンクLの内の他の1つに関する情報が記録される。以降同様に、リンクレコードLRT1には、道路属性により分類されるリンクLの内、他のリンクレコードLR(T1−1)に記録されていない1つのリンクLに関する情報が記録される。ここで、リンクレコードLR2〜LRTは、リンクレコードLR1と同様に、リンク属性と、リンク接続情報とから構成される。以上から明らかなように、リンクレコードLR1〜LRT1には、互いに異なるリンクLに関する情報が記録される。

0090

さて、次に、第1のリンクテーブルに記載される情報の具体例を、図26の道路網の場合について具体的に説明する。上述したように、図26の道路網は、11個のノードN0〜N10と、11個のリンクL0〜L10とから構成される。また、説明をより具体的にするために、リンクL0〜L2は、ノードN0を先頭として、L0→L1→L2の順番で接続されることにより、1本の道路(例えば、国道)を構成すると仮定する。この仮定下では、リンクL0〜L2は互いに同一の道路属性(国道)を有する。リンクL3〜L5は、ノードN4を先頭として、L3→L4→L5の順番で接続されることにより、1本の道路(例えば、県道)を構成すると仮定する。この仮定下では、リンクL3〜L5は互いに同一の道路属性(県道)を有する。リンクL6〜L8は、ノードN7を先頭として、L6→L7→L8の順番で接続されることにより、1本の道路(例えば、幅員が5.5m以上の私道)を構成すると仮定する。この仮定下では、リンクL6〜L8は互いに同一の道路属性(私道)を有する。リンクL9およびL10は、ノードN5を先頭として、L9→L10の順番で接続されることにより、1本の道路(例えば、市道)を構成すると仮定する。この仮定下では、リンクL9およびL10は互いに同一の道路属性(市道)を有する。

0091

以上の仮定下では、道路は、国道、県道、私道および市道の4本であるから、第1のリンクテーブルの道路数Sとして、「4」が記録される。また、道路属性としては、国道、県道、私道および市道の4種類があるので、第1のリンクテーブルには、4個の道路レコードRR1〜RR4が記録される。まず、道路レコードRR1について説明する。道路属性としては「国道」を表す情報が記録される。また、リンク数T1としては、国道がリンクL0〜L2で構成されることから「3」を示す情報が記録される。また、リンクL0〜L2で表される道路の先頭は、ノードN0により表される。ノードN0のレコード番号は「1」である(図28参照)。ゆえに、先頭ノードNの番号としては「1」が記録される。次に、リンクレコードLR11(リンクL0のレコード)において、リンク属性については説明を省略する。

0092

さて、ここで、各リンクレコードLRに記録されるリンク接続情報、および図27に示されるノード接続情報を説明する。同時に、ノードNとリンクLの接続関係をたどる処理についても説明する。例えば、図26に示すように、ノードN2はリンクL1、L2、L6、およびL7の4本と接続している。このように、各ノードN2を中心として、4本のリンクL1、L2、L6およびL7がつながっている。また、ノードレコードNR10には、ノードN2に関連する情報が記録される(図27参照)。また、リンクレコードLR12、LR13、LR31およびLR32には、リンクL1、L2、L6およびL7に関連する情報が記録される(図31参照)。ノードレコードNR10のノード接続情報(図27参照)、および各リンクレコードLR12、LR13、LR31およびLR32のリンク接続情報(図31参照)には、ノードN2に接続されたリンクL1、L2、L6およびL7をたどるための情報が記録される。まず、ノードレコードNR10には、ノード接続情報として、ノードN2に接続された最初のリンクL(今、仮にリンクL1とする)が記録されたリンクレコードLR12を参照するための情報が記録される。より具体的には、ノード接続情報としては、リンクテーブルの先頭からリンクレコードLR12までのオフセットアドレスを記録しても良いし、リンクレコードLR12のリンクレコード番号を記録しても良い。ここで、リンクレコード番号とは、リンクテーブルにおいて最初のリンクレコードLR11を「0」として、リンクレコードLR12以降が何番目に記録されているかを特定する番号を意味する。以上のリンクレコード番号を図31のリンクレコードLRに当てはめると、リンクレコードLR11〜LR13のリンクレコード番号は「0」〜「3」となる。また、リンクレコードLR21〜LR23のリンクレコード番号は「4」〜「6」となる。また、リンクレコードLR31〜LR33のリンクレコード番号は「7」〜「9」となる。さらに、リンクレコードLR41およびLR42のリンクレコード番号は「10」および「11」となる。

0093

ここで注意を要するのは、ノード接続情報には、同じユニットU内の道路網の接続をたどる場合に限り、オフセットアドレスおよびリンクレコード番号が記録される。同様に、リンク接続情報には、同じユニットU内の道路網の接続をたどる場合に限り、オフセットアドレスおよびノードレコード番号が参照される。詳しくは図37および図38を参照して説明するが、あるユニットUおよび隣接ユニットNUの境界をまたぐような道路網の接続をたどる場合には、オフセットアドレスおよびリンクレコードは参照されない。

0094

図32の例では、ノードレコードNR10のノード接続情報には、当該ノードレコードNR10から、リンクテーブルのリンクレコードLR12を参照可能なように、当該リンクレコードLR12までのオフセットアドレスまたは当該リンクレコードLR12のリンクレコード番号が記録される。また、図32の例では、リンクレコードLR12からはリンクレコードLR32が参照されるので、リンクレコードLR12のリンク接続情報には、リンクL1と接続する他のリンクL6を参照可能なように、当該リンクレコードLR32へのオフセットアドレスまたは当該リンクレコードLR32のリンクレコード番号が記録される。かかるノードレコードNR10のノード接続情報およびリンクレコードLR12のリンク接続情報により、リンクL1はノードN2を起点として、リンクL6と接続していることが分かる。

0095

ここで注意を要するのは、リンクレコードLR12のリンク接続情報としては、リンクレコード番号やオフセットアドレスだけでなく、当該リンク接続情報が他のリンクLに対してであることを示すフラグを記録しておく。さらに注意を要するのは、同一道路レコードRR内で記録されるリンクLを参照するためのリンク接続情報は、各リンクレコードLRには記録されない。同一道路レコードRRに属するリンクL同士は、リンク接続情報を参照しなくとも、リンクレコードLRの並び方によりたどることができるからである。つまり、道路レコードRR1においてリンクレコードLR11とリンクレコードLR12とは、連続するアドレス領域に並べて記録されるため、リンクL1およびリンクL2は相互に接続していると判断することができる。同様に、道路レコードRR3において、リンクレコードLR31およびLR32は連続アドレス領域に並べて記録されるため、リンクL6とリンクL7とは相互に接続していると判断することができる。

0096

さて、リンクレコードLR12の次に参照されるリンクレコードLR31に記録されたリンクL6は、道路レコードRR1以外に区分されたリンクLとは接続されていない。そのため、リンクレコードLR32のリンク接続情報としては、リンクL1、L2、L6およびL7の中心に位置するノードN2が記録されたノードレコードNR10を参照可能な情報が記録される。リンクレコードLR32のリンク接続情報としても、ノードレコードNR10へのオフセットアドレスまたは当該ノードレコードNR10のノードレコード番号が用いられる。ここで注意を要するのは、リンクレコードLR32のリンク接続情報としては、ノードレコードNR10のノードレコード番号またはオフセットアドレスだけでなく、当該リンク接続情報がノードテーブルNRに対して設定されていることを示すフラグも記録される。

0097

以上のように、各ノードレコードNRには、最初に接続するリンクLへのノード接続情報のみを記録し、各リンクレコードLRには、そこに記録されるリンクLに接続する他の道路レコードRR内のリンクLへのリンク接続情報、もしくは起点となったノードNが記録されるノードレコードNRへのリンク接続情報を記録することによって、各ノードNを起点としたリンクLの接続をたどることができる。

0098

「ユニットヘッダのデータ構造」さて、再度図7を参照して、ユニットヘッダのデータ構造について詳細に説明する。ユニットヘッダには、地図ファイルCFのユニットデータの管理情報が記録される。ユニットヘッダは、少なくともユニットID、バージョンコード、およびユニットデータを構成する8種類のテーブルのデータサイズから構成される。ユニットIDは、当該地図ファイルCFにより表されるユニットUを一意に特定できる識別番号である。より具体的には、ユニットIDは、ユニットUのレベルL、およびユニットUの親子関係および隣接関係が特定できる番号であり、地図ファイルCFのパス名と相互に変換できるものが望ましい。例えば、ユニットIDを32ビット(4バイト)のコードで表現するとし、MSBから2ビットをリザーブビットとし、順にユニットレベルLを2ビット、レベル「3」の経度方向の分割位置X3を5ビット、レベル「3」の緯度方向の分割位置Y3を5ビット、レベル「2」の経度方向の分割位置X2を3ビット、レベル「2」の緯度方向の分割位置Y2を3ビット、レベル「1」の経度方向の分割位置X1を3ビット、レベル「1」の緯度方向の分割位置Y1を3ビット、レベル「0」の経度方向の分割位置X0を3ビット、レベル「0」の緯度方向の分割位置Y0を3ビットで表す。ここで、レベル「3」の経度方向の分割位置X3は、ユニットUがレベル「3」に属するとした場合に東経方向に数えて何番目(起算点は経度0度)に位置するかを示す数である。レベル「3」の緯度方向の分割位置Y3は、ユニットUがレベル「3」に属するとした場合に北緯方向に数えて何番目(起算点は北緯0度)に位置するかを示す数である。レベル「2」の経度方向の分割位置X2は、ユニットUがレベル「2」に属するとした場合に東経方向に数えて何番目(起算点はレベル「3」のユニットUの左下)に位置するかを示す数である。レベル「2」の緯度方向の分割位置Y2は、ユニットUがレベル「2」に属するとした場合に北緯方向に数えて何番目(起算点はレベル「3」のユニットUの左下)に位置するかを示す数である。レベル「1」の経度方向の分割位置X1は、ユニットUがレベル「1」に属するとした場合に東経方向に数えて何番目(起算点はレベル「2」のユニットUの左下)に位置するかを示す数である。レベル「1」の緯度方向の分割位置Y1は、ユニットUがレベル「1」に属するとした場合に北緯方向に数えて何番目(起算点はレベル「2」のユニットUの左下)に位置するかを示す数である。レベル「0」の経度方向の分割位置X0は、ユニットUがレベル「0」に属するとした場合に東経方向に数えて何番目(起算点はレベル「1」のユニットUの左下)に位置するかを示す数である。レベル「0」の緯度方向の分割位置Y0は、ユニットUがレベル「0」に属するとした場合に北緯方向に数えて何番目(起算点はレベル「1」のユニットUの左下)に位置するかを示す数である。

0099

例えば、図4に示すレベル「0」のユニットU0 のパス名は「¥MAP¥D1606¥D0401¥D0503¥M0201.map」であるため、前述のL=0、X3=16、Y3=6、X2=4、Y2=1、X1=5、Y1=3、X0=2、Y0=1となる。この場合、ユニットU0 のユニットIDは、135928529(10進数表記)となる。以上から明らかなように、地図ファイルCFのパス名からユニットIDを一意に特定することができ、逆にユニットIDからパス名を一意に特定することができる。

0100

またバージョンコードは、地図ファイルCF(ユニットU)のバージョンを表すための識別コードであり、例えば、当該ユニットのフォーマットバージョンを表すコードを2バイト、当該ユニットのコンテンツバージョンを表すコードを2バイト等で記述した、合計4バイトのコードで表すものとする。このバージョンコードは、センタ局2からあるユニットIDの地図ファイルCFが端末装置1にダウンロードされた際に、端末装置1の第1の記憶装置19に既に格納されている同一ユニットIDの地図ファイルCFと置き換えるか否かの判断等に使用される。なお、この際の詳細な処理については後述する。

0101

また、各テーブルのデータサイズには、地図ファイルCFを構成する各テーブルのデータサイズが記録されており、それぞれは例えば2バイトで表される。各テーブルのデータサイズを順に加算していくことにより、各テーブルが格納されている、地図ファイルCFの先頭からのオフセットアドレスが算出可能となる。なお、各テーブルのデータサイズとしては、基本背景テーブルのデータサイズ、詳細背景テーブルのデータサイズ、基本文字記号テーブルのデータサイズ、詳細文字記号テーブルのデータサイズ、第1のノードテーブルのデータサイズ、第1のリンクテーブルのデータサイズ、第2のノードテーブルのデータサイズ、第2のリンクテーブルのデータサイズが並ぶ。それぞれのテーブルの内容については上述した通りである。

0102

以上、地図ファイルCFの詳細なデータ構造について説明した。次に、第1のデータベース111から地図ファイルCFを読み出す際の端末装置1の動作について、図面を参照して説明する。
「読み出し処理」図1を参照して説明したように、本実施形態の端末装置1は、典型的にはカーナビゲーションシステムである。周知のように、マップマッチング、経路探索、または経路案内等の処理が実行される。以下には、これらの処理の内、経路探索処理に関連して、地図ファイルCFを読み出す処理、あるユニットUと隣接ユニットNUにまたがる道路の接続をたどる処理、および階層間でのノードNとリンクLとの対応づけを行う処理について詳細に説明する。なお、以下では、出発地および目的地の間の最短ルートを求める処理そのものについては本願発明のポイントではないため特に説明しない。

0103

図33は、経路探索処理の概念を示す図である。図33に示すように、最短ルートを求める処理では、出発地SP側と目的地DP側の両方向から探索が広げられる。さらに、経路探索処理では、下位階層から上位階層までの複数階層の地図ファイルCFが用いられる。この時、出発地SPおよび目的地DP周辺では、詳細な道路網を表す下位階層の地図ファイルCFを用いて、最短ルートが探索される。一方、出発地SPおよび目的地DP周辺以外では、粗い道路網を表す上位階層の地図ファイルCFが用いられる。以上の図33に示す経路探索処理では、いわゆる双方向階層別探索の手法が用いられる。また、地図ファイルCFを用いて、出発地SPから目的地DPへの最短ルートを求める場合には、周知のダイクストラ法等が使用される。なお、ダイクストラ法については、本願発明のポイントではなく、かつ周知の技術であるため、これ以上説明しない。

0104

以下、図34フローチャートを参照して、端末装置1で実行される双方向階層別探索の処理手順を詳細に説明する。まず、双方向階層別探索では、端末装置1の出発地SPおよび目的地DPの設定が実行される(ステップS101,S102)。ステップS101およびS102において、出発地SPおよび目的地DPは、出力装置110のディスプレイに表示されるメニューに従って、端末装置1のユーザが入力装置11を操作することにより設定される。ここで、最近のカーナビゲーションシステムでは、出発地SPおよび目的地DPは、一般的に、住所電話番号、地名または施設名称等を使って設定される。設定された出発地SPおよび目的地DPを特定する情報は、入力装置11からデータ処理部13に送信される。

0105

ステップS102が終了すると、データ処理部13は、読み出し/書き込み制御部18と協働して、経路探索処理に必要な地図ファイルCFを、第1の記憶装置19から主記憶(図示せず)に順次読み込む(ステップS103)。前述したように、第1の記憶装置19に格納された各地図ファイルCFは、図2等に示すように、地図を矩形領域に分割したユニットUを単位としてデジタルデータ化される。さらに、各地図ファイルCFは、ファイルシステムにより管理される。ファイルシステムは、第1の記憶装置19の論理領域がツリー構造をとるようにディレクトリを作成する。これによって、各地図ファイルCFが格納される論理領域は、ルートおよびファイル名、ならびにそれらの間に介在するサブディレクトリ名により表されるパスにより一意に特定される。また、本実施形態のツリー構造およびファイル名は、上述したように、ユニットU同士の親子関係および隣接関係を特定する。ファイルシステムを構成するデータ処理部13および読み出し/書き込み制御部18は、最初のステップS103において、入力装置11から送信されてくる出発地SP周辺を表す地図ファイルCFを第1の記憶装置19から読み出すためには、当該地図ファイルCFのパス名を求めなければならない。

0106

ここで、図35は、図34のステップS103の詳細な処理手順を示すフローチャートである。図35の処理を簡単に説明すると、データ処理部13が読み込むべき地図ファイルCFのレベル(階層)および代表点となる地点の座標情報から、当該地図ファイルCFのパス名を求める。そして、読み出し/書き込み制御部18は、データ処理部13により求められたパス名を基に、第1の記憶装置19から地図ファイルCFを読み出す。以下、図35のフローチャートを参照して、図4および図5に示すレベル「0」のユニットU0 を表す地図ファイルCF(「¥M0201.map」)を読み出す際の処理手順を説明する。

0107

ここで、代表点とは、読み出すべき地図ファイルCFがカバーする範囲に含まれる1つの地点を意味する。以下の説明において、経度座標LON0 および緯度座標LAT0 は、ユニットU0 の代表点の経度方向の位置を示す座標および緯度方向の位置を示す座標とする。本実施形態では、経度座標LON0 および緯度座標LAT0 は、東経132度39分20秒および北緯32度55分37秒とする。

0108

さらに、ステップS103の処理には、いくつかのパラメータが必要となる。以下の説明において、経度幅W3は、レベル「3」に属する各ユニットUがカバーする矩形領域の経度方向に沿う辺の長さを意味する。緯度幅H3は、レベル「3」に属する各ユニットUがカバーする矩形領域の緯度方向に沿う辺の長さを意味する。本実施形態の場合、図2および図3で説明したように、レベル「3」の矩形領域が約640km四方の場合には、経度幅W3および緯度幅H3は28800秒(8度)および19200秒(5度20分)である。経度幅W2は、レベル「2」に属する各ユニットUがカバーする矩形領域の経度方向に沿う辺の長さを意味する。緯度幅H2は、レベル「2」に属する各ユニットUがカバーする矩形領域の緯度方向に沿う辺の長さを意味する。レベル「2」の矩形領域が約80km四方の場合には、経度幅W2および緯度幅H2は3600秒(1度)および2400秒(40分)である。経度幅W1は、レベル「1」に属する各ユニットUがカバーする矩形領域の経度方向に沿う辺の長さを意味する。緯度幅H1は、レベル「1」に属する各ユニットUがカバーする矩形領域の緯度方向に沿う辺の長さを意味する。レベル「1」の矩形領域が約10km毎の場合には、経度幅W1および緯度幅H1は450秒(7分30秒)および300秒(5分)である。経度幅W0は、レベル「0」に属する各ユニットUがカバーする矩形領域の経度方向に沿う辺の長さを意味する。緯度幅H0は、レベル「0」に属する各ユニットUがカバーする矩形領域の緯度方向に沿う辺の長さを意味する。レベル「0」の矩形領域が約1.2km毎の場合には、経度幅W0および緯度幅H0は56.25秒および37.5秒である。

0109

さて、データ処理部13は、まず、代表点の経度座標LON0 および緯度LAT0 を特定し(ステップS201)、読み込むべき地図ファイルCFのレベルL(ユニットU0 の地図ファイルCFを読み込む場合、L=0)を特定する(ステップS202)。ここで、ステップS201およびS202は、双方向階層別探索において一般的に実行される処理であるため、ここでは詳細に説明しない。

0110

次に、データ処理部13は、ステップS203に進み、代表点の経度座標LON0 をレベル「3」の経度幅W3で除算した時の商DLON3、および、当該代表点の緯度LAT0 をレベル「3」の経度幅W3で除算した時の商DLON3を算出する。今、経度幅W3=28800秒(8度)、緯度幅H3=19200秒(5度20分)、経度座標LON0 =東経132度39分20秒、緯度座標LAT0 =北緯32度55分37秒であるから、商DLON3=16、商DLAT3=6となる。データ処理部13は、算出された商DLON3および商DLAT3を順番に並べて4桁の数字を作成する。今回作成される4桁の数字は、「1606」である。ここで、商DLON3および/または商DLAT3が1桁となる場合は、下から2桁目に「0」を付ける。

0111

データ処理部13は、作成した4桁の数字の先頭に、ディレクトリの識別子「¥」およびファイル名の頭文字を定義する「M」を付加し、さらにその末尾にファイル名の拡張子「.map」を付加する。これによって、データ処理部13は、代表点の経度座標LON0 および緯度座標LAT0 から、読み込むべき地図ファイルCF(ユニットU0 のもの)のファイル名(今回の場合、「¥M1606.map」)を導き出す。さらに、データ処理部13は、作成した4桁の数字の先頭に、ディレクトリの識別子「¥」およびサブディレクトリ名の頭文字を定義する「D」を付加する。これによって、データ処理部13は、代表点の経度座標LON0 および緯度座標LAT0 から、読み込むべき地図ファイルCFが格納されたサブディレクトリ名(今回の場合「¥D1606」)を導出する(ステップS203)。

0112

次に、データ処理部13は、ステップS202で指定されたレベルLが「3」か否かを判断する(ステップS204)。レベルLが「3」の場合、データ処理部13は、ステップS205に進み、ルート(「¥MAP」)の後に、ステップS203で導出したファイル名(「¥M1606.map」)を付加して、パス名を導出する。したがって、パス名は「¥MAP¥M1606.map」となる。データ処理部13は、導出したパス名を読み出し/書き込み制御部18に出力する(ステップS205)。読み出し/書き込み制御部18は、入力されたパス名(「¥MAP¥M1606.map」)に従って、地図ファイルCFを第1の記憶装置19内の第1のデータベース111から読み出す。読み出し/書き込み制御部18は、読み出した地図ファイルCFをデータ処理部13内の主記憶(図示せず)に転送する。このようにして、データ処理部13は、地図ファイルCFを第1の記憶装置19から主記憶に読み込む(ステップS206)。

0113

ところで、上述したように、ステップS202で指定されたレベルは「0」であるから、データ処理部13は、ステップS204においてレベルLが「3」でないと判断して、ステップS207に進む。データ処理部13は、ステップS203で導出した商DLON3の余りRLON3を算出した後、当該余りRLON3をレベル「2」の経度幅W2で除算した時の商DLON2を算出する。さらに、データ処理部13は、ステップS203で導出した商DLAT3の余りRLAT3を算出した後、当該余りRLAT3をレベル「2」の緯度幅H2で除算した時の商DLAT2を算出する。今、上述した数値を用いた場合、商DLON2および商DLAT2は、DLON2=4およびDLAT2=1となる。データ処理部13は、算出された商DLON2および商DLAT2を順番に並べて4桁の数字を作成する。今回作成される4桁の数字は、「0401」である。ここで、商DLON2および/または商DLAT2が1桁となる場合は、2桁目に「0」を付ける。

0114

データ処理部13は、作成した4桁の数字の先頭に、ディレクトリの識別子「¥」およびファイル名の頭文字を定義する「M」を付加し、さらにその末尾にファイル名の拡張子「.map」を付加する。これによって、データ処理部13は、代表点の経度座標LON0 および緯度座標LAT0 から、読み込むべき地図ファイルCFのファイル名(今回の場合、「¥M0401.map」)を導き出す。さらに、データ処理部13は、作成した4桁の数字の先頭に、ディレクトリの識別子「¥」およびサブディレクトリ名の頭文字を定義する「D」を付加する。これによって、データ処理部13は、代表点の経度座標LON0 および緯度座標LAT0 から、読み込むべき地図ファイルCF(ユニットU0 のもの)が格納されたサブディレクトリ名(今回の場合「¥D0401])を導出する(ステップS207)。

0115

次に、データ処理部13は、ステップS202で指定されたレベルLが「2」か否かを判断する(ステップS208)。レベルLが「2」の場合、データ処理部13は、ステップS205に進み、ルート(「¥MAP」)の後に、ステップS203で導出したサブディレクトリ名(「¥D1606」)およびステップS207で導出したファイル名(「¥M0401.map」)を付加して、パス名を導出する。したがって、パス名は「¥MAP¥D1606¥M0401.map」となる。データ処理部13は、導出したパス名を読み出し/書き込み制御部18に出力する(ステップS209)。読み出し/書き込み制御部18は、入力されたパス名(「¥MAP¥D1606¥M0401.map」)に従って、地図ファイルCFを第1の記憶装置19内の第1のデータベース111から読み出す。読み出し/書き込み制御部18は、読み出した地図ファイルCFをデータ処理部13内の主記憶(図示せず)に転送する。このようにして、データ処理部13は、地図ファイルCFを第1の記憶装置19から主記憶に読み込む(ステップS206)。

0116

上述したように、ステップS202で指定されたレベルは「0」であるから、データ処理部13は、ステップS208においてレベルLが「2」でないと判断して、ステップS2010に進む。データ処理部13は、ステップS207で導出した商DLON2の余りRLON2を算出した後、当該余りRLON2をレベル「1」の経度幅W1で除算した時の商DLON1を算出する。さらに、データ処理部13は、ステップS207で導出した商DLAT2の余りRLAT2を算出した後、当該余りRLAT2をレベル「1」の緯度幅H1で除算した時の商DLAT1を算出する。今、上述した数値を用いた場合、商DLON1および商DLAT1は、DLON1=5およびDLAT1=3となる。データ処理部13は、算出された商DLON1および商DLAT1を順番に並べて4桁の数字を作成する。今回作成される4桁の数字は、「0503」である。ここで、商DLON1および/または商DLAT1が1桁となる場合は、2桁目に「0」を付ける。

0117

データ処理部13は、作成した4桁の数字の先頭に、ディレクトリの識別子「¥」およびファイル名の頭文字を定義する「M」を付加し、さらにその末尾にファイル名の拡張子「.map」を付加する。これによって、データ処理部13は、代表点の経度座標LON0 および緯度座標LAT0 から、読み込むべき地図ファイルCFのファイル名(「¥M0503.map」)を導き出す。さらに、データ処理部13は、作成した4桁の数字の先頭に、ディレクトリの識別子「¥」およびサブディレクトリ名の頭文字を定義する「D」を付加する。これによって、データ処理部13は、代表点の経度座標LON0 および緯度座標LAT0 から、読み込むべき地図ファイルCF(ユニットU0 のもの)が格納されたサブディレクトリ名(今回の場合「¥D0503])を導出する(ステップS2010)。

0118

次に、データ処理部13は、ステップS202で指定されたレベルLが「1」か否かを判断する(ステップS2011)。レベルLが「1」の場合、データ処理部13は、ステップS2012に進み、ルート(「¥MAP」)の後に、ステップS203で導出したサブディレクトリ名(「¥D1606」)、ステップS207で導出したサブディレクトリ名(「¥D401」)およびステップS2010で導出したファイル名(¥M0503.map)を付加して、パス名を導出する。したがって、パス名は「¥MAP¥D1606¥D0401¥M0503.map」となる。データ処理部13は、導出したパス名を読み出し/書き込み制御部18に出力する(ステップS2012)。読み出し/書き込み制御部18は、入力されたパス名(「¥MAP¥D1606¥D0401¥M0503.map」)に従って、地図ファイルCFを第1の記憶装置19内の第1のデータベース111から読み出す。読み出し/書き込み制御部18は、読み出した地図ファイルCFをデータ処理部13内の主記憶(図示せず)に転送する。このようにして、データ処理部13は、地図ファイルCFを第1の記憶装置19から主記憶に読み込む(ステップS206)。

0119

上述したように、ステップS202で指定されたレベルLは「0」であるから、データ処理部13は、ステップS2011においてレベルLが「1」でないと判断して、ステップS2010に進む。データ処理部13は、ステップS2010で導出した商DLON1の余りRLON1を算出した後、当該余りRLON1をレベル「0」の経度幅W0で除算した時の商DLON0を算出する。さらに、データ処理部13は、ステップS2010で導出した商DLAT1の余りRLAT1を算出した後、当該余りRLAT1をレベル「0」の緯度幅H0で除算した時の商DLAT0を算出する。今、上述した数値を用いた場合、商DLON0および商DLAT0は、DLON0=2およびDLAT0=1となる。データ処理部13は、算出された商DLON0および商DLAT0を順番に並べて4桁の数字を作成する。今回作成される4桁の数字は、「0201」である。ここで、商DLON0および/または商DLAT0が1桁となる場合は、2桁目に「0」を付ける。データ処理部13は、作成した4桁の数字の先頭に、ディレクトリの識別子「¥」およびファイル名の頭文字を定義する「M」を付加し、さらにその末尾にファイル名の拡張子「.map」を付加する。これによって、データ処理部13は、代表点の経度座標LON0 および緯度座標LAT0 から、読み込むべき地図ファイルCFのファイル名(今回の場合、「¥M0201.map」)を導き出す(ステップS2013)。ここで、ステップS2013では、レベルLが最下位層の「0」と自動的に判断できるので、データ処理部13は、サブディレクトリ名を導出しない。

0120

次に、データ処理部13は、ステップS2014に進み、ルート(「¥MAP」)の後に、ステップS203、S207およびS2010で導出したサブディレクトリ名の配列(「¥D1606¥D401¥D0503)ならびにステップS2013で導出したファイル名(今回の場合、「¥M0201.map」)を付加して、パス名を導出する。したがって、パス名は「¥MAP¥D1606¥D0401¥D0503¥M0201.map」となる。データ処理部13は、導出したパス名を読み出し/書き込み制御部18に出力する(ステップS2014)。読み出し/書き込み制御部18は、入力されたパス名(「¥MAP¥D1606¥D0401¥M0503.map」)に従って、地図ファイルCFを第1の記憶装置19内の第1のデータベース111から読み出す。読み出し/書き込み制御部18は、読み出した地図ファイルCFをデータ処理部13内の主記憶(図示せず)に転送する。このようにして、データ処理部13は、所望の地図ファイルCF(ユニットU0 を表す地図を表示可能なデータ)を第1の記憶装置19から主記憶に読み込む(ステップS206)。

0121

データ処理部13は、以上のステップS206の後、図35のフローチャートから抜けて、図34のステップS104に進む。データ処理部13は、主記憶上に読み込まれた地図ファイルCFを用いて、出発地SP側からの経路探索処理を行う(ステップS104)。ここで注意を要するのは、ダイクストラ法等の手法は周知であるため、その詳細な説明を省略する。ダイクストラ法等を簡単に説明すると、地図ファイルCF内の道路ネットワークの接続をたどりながら最短ルートを求める処理が行われる。かかる地図ファイルCF内でのノードNとリンクLの接続関係をたどる手順については、図32を参照して前述の通りである。

0122

また、データ処理部13は、ステップS102の後、ステップS103と並行して、ステップS105を実行する。データ処理部13は、ステップS102で設定された目的地DP周辺の地図ファイルCFを第1の記憶装置19から、自身の内部に有する主記憶(図示せず)に読み込む(ステップS105)。さらに、データ処理部13は、ステップS105で読み込んだ地図ファイルCFを用いて、目的地DP側の経路探索処理を行う(ステップS106)。ここで、ステップS105およびS106の処理については、ステップS103およびステップS104と同様であるため詳細な説明は省略する。

0123

データ処理部13は、ステップS104およびS106の処理が終了すると、当該ステップS104およびS106で使用された地図ファイルCFの階層での探索終了条件を満たしたか否かの判断を行う(ステップS107)。ステップS107では、一般的に、読み込んだ地図ファイルCFの数、または探索したノードNの数等が所定の値に達しているか否かに基づいて、探索条件が終了したか否かが判断される。ステップS107において探索終了条件を満たしていないと判断された場合には、データ処理部13は、ステップS103およびS105に戻って、出発地SP側および目的地DP側の双方からの探索処理で既に読み込まれている地図ファイルCFに隣接する地図ファイルCFを読み込む。ここで、既に読み込まれている地図ファイルCFがユニットUの地図を表すとすると、隣接する地図ファイルCFは、隣接ユニットNU(図26参照)の地図を表すこととなる。データ処理部13は、新たな代表点の経度座標LONおよび緯度座標LATを求めて、隣接する地図ファイルCFのパス名を導出し、当該パス名により特定される地図ファイルCFを第1の記憶装置19から主記憶に読み込む。

0124

ここで、図36に示すように、隣接ユニットNUを決定するための新しい代表点の位置は、道路網の接続をたどるリンクLが、どのユニット境界上の隣接ノード(詳しくは図26を参照)を経由して当該隣接ユニットNU内のリンクLと接続するかによって異なる。より具体的に説明すると、図36のリンクL11は、ユニットUの境界(矩形)の上辺上に位置する隣接ノードN12を経由して隣接ユニットNU1のあるリンクLと接続する。このため、ユニットUの代表点Pの緯度座標LATに対して、当該ユニットUが属するレベルLの緯度幅Hを加算した緯度座標LAT1をもつ地点が新しい代表点P1と定められる。

0125

一方、図36のリンクL12は、ユニットUの境界(矩形)の右辺上に位置する隣接ノードN13を経由して隣接ユニットNU2内のあるリンクLと接続する。このため、ユニットUの代表点Pの経度座標LONに対して、当該ユニットUが属するレベルLの経度幅Wを加算した経度座標LON2をもつ地点が新しい代表点P2と定められる。

0126

2回目以降のステップS103およびS105では、データ処理部13は、図36を参照して説明したようにして求められた新しい代表点に基づいて、当該代表点を含む範囲を表す地図の地図ファイルCFを読み込む。なお、この際の処理手順は前述の通りである。次のステップS104およびS106では、データ処理部13は、ステップS103およびS105で読み込んだ地図ファイルCFを使って探索処理を行う。かかる探索処理は、前回読み込んだ地図ファイルCFから今回読み込んだものへと、つまりユニットUと隣接ユニットNUとの境界をまたいで道路網の接続をたどることを意味している。

0127

ところで、従来の技術では、ユニットUおよび隣接ユニットNUの境界をまたいだ場合であっても、道路網の接続をたどることができるように、各地図ファイルの隣接ノードのレコードに、隣接ユニットNUの隣接ノードを特定する番号またはオフセットアドレス等が記録されていた。しかし、このような地図ファイルの内部データ構造に関わる情報を当該ユニットに記録してしまうと、隣接ユニットNUを表す地図ファイルが更新された場合、上記番号またはオフセットアドレスが変わってしまう場合がある。したがって、1つの地図ファイルが更新されることにより、その周囲のすべての隣接ユニットNUを表す地図ファイルが更新される必要が生じるおそれがあるという問題点があった。かかる問題点を解消すべく、本実施形態の各地図ファイルCFには、隣接ユニットNUの内部データ構造に直接関わる情報は記録されておらず、データ処理部13は、ノードNの座標情報および/またはリンクLの属性情報を用いて、隣接ユニットNUの隣接ノードNをたどる処理を実行する。

0128

以下、図37および図38の2つの図面を参照して、図34のステップS104またはS106における、データ処理部13がユニットUと隣接ユニットNUの境界をまたいで道路網の接続をたどる処理について詳細に説明する。図37は、互いに隣接し合う4個のユニットU1〜U4を並べた際に構成される道路網を示している。ユニットU1に含まれる道路網は、4個のノードN10〜N13と、3個のリンクL10〜L12とから構成される。ユニットU1では、3個のノードN10、N12およびN13(●印参照)は隣接ノードであって、ユニットU1の境界上に位置する。また、ユニットU2に含まれる道路網は、5個のノードN20〜N24と、4個のリンクL20〜L23とから構成される。ユニットU2では、4個のノードN20およびN22〜24(●印参照)は、隣接ノードであって、ユニットU2の境界上に位置する。また、ユニットU3に含まれる道路網は、4個のノードN30〜N33と、3個のリンクL30〜L32とから構成される。ユニットU3では、ノードN30、N32およびN33(●印参照)が隣接ノードであり、ユニットU3の境界上に位置する。さらに、ユニットU4に含まれる道路網は、4個のノードN40〜N43と、3個のリンクL40〜L42とから構成される。3個のノードN40〜N43(●印参照)は、隣接ノードであって、ユニットU4の境界上に位置する。さらに、図37において、ノードN13およびN20が接続され、ノードN12およびN30が接続され、ノードN24およびN43が接続され、さらにノードN33およびN40が接続され、これによって、1つの道路網が構成される。

0129

以上の図37の道路網において、リンクL12は、隣接ノードN13およびN20を経由して、リンクL20とつながっている。上述したように、経路探索処理において、データ処理部13は、隣接ユニットNUを表す地図ファイルCFを順次読み込んで、目的地DPまたは出発地SPの方向へと探索を広げていく。そのためには、データ処理部13は、あるユニットUおよび隣接ユニットNUの境界をまたぐような2個のリンクLの接続関係をたどる必要がある。そこで、まず、データ処理部13は、主記憶上に読み込まれたユニットU(つまり、ユニットU1)の地図ファイルCF(より具体的には、リンクレコードRR(図30および図31参照))から、ユニットU1からユニットU2へと向かうリンクL12のリンク属性を取り出す(図38;ステップS301)。以下では、ユニットU1の境界へと向かうリンクL12を脱出リンクL12と呼ぶこととする。

0130

次に、データ処理部13は、脱出リンクL12の接続先情報(ノードレコード番号またはオフセットアドレス)を参照して、地図ファイルCF(より具体的には、第1または第2のノードテーブル)から、当該脱出リンクL12に接続された隣接ノードN13のノードレコードNR(図27参照)を探し出す。その後、データ処理部13は、探し出したノードレコードNRから、隣接ノードN13のノード座標を取り出す(ステップS302)。以下では、脱出リンクL12に接続された隣接ノードN13を脱出ノードN13と呼ぶこととする。

0131

次に、データ処理部13は、主記憶上に読み込まれている隣接ユニットNU(つまり、ユニットN2)の地図ファイルCF(より具体的には、第1または第2のノードテーブル)から、ノード座標を1つずつ取り出す(ステップS303)。データ処理部13は、ステップS302で取り出した脱出ノードN13のノード座標と、ステップS303で取り出したノード座標との差分値を算出して、当該差分値が所定の閾値以下であるか否かを判断する(ステップS304)。ここで、図29を参照して説明したように、本実施形態では、ノード座標は正規化された値で記録されている。上記所定の閾値としては、正規化された座標値の幅により異なるが、「1」〜「2」程度の値が好ましい。データ処理部13は、ステップS304の条件を満たすまで、ステップS303およびS304を繰り返し実行する。ただし、データ処理部13は、ステップS303を実行するたびに、過去に取り出したものとは異なるノード座標を取り出す。ここで、ステップS304の条件を満たすということは、ステップS303で取り出したノード座標を有するノードNが脱出ノードN13と同じ位置を示していることとなる。つまり、制御部13は、ステップS303およびS304を繰り返し実行することにより、脱出ノードN13とほぼ同じ位置を有する隣接ノードN20を探し出すことができる。以下では、探し出された隣接ノードN20を進入ノードと呼ぶこととする。

0132

ここで、一般的に、ステップS303においては、ノードレコード番号(図28参照)の順番に従って、ノード座標が1つずつ順番に取り出される。本実施形態では、図26および図28を参照して説明したように、第1または第2のノードレコードにおいて、隣接ノードNのノードレコードNRは、非隣接レコードNのノードレコードNRの前に記録されている。これによって、データ処理部13は、非隣接ノードNのノードレコードNRからノード座標を取り出すことなく、進入ノードを見つけ出すことができる。これによって、データ処理部13が進入ノードを検索する処理の負荷を最小限に抑えることができる。すわなち、データ処理部13は、隣接ユニットNUの地図ファイルCFに記録された第1および第2のノードテーブル内に並ぶ全てのノードレコードNRを検索しなくても、当該第1または第2のノードテーブルの先頭から隣接ノードの数だけノードレコードNRを検索すれば、必ず進入ノードを見つけ出すことができる。このように、本実施形態におけるノードレコードNRの並べ方は、進入ノードを検索する処理の高速化にも寄与する。

0133

また、隣接ノードのノードレコードNRは、図26を参照して説明したように、ユニットU(矩形)の左辺→上辺→右辺→下辺という優先順位に従って並べられる。さらに、左辺および右辺上に位置する隣接ノードのノードレコードNRは緯度の昇順に並べられ、上辺および下辺上に位置する隣接ノードのノードレコードNRは経度の昇順に並べられる。また、非隣接ノードのレコードNRについては、まず緯度の昇順に並べられ、緯度が同一座標の複数の非隣接ノードのレコードNRについては経度の昇順に並べられる。かかる並べ方によって、進入ノードの検索処理をさらに高速化することができる。例えば、上記の並べ方の規則に従えば、図39の隣接ノードN10〜N20のノードレコードNRは、N10→N11→N12→N13→N14→N15→N16→N17→N18→N19→N20の順で、ユニットU1の地図ファイルCF内に記録される。同様に、隣接ノードN20〜N27のノードテーブルU2のノードレコードNRは、N20→N21→N22→N23→N24→N25→N26→N27の順で、ユニットU2の地図ファイルCF内に記録される。さらに、ユニットU3の地図ファイルCF内には、ノードN30→N31→N32→N33→N34→N35→N36→N37→N38の順にノードレコードNRが記録される。

0134

通常、経路探索処理では、読み込んだ地図ファイルCF内で探索が広げられ、探索中のルートが隣接ノードに到達した際には、その対応する隣接ユニットNUが新たに読み込まれる。本実施形態では、隣接ユニットNUの地図ファイルCFが読み込まれた際に、まず前回読み込まれた地図ファイルCFと今回読み込まれた地図ファイルCFとの、ユニットの間の境界上に存在する全隣接ノードの対応付けが行われる。この際に、前述のようにノードテーブルにおいて、隣接ノードのノードレコードNRが、上述した順位で記録されることにより、隣接ノードの対応付けを高速化することができる。このため、例えば、ユニットU1の隣接ノードN12と同じ位置を示すユニットU3の隣接ノードN35が見つかれば、ユニット1の次の隣接ノードN13に対応するユニット3の隣接ノードN36は必ずN35の次のレコードに並んでいる。また同様に、ユニット2の隣接ノードN20に対応するユニット1の隣接ノードN16が見つかれば、ユニット2の次の隣接ノードN21に対応するユニット1の隣接ノードN17は必ずN16の次のレコードに並んでいる。このように、前述のような規則性に従って隣接ノードを並べることにより、隣接ユニット間における隣接ノードの検索処理を高速化することができる。

0135

さて、ステップS304で進入ノードが見つかると、データ処理部13は、進入ノードN20の接続先情報(ノードレコード番号またはオフセットアドレス)を参照して、ユニットU2の地図ファイルCF(より具体的には、第1または第2のリンクテーブル)から、当該進入ノードN20に接続されたリンクL20のリンクレコードLR(図30および図31参照)を探し出す。以下では、進入ノードN20に接続されたリンクL20を進入リンクL20と呼ぶこととする。その後、データ処理部13は、探し出したリンクレコードLRから、進入リンクL20の属性情報を取り出す(ステップS305)。

0136

次に、データ処理部13は、ステップS301で取り出した脱出リンクL12の属性情報と、ステップS305から取り出した進入リンクL20の属性情報が同じか否かを判断する(ステップS306)。データ処理部13は、2つの属性情報が互いに異なると判断した場合、ステップS303に戻って、新しい進入ノードNを探す。ここで、本実施形態では、図2を参照して説明したように、互いに異なる縮尺の地図を表すいくつかの地図ファイルCFが第1の記憶装置19には格納されている。下位階層の地図ファイルCFは、詳細な道路網を表すことができるので、2つのノード座標の差分値が所定の閾値以下であれば、両ノードNが同じ位置を示す確率が相対的に高くなる。しかしながら、上位階層の地図ファイルCFは粗い道路網しか表すことができないので、2つのノード座標の差分値が所定の閾値以下であっても、両ノードNが同じ位置を示す確率は相対的に低くなる。本実施形態では、ステップS306において脱出リンクおよび進入リンクの属性を一致/不一致を判断することにより、データ処理部13が、ある道路から別の道路をたどることなく、同じ1本の道路を正確にたどるようにしている。つまり、ステップS306の処理は、下位階層の地図ファイルCFに対して実行されなくともよい。

0137

データ処理部13は、ステップS306で脱出リンクL12および進入リンクL20の属性情報が一致していると判断すると、1本の道路を正確にたどっているとみなして、図38のフローチャートから抜けて、図34のステップS107に進む。データ処理部13は、今回の読み込み続けた地図ファイルCFの階層での探索終了条件を満たしたと判断した場合、出発地SP側の経路と目的地DP側の経路がつながったかどうかを判断する(ステップS108)。データ処理部13は、出発地SP側と目的地DP側の経路とがつながっている場合には、両地点間の最短ルートが求まったと判断し、経路探索処理を終了する。一方、出発地SP側と目的地DP側との経路がまだつながっていない場合には、データ処理部13は、ステップS109に進み、1つ上位の階層に移行して、広域かつ粗い道路網を表す地図ファイルCFを使って経路探索処理を続行する。

0138

次に、ある下位階層から上位階層への以降処理について詳細に説明する。この時、データ処理部13は、下位階層における探索処理の終点となるノードN(探索中のルートの終点)から、上位階層の地図ファイルCF内に存在しかつ同じ位置を示すノードNへと移行する。したがって、データ処理部13が上位階層への移行処理を確実に行うためには、上位階層の地図ファイルCFに含まれるすべてのノードNが、その子ユニットCUの各ノードNから必ず検索できる必要がある。

0139

従来では、かかる検索を実現するために、下位階層のノードNと同じ位置を示すに上位階層のノードNのノード番号やオフセットアドレス等がノードレコード内に記録されるという方法が採用されていた。しかし、このような上位階層の地図ファイルの内部データ構造に関わる情報が下位階層の地図ファイルに記録されると、上位階層の地図ファイルが更新された場合、下位階層の地図ファイルも更新されなければ、下位階層から上位階層への移行処理をスムーズに行えなくなるという問題点があった。そこで、本実施形態では、各地図ファイルCFには、上位階層の地図ファイルCFの内部データ構造に直接関わるような情報は記録されず、階層移行を行う際にノードの座標情報やリンクの属性情報が参照される。しかし、この場合、一般的に上位階層の地図ファイルCFが表す地図は、下位階層の地図ファイルCFが表す地図に比べて座標の分解能が低い。そのため、図40に示すように、下位階層および上位階層の地図ファイルCFでは互いに異なる座標をもっていた2つのノードNが、上位階層の地図ファイルCFにおける座標の丸め誤差のために、同一の座標をもってしまう可能性がある。したがって、ノード座標だけでは、下位階層のノードNと一致する上位階層のノードNを一意に特定することはできない。

0140

そこで、本実施形態では、ノード座標だけでなく、ノードレコードNRの記録順序(並び方)が利用される。すなわち、前述のように第1または第2のノードテーブルにおけるノードレコードNRの並びの順は、隣接ノード、非隣接ノード共に明確に規定されている。このため、座標の丸め誤差が生じるような上位階層のユニットUにおいても、丸め誤差が生じる前の正規化経度緯度座標を利用して、座標の昇順でノードレコードNRが記録される。これによって、データ処理部13は、下位階層のノードNから、同じ位置を示しかつ上位階層の親ユニットPUに含まれるノードNを検索する場合にも、下位階層ユニットU内に記録されているノードNの内で、親ユニットUにも記録されており、かつ上位階層で丸め誤差が生じた場合に同一座標になると考えられるノードNの中から、ノードレコードNRの記録順序に基づいて、親ユニットPU内で対応するノードNを一意に特定することができる。

0141

より具体的には、前述のように地図ファイルCFでは、相対的に1階層上の親ユニットPUは、その子ユニットCUに対して、経度方向および緯度方向共に8倍のユニット幅を有する。その一方で、階層には関係なく、各ノードは、ユニットUの経度方向および緯度方向共に8000h(16ビット)で正規化した正規化座標をもつ。すなわち、親ユニットPUは子ユニットCUに対して、その座標分解能が、経度方向および緯度方向共に1/8であるということができる。このため、子ユニットCUの正規化経度および正規化緯度座標16ビットの内、上位13ビットが同じ値をもつノードNは、その親ユニットPUにおいて同一の正規化座標をもつことになる。

0142

例えば、図41に示すように、子ユニットCUに記録されている5つのノードNa、Nb、Nc、Nd、Neの正規化経度および正規化緯度座標16ビットの内、その上位13ビットが同じ値をもち、かつこの内の4つのノードNa、Nc、Nd、Neの親となるノードNa2、Nc2、Nd2およびNe2が親ユニットPUに記録されている(各ノードレコードNRに、親ノードPUが存在することを示すフラグあるいはコードを記録している)とする。この場合、図42に示すように、子ユニットCUのノードテーブルには、ノードNa、Nb、Nc、NdおよびNeの5個のノードレコードNRは、緯度および経度の昇順に従って(前述)、Na→Nb→Nc→Nd→Neの順に記録されている。なお、この際、ノードNa、Nb、Nc、NdおよびNeの5個のノードレコードNRは、ノードテーブル内で必ずしも連続しているわけではない。

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ