(57)【特許請求の範囲】
【請求項１】
地域に配置されている地理的特徴を表す地図データを編成する方法であって、
ナビゲーション・コンピュータによって、前記地図データを複数の個別のパーセルに分類する段階を具備し、
各パーセルは、前記地図データの一部を含み、当該各パーセルの一部は、複数の矩形エリアの対応する個別の一つに配置された地理的特徴を表し、前記地域は、複数の矩形エリアに分割されており、第１の座標方向における一様なディメンションと当該第１の座標方向に垂直をなす第２の座標方向におけるディメンションとに対応するサイズを有する各矩形エリアは、各パーセルに含まれる地図データの一部が所定の最大パーセル・データ・サイズを越えないように選択されており、
第２の座標方向に伸びている境界であって、他の矩形エリアと第２の座標方向で隣接する各矩形エリアについての境界は、同一線上にあることを特徴としており、
さらに、方法が、
ナビゲーション・コンピュータによって、前記パーセルをコンピュータ用記憶媒体に保存する段階を具備する方法。
【請求項２】
前記第１の座標方向は、緯度であり、前記第２の座標方向は、経度であることを特徴とする請求項１に記載の方法。
【請求項３】
前記第１の座標方向は、経度であり、前記第２の座標方向は、緯度であることを特徴とする請求項１に記載の方法。
【請求項４】
前記コンピュータ用記憶媒体は、ＣＤ−ＲＯＭディスクであることを特徴とする請求項１に記載の方法。
【請求項５】
前記コンピュータ用記憶媒体は、ＤＶＤ−ＲＯＭディスクであることを特徴とする請求項１に記載の方法。
【請求項６】
前記コンピュータ用記憶媒体は、ハードディスクであることを特徴とする請求項１に記載の方法。
【請求項７】
前記分類する段階は、さらに、前記パーセルを順次編成することを特徴とする請求項１に記載の方法。
【請求項８】
前記分類する段階は、さらに、
前記地図データを複数の個別のコレクションに分類する段階を具備し、
各個別コレクションは、対応する個別のセクションに配置されている地理的特徴を表す地図データの一部を含み、前記第１の座標方向における一様なディメンションに対応するサイズを有する各セクションは、前記第２の座標方向における地域にわたり伸びており、  さらに、前記分類する段階は、
第１の座標方向における地域の第１のエッジに配置されたセクションに含まれる矩形エリアに含まれる地図データを表しているパーセルから開始して、当該パーセルに直ぐ隣接するセクションに含まれた矩形エリアに含まれた地図データを表しているパーセルに向けて、さらに、地域の第２のエッジに配置されたセクションに含まれた矩形エリアに含まれた地図データを表しているパーセルまで、パーセルを順次編成する段階を具備し、第２のエッジは、第１のエッジの反対側であることを特徴する請求項１に記載の方法。
【請求項９】
前記分類する段階は、さらに、
前記パーセルを当該パーセルに対応する矩形エリアの地理的座標によって順次編成する段階を更に具備することを特徴とする請求項１に記載の方法。
【請求項１０】
ナビゲーション・コンピュータが、パーセルＩＤを各パーセルに割り当てる段階を更に具備することを特徴とする請求項１に記載の方法。
【請求項１１】
ナビゲーション・コンピュータが、パーセルに当該パーセルに対応するパーセルＩＤｓを割り当てる段階を更に具備し、前記パーセルＩＤｓは、パーセルよって表される矩形エリアの地理的座標により順次割り当てられることを特徴とする請求項１に記載の方法。
【請求項１２】
前記パーセルは、一つのコーナーに配置された矩形エリアに含まれる地理的特徴を表す地図データを含んでいるパーセルで開始しかつ反対側のコーナーに配置された矩形エリアに含まれる地理的特徴を表す地図データを含んでいるパーセルで終了する通し番号技術によって識別されることを特徴とする請求項１に記載の方法。
【請求項１３】
前記一様なディメンションは、ナビゲーション・コンピュータのディスプレイ画面上に表示することができる座標方向の最大変化に対応することを特徴とする請求項１に記載の方法。
【請求項１４】
前記一様なディメンションは、ナビゲーション・コンピュータのディスプレイ画面上に表示することができる緯度又は経度の最大変化に対応することを特徴とする請求項１に記載の方法。
【請求項１５】
前記一様なディメンションは、ナビゲーション・コンピュータのディスプレイ画面上に表示することができる所与のズーム・レベルにおける座標方向の最大変化に対応することを特徴とする請求項１に記載の方法。
【請求項１６】
地域に配置されている地理的特徴を表す地図データを編成するためのコンピュータプログラムが、ナビゲーション・コンピュータに、
前記地図データを複数の個別のパーセルに分類する段階を実行させ、
各パーセルは、前記地図データの一部を含み、当該各パーセルの一部は、複数の矩形エリアの対応する個別の一つに配置された地理的特徴を表し、前記地域は、複数の矩形エリアに分割されており、第１の座標方向における一様なディメンションと当該第１の座標方向に垂直をなす第２の座標方向におけるディメンションとに対応するサイズを有する各矩形エリアは、各パーセルに含まれる地図データの一部が所定の最大パーセル・データ・サイズを越えないように選択されており、
第２の座標方向に伸びている境界であって、他の矩形エリアと第２の座標方向で隣接する各矩形エリアについての境界は、同一線上にあることを特徴としており、
コンピュータプログラムが、ナビゲーション・コンピュータに、さらに、
前記パーセルをコンピュータ用記憶媒体に保存する段階を実行させることを特徴とするコンピュータプログラム。
【請求項１７】
地域に配置された地理的特徴を表す地図データを編成する方法であって、
ナビゲーション・コンピュータが、パーセルに対応する矩形エリアに対する第１の座標方向における一様なディメンションを決定する段階と；
ナビゲーション・コンピュータが、パーセルに対する最大データ・サイズを決定する段階と；及び
ナビゲーション・コンピュータが、前記地図データを個別のパーセルに分類する段階とを具備し、
各パーセルは、対応する個別の矩形エリアに配置された地理的特徴を表す前記地図データの一部を含み、
各矩形エリアは、第１の座標方向における一様なディメンションに対応するサイズ、及びパーセルに含まれる地図データの一部がパーセルに対する最大データ・サイズを越えないように選択される第２の座標方向におけるディメンションを有し、
前記第２の座標方向に伸びている境界であって、他の矩形エリアと第２の座標方向で隣接する各矩形エリアについての境界は、同一線上にあることを特徴としており、
さらに、方法が、
ナビゲーション・コンピュータによって、前記パーセルをコンピュータ用記憶装置に保存する段階を具備することを特徴とする方法。
【請求項１８】
前記第１の座標方向は、経度であり、かつ前記第２の座標方向は、緯度であることを特徴とする請求項１７に記載の方法。
【請求項１９】
前記分類する段階は、
順次前記パーセルを編成する段階を更に具備することを特徴とする請求項１７に記載の方法。
【請求項２０】
前記分類する段階は、
前記パーセルによって表される矩形エリアの地理的座標により該パーセルを配列する段階を更に具備することを特徴とする請求項１７に記載の方法。
【請求項２１】
ナビゲーション・コンピュータが、前記パーセルのそれぞれにパーセル識別番号を割り当てる段階を更に具備することを特徴とする請求項１７に記載の方法。
【請求項２２】
ナビゲーション・コンピュータが、前記パーセルのそれぞれに順次パーセル識別番号を割り当てる段階を更に具備することを特徴とする請求項１７に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、ナビゲーション・システムにおけるもののようなナビゲーション・アプリケーション・プログラムによる地図データの使用を容易にする地図データの編成及び記憶のための方法及びシステムに関する。また、本発明は、上記編成の方法を有しているそこに記憶された地図データを有している物理的な記憶媒体に関する。
【０００２】
【従来の技術】
ほとんどのナビゲーション・システムは、読取り専用ディスク（例えば、ＣＤ−ＲＯＭディスク、ＤＶＤ−ＲＯＭディスク、等）又はハード・ディスクに記憶される地図データを使用する。地図ディスプレイのような、あるナビゲーション・システムの特徴の性能に影響を及ぼす重要なファクタは、ディスクから地図データをフェッチするために必要な時間である。地図データをフェッチするために必要な時間の大部分は、デバイスのシーク時間（即ち、現在のトラックからデータが配置されるトラックに移動するためのナビゲーション・システムの読取りヘッドのための時間）によるところが大きい。このファクタは、ＣＤ−ＲＯＭ及びＤＶＤ−ＲＯＭディスクに対して重要であるがハード・ディスクにもある程度適用する。
【０００３】
シーク時間がディスクからデータをフェッチするために必要な時間の大部分を占めるので、所与の要求に対するシークの回数（それゆえに合計シーク時間）を低減しそれによってナビゲーション・システムの性能を改良するような地図データを編成するための技術が開発されている。ある一定のナビゲーション・システム機能に対して地図データをアクセスする場合のシークの回数を低減するための一つの方法は、空間的に地図データを編成することである。一般的に、地図データが空間的に編成される場合、地理的地域において物理的に互いに近い地理的特徴は、地図データベースにおいて物理的に（又は論理的に）互いに近い（及び潜在的にまた地図データが記憶される媒体で互いに近い）データ記録によって表される。
【０００４】
それにより地理的特徴を表すデータを空間的に編成することができる様々な方法が存在する。地理的特徴を表すデータを空間的に編成することができる方法の一つは、互いに近くに配置された地理的特徴を表すデータ・エンティティのグループを最初に識別し次いでグループを空間的に配列することである。データのグループは、“パーセル”、“バケット”又は“地図地域”と称されうるが、他の用語を用いることもありうる。また、各グループ内のデータ・エンティティは、空間的に編成されうるか又はグループ内のデータ・エンティティは、別の配列により編成されうる。地図データを空間的に編成する方法は、ここにその開示全体が参考文献として採り入れられる米国特許公報第５，９６８，１０９号及び５，９７４，４１９号に記述されている。
【０００５】
【発明が解決しようとする課題】
ある地図データ・パーセル化技術は、一様なデータ・サイズ・パーセル（例えば、３２又は６４キロバイト／パーセル）又は固定地理的サイズ・パーセル（例えば、０．０２度デルタ緯度×０．０３デルタ経度又はある他の緯度／経度“矩形”）を達成しようとしている。一様なデータ・サイズ・パーセルの欠点は、地図ディスプレイ矩形がディスク上で隣接していないいくつかのパーセルをスパンする場合に、いくつかのシークは、要求されたデータをフェッチすることを必要とし、それによりナビゲーション・システムの性能に対して潜在的にマイナスに影響を及ぼすということである。他方、一様な地理的サイズ・パーセルの欠点は、パーセルのデータ・サイズが稠密実装エリアから希薄実装エリアまで広い範囲で変化するということである。各一様な地理的サイズ・パーセルに対応するエリアがあまりにも小さい場合には、各パーセルに関する上方を記憶するために必要なオーバーヘッドは、過度になる。しかしながら、各一様な地理的サイズ・パーセルに対応するエリアがあまりにも大きい場合には、稠密実装地域に含まれるデータの量は、パーセルのデータ・サイズ制限（限度）を越えうる。例えば、パーセルのバイト・ポジションを位置決めするために２バイト・オフセットが用いられる場合には、６４キロバイトの固有の制限は、パーセルに記憶することができるデータの量を抑制する。
【０００６】
従って、地域にわたるデータ密度における広い範囲の変化に適合すると同時に、エリアを表すために必要なデータを取得するために必要なフェッチの回数を低減する地図データを編成するための改良された方法に対する必要性が存在する。
【０００７】
【課題を解決するための手段】
上述した課題及び他の課題を達成するために、本発明は、ナビゲーション・システムにおけるナビゲーション・アプリケーション・プログラムのようなナビゲーション・アプリケーション・プログラムによって地図データの使用を容易にする地図データを編成しかつ記憶する方法及びシステムを備えている。地図データは、地域に配置された地理的特徴を表す。地図データは、各パーセルが地図データの一部を含むようにパーセルに編成される。各パーセルに含まれる地図データは、地域に配置された複数の矩形エリアの対応する個別のものに含まれるそれらの地理的特徴を表す。各矩形エリアは、第１の座標方向に一様なディメンションを有するが、しかし矩形エリアに含まれる地理的特徴を表す地図データがパーセルに対する最大データ・サイズに近いがそれを越えないような他の座標方向にディメンションを有する。
【０００８】
【発明の実施の形態】
本発明は、地域に配置された地理的特徴を表す地図データを記憶する方法であって、前記地図データを複数の個別の中間コレクションに分類する段階と、各中間コレクションに含まれる前記地図マップを個別のパーセルに分類する段階とを具備し、各個別の中間コレクションは、対応する個別の中間セクションに配置された地理的特徴を表す前記地図データの一部を含み、各中間セクションは、第１の座標方向における第１の次元に対応しかつ第２の座標方向の地域にわたり拡張するサイズを有し、かつ各パーセルは、対応する個別の矩形エリアに配置された地理的特徴を表す前記地図データの一部を含み、各矩形エリアは、第１の座標方向における第１の次元に対応するサイズ及び パーセルに含まれる地図データの一部が所定の最大パーセル・サイズを越えないように選択される第２の座標方向におけるディメンションを有するように構成してもよい。
【０００９】
本発明の方法では、前記第１の座標方向は、緯度であり、前記第２の座標方向は、経度であってもよい。
【００１０】
本発明の方法では、前記第１の座標方向は、経度であり、前記第２の座標方向は、緯度であってもよい。
【００１１】
本発明の方法では、物理的記憶媒体に前記パーセルを記憶する段階を更に具備してもよい。
【００１２】
本発明の方法では、前記物理的記憶媒体は、ＣＤ−ＲＯＭディスクであってもよい。
【００１３】
本発明の方法では、前記物理的記憶媒体は、ＤＶＤ−ＲＯＭディスクであってもよい。
【００１４】
本発明の方法では、前記物理的記憶媒体は、ハードディスクであってもよい。
【００１５】
本発明の方法では、各中間コレクションに含まれる前記地図データを個別のパーセルに分類する段階の後、媒体上に連続的に前記パーセルを編成する段階を更に具備してもよい。
【００１６】
本発明の方法では、各中間コレクションに含まれる前記地図データを個別のパーセルに分類する段階の後、第１の座標方向の地域の第１のエッジに配置された中間セクションに含まれる矩形エリアに含まれる地図データを表しているパーセルで開始して媒体上に連続的に前記パーセルを編成し、そして地域の第２のエッジに配置された中間セクションに含まれた矩形エリアに含まれた地図データを表しているパーセルが媒体上に連続的に編成されるまで、それに直ぐ隣接する中間セクションに含まれた矩形エリアに含まれた地図データを表しているパーセル、等に続く段階を更に具備し、第２のエッジは、第１のエッジの反対側であってもよい。
【００１７】
本発明の方法では、各中間コレクションに含まれる前記矩形エリアに含まれる前記地図データを表しているパーセルに対して、第２の座標方向の地域の第１のエッジに配置された矩形エリアに含まれる地理的特徴を表している地図データを含んでいるパーセルで開始して媒体上に連続的に前記パーセルを編成し、そして第２の座標方向の地域の第２のエッジに配置された矩形エリアに含まれた地図データを表しているパーセルが媒体上に連続的に編成されるまで、それに直ぐ隣接する矩形エリアに含まれた地図データを表しているパーセル、等に続く段階を更に具備し、第２のエッジは、第１のエッジの反対側であり、媒体上に連続的に編成されてもよい。
【００１８】
本発明の方法では、それによって表される対応矩形エリアの地理的座標によって媒体上に連続的にパーセルを編成する段階を更に具備してもよい。
【００１９】
本発明の方法では、パーセルＩＤを各パーセルに割り当てる段階を更に具備してもよい。
【００２０】
本発明の方法では、パーセルにパーセルＩＤｓを割り当てる段階を更に具備し、前記パーセルＩＤｓは、それによって表される対応矩形エリアの地理的座標により連続的に割り当てられてもよい。
【００２１】
本発明の方法では、前記パーセルは、一つのコーナーに配置された矩形エリアに含まれる地理的特徴を表す地図データを含んでいるパーセルで開始しかつ反対側のコーナーに配置された矩形エリアに含まれる地理的特徴を表す地図データを含んでいるパーセルで終了する通し番号技術によって識別されてもよい。
【００２２】
本発明の方法では、前記第１のディメンションは、ナビゲーション・システムのディスプレイ画面上に表示することができる座標方向の最大変化に対応するようにしてもよい。
【００２３】
本発明の方法では、前記第１のディメンションは、ナビゲーション・システムのディスプレイ画面上に表示することができる緯度又は経度の最大変化に対応するようにしてもよい。
【００２４】
本発明の方法では、前記第１のディメンションは、ナビゲーション・システムのディスプレイ画面上に表示することができる所与のズーム・レベルにおける座標方向の最大変化に対応するようにしてもよい。
【００２５】
本発明の方法により形成された地図データベース製品を含んでもよい。
【００２６】
本発明の方法により編成された地図データを有するナビゲーション・システムを含んでもよい。
【００２７】
本発明の地図データベースは、地域に配置された地理的特徴を表す地図データを備え、前記地図データは、各パーセルが地域を含む複数の矩形エリアの対応する個別の矩形エリア内に含まれる地理的特徴を表す前記地図データの一部を含むようにパーセルに空間的に編成され、各パーセルの地図データの一部は、パーセルに対して決定された最大データ・サイズを越えず；前記複数の矩形形エリアの各矩形エリアは、一つの座標方向において同じディメンションを有し；かつ
前記矩形エリアは、対応矩形エリアから形成されたパーセルが、パーセルに対して決定された最大データ・サイズを越えないでパーセルに対して決定された最大データ・サイズに近いデータ・サイズを含むように変化する他の座標方向におけるディメンションを有するように構成してもよい。
【００２８】
本発明の地図データベースでは、前記地図データは、コンピュータ読取り可能媒体に記憶されるように構成してもよい。
【００２９】
本発明の地図データベースでは、前記コンピュータ読取り可能媒体は、ＣＤ−ＲＯＭディスクであってもよい。
【００３０】
本発明の地図データベースでは、前記コンピュータ読取り可能媒体は、ＤＶＤ−ＲＯＭディスクであってもよい。
【００３１】
本発明の地図データベースでは、前記コンピュータ読取り可能媒体は、ハード・ディスクであってもよい。
【００３２】
本発明のナビゲーション・システムでは、前記パーセルは、当該パーセルの対応矩形エリアの地理的座標によりコンピュータ読取り可能媒体に配列されるように構成してもよい。
【００３３】
本発明のナビゲーション・システムでは、前記パーセルのそれぞれは、パーセル識別番号が割り当てられるように構成してもよい。
【００３４】
本発明のナビゲーション・システムでは、前記複数のパーセルは、順次にパーセル識別番号が割り当てられるように構成してもよい。
【００３５】
本発明のナビゲーション・システムでは、前記複数のパーセルは、行によってかつ各行内で順次にパーセル識別番号が割り当てられるように構成してもよい。
【００３６】
本発明の方法は、地域に配置された地理的特徴を表す地図データを記憶する方法であって、データ・パーセルに対応する矩形エリアに対する第１の座標方向における一様なディメンションを決定する段階と；パーセルに対する最大データ・サイズを決定する段階と；及び前記地図データを個別のパーセルに分類する段階とを具備し、各パーセルは、対応する個別の矩形エリアに配置された地理的特徴を表す前記地図データの一部を含み、各矩形エリアは、第１の座標方向における一様なディメンションに対応するサイズ、及びパーセルに含まれる地図データの一部がパーセルに対する最大データ・サイズを越えないように選択される第２の座標方向におけるディメンションを有することを特徴とする。
【００３７】
本発明の方法では、前記第１の座標方向は、経度であり、かつ前記第２の座標方向は、緯度であってもよい。
【００３８】
本発明の方法では、物理的記憶媒体に前記パーセルを記憶する段階を更に具備してもよい。
【００３９】
本発明の方法では、前記地図データを個別のパーセルに分類する段階の後で、順次媒体上に前記パーセルを編成する段階を更に具備してもよい。
【００４０】
本発明の方法では、前記パーセルによって表される対応矩形エリアの地理的座標によりコンピュータ読取り可能媒体に該パーセルを配列する段階を更に具備してもよい。
【００４１】
本発明の方法では、前記パーセルのそれぞれにパーセル識別番号を割り当てる段階を更に具備してもよい。
【００４２】
本発明の方法では、前記パーセルのそれぞれに順次パーセル識別番号を割り当てる段階を更に具備してもよい。
【００４３】
本発明の方法では、前記パーセルのそれぞれに行によってかつ各行内で順次にパーセル識別番号を割り当てる段階を更に具備してもよい。
【００４４】
【実施例】
ここに記述する地図データを編成するための第１の実施例は、わずか二つのシークにおける地図エリアを読み出すことを提供する。更に、実施例は、それらのパーセルがディスク全体にわたり広げるという問題を回避すると同時に、比較的一様なサイズのデータ・パーセルを達成する。
【００４５】
第１のパーセル化方法
所与のズーム・レベルにおける地図ディスプレイ矩形毎にわずか二つのシークを必要とするパーセルを発生するために地図データを編成するための以下の方法を用いることができる。データを編成する前に、例えば、３２キロバイト、６４キロバイト、１２８キロバイト、等の、地図データのパーセルに対する最大データ・サイズが決定される。
【００４６】
第１段階
所与の地域における地理的特徴を表す地図データのデータベースから開始することにより、所与の地図ズーム・レベルに対して表示される緯度における最大変化が決定される。例えば、ナビゲーション・システムが１２ｃｍ（水平）×９ｃｍ（垂直）の大きさのディスプレイを有するものと想定する。所与のズーム・レベルにおいて、ディスプレイの１２ｃｍに対応する緯度における変化が決定される。（ディスプレイ上の方向の新しい方向付け（リオリエンテーション）を提供するためにより大きな水平及び垂直の大きさを用いる）。緯度におけるこの変化は、“デルタ−Ｙ”と称することができる。データベースの北側（又は南側）端から始めて、地図データベース適用範囲全体は、それぞれが正確にデルタ−Ｙ緯度単位（ユニット）だけ高い地図データの水平中間セクション（又はバンド）を表す中間コレクションに分けられる。図１は、サン・ディエゴ・カウンティ（郡）の一部に対して実施されたこの処理を示す。
【００４７】
第２段階
各水平中間セクションに関連付けられる地図データは、パーセルにグループ分けされる。各水平中間セクションに対して、パーセルへの地図データのグループ分けは、水平中間セクションの一端（即ち、西側端又は東側端のいずれか）で地理的特徴を表しているデータで始まりかつ水平中間セクションの反対側の端に向って作動する。先に決定した最大データ・サイズ、例えば、３２キロバイト、６４キロバイト、１２８キロバイト、等を越えることなくパーセルに対して先に決定された最大データ・サイズに到達した場合に、中間セクションと関連付けられた地図データは、パーセルにグループ分けされる。（パーセル境界を決定する場合には、ある割合がパーセル・オーバーヘッドに対して確保されうる。）パーセルを形成するためのこの処理は、地図データベースに対応する各水平中間セクションに対して実行される。稠密実装エリアにおいて、パーセルに対応する矩形エリアは、狭い幅を有する。希薄実装エリアにおいて、パーセルに対応する矩形エリアは、幅が広い。定義により、パーセルに対応する全ての矩形エリアは、同じ高さを有する。図２は、図１と同じ地域を示す。図２では、トップ・ツウー（上から二つの）水平中間セクションにおける特徴を表しているデータは、パーセルに編成されている。パーセルのそれぞれの経度境界は、垂直線によって示されている。
【００４８】
第３段階
一度全てのパーセルが定義されたならば、それらは、媒体、例えば、ＣＤ−ＲＯＭディスク、ＤＶＤ−ＲＯＭディスク、ハード・ディスク又は他の媒体上に順次編成される。（ＣＤ−ＲＯＭディスク又はＤＶＤディスクが用いられう場合には、それは再書込み可能であるか又は再書込み可能ではない。）パーセルは、  一つのコーナーにおける矩形エリアに含まれるデータを表すパーセルで開始しかつその端に対する水平行に沿って矩形エリアに含まれる特徴を表すデータを含むパーセルに進みかつ次の行の始まりにジャンプして戻ることにより編成される。パーセルは、各パーセルに独自のパーセルＩＤを割り当てることによって識別することができる。パーセルＩＤｓは、行又は列のいずれかによって又は一つのコーナーから開始して反対側のコーナーで終了する通し番号付け技術を用いることによって割り当てることができる。図３は、媒体上の配置に対するパーセルの順序付けを示す。
【００４９】
地図データのフェッチング
ナビゲーション・システムの地図ディスプレイ・アプリケーションがディスプレイに対して地図矩形を要求するときはいつでも、地図矩形と交叉する全てのパーセルが識別される。図１〜３に関連して上述した地図データのパーセル化のための実施例を用いて、矩形は、パーセルの２行よりも多くとは交叉しない（パーセルの２行としか交叉しない）。その結果、交叉しているパーセルは、最大で二つのシークにおいて読み出すことができる。図４は、ナビゲーション・システムの地図ディスプレイ・アプリケーションが矩形エリアに対応しているデータを要求するような例を示す。矩形エリアは、図４において“フェッチ・エリア”と称される。図４では、要求された矩形は、行１のパーセル６、７、及び８並びに行２のパーセル５、６、及び７と交叉する。各行のパーセルが隣接するので、行１のパーセル６、７、及び８は、一つのシークで読み出すことができ、かつ行２のパーセル５、６、及び７は、第２のシークの後に読み出すことができる。
【００５０】
代替
上述した地図データを編成するための方法の第１の実施例では、地図データは、一様な大きさの水平セクション（即ち、地域の西側から東側に緯度の方向に拡張するセクション）に基づき中間コレクションにまず分けられ、次いでパーセルは、最大パーセル・サイズを越えることなく所望のパーセル・サイズのパーセルを形成するために必要なデータの量に基づき各中間コレクション内の各パーセルに対する経度境界を決定することによって各中間コレクションから形成される。代替実施例では、座標方向を交換することができる。そこで、代替実施例では、一様な大きさの垂直セクション（即ち、地域の北側から南側に経度の方向に拡張するセクション）で中間コレクションを形成することができ次いで最大パーセル・サイズを越えることなく所望のパーセル・サイズのパーセルを形成するために必要なデータの量に基づき各中間コレクション内の緯度境界を決定することによって各中間コレクションからパーセルを形成することができる。
【００５１】
上述した第１の実施例では、サイズ（即ち、“デルタ−Ｙ”）は、ナビゲーション・システムのディスプレイ上の所与のズーム・レベルにおいて示される緯度の変化に基づき水平に拡張している中間セクションに対して選択された。上述した第１の実施例では、地図データの中間水平セクションは、高さが全てデルタ−Ｙユニット（単位）であった。このデルタ−Ｙサイズを有している中間水平セクションで形成されたパーセルにより、地域の所与の矩形部分をディスプレイするために必要な地図データは、二つだけのシークでフェッチすることができる。この原理は、拡張することができる。例えば、中間水平セクションがディスプレイ・サイズに対応する緯度の変化の大きさの半分（例えば、デルタ−Ｙの１／２倍）である場合には、所与の矩形エリアは、３つのシークだけでフェッチすることができる；中間水平セクションがディスプレイ・サイズに対応する緯度の変化の３分の１（例えば、デルタ−Ｙの１／３倍）である場合には、所与の矩形エリアは、４つのシークだけでフェッチすることができる、等。
【００５２】
別の実施例では、中間水平セクションが、ディスプレイ・サイズに対応する緯度の変化の大きさよりも大きい場合には、所与の矩形エリアをたった一つのシークの時間のかなりの割合でフェッチすることができる。例えば、中間水平セクションが、ディスプレイ・サイズに対応する緯度の変化の大きさの２倍（例えば、デルタ−Ｙの２倍）である場合には、所与の矩形エリアをたった一つのシークの約半分の時間でフェッチすることができる。
【００５３】
第１の実施例では、サイズ（即ち、“デルタ−Ｙ”）は、ナビゲーション・システムのディスプレイの所与のズーム・レベルにおいて示される緯度の変化に基づき水平的に拡張している中間セクションに対して選択された。ナビゲーション・システムは、複数の異なるズーム・レベルを支持しうる。従って、各レイヤーが複数の異なるズーム・レベルの個別のものに対応している、地図データの個別のレイヤーを準備しうる。各個別のレイヤーは、第１の実施例による方法を用いて形成される。
【００５４】
第１の実施例では、地図データベースを形成するための処理は、それぞれが正確にデルタ−Ｙ緯度ユニットの高さである地図データの水平中間セッション（又はバンド）を表す中間コレクションに地図データベース適用範囲全体をまず分けて次いで中間コレクションのそれぞれからパーセルを形成する段階を含んでいた。代替実施例では、これらの段階を組合せることができる。例えば、デルタ−Ｙに対する値を決定した後、中間セクションに対応している中間コレクションに地図データをまず分類することなく地図データのオリジナル・コレクションからパーセルを形成することができる。この代替処理によれば、パーセルは、地域のコーナーにおける特徴を表しているデータで始めてかつ矩形ウィンドウをラスタのように移動させることによって地図データのオリジナル・コレクションから形成される。ウィンドウは、デルタ−Ｙに等しい一つの座標方向にディメンションを有しかつゼロで始まりかつパーセルが形成されるまで増大される他の座標方向にディメンションを有する。パーセルは、ウィンドウ内に囲まれたデータがパーセルに対する最大データ・サイズに達する毎に形成される。
【００５５】
上述した実施例において、地図データは、ＣＤ−ＲＯＭディスク、ＤＶＤディスク又はハードディスクに記憶されるということが示された。開示した実施例は、特定の種類の媒体又は技術に限定されるものではなく、かつ現在入手可能であるか又は将来に入手可能になる記憶媒体のタイプを用いうる。
【００５６】
上述した詳細な記述は、限定することではなく説明のためであるということを意図しておりかつ全ての同等物を含んでいる特許請求の範囲は、本発明の範疇を規定することを意図するということが理解される。
【図面の簡単な説明】
【図１】  地図データを編成するための第１の実施例による地理的エリアの地図でありかつ処理における段階を説明するために用いられる。
【図２】  図１に示す地理的エリアの同じ地図でありかつ地図データを編成するための処理における別の段階を説明するために用いられる。
【図３】  図１及び図２に関連して記述した処理により形成された地図データのパーセルを番号付けしかつ順序付けるための方法を示す図である。
【図４】  図１〜図３に関連して記述した処理により編成された地図データをナビゲーション・システムによってフェッチすることができる方法を示す図である。
【図１】
0004846932.tif 000002
【図２】
0004846932.tif 000003
【図３】
0004846932.tif 000004
【図４】
0004846932.tif 000005