ナビゲーションシステムを使って計算された経路のプレビューを提供する方法及びシステム

トップ :: G 物理学 :: G01 測定;試験

【発明の名称】	ナビゲーションシステムを使って計算された経路のプレビューを提供する方法及びシステム
【発明者】	【氏名】マシューフリーデリック【氏名】ウィリアムマックドナー【氏名】リチャードアシュビー
【要約】	【課題】目的地までの推奨経路を決定するために地理的データベースを使用し、推奨経路をたどるための詳細な操縦案内を提供する。【解決手段】推奨経路を決定する時にナビゲーションシステムが使用する地理的データベースの部分は、それにより表されている道路名称の実際のテキストを含むデータベースの別の部分に対するリファレンスを含んでいる。ナビゲーションシステムは推奨経路を決定するために地理的データベースのデータを使用するので、推奨経路内の道路を表すデータは道路名称の実際のテキストを含む地理的データベースの他の部分に対するリファレンスと共に記憶される。推奨経路が決定されると、プレビュー機能は推奨経路内の道路を表すデータを評価し、経路プレビューデータ構成のリストを提供し、その中に道路名称の実際のテキストを含む地理的データベースの部分に対するリファレンスを含む。

【特許請求の範囲】
【請求項１】第一タイプのデータエンティティと、第二タイプのデータエンティティとを備え、各ナビゲーション可能道路区分が、少なくとも一つの独立した前記第一タイプのデータエンティティによって表され、前記第一タイプの各データエンティティが、前記第一タイプの各データエンティティが表す前記道路区分のナビゲーション可能属性を含み、更に前記第一タイプのデータエンティティが表す道路区分の各道路の名称は、前記第二タイプのデータエンティティにより表され、前記第一タイプのデータエンティティは、前記第二タイプのデータエンティティからは独立しているが、地理的データベース内に共に配置され、更に、前記第一タイプの各データエンティティが、前記第一タイプのデータエンティティが表す道路区分の名称を含む前記第二タイプのデータエンティティへのリファレンスを含むことを特徴とする地理的範囲内に位置するナビゲーション可能道路区分を表すための地理的データベースの構成。
【請求項２】前記第一タイプの各データエンティティ内のリファレンスが照会する前記第二タイプのデータエンティティが、前記第一タイプのデータエンティティにより表される道路区分を照会する名称を、前記第一タイプのデータエンティティが表す道路区分沿いに配置された道路標識により表すことを特徴とする請求項１に記載の構成。
【請求項３】前記第一タイプのデータエンティティが、前記地理的データベース内に空間的に編成されることを特徴とする請求項１に記載の構成。
【請求項４】前記第二タイプのデータエンティティが、前記地理的データベース内にアルファベット順に編成されることを特徴とする請求項１に記載の構成。
【請求項５】前記第一タイプのデータエンティティが、前記地理的データベース内に空間的に編成されることを特徴とする請求項４に記載の構成。
【請求項６】前記地理的データベースが、第三タイプのデータエンティティを更に備え、各ナビゲーション可能道路区分が少なくとも一つの前記第三タイプの独立したデータエンティティにより表され、前記第三タイプの各データエンティティが、表されている道路区分に関する説明的属性を更に含んでいることを特徴とする請求項１に記載の構成。
【請求項７】前記データベース構成が、コンピューターで読み取り可能な物理的記憶媒体上に記憶されることを特徴とする請求項１に記載の構成。
【請求項８】ハードウェア構成要素及びソフトエェア構成要素を含み、コンピューターで読み取り可能な媒体上に記憶された地理的データベースを使うナビゲーションシステム内における、出発地と目的地との間の推奨経路を表すデータ出力が、経路指定データを含む地理的データベースの第一部分を使って決定できるような経路計算機能と、前記推奨経路をたどるための詳細な操縦指示が、操縦データを含む地理的データベースの第二部分を使ってナビゲーションシステムのユーザーに一度に一つづつ提供されるような経路案内機能と、前記推奨経路を表すデータ出力を得る第一ルーチンと、経路プレビューイベントが示されているか否かを決定するために前記推奨経路を表すデータ出力の中のエントリーを評価する第二ルーチンと、各エントリーに関連する推奨経路内の道路のよく知られた名称に対するリファレンスを含むようなデータを前記経路プレビューイベントが示されている推奨経路を表すデータ出力の中に記憶する第三ルーチンとを含み、前記詳細な操縦指示の前に推奨経路の概要がユーザーに提供されるような経路プレビュー機能とから成ることを特徴とするコンビネーション。
【請求項９】地理的データベースが第一タイプのデータエンティティと第二タイプのデータエンティティとを含み、各ナビゲーション可能道路区分が少なくとも一つの独立した前記第一タイプのデータエンティティにより表され、前記第一タイプの各データエンティティが前記第一タイプの各データエンティティによって表されているナビゲーション可能道路区分属性を含み、更に前記第一タイプのデータエンティティにより表される道路区分の各名称が前記第二タイプのデータエンティティにより表され、前記第一タイプのデータエンティティは、前記第二タイプのデータエンティティから独立してはいるが、地理的データベース内に共に配置されているような、地理的範囲内に位置するナビゲーション可能道路区分を表すデータを含む地理的データベース内において、或る名称で知られる道路区分を表す前記第一タイプの各データエンティティ内に、表された道路区分の周知されている名称に関する前記第一タイプのデータエンティティ内に含まれた表示を含んでいることを特徴とするデータベース。
【請求項１０】前記表示が、前記第二タイプのデータエンティティ内の一つのデータエンティティに対するリファレンスであることを特徴とする請求項９に記載のデータベース。
【請求項１１】前記第一タイプのデータエンティティ内の前記リファレンスが照会する前記第二タイプのデータ記録は、前記第一タイプのデータエンティティにより表される道路区分を照会する名称を、表されている道路区分が一部分である道路沿いに配置された道路標識により表すことを特徴とする請求項１０に記載のデータベース。
【請求項１２】前記第二タイプのデータエンティティが、前記地理的データベース内にアルファベット順で編成されることを特徴とする請求項９に記載のデータベース。
【請求項１３】前記第一タイプのデータエンティティが、前記地理的データベース内に空間的に編成されることを特徴とする請求項１２に記載のデータベース。
【請求項１４】前記地理的データベースが、第三タイプのデータエンティティを更に備え、各ナビゲーション可能道路区分が少なくとも一つの独立した前記第三タイプのデータエンティティにより表され、前記第三タイプの各データエンティティが、前記表されている道路区分に関係する操縦指示を提供するために使われる属性を含むことを特徴とする請求項９に記載のデータベース。
【請求項１５】データベース構成がコンピューターで読み取り可能な物理的記憶媒体上に記憶されることを特徴とする請求項９に記載のデータベース。
【請求項１６】第一リスト内のデータエンティティが出発地と目的地の間の合法的な連続する経路を形成する道路区分を表し、地理的データベースからのデータエンティティの第一リストにより表される前記出発地と前記目的地との間の推奨経路を、前記地理的データベースを使って計算する段階と、前記推奨経路の計算中に、前記第一リスト内で表された各道路区分の周知されている名称の表示を記憶する段階とから成ることを特徴とするナビゲーションアプリケーションにより計算される経路の経路プレビューを提供する方法【請求項１７】前記ナビゲーションアプリケーションのユーザーに前記推奨経路のプレビューを提供する段階を更に含み、前記プレビューが、前記推奨経路内の道路の周知されている名称を含むことを特徴とする請求項１６に記載の方法。
【請求項１８】前記表示が、地理的特徴の名称を含んでいる地理的データベースの一部分に対するリファレンスであることを特徴とする請求項１６に記載の方法。
【請求項１９】前記推奨経路に含まれる各道路を表すデータを含むリストを、ある関数に提供する段階と、前記推奨経路に含まれる各道路を表すデータを評価する段階と、前記推奨経路内の道路の周知されている名称の表示を含むような経路プレビューデータ構成を前記評価する段階に基づいて形成する段階と、推奨経路のプレビューをナビゲーションアプリケーションのユーザーに提供するために前記経路プレビューデータ構成を使う段階とを更に含むことを特徴とする請求項１６に記載の方法。
【請求項２０】前記経路プレビューデータ構成を使って推奨経路のプレビューをユーザーに提供する前に、前記経路プレビューデータ構成に含まれる各表示と関連する道路の名称を前記地理的データベースから得る段階を更に含むことを特徴とする請求項１９に記載の方法。
【請求項２１】前記経路プレビューデータ構成に含まれる各表示と関連する道路の名称を前記地理的データベースから得る段階の前に、前記表示を再順序付けする段階を更に含むことを特徴とする請求項２０に記載の方法。
【請求項２２】前記再順序付けする段階では、表示を媒体順に配列することを特徴とする請求項２１に記載の方法。
【請求項２３】前記再順序付けする段階では、表示を番号順に配列することを特徴とする請求項２１に記載の方法。
【請求項２４】前記再順序付けする段階では、名称がアルファベット順で得られるように、表示を配列することを特徴とする請求項２１に記載の方法。
【請求項２５】前記経路プレビューデータ構成に含まれた各表示と関連する道路の名称を得る段階が、再順序付けする段階により形成された順序に従って実行されることを特徴とする請求項２０に記載の方法。
【請求項２６】ハードウェア構成要素とソフトウェアの構成要素を含み、コンピューターで読み取り可能な媒体上に記憶される地理的データベースを使うナビゲーションシステムのための操作方法において、経路指定データを含む出力により表される出発地と目的地の間の推奨経路を決定するために前記経路指定データを含む地理的データベースの第一部分を使う段階と、ナビゲーションシステムのユーザーに前記推奨経路をたどるための詳細な操縦指示を一度に一つづつ提供するために操縦データを含む地理的データベースの第二部分を使う段階と、前記操縦指示を提供する前に、プレビューのエントリーを決定するために前記推奨経路を表すデータを評価する段階、及び前記推奨経路を表す前記データ内に含まれ経路指定データが表す道路の名称を含む地理的データベースの第三部分に対するリファレンスを前記第一部分に記憶する段階とにより形成された前記推奨経路のプレビューをユーザーに提供する段階とから成ることを特徴とする方法。
【請求項２７】前記評価する段階が、前記推奨経路に名称の変更が生じた場合、名称の変更を記載するプレビュー用のエントリーを形成する段階を含むことを特徴とする請求項２６に記載の方法。
【請求項２８】前記評価する段階が、前記推奨経路内に管理されたアクセス道路が入っている場合、管理されたアクセス道路が入っていることを示すプレビュー用のエントリーを形成する段階を含むことを特徴とする請求項２６に記載の方法。
【請求項２９】前記評価する段階が、前記推奨経路内に迂回路が入っている場合、迂回路が入っていることを示すプレビュー用のエントリーを形成する段階を含むことを特徴とする請求項２６に記載の方法。

【発明の詳細な説明】【０００１】
【発明の属する技術分野】本発明は、道路を走行する車両用のナビゲーションシステムによって計算された経路のプレビューを提供することに関する。
【０００２】
【従来の技術】ナビゲーションシステムは、道路を走行する車両（乗用車、トラック、バスなど）に利用されている。このような車載ナビゲーションシステムは、エンドユーザー（例えばナビゲーションシステムを搭載した車両の運転者及び／又は同乗者）にナビゲーション関する様々な役立つ特徴を提供する。例えば、ナビゲーションシステムの中には、地理的範囲内の指定区域間の道路によって最適の走行経路を決定できるものがある。ナビゲーションシステムのプログラミングは、エンドユーザーからの入力と自分の物理的位置を決定できる装置（ＧＰＳシステムのような）からの随意的な入力を使い、二つの地点間の様々な経路を調べ地理的範囲内の出発地から目的地まで走行するための最適経路を決定する。ナビゲーションシステムは次に、最適経路に関する情報をエンドユーザーに、出発地から目的地までエンドユーザーが走行する際に必要な運転操縦を確認するのに役立つ形で提供する。この指示は、エンドユーザーが走行する道路に沿って視覚的及び／又は聴覚的な形式で提供される。ナビゲーションシステムによっては、ナビゲーションシステムのハードウェアの一部であるコンピューターディスプレイ上に、目的地までの経路を強調した詳細な地図、経路に沿った様々な地点で必要な操縦のタイプ、一定のタイプの特徴に関する位置等を示すことができる。
【０００３】こうしたタイプの特徴を提供するために、ナビゲーションシステムは地理的データを使用する。地理的データは、ある地理的範囲内の物理的特徴を表すデータを含む一つ又はそれ以上のデータベースの形態をしている。地理的データベースは、ある地理的範囲内の道路と交差点を表すデータを含んでおり、交差点でのＵターン禁止、道路での速度制限、様々な道路の名称、道路に沿った住所範囲のような、表された道路と交差点に関係する情報も含んでいる。
【０００４】
【発明が解決しようとする課題】ナビゲーションシステムは多くの重要な特徴を提供するが、依然として改良の余地がある。改良の余地のある一つの領域は、経路プレビューに関する特徴を提供することに関係している。経路プレビューの特徴は、計算された経路のプレビューをエンドユーザーに提供することである。プレビューは、計算された経路に関する概略又は概要から構成される。この概略又は概要には、限られた量の他の情報と共に、計算された経路内の道路名称が含まれている。経路プレビューは表示することはできるが、テキスト又は図形の形でエンドユーザーに提供することができる。経路プレビューは、経路走行に関する詳細な操縦指示を含んでいない。
【０００５】経路プレビューは、ナビゲーションシステムが経路を計算した直後で、エンドユーザーが経路に沿ってあまり遠くまで走行しないうちに、エンドユーザーに提示される。計算された経路のプレビューにより、エンドユーザーは経路走行を始める前に経路を一般的に知る機会が与えられる。ナビゲーションシステムの中には、経路プレビューを提示する際、エンドユーザーに計算された経路を拒否したり又は計算された経路を修正する機会を与えるものがある。例えば、エンドユーザーは、計算された経路の中で、交通量が多かったり、構造的に流れが悪かったりしているのが分かっている道路を避けたいと考える。エンドユーザーは経路プレビューの情報に基づいて、ナビゲーションシステムが代替の経路を計算するように要求することができる。エンドユーザーが代替経路を要求しない場合でも、エンドユーザーは、計算された経路を走行する前に計算された経路内の道路を知ることになれば、より好都合であろう。従って、経路に沿って走行する前に計算された経路プレビューをエンドユーザーに提供することは有益で望ましい機能である。
【０００６】経路プレビューは望ましい機能ではあるが、ナビゲーションシステムによってはこの機能を提供することが困難である。ナビゲーションシステムの中には、比較的制限されたメモリ、比較的遅いＩ／Ｏ、比較的遅いプロセッサのように計算リソースの比較的限定されているものがある。
【０００７】ナビゲーションシステムに経路プレビューを提供する一つの方法は、ナビゲーションシステムの経路案内機能が生成した操縦指示から、道路名称又は他の詳細情報を抽出することである。上記のように、幾つかのナビゲーションシステムは経路案内機能を含んでおり、この経路案内機能は、出発地から目的地までの計算された経路に沿って走行するために必要な操縦を確認する視覚的及び／又は聴覚的な操縦指示をエンドユーザーに提供する。経路案内機能が生成する操縦指示は非常に細かくすることもできるが、そうした操縦指示を生成し提供するためにはナビゲーションシステムは相応の計算リソースを必要とする。しかし、経路を走行する場合、操縦指示は一度に一つずつ提供される。従って、操縦指示を生成して提供するには比較的長い時間を利用できるので、計算リソースが並みのナビゲーションシステムでも、内容が豊富で詳しい操縦指示をエンドユーザーに提供することができる。
【０００８】この態様の経路ガイダンス機能の場合、計算された経路のプレビューを提供するために経路ガイダンス機能が生成した操縦指示からデータを用いることが困難になることがある。経路プレビューに必要なデータ（すなわち、道路名称と恐らくは他の可能な情報）は経路ガイダンス機能が生成した比較的複雑な操縦指示の中に埋没しているので、操縦指示を生成して経路プレビューに必要な情報を操縦指示から取り出すには、相応の計算リソースが必要となる。ナビゲーションシステムの計算リソースが比較的限定されている場合、こうした方法で経路プレビューの機能を提供するには、比較的長い時間を要する。経路プレビュー機能の目的は、経路走行を始める前に計算された経路を受け入れるべきか否かをエンドユーザーが評価できるようにすることなので、リソースの限定されたナビゲーションシステムであっても、経路プレビューの機能を比較的速く作動させることが重要である。従って、リソースの限定されたナビゲーションシステムであっても速く作動する経路プレビュー機能を提供することが必要である。車載ナビゲーションシステムの中には、例えば大きな記憶容量と高速のＩ／Ｏのような大型の計算リソースを有しているものもある。このようなタイプの車載ナビゲーションシステムのユーザーは、計算された経路のプレビューを素早く生成できるという改良点を得ることができる。
【０００９】ナビゲーションシステムに関連する情報及び特徴は、車載ナビゲーションシステム以外に、計算プラットフォームに提供することができる。ナビゲーションシステム関連の機能を提供するナビゲーションアプリケーションプログラムは、様々な種類のコンピューターハードウェアのプラットフォーム上で、又、様々な種類のコンピューターアーキテクチャで利用できる。例えば、ナビゲーションアプリケーションプログラムは、デスクトップコンピューター及びノート型コンピューターを含むパーソナルコンピューター上に提供される。ナビゲーションアプリケーションプログラムは、無線ネットワーク及びインターネットを含むネットワークのような分散処理システム上にも提供される。ナビゲーションアプリケーションプログラムは、パーソナルデジタル用具、電話、ポケットベル（登録商標）、パームパイロット型装置等のような手に持つタイプのコンピューター装置にも含めることができる。更に、ナビゲーションアプリケーションプログラムは、パーソナルナビゲーションシステムのような特定の目的の電子装置に含めることができる。これらのタイプのプラットフォーム及びシステムにインストールされているナビゲーションアプリケーションプログラムのユーザーは、計算された経路のプレビューが素早く生成されるという改良点も得ることもできる。従って、ナビゲーションシステム又はナビゲーションアプリケーションプログラムを経路プレビュー機能に提供するが必要である。また、リソースが比較的制限されたコンピューターのプラットフォーム上でも素早く作動する経路プレビュー機能を提供する必要がある。
【００１０】
【課題を解決するための手段】本発明は、これら及び他の目的に取り組むために、ナビゲーションシステムに含まれるプレビュー機能を備えている。ナビゲーションシステムは、地理的データベースを用いて目的地までの推奨経路を決定し、計算された推奨経路をたどるための詳しい操縦指示を提供する。プレビュー機能は、推奨経路をたどるための詳しい操縦指示を提供する前に、推奨経路の概要を提供する。プレビュー機能はナビゲーションシステムのプログラミングに含まれている。プレビュー機能は、地理的データベースに組み込まれている特徴を用いるが、ナビゲーションシステムが推奨経路の決定時に使用する地理的データベースの部分は、表されている道路名称の実際のテキストを含む地理的データベースの別の部分に対するリファレンスを含んでいる。ナビゲーションシステムが推奨経路を決定するために地理的データベースを使うので、推奨経路内の道路を表すデータは、道路名称の実際のテキストを含む地理的データベースの他の部分に対するリファレンスを含めて、記憶される。推奨経路が決定されると、プレビュー機能は推奨経路内の道路を表すデータを評価し、経路プレビューデータ構成のリストを提供する。経路プレビューデータ構成のリストは、道路名称の実際のテキストを含む地理的データベースの一部に対するリファレンスを含んでいる。経路プレビューデータ構成のリストは、推奨経路の概要を含むプレビューをナビゲーションシステムのユーザーに提供するのに使われる。ユーザーに提供されるプレビューには、推奨経路内の道路名称を入れておくことができる。この道路名称は経路プレビューデータ構成のリストに含まれているリファレンスを用いて、地理的データベースから入手するができる。道路名称を得る場合、リファレンスを再順序付けすることにより、道路名称の実際のテキストへ素早くアクセスできるようになる。計算された経路のプレビューを提供することにより、ユーザーは、経路をたどるための詳しい案内を与えられる前に、経路について知ることになる。
【００１１】本開示の都合上「ナビゲーションシステム」とは、車内に搭載されているナビゲーションシステム（即ち、車載ナビゲーションシステム）を意味する。又「ナビゲーションシステム」は、ナビゲーション関連の特徴を提供しパーソナルコンピューター、ネットワーク、携帯形電子装置等にインストールされているアプリケーションを含む地理的データを用いるコンピュータープラットフォーム上にインストールされているあらゆるソフトウェアアプリケーションを意味する。
【００１２】
【発明の実施の形態】（Ｉ）ナビゲーションシステムの概要図１は、ナビゲーションシステム１１０のブロック線図である。ナビゲーションシステム１１０は乗用車又はトラックのような車両１１１に搭載されるが、代替実施例では、車両の外側に配置することも、又以下に述べるように、他の様々なプラットフォーム又は環境で実行することもできる。ナビゲーションシステム１１０は、ハードウェア構成要素とソフトウェア構成要素を組み合わせたものである。一つの実施例ではナビゲーションシステム１１０はプロセッサ１１２と、プロセッサ１１２に接続されたドライブ１１４と、プログラミング１１８と他の情報も記憶できる不揮発性メモリ記憶装置１１６とを含んでいる。プロセッサ１１２はナビゲーションシステムに使われる何れのタイプのものでもよく、例えば日立のＳＨＩ、インテルの８０３８６、インテルの９６０、モートローラの６８０２０（あるいは同様の又はそれ以上のアドレス空間を有する他のプロセッサ）等のフラットアドレス空間を使う３２ビットプロセッサを挙げることができる。上記以外のタイプのプロセッサも、将来開発されるプロセッサを含め差し支えない。
【００１３】ナビゲーションシステム１１０は又、位置決めシステム１２４を含んでいる。位置決めシステム１２４は、ＧＰＳタイプの技術、推測航法タイプのシステム、これらのシステムを組み合わせたもの、又は他のシステムを利用しており、これらは全て技術的に既知である。位置決めシステム１２４は、車両の移動距離、速度、方向等を測定する適当な感知装置１２５を含んでいる。位置決めシステム１２４は、技術的に既知の方法でＧＰＳ信号を得る適切な技術を含んでいる。位置決めシステム１２４はプロセッサ１１２へ出力を提供する。プロセッサ１１２上で実行されるソフトウェア１１８は位置決めシステム１２４からの出力を使い、ナビゲーションシステム１１０の位置、方向、速度などを決定する。
【００１４】ナビゲーションシステム１１０は、ユーザーインターフェース１３１も含んでいる。ユーザーインターフェース１３１は、エンドユーザーが情報をナビゲーションシステムへ入力できるようにするための適当な装置を含んでいる。この入力情報には、ナビゲーションシステムのナビゲーションの機能を使用するための要求が含まれている。例えば入力情報には、所望の目的地への経路に関する要求が含まれている。入力情報には他の種類の情報が含まれていてもよい。情報をナビゲーションシステムへ入力するために使われる装置には、音声認識プログラムのような適当なソフトウェアと並んで、キーパッド、キーボード、マイクロホン等が含まれる。ユーザーインターフェース１３１は、情報をエンドユーザーに送り返す適当な装置も含んでいる。この装置として、ディスプレイ、スピーカー、又は他の手段を挙げることができる。
【００１５】図１と２で、ナビゲーションシステムを作動させるために、プログラミング１１８は不揮発性メモリ１１６からプロセッサ１１２に関係するＲＡＭ１３４へロードされる。プログラミング１１８は、ナビゲーションシステム１１０の運行機能と特徴を提供するナビゲーション関連アプリケーションソフトウェア１１９を含んでいる。ナビゲーション関連アプリケーションソフトウェア１１９は、様々なナビゲーション特徴と機能を提供するために、地理的データ１４０を使用するが、位置決めシステム１２４からの出力と関連させて使用する。ナビゲーション関連アプリケーションソフトウェア１１９は、これら様々なナビゲーションに関連する特徴と機能を提供する独立したコンポーネントアプリケーション（プログラム、サブプログラム、ルーチン、又はツールとも呼ぶ）を含んでいる。
【００１６】図２は、図１のナビゲーションシステム１１０に含まれるナビゲーション関連アプリケーションソフトウェア１１９の実施例のための幾つかのコンポーネントアプリケーションを示す。これらのコンポーネントアプリケーションは、ジオコーディング１４１（位置決めシステム１２４からの地理的座標を、地理的データ１４０により表されるデータ表示特徴に関連づけする）と、経路計算１４２と、経路案内１４４（所望目的地へ到達するための詳しい方向を提供する）と、地図表示１４６と、車両位置決め１４８（車両位置を地理的データ１４０と関連づけする）と、他の機能１５２とを含んでいる。他のコンポーネントアプリケーション、プログラム又はツールは、ナビゲーションプログラミング１１９に含まれている。
【００１７】本実施例では、ナビゲーションアプリケーションソフトウェア１１９は、経路プレビュー機能１５０を含んでいる。本実施例では、経路プレビュー機能１５０は、経路案内アプリケーション１４４の一部分である。経路プレビュー機能１５０は、車両が経路計算アプリケーション１４２により計算された経路に沿って走行しているときに詳細な操縦指示と解説を提供する機能１５１からは独立している。経路プレビュー機能１５０を、以下に詳しく述べる。代替実施例では、経路プレビュー機能１５０は、経路案内アプリケーション１４４から独立したアプリケーションとして提供されていてもよい。
【００１８】プログラミング１１８のコンポーネントアプリケーションは、定められたプログラミングインターフェースを通して同時に機能する。ナビゲーション関連アプリケーションソフトウェア１１９は地理的データ１４０に直接アクセスするが、代替的には、インターフェース階層１５４及びオペレーティングシステム１５６を通して地理的データ１４０にアクセスする。インターフェース階層１５４とオペレーションシステム１５６は、プログラミング１１８の一部であってもよく、又は個別に提供されていてもよい（インターフェース階層の一つの実施例は、番号第０８／７４０，２９８号に記載されており、その開示全体全体を参考までここに援用する）。
【００１９】ナビゲーション関連アプリケーションソフトウェア１１９に加え、プログラミング１１８はマネージャーアプリケーションソフトウェア１５５も含んでいる。マネージャーアプリケーションソフトウェア１５５は、ユーザーインターフェース１３１及び位置決めシステム１２４内のハードウェアにインターフェースを提供する。マネージャーアプリケーションソフトウェア１５５は、ナビゲーションアプリケーション１１９からのデータ要求を調整してもよい。
【００２０】（II）地理地図データベース（Ａ）概要ナビゲーションシステムの速さ及び／又は機能は、システムに用いられる地理的データの記憶保存、配置、及び／又は構成を改良することにより高めることができる。そうした改良により、データを用いるナビゲーションシステムのナビゲーション関連アプリケーションにおいてそれらの機能がデータを使うのを容易にすることができる。データにアクセスしデータを使用するナビゲーション関連アプリケーション１１９は、地理的データを記憶し、配置し、及び／又は構成する方法に基づいて、地理的データに組み込まれた改良点を活用するルーチンを実行することができる。この組み合わせにより、結果的にナビゲーションシステムの全体的性能を改良できる。
【００２１】図２では、地理的データ１４０は、一つ又はそれ以上のデータベース１６２に編成され、記憶媒体１６４に記憶される。記憶媒体１６４をドライブ１１４にインストールし、ナビゲーションシステムが地理的データ１４０を読んで使えるようにする。記憶媒体１６４は取り外し、取り替えができるようになっており、車両が走行している地理的範囲に関する適当なデータベース１６２を有する記憶媒体を使うことができる。更に、記憶媒体１６４は、記憶媒体上の地理的データ１４０を容易に更新できるように、取り替えることができる。一つの実施例では、地理的データは、イリノイ州、ローズモントのナビゲーションテクノロジー社が提供している。しかし、この明細書に開示する本発明の概念は、特定のデータソースには限定されないということが理解される。
【００２２】一つの実施例では、記憶媒体１６４はＣＤＲＯＭディスクである。代替実施例では、記憶媒体１６４はＰＣＭＣＩＡカードであってもよく、その場合はドライブ１１４がＰＣＭＣＩＡスロットに交換されることになろう。将来開発される記憶媒体は勿論、固定ディスク又はハードディスク、ＤＶＤディスク、又は他の最新の利用可能な記憶媒体を始めとする様々な記憶媒体を使うことができる。記憶媒体１６４と地理的データ１４０は、ナビゲーションシステムが置かれている位置に物理的に必ずしも置かれなくてもよい。代替実施例では、一部又は全部の地理的データ１４０を記憶する記憶媒体１６４は、ナビゲーションシステムの他の部分から離れていてもよく、必要に応じて地理的データの一部が通信リンク経由で提供される。
【００２３】地理的データベース１６２は、地理的範囲内の道路網に関する情報を含んでいる。一つの実施例では、地理的データベース１６２は、節点データと区分データとを含んでいる。これらのデータは物理的な道路網の構成要素を表す。節点データは地理的範囲内にある（道路の交差点及び他の位置のような）物理的位置を表し、区分データは節点データが表す物理的位置の間にある道路の一部を表す。地理的範囲内の各道路区分は、地理的データベース１６２内の道路区分データエンティティ（すなわち記録）により表される。地理的データベース１６２内の各道路区分データ記録は、道路区分データ記録により表される道路区分の各端の座標位置を表す二つの節点と関連している。節点データ及び区分データエンティティ内に含まれている情報を、図３，４、６を参照して説明する（用語「節点」と「区分」は、これらの物理的地理的特徴を述べる専門用語で、これらの特徴を述べる他の専門用語も本概念の範囲内に含むことを意図している）。
【００２４】図３は、地理的範囲２１２の地図２１０を示す。複数の位置２１４が、地理的範囲２１２内に示されている。各ロケーション２１４は地理的範囲２１２内の場所又は地点を示しており、そこには地理的データベース１６２内に情報として含まれることが望ましい特徴が配置されている。これらの位置２１４の各々は固有の物理的位置（緯度、経度、及び随意的に絶対的又は相対的な標高も）を有しているので、これらの各位置２１４は、二次元（又は三次元）の地理的座標（すなわち緯度、経度、及び随意的に標高も）で個別に特定することができる。位置２１４は二つ又はそれ以上の道路が出会う交差点、道路の方向が変わる道路区分に沿った地点、速度制限が変わる道路区分に沿った地点、道路が行き止まりになる地点等に対応する。位置２１４は、ホテル又は市民会館、湖のような自然の特徴の境界線、鉄道線路や船着場に沿った位置のような対象地点の位置に対応する。位置２１４は、地理的範囲２１２内に物理的に配置された任意の位置に対応していてもよい。
【００２５】図４は、地図２１０の一部２１６の拡大図である。図４中の部分２１６は、地理的範囲２１２内の道路網２２０の一部分を示す。道路網２２０は、他のものと共に地理的範囲２１２内にある道路と交差点を含んでいる。地図２１０の図示された部分である図４に示すように、２１６内の各道路は一つ又はそれ以上の区分２２２（１）、２２２（２）、・・２２２（ｎ）から成る。一つの実施例では、道路区分は道路の一部を示す。図４では、各道路区分２２２は二つの節点２２３と関連付けて示され、一方の節点は道路区分の一方の端にある地点を表し、他方の節点は道路区分の他方の端にある地点を示している。道路区分の何れかの端にある節点は、例えば交差点のように道路が他の道路と出会う位置、又は道路が行き止まりになる場所に対応する。
【００２６】あるタイプの地理的データベースでは、地理的範囲内に表される各道路区分には少なくとも一つのデータベースエントリー（「エンティティ」又は「記録」とも呼ぶ）がある。道路区分データ記録２５８を図６に示す。この道路区分データ記録は、節点を二つの節点の地理的位置（例えば緯度と経度座標）及び／又は道路区分と関連させて確認できるようにする情報（「属性」、「フィールド」などのような）と関連していてもよい。道路区分データ記録は更に、道路区分記録で表される一部分の道路での走行速度、道路区分記録で表される一部分の道路で許されている走行方向、道路区分記録で表される一部分の道路の端の交差点に対応する各節点で定められているターンの制限、道路区分記録で表される道路部分の街路住所範囲等を規定する情報に関連していてもよい。道路区分に関連する様々な属性は、単一の道路区分記録に含まれているが、相互参照される二つ以上のタイプの道路区分記録に含まれているのが好ましい。
【００２７】地理的範囲２１２を表す地理的データベースには、地理的範囲内の各節点に関するデータベースエントリー（エンティティ又は記録）があってもよい。節点データ記録２６０を図６に示す。節点データ記録は節点及び／又は地理的位置（例えば、緯度と経度の座標）と接続する道路区分の特定を可能にする情報（「属性」、「フィールド」等）と関連していてもよい。
【００２８】（Ｂ）地理的データの独立したサブセット様々なナビゲーション関連機能を実行するために地理的データへのアクセスを高める一つの方法は、地理的データの独立したコレクション又はサブセットを提供し、これをナビゲーション関連アプリケーション（図２の１１９）によって実行される各々の個別機能が使えるようにすることである。これらの各独立サブセットは、一つ又はそれ以上の特定の機能で使えるように整えられる。例えば、経路計算機能１４２は通常、道路区分に関連する地理的データベース１６２内の全情報の一部分だけを使っている。経路計算機能１４２を実行している場合、道路区分での速度、一つの道路区分から別の道路区分へのターン制限などの情報が必要である。しかし、経路計算機能１４２は、経路計算に道路名称を必ずしも必要としない。同様に、地図表示機能１４６を使う場合、速度制限又はターン制限のような道路区分に関する幾つかの情報は必要ではない。替わりに、地図表示機能１４６を実行する場合、道路の形状と位置と、恐らくは道路名称のような道路区分に関する情報の一部分だけを使っている。更に経路案内機能１４４を実行している場合でも、速度制限又はターン制限のような道路区分に関する幾つかの情報は必要でない。替わりに、経路案内機能１４４を実行している場合、道路区分により表される道路名称、道路区分沿いの住所範囲、道路区分沿いの何らかの標識等を含む情報を使っている。様々なナビゲーション機能が使う情報は重複しているが、これらの何れかのナビゲーション機能が使っている幾つかのデータは別の機能では使われていない。各道路区分に関連する全情報が単一データベース内の単一データエントリーとして関連する場合、各データエンティティ記録はかなり大量になるであろう。こうなると、ナビゲーション機能１１９の何れかの機能がエンティティ記録にアクセスする度に、メモリ内の大量の情報を読まなければならないであろうが、この情報の多くはナビゲーション機能には必要ないものであろう。更に、記憶媒体１６４からデータエンティティを読む場合、各データエンティティはかなり大きいので、一度に読み出せるデータエンティティはかなり少ない。
【００２９】地理的データベース１６２内の情報を各ナビゲーション機能がより効率的なフォーマットで使用できる形として提供するために、所定の地理的範囲用に地理的データベース１６２全体を分割したサブセットを、タイプの異なる各ナビゲーション機能１１９に提供する。
【００３０】図５は、地理的データベース１６２の線図である。地理的データベース１６２は個別のセットから構成され、この独立したセットは経路データと、地図作成データ２３８（地図表示用）と、操縦データ２４０（経路案内用）と、対象地点データ２４２（ホテル、レストラン、美術館、スタジアム、空港のような特定の対象地点を確認する）と、合流点データ２４４（交差点名を確認する）と、ナビゲーション特徴名称データ２４６（実際の道路名称と他の地理的特徴を確認する）と、郵便番号データ２４８と、場所データ２５０（地方自治体、州、郡等を確認する）とから成る。地理的データベース１６２は他のタイプのデータ２５２に関するデータサブセットを含んでいてもよい。
【００３１】各データサブセットは、特定のナビゲーション機能が使うのに必要なデータだけを含んでいる。従って、経路データはナビゲーションに関連するデータ属性を含んでいる。地図作成データは地図表示に関連するデータ属性を含んでいる。操縦データは道路の解説に関連するデータ属性（例えば経路案内）を含んでいる。こうした各サブセットの間ではデータが幾分か重なり合うこともあり、データの一部分が結果的に二つ以上のサブセットに含まれることがある。例えば、経路データサブセット２３６内の道路区分データエンティティと、地図作成データサブセット２３８内の道路区分データエンティティは、区分の端に位置する節点を識別する属性を含んでいる。このような重複のため結果的に全体のデータ記憶要件は大きくなるが、結果的に各ナビゲーション機能はより少量のデータを扱うので効率が良くなる。
【００３２】各ナビゲーション機能に個別の地理的データサブセットを提供する際には、これらの各ナビゲーション機能の使い方が予期通りに他の機能と関連することを考慮している。例えば、エンドユーザーは、まず現在位置を見て、次に目的地を入力し、目的地に向けてどう出発するかという指示を受け、経路の最初の部分を示す地図を観察し、更に指示を受け、経路の次の部分を表示することを望む。このようなタイプの使用が予想されるので、データをサブセットへ分割することにより、各個別機能を使う際にデータを有効に利用できる。
【００３３】地理的データをサブセットに分割することにより、種々のナビゲーション機能の各々はデータを効果的に利用できるが、これらの異なるデータベースサブセットを使う種々のナビゲーション関連機能は共同で機能しなければならない。例えば上記の例では、計算した経路をエンドユーザーが入手した後に、計算された経路を強調表示した状態の地図をユーザーインターフェースのディスプレイ上に表示するのが望ましい。これを実現するには、まず地理的データの経路指定サブセット２３６にアクセスし、最適経路に関する経路指定道路区分データエンティティを取得し、次に地理的データの地図作成サブセット２３８にアクセスし、経路指定データエンティティに対応する地図作成道路区分データエンティティを取得する。これらのデータサブセットを一緒に機能させるために、相互参照、サーチツリー又は他のデータ検索技術を提供する索引が含まれている。索引は、データの何れかのサブセットの中又は外に置くことができる。図５は外部索引２５４を示す。索引をつけたデータをデータ外に記憶することにより、索引はロードできるようになり、様々なサブセットのデータ中でどのデータを次にロードしなければならないかを決定するのに使えるという利点が得られる。
【００３４】図６は、図５の経路指定データ２３６内に含まれている二種類のデータ記録を示す。図６は、経路指定データ記録（又はエンティティ）２５８と、二つの節点データ記録（又はエンティティ）２６０（１）及び２６０（２）の構成要素を示す。道路区分記録２５８は、地理的データベース１６２内でデータ記録を確認するための区分ＩＤ２５８（１）を含んでいる。道路区分データ記録２５８は、表された道路区分上での車両走行方向に関して、制約が課されているなら、この制約を示すデータ２５８（２）を含んでいてもよい。道路区分データ記録２５８は、速度の範囲（すなわち、表された道路区分上で許される走行車両の速度）を示すデータ２５８（３）を含んでいる。道路区分データ記録２５８は、表された道路区分が管理されたアクセス道路（高速道路）の一部であるの否か、管理されたアクセス道路へのランプの一部であるの否かなどを示すデータ２５８（４）を含んでいる。道路区分データ記録２５８は表された道路区分の等級を示すデータ２５８（５）を含んでいる。（道路区分の等級は機能クラスに対応する。例えば等級「４」の道路区分は、高速道路やフリーウェイのような交通量の多い管理されたアクセス道路を含んでいる。等級「３」の道路区分はあまり速度変化がなく交通量の多い道路であるが、必ずしも管理されたアクセス道路ではない。等級の低い道路は交通量が相応に少ないことを示し、一般的に速度の変化が多いか、又は速度が遅いことを示す。等級「０」の道路区分は交通量が最も少ないことを示す。例えば、これはわき道、路地等である。）
【００３５】道路区分データ記録２５８は、表されている道路区分に名称があるとすれば、その一つ又は複数の名称を示すデータを含んでいる。一つの実施例で、道路区分データ記録２５８は、ナビゲーション可能特徴名称データサブセット２４６内に含まれる一つ又はそれ以上の対応するデータ記録に対する一つ又はそれ以上のリファレンス２５８（６）を含んでいる。道路は二つ以上の名称で知られていてもよい。地理的データベース１６２は、各道路に関して分かっている全道路名称を、ナビゲーション可能特徴名称データサブセット２４６内に含んでいてもよい。これにより、エンドユーザーは、分かっている道路名称を所望の目的地として指定できるようになる。しかし本実施例では、道路について知られている全名称は、道路区分データ記録２５８によって必ずしも照会されない。替わりに、経路案内データ区分記録２５８内の一つ又はそれ以上のリファレンス２５８（６）は、道路区分を照会する道路標識に使われている名称だけを指す。特に本実施例では、道路区分データ記録２５８内のリファレンス２５８（６）は、ナビゲーション可能特徴名称データ２４６内の記録を指すか又はさもなければ確認する一つ又はそれ以上のＩＤ関連を含んでいるが、このナビゲーション可能特徴名称データ２４６は表された道路区分を照会する名称を、表示された道路区分沿いの何れかの標識よる名称で含んでいる。道路標識上の名称が使われるのは、これらの名称が道路を知る上で最もよく知られている名称だからである。更に道路標識上の名称が使われるのはドライバーが運転中に遭遇するであろう名称だからである。（道路区分データエンティティ２５８により表される道路区分が名称を持たない場合、ナビゲーション特徴データ２４６内の記録にリファレンスは存在しない。）
【００３６】道路区分データ記録２５８は、道路区分エンドポイントの地理的座標（例えば緯度と経度）を提供するデータ記録２５８（７）も含んでいる。一つの実施例では、データ２５８（７）は、表された道路区分エンドポイントに対応する節点を示す節点データ記録２６０（１）及び（２）に対するリファレンスである。有効な継承区分があるとすれば、それを道路区分のエンドポイントにおいて示すデータ２５８（７）（１）（２）及びデータ２５８（７）（２）（２）は、道路区分データ記録２５８と関連し、無効な継承区分があるとすれば、それを道路区分のエンドポイントにおいて示すデータ２５８（７）（１）（２）及びデータ２５８（７）（２）（２）は、道路区分データ記録２５８と関連している。正当な継承区分とは、他の節点に接続している区分であり、車両は当該節点を越えて他の区分へ向かって走行でき、無効な継承区分とは他の節点に接続している区分であり、車両は当該節点を越えて他の区分へ向かって走行できない。
【００３７】道路区分データ記録２５８は、区分が特定の解説と関連しているか否かを示すデータ２５８（９）と、区分が迂回部分の一部分であるか否かを示すデータ２５８（１０）と、区分が船着場の一部分であるか否かを示すデータ２５８（１１）と、区分が特別な交通状況であるか否かを示すデータ２５８（１２）と、区分が高速道路のインターチェンジの一部分であるか否かを示すデータ２５８（１３）と、表された道路区分がある行政区を示すデータ２５８（１４）と、区分に車両規制（例えばトラック乗り入れ禁止、タクシー乗り入れ禁止など）があるか否かを示すデータ２５８（１５）とを含んでいる。
【００３８】道路区分データ記録２５８は、表示された道路区分の様々な他の属性を含むか又は照会する他のデータ２５８（８）を含んでいても又は関連していてもよい。道路区分に関連する様々な属性は、一つの道路区分記録に含まれていても、又は相互参照される二つ以上のタイプの記録に含まれていてもよい。
【００３９】図７は、図５に示されているナビゲーション特徴データ２４６内に含まれる一つのナビゲーション特徴名称データ記録２６２の構成要素を示す。ナビゲーション特徴名称記録２６２の第一データ構成要素は、ナビゲーション特徴名称ＩＤ２６２（１）である。ナビゲーション特徴名称ＩＤ２６２（１）は、地理的データベース１６２内のナビゲーション特徴名称記録２６２に関連する固有の番号である。ナビゲーション特徴名称ＩＤ２６２（１）は、ナビゲーション特徴名称記録２６２が表す特徴名称を含むデータ構成要素２６２（２）も含んでいる。道路標識属性２５８（６）上の名称で参照されるナビゲーション特徴名称記録２６２の場合、このデータ構成要素２６２（２）は、表示された道路区分を照会する名称を、表示された道路区分沿いの何れかの道路標識による名称で含んでいる。例えば、表されている道路区分沿いの道路標識上の名前が「ＨＩＧＧＩＮＳ」である場合、この名称の付いた交差点を示す経路指定区分データ記録２５８内の道路標識リファレンス２５８（６）上で名称によって照会されるナビゲーション特徴名称記録２６２のデータ構成要素２６２（２）は、テキスト「ＨＩＧＧＩＮＳ」を含んでいる。
【００４０】ナビゲーション特徴名称記録２６２の別のデータ構成要素２６２（３）は（ネームフィールド２６２（２）に含まれている）名称が照会するタイプの特徴を示している。ナビゲーション特徴名称記録２６２が道路名称を照会する場合、このデータ構成要素２６２（３）は、ナビゲーション特徴名称記録２６２が「道路」の名称を表していることを示す。ナビゲーション特徴名称記録２６２は交差点、港のような他の種類の名称がついている特徴を表すのにも用いられる。（表された特徴の名称を得るために、他の種類の特徴を示すデータ記録は、ナビゲーション特徴名称記録を照会してもよい。）各ナビゲーション特徴名称記録２６２は、他のデータ構成要素２６２（４）を含んでいてもよい。
【００４１】（Ｃ）地理的データの階層化地理的データの利用を向上させるために地理的データを編成する別の方法は、階層状のデータを提供することである。地図表示機能１４６及び経路計算機能１４２のような幾つかのナビゲーション機能は、詳細レベルが様々なデータを用いることができる。例えば、地図表示機能１４６を使う場合、時によってはパニング及びズーミングを提供することが望ましい。地図表示データ２３６が、低い階層ではより詳しく高い階層ではあまり詳しくなく階層状に編成されている場合、ズーミングを効率的に行うことができる。同様に、経路計算機能１４２を用いる場合、詳しさのレベルが様々なデータを用いるのが有利である。例えば、二つの位置の間での経路を計算する場合、派生街路及び横道を含めて、経路沿いの各交差点から分岐する可能性がある全道路区分を調べることは、効率が悪いことになろう。そうではなく、経路がひとたび主幹道路又は高速道路「上に」乗ったならば、目的地に近づき派生道路へ出なければならなくなるまで、主幹道路又は高速道路を走るほうが一般には望ましい。経路指定データ２３６を階層化すると、派生道路を省略した高い階層を使うことができ、経路を計算する際に調査対象となる道路区分の数を最小にできることがある。従って、幾つかのサブセットタイプのデータでは地理的データを、個別の階層に対応する独立コレクション又はグループの形で提供する。
【００４２】上記のように、階層化は道路区分の等級を使って行える。道路区分を表す道路区分エンティティが含まれている最も高いデータ階層を特定するために、道路区分の等級を使うことができる。例えば図８を参照すると、経路指定タイプのデータ２３６は、Ｒ０、Ｒ１、Ｒ２、Ｒ３及びＲ４のデータから成る五つの個別の階層を含んでおり、各階層が、異なるレベルの詳しさを有する経路指定データの独立したコレクションから成っており、これらは経路計算機能１４２で使われている。地理的データベースの経路指定データ２３６では、階層０（Ｒ０）は、等級が「０」又はそれ以上の道路区分データエンティティを含んでいる。従って、階層０は、地理的範囲内の全道路の全ての部分に対応する道路区分データエンティティを含んでいる。経路指定データ２３６の階層１は経路指定データの独立したサブセット（又はコレクション）から成り、等級が「１」又はそれ以上の経路指定区分データエンティティ（及び前記エンティティに対応する経路指定データ属性の一部又は全て）だけを含んでいる。経路指定データ階層２は経路指定データの独立したサブセットから成り、等級が「２」又はそれ以上の経路指定区分データエンティティ（及び前記エンティティに対応する経路指定データ属性の一部又は全て）を含み、以下階層３，４についても同じである。最高階層（階層ｎ）は、ｎ等級の記録だけを含んでいる。本実施例ではｎは４であるが、他の実施例で、ｎは０よりも大きい何れの数であってもよい。階層が高いほど、記録は少なくなるが、その記録は走行が一般に速く行われる道路を示している。
【００４３】同様に、他のタイプのデータが独立した階層のデータを含み、各階層が異なるレベルの詳しさを有していてもよい。例えば、地図表示機能１４６で用いられる地図作成データタイプ２３８は多数の階層の形で提供される。地図表示機能１４６は、地図作成データ２３６の様々な階層を使って、素早いパニング及びズーミングを提供できる。複数のデータを階層に編成すると、データを幾らか重複させる結果となる。例えば、図８の実施例では、等級が「４」の道路区分を示す経路指定記録は、経路指定データの五つの独立階層に含まれている。しかし、階層化により効率が向上し、不利な点は相殺される。上記の独立タイプのデータを使う場合、これらの階層を同時に機能させることが必要となる。この目的のために索引を提供する。図８は索引２７０を示している。内部索引２７０は様々なタイプのデータに含まれている。外部索引をこの目的のために使ってもよい。
【００４４】（Ｄ）空間的な編成と地理的データへのアクセスデータをサブセット又はタイプに編成することは、ナビゲーション関連アプリケーション１１９内の各機能によって更に管理し易いサイズの独立したデータコレクションを提供することになる。幾つかのサブセットタイプでは、空間的に容易にアクセスできるように、データを更に編成することができる。
【００４５】図２に示すナビゲーション関連アプリケーション１１９中の幾つかのナビゲーション機能は、空間的に地理的データにアクセスし、又は地理的データを空間的に使用する。これを行うための一つの方法は、ナビゲーションアプリケーション機能が、地理的範囲内のデータエンティティによって表される地理的特徴の物理的位置に基づいて、地理的データベース１６２内のデータエンティを使用することである。例えば、ある機能は、所定のデータエンティティによって表される道路区分と接続している全道路区分を表すデータエンティティを見つけなければならない。空間アクセスを行う別の方法は、ナビゲーション関連アプリケーション内の機能が、地理的範囲内又は地理的範囲の定義された領域内のある位置の近くにある特徴を示す幾つか又はすべてのデータ記録を検索しなければならない時の方法である。
【００４６】図５では、地理的データの幾つかのサブセットが空間的に編成され、他のデータのサブセットは空間的以外の方法で編成される。空間的に編成されたデータの配列は、地理的に近くにある特徴を示すデータがデータベース１６２内で及び／又は媒体１６４上に理論的に及び／又は物理的に近くなるようになされる。幾つかのナビゲーションアプリケーション機能では、各データを空間的に編成することにより、密接に関連する地理的データを媒体からより速く読み出すことと、関連地理的データをメモリにロードすることとが可能になる。この種の編成により、記憶媒体１６４へのアクセスが最短となり、これらのナビゲーション機能の作動が速くなる。
【００４７】空間的に編成された地理的データ１４０のサブセットは、経路計算データ２３６と地図作成データ（地図表示）２３８とを含んでいる。他の種類のデータも空間的に編成できる。種々の方法で空間的編成をデータに適用することができる。例えば、空間的編成は各データ記録に又は複数のデータ記録を分類することに適用することができる（例えば、以下に述べるようなデータのパーセル化）。幾つかのデータサブセットは、空間的以外の方法で編成されアクセスされる。例えば、幾つかのデータサブセットは、アルファベット順で編成され、あるいは市、州、国等を単位として編成される。非空間的に編成されたデータとしては、合流点データ２４４、ナビゲーション特徴名称データ２４６、対象地点データ２４２、郵便番号データ２４８、場所データ２５０を挙げることができる。他のタイプのデータも非空間的に編成してもよい。
【００４８】（Ｅ）地理的データのパーセル化地理的データを使う場合に、幾つかの要素はナビゲーションアプリケーションプログラムの作動と性能に影響を与える。合理的な高レベルの機能を提供するため、かなり大きなデータベースが提供される。ＣＤＲＯＭディスク、ＤＶＤディスク、ＰＣＭＣＩＡカードのような記憶媒体は、適当な機能性を提供するのに十分な規模と複雑さを有するデータベースを扱うことができる。しかし、これらのタイプの媒体へのアクセスはかなり遅い。ナビゲーションシステムは車載されるか又は携帯されるので、ナビゲーションシステムのハードウェアリソースは制限されている。車載又は携帯ユニットであるナビゲーションシステムは、メモリリソースが限られ、媒体へのアクセス速度もかなり遅い。ナビゲーションアプリケーションが大容量のメモリとハードウェアリソースを有するプラットフォーム上に備えられる場合でも、規模は違うが、同様のことが考えられる。
【００４９】ナビゲーションシステムのメモリリソースが限定されているため、所定の地理的範囲全体の全データ記録をナビゲーションシステムのメモリに一度にロードできないとすれば、必要な機能を実行するのに必要なデータだけをメモリにロードすることが望ましい。これを実現するため、地理的データベース１６２内のデータをパーセル状に編成する。一つのパーセルデータを、媒体への一回のアクセスで得られるデータ記録を含むように整える。これは、他の要素にも関係するが、一回のディスクアクセスでアクセスし得るデータ量に関係する。ＣＤＲＯＭディスクのような幾つかのタイプの媒体では、一つのパーセルを１６キロバイトのデータ量となるように整える。（他のサイズとして、１Ｋ、２Ｋ、４Ｋ、８Ｋ、３２Ｋ等を挙げることができる）。
【００５０】図９に示すように、各パーセル３２０内のデータが論理的及び／又は物理的に一緒に分類されるように、データパーセル３２０を記憶しデータベース１６２を形成する。あるパーセルデータへのアクセスが行われると、そのデータ記録全てが媒体からナビゲーションシステムのメモリへ一度に読み出される。データは、パーセル状に形成される前に、種々のタイプ（例えば、図５の経路指定、地図作成、操縦等）にまず分けられてから編成される。更に、階層毎（例えば経路指定、地図作成）に編成されたタイプのデータに対し、（図８に示すような）これらのタイプのデータが、パーセル状のデータを編成する前に、階層状に独立して編成される。
【００５１】（１）空間的に編成されたデータのパーセル化データをパーセル化する場合、ナビゲーション機能を実行するためにアクセスされ読み出されなければならないパーセルの数を最も少なくするような方法で行うことが一般には望ましい。上記のように、表されている特徴が物理的に近いということに基づいて、地理的特徴を示すデータを記憶するのが時には望ましい。空間的に編成されたデータに関しては、一般的にはデータが表す特徴の物理的な地理ロケーションに基づき、又はデータが表す特徴の地理的な近さに基づき、データをメモリにロードする手段を提供するのが有利である。これは、データを空間的にパーセル化することで実現できる。空間的にパーセル化されたデータの配置は、地理的に近い特徴を表すデータを論理的及び／又は物理的にデータベース１６２内及び／又は媒体１６４上で近くに置くように行われる。幾つかのナビゲーションアプリケーション機能の場合、各データを空間的にパーセル化するにより、密接に関連する地理的データを媒体からより速く読み出す段階と、関連する地理的データをメモリへロードする段階が提供される。この種の編成により、記憶媒体１６４へのアクセスは最短となり、これらのナビゲーション機能の作動が速まる。
【００５２】地理的データを空間的にパーセル化するための手順は様々である。例えば、単純なパーセル化の方法では地理的データを複数のパーセルに分割するが、この場合、各パーセル内のデータにより、サイズが規則正しい複数の長方形の各長方形に包含されている特徴が表され、この複数の長方形で地理的範囲上に一つの整然とした長方形のグリッドを形成させる。空間的にパーセル化する別の方法では、長方形の領域内に包含されるパーセル状にデータを分割するが、この場合、各長方形は、前記領域の部分を囲んでいる長方形を最大閾値より小さなパーセルサイズが得られるまで二分割することにより形成される。更に、パーセルに分割する手順は、１９９６年１０月２５日出願の同時係属出願番号第０８／７４０，２９５号と１９９７年９月５日出願の同時係属特許出願番号第０８／９３５，８０９号に開示されており、それらの開示全体を参考としてここに援用する。更に、上記開示の主題を適用できる別のパーセル化方法が、米国特許番号第４，８８８，６９８号及び第４，９３７，５７２号に開示されている。
【００５３】空間的に編成されたデータのパーセル化を図１０に示す。図１０は、図３に以前示した地理的範囲２１２の地図２１０を示す。地図２１０上の複数の位置２１４（ドット又はポイントで表示されている）が示されている。各位置２１４は、地理的範囲２１２内の場所又は地点を表し、そこには或る特徴が配置され、それについての情報が図２の地理的データベース１６２内に含まれている。例えば、位置２１４は、道路区分のエンドポイント、道路区分に沿った地点、対象地点（例えばホテル、市民会館等）の地点等の物理的位置に対応し、これらの位置は地理的データベース１６２内のデータによって表される。これらの各位置２１４は、固有の物理的位置（緯度、経度、絶対的又は相対的に表された随意的な標高）を有し、各位置２１４は、二次元（又は三次元）の地理的座標（すなわち、緯度、経度、随意的な標高）により個別に特定することができる。
【００５４】図１０でグリッド３１７は、地図２１０に表された地理的範囲２１２と重なっている。グリッド３１７は、地理的範囲２１２を複数の長方形の領域３１９に分割する。グリッド３１７のグリッド線は長方形の領域３１９の境界線を表す。これら長方形の領域３１９のサイズは、全て同じでもよく、又パーセル化に用いられる手順により異なっていてもよい。同様に、境界線のロケーションは使われるパーセル化の手順に左右される。一般に、何れかの空間的なパーセル化手順を用いる時、各長方形の領域３１９の範囲内に含まれている特徴を表す特定のタイプのデータに関するデータ記録は、データの独立パーセル内へ一緒にグループ化される。図９では、地理的データベース１６２の経路指定サブセット２３６から成る道路区分記録や節点記録のような複数のデータ記録は、複数のグループ（すなわち、パーセル３２０）に分割される。空間的に編成されるデータの場合、図９の経路指定の各パーセルは、図１０が示す複数の長方形３１９の中の独立した一つの長方形内に包含される地理的特徴を表すデータ記録を含んでいる。
【００５５】図９に示すようにパーセル３２０は、各パーセル３２０内のデータが論理的及び／又は物理的に一緒に分類されるように、記憶されてデータベース１６２を形成する。パーセルは、ナビゲーションシステムが同時にアクセスするデータ記録の量を示すので、一つのパーセルのデータがアクセスされると、そのデータ記録のすべてがナビゲーションシステムのメモリに読み込まれる。これは、図１０の地図２１０を見ると、例えば区分記録又は節点記録、即ち、各長方形３１９内に包含された地理的特徴を表す空間的に編成されたタイプのデータの全データ記録が共に一つのグループとしてアクセスされる。ある種類のナビゲーション機能の場合、地理的範囲内で物理的に近い特徴を表す全データ記録は同時にメモリに含むのが望ましいということが理解できる。
【００５６】パーセル３２０は、これらのタイプのデータ用に形成される時、順序付けされる。様々なタイプの順序付けが使われる。一般に、パーセルの順序付けは、データの探索を最小にするような方法でなされるのが望ましい。空間的に編成されたパーセルを順序付けする一つの方法では、各タイプのデータ内にあるｋｄツリー索引から深さ優先の順序付けを使っている。これは、ペアノキー順序付けに似た順序付けを提供する。パーセルは、ディスク（すなわち、図２の媒体１６４）上に略々ぺアノキー順序付けの状態で記憶される。パーセルに空間的にアクセスするため、ｋｄツリーのような一つ又はそれ以上の索引を使うことができる。この索引は、ナビゲーションシステム内のプログラムが最新の車両位置に対応する地図データを始めて捜す場合のような、任意のポジションを最初に突き止めるのに役立つ。
【００５７】パーセル３２０を順序付けする時、各パーセルに個別のパーセル識別子（例えば「パーセルＩＤ」）を割り当てる。パーセルＩＤは、パーセルを識別することのできる識別子（例えば番号）であり、パーセル又はパーセル内のデータを検索することが必要な場合にパーセルを照会するのに使われる。一つの実施例では、パーセルＩＤは、パーセルが形成されているのと同じ順序及びパーセルがデータベース中に順序付けされているのと同じ順序でパーセルに割り当てられる。これにより、パーセルのサイズを知れば、媒体上に何れかのパーセルの位置を突き止めるために、パーセルＩＤをデータベースファイルの開始個所からのオフセットとして使えるという利点が得られる。
【００５８】（２）非空間的に編成されたデータのパーセル化幾つかの種類のデータは空間的に編成されていない。パーセル化はこれらのデータにも同様な利点を提供する。非空間的に編成されたデータの各パーセルは、必ずしも図１０の何れかの長方形領域３１９に対応しない。例えば、街路や交差点のような地理的特徴の名称を表すナビゲーション特徴名称データは、空間的にではなくアルファベット順に編成される。また、場所データ２５０は、空間的に編成されない種類のデータである。場所データ２５０は、管理階層により編成される。場所データ２５０は、行政又は管理領域（例えば、国、市、州、郡、地帯、居住地など）を表すのに使われる場所データ記録を含んでいる。場所データ２５０は、データが表す場所の管理レベルを考慮に入れた階層方法で編成される。この階層方法で場所データ記録が一旦編成されると、それらはパーセル３２０（図９）状に形成され、記憶され、地理的データベースを形成する。場所データエンティティは空間的に編成されないので、場所データの各パーセルは、必ずしも図１０の何れかの長方形領域３１９には対応しない。
【００５９】ある実施例で場所データは、管理階層に対応するレベルに従って配列される。レベル１の場所データ記録（すなわち地理的特徴が地理的データベース１６２により表示される「国」に対応する場所データ記録）は、最初は場所データ２５０に含まれる。地理的データベースが二つ以上の国を表す場合（例えばカナダや合衆国）は、レベル１の記録はアルファベット順に順序付けされる。次に地理的特徴が地理的データベース２５０により表されるレベル２の場所データ記録全て（すなわち、合衆国の「州」又はカナダの「州」に対応するデータ記録）が配列される。これらの場所データは、所属するレベル１の記録により表される国の場所記録に従ってまず順序付けされ、次に国に従って分類された後、アルファベット順に分類される。従って、地理的データベースがカナダと合衆国とを含む場合、カナダの州を表す場所データの全記録がまずアルファベット順に配列され、その後にアルファベット順に配列されている合衆国の州を表す場所データの全記録が続く（地理的データは必ずしも合衆国の全ての州又はカナダの全ての州を含まないことを注意せよ。地理的データベースに表されている州だけしか含まれない）。
【００６０】次に地理的特徴が地理的データベース１６２により表されているレベル３の全場所データ記録（すなわち、合衆国とカナダの「郡」に対応するデータ記録）が配列される。これらの場所データは、所属するレベル２の記録により表される合衆国の州（又はカナダの州）の場所記録に従ってまず順序付けされ、次にアルファベット順に順序付けされる。従って、地理的データベースがイリノイ州とアイオワ州を含む場合、イリノイ州を表す場所データの全記録がまずアルファベット順に配列され、その後にアルファベット順に配列されているアイオワ州を表す場所データの全記録が続く。
【００６１】最後に、地理的特徴が地理的データベース１６２により表されているレベル４の全場所データ記録（すなわち、合衆国又はカナダの「市」に対応するデータ記録）が配列される。これらの場所データは、所属するレベル２の記録により表される合衆国の州（又はカナダの州）の場所記録に従ってまず順序付けされ、次にアルファベット順で順序付けされる。従って、地理的データベースがイリノイ州とアイオワ州を含む場合、イリノイ州の市を表す場所データの全記録がアルファベット順にまず配列され、その後にアルファベット順に配列されているアイオワ州の市を表す場所データの全記録が続く。
【００６２】上記の場所データのパーセル化は、これらのデータ記録を編成することのできる一つの方法を示す。他の種類の編成方法を使ってもよい。例えば、他の種類の階層配列を場所データに使ってもよい。替わりに場所データ記録を、経路指定データのように空間的に編成してもよい。ナビゲーション特徴名称データ２４６のサブセット内で、ナビゲーション特徴記録２６２はナビゲーション特徴ＩＤ（即ち２６２（１））により編成される。ナビゲーション特徴名称ＩＤは、表された名称によってアルファベット順に割り当てられる。他の種類のデータのように、ナビゲーション特徴名称記録は複数のパーセルに編成されており、各パーセルは複数のナビゲーション特徴記録２６２を含んでいる。従って、全てのナビゲーション特徴名称データサブセット２４６（図５）から成る複数のナビゲーション特徴記録２６２は、複数のパーセル３２０に含まれている。
【００６３】（Ｆ）地理的データベースの特徴の利用地理的データベースを用いるナビゲーション関連アプリケーションの性能を改良するために、上記の幾つか又はすべての機能を地理的データベース内で実行することができる。これらの機能は、地理的データの部分を配列及び／又は編成することにより性能を改良するが、その際は、一定のナビゲーション機能を実行するための地理的データベース内のデータへのアクセス又は利用を容易にする方法で行われる。地理的データベースが提供する特徴を向上させる幾つか又はすべての性能からナビゲーション関連アプリケーションが利益を得るためには、地理的データベースを用いるか又はアクセスするアプリケーション機能は、前記の特徴を利用できるように書かれてなければならない。
【００６４】例えば、経路計算機能１４２（図２）は、出発地点と目的地点との間の各交差点から候補となる経路を調べることにより、推奨経路を計算する。一般に制限速度が最高で及び／又は交通量が最大である道路区分だけに候補となる経路の調査を限定できる場合、経路計算機能１４２は推奨経路をより速く決定できる。この種の限定された調査を可能にするため、図８に関連して述べたように、地理的データベースを階層状へ編成することができる。経路指定データを階層に編成する場合、等級の高い（一般に高速）道路は、物理的に独立したコレクション（又は階層）に編成されている。しかし、等級の高い道路は、高速であっても一般的に詳しくは記述されてなく、経路の開始部分や最終部分などのように、経路計算プロセス全体を通して利用するには適当でないことがある。
【００６５】地理的データベース１６２内の経路データ２３６の階層化配列特徴を利用するために、経路計算機能１４２は、経路計算プロセスの様々な段階で経路指定データ２３６のどの階層を用いるべきかを決定する適当な指示又はルーチンを含むことができる。この経路計算機能１４２は、経路計算プロセスのどの段階でどの階層を用いるべきかを様々な要因に基づいて決定するために、適切な論理又はアルゴリズムを使う。次に、適当な階層の決定に基づいて、経路計算機能１４２（又は別のサブプログラム）は、どの階層から経路指定データを取り出すべきかを指示するように、適当な機能を呼び出すか又はコマンドを発する。従って、経路計算アプリケーションの論理又はアルゴリズムが経路指定データ２３６の階層を利用するためには、経路指定データ内の様々な階層の数と各階層での詳しさのレベルを考慮することが必要である。
【００６６】ナビゲーション関連アプリケーション１１９の他の機能は、地理的データベースの特徴を考慮するように設計されていてもよい。例えば、ディスプレイ画面上に地理的範囲の特定の区域を表示するため、ナビゲーションアプリケーション内の機能は、表示されることが望ましい範囲の地理的座標を、前記範囲を表すために必要な地図作成データを含むパーセルのＩＤへ翻訳できなければならない。地図作成データを含む媒体上でパーセルを識別することは、インターフェース階層機能１５４（図２）のライブラリで可能になるが、この機能１５４は、地理的データベースの一部として準備された索引を使って、空間座標をパーセルのＩＤへ翻訳することを容易にする。
【００６７】（III）経路プレビュー機能（Ａ）ナビゲーションプログラミングの概要図２に関連して先に述べたように、ナビゲーションシステム１１０が実行するナビゲーション関連機能及び／又は特徴を提供するアプリケーション１１９は、ナビゲーションシステム１１０のソフトウェア部分１１８に含まれている。これらのナビゲーション関連プログラム及びアプリケーション１１９は、様々なナビゲーショ関連特徴及び／又は機能を提供するため、ユーザーインターフェース１３１からの入力と恐らくは位置決めシステム１２４からの出力とにも関連して、地理的データベース１４０を使っている。
【００６８】一つの実施例では、ナビゲーション関連プログラム及びアプリケーション１１９は、持ち運び可能で、様々な種類のシステム及び／又はプラットフォームに組み込めるモジュールとして提供されている。ナビゲーション関連アプリケーション１１９は、不揮発性媒体１１６（図１）上に記憶される実行可能な単一プログラムを形成するようにコンパイルされる。替わりに、ナビゲーション関連アプリケーション１１９は、一つ又はそれ以上の独立プログラムとして提供されていてもよい。
【００６９】一つの実施例では、ナビゲーション関連アプリケーション１１９は、そのプログラミングとデータ利用に関してオブジェクト指向の手法を採っている。この実施例によれば、各ナビゲーション関連アプリケーションは、一つ又はそれ以上のオブジェクトで形成され、各オブジェクトは所定の機能に従って入力データを受け取って出力データを生成するが、各オブジェクトが他のオブジェクトに対する方法を呼び起こしてもよい。本実施例の一つで、各オブジェクトは、他のオブジェクトに対して不透明な固有のメモリを有する。一つの実施例では、オブジェクトは、データを一つのオブジェクトから別のオブジェクトまで運ぶのに使われるか、又は入力として受け取られたデータを変換するのに使われる。一つの実施例では、ナビゲーション関連アプリケーション１１９は、Ｃプログラミング言語で書かれるが、代替実施例では、Ｃ++、ジャバ、ビジュアルベーシック等の別のプログラミング言語を用いてもよい。
【００７０】（Ｂ）経路計算アプリケーション図２に関連して述べたように、ナビゲーションシステム１１０の経路計算機能は、経路計算アプリケーション１４２により実行される。図１１に示す実施例では、マネージャーアプリケーション１５５は経路を計算するために、ナビゲーションアプリケーション１４２に要求を与える。マネージャーアプリケーション１５５による要求は、少なくとも一つの出発地と目的地を規定する。マネージャーアプリケーション１５５による経路計算アプリケーション１４２への要求は、所望の中間停車地点、ドライバーの好みのもの、出発時間等の追加情報を含んでいる。
【００７１】一つの実施例では、経路を計算する要求は、エンドユーザーから開始される。エンドユーザーは、ユーザーインターフェース１３１を使って望みの目的地を指示する。エンドユーザーがユーザーインターフェース１３１を使って出発地を指示しない場合、最新の車両位置が出発地として取られる。一つの実施例では、出発地及び目的地が、地理的データベース内のデータに関連して、経路計算機能１４２に対して規定される。例えば、出発地と目的地は、識別された道路区分データ記録により表される道路区分か又は前記区分に沿って規定される。マネージャーアプリケーション１５５は、車両が位置している最新道路区分を表す道路区分データ記録のＩＤを車両位置決めアプリケーション１４８から入手する。マネージャーアプリケーション１５５は、エンドユーザーが指示した所望の目的地が位置している道路区分を表す道路区分データ記録のＩＤを、ジオコーディングアプリケーション１４１から入手する。（エンドユーザーが所望の出発地も規定する場合、マネージャーアプリケーション１５５は、所望の出発地が位置している道路区分を表す前記道路区分データ記録のＩＤを、ジオコーディングアプリケーション１４１から入手する。）従って、この実施例では、マネージャーアプリケーション１５５が経路計算アプリケーション１４２に規定された出発地と目的地の間の経路を計算するように要求すると、マネージャーアプリケーション１５５はまず、ジオコーディングアプリケーション１４１からデータを入手し、そして恐らくは出発地と目的地を地理的データベース１６２内のデータを関連させる車両位置決めアプリケーション１４８をも入手する。代替実施例では、エンドユーザーが規定した出発地及び目的地又は車両ポジションを関連させる機能は、経路計算アプリケーション１４２内のルーチンを含む他のルーチンにより実行される。
【００７２】上記のように経路計算アプリケーション１４２は、経路計算に影響する追加データを受け取る。例えば、経路計算アプリケーション１４２は、有料道路又は高速道路を回避するというようなエンドユーザーの好みを規定するデータを受け取る。経路計算アプリケーション１４２は、経路走行が始まる時間を確認するデータを受け取ってもよく、このデータは経路計算に影響を与える可能性がある。経路計算機能１４２は、エンドユーザーが止まりたいと思う中間停車地点を示すデータを受け取ってもよい。
【００７３】出発地と目的地の位置を確認するデータが与えられると、経路計算アプリケーション１４２は出発地と目的地の間の経路を計算する。経路計算アプリケーション１４２は、この目的のために様々な手段またはアルゴリズムの内の何れかを使う。例えば、使われる方法は、Ａ*アルゴリズム又はディクストラアルゴリズムのいずれかを含んでいる。経路を計算する方法が１９９８年３月２５日出願の番号第０８／８９３，２０１号に開示されており、その開示全体を参考としてここに援用する。（上記特許出願に開示されている方法は経路を計算できる一部の方法しか示していないが、この明細書で請求する主題は如何なる特定の経路計算方法にも限定されるものではない。現在周知の又は将来開発される何れの経路計算方法も採用することができる。）
【００７４】使われる方法がどんなものであるにせよ、経路計算アプリケーション１４２の目的は、出発地と目的地との間の法的に正当な推奨経路を形成する一連の道路区分を特定するリストを作成することである。（「法的に正当な推奨経路」とは、一方通行、ターン制限等、既知の交通規制を遵守することである。）経路計算アプリケーション１４２で使われる方法は、一つ又はそれ以上の所定判定規準に適合させるために、推奨経路を最適化するように設計される。こうした判定規準には最低走行時間、最短距離、最低ターン回数などが含まれている。経路計算アプリケーション１４２に使われる方法が一つ又はそれ以上の判定規準に合わせて最適化された推奨経路を見つけるように設計されている場合、推奨経路はこれらの一つ又はそれ以上の判定規準に理想的に合致する。
【００７５】推奨経路を計算する上記何れかの方法を使う場合、経路計算アプリケーション１４２は、出発地点から続く幾つかの様々な代替候補となる通路が推奨経路内に含まれるように調べる。経路計算アプリケーション１４２は又、目的地から逆戻りする幾つかの様々な代替候補となる通路が推奨経路内に含まれるように調べるようにしてもよい。又、経路計算アプリケーション１４２は、推奨経路の候補となる部分に沿った全て又は幾つかの交差点から続く幾つかの様々な代替候補となる通路を調べてもよい。例えば、二つ以上の正当な継承道路区分を有する交差点が、調査中の既存の代替候補となる推奨通路沿いに見出される場合は常に、追加の代替通路を特定し調べる。様々な代替候補となる推奨通路の数は急速に増加する。経路計算方法によっては、経路計算が進むにつれて、調査中の幾つかの代替候補となる推奨通路を、他のより有望な代替候補である推奨通路との比較に基づいて放棄してもよい。経路計算方法によっては、経路計算が進むにつれて、他のより有望な代替候補である推奨通路を優先し、調査中の幾つかの候補となる通路を更に調べることを中止又は延期してもよい。
【００７６】経路計算アプリケーション１４２は、様々な代替候補となる推奨通路を推奨経路内に含むように評価する場合、代替候補となる各推奨通路内に含まれた道路区分を特定するデータを記憶する。経路計算アプリケーション１４２は、候補となる推奨通路内に含まれているとして確認された道路区分を表す道路区分データエンティティ２５８から全データの内の一部データを記憶する。一つの本実施例では、各々の異なる代替通路内に含まれている道路区分を表す道路区分データ記録を識別するデータベースＩＤ（例えば図６の区分ＩＤ２５８（１））が記憶される。本実施例によれば、経路計算アプリケーション１４２は、候補となる推奨通路内に含まれるとして確認された道路区分を表す道路区分データエンティティ２５８の各々に関し、道路標識データ２５８（６）における名称、分類２５８（４）、区分が特別の解説に関連するか否か２５８（９）、区分が迂回路の一部であるか否か２５８（１０）、区分が港の一部であるか否か２５８（１１）を記憶する。経路計算アプリケーション１４２は又、代替候補となる各推奨通路に含まれる全道路区分の合計距離、代替候補となる各推奨通路の合計全走行時間等のような、代替候補となる各推奨通路に関する追加データを記憶してもよい。
【００７７】図１１では、経路計算アプリケーション１４２が推奨経路を探し出した後に、出力４００が経路案内アプリケーション１４４へ提供される。図１２は、経路計算アプリケーション１４２の出力４００の構成要素を示す図である。経路計算出力４００は、順序付けされたリスト４１０を含んでいる。順序付けされたリストの各エントリーは、出発地と目的地との間の推奨経路の一部を形成する道路区分を表す道路区分データエンティティ２５８を識別する。複数のデータエンティティ２５８は、経路計算アプリケーション１４２が計算した出発地点と目的地との間で連続するナビゲーション可能な経路を形成する道路区分を表している。
【００７８】リスト４１０内の各エントリーは、区分データエンティティ２５８からの一部又は全ての情報を含んでいる。例えば、リスト４１０内の各エントリーは、表された道路区分に関連するレコード２５８からの道路標識道路情報２５８（６）の名称を含んでいる。上記のように、道路区分を一つ又はそれ以上の道路標識上の名称によって照会する場合、経路指定データ２３６内のこの道路区分を表すデータ記録２５８は、道路標識上のこれらの名称を含むナビゲーション特徴名称データ２６６内の対応する各記録２６２に対するリファレンス２５８（６）を含んでいる。リスト４１０の各エントリーは又、分類２５８（４）、道路区分が特別の解説と関連するか否かを示すデータ２５８（９）、道路区分が迂回路の一部であるか否か２５８を示すデータ２５８（１０）、道路区分が船着場の一部であるか否かを示すデータ２５８（１１）、道路区分が特別な交通状況の一部であるか否かを示すデータ２５８（１２）、道路区分が高速道路インターチェンジの一部であるか否かを示すデータ２５８（１３）、表された道路区分が配置されている行政区域（例えば市、州など）を示すデータ２５８（１４）、道路区分が車両規制（例えばトラック乗り入れ禁止、タクシー乗り入れ禁止等）を含むか否かを示すデータ２５８（１５）のような道路区分を表す記録２５８からの他のデータも含んでいてもよい。
【００７９】リスト４１０の各エントリーは追加情報を含んでいる。経路計算出力４００は、道路区分データエンティティからのデータを含む順序付けされたエントリーのリストに加えて、他の情報４３０を含んでいる。
【００８０】本実施例では、経路計算アプリケーション１４２が生成した出力４００は、経路案内アプリケーション１４４への入力として使われる。経路案内アプリケーション１４４は、車両が経路計算アプリケーション１４２の計算した経路沿いを走行している時に詳細な操縦指示と解説を提供する機能１５１を含んでいる。これらの機能１５１は、詳細な操縦指示を作成するために、地理的データベース１６２から得られた追加情報と、経路計算アプリケーション１４２からの出力４００に含まれるリスト４１０のエントリーからのデータを使っている。これらの詳細な操縦指示を作成する方法は、同時係属出願第０８／８９３，２０１と０９／１９６，２７９に記載されており、その開示全体を参考としてここに援用する。
【００８１】経路案内アプリケーション１４４の機能１５１が作成した詳細な操縦指示は、経路案内アプリケーション１４４のデータ出力４５０として提供される。このデータ出力４５０は、マネージャーアプリケーション１５５へ戻される。データ出力４５０は、エンドユーザーへ表示用に、ユーザーインターフェース１３１へ直接送られる。替わりに、経路案内アプリケーション１４４によりマネージャーアプリケーション１５５へ戻されたデータ出力４５０は、マネージャーアプリケーション１５５内のプログラミングにより更に処理されてもよい。ユーザーインターフェース１３１を通して行われるエンドユーザーへの経路案内情報の表示は、音声指示、テキストの視覚的提示、図形の視覚的提示、又はこれら又は他のタイプを任意に組み合わせた情報提示の何れの形でもよい。
【００８２】（Ｃ）経路プレビュー機能本実施例では、図１１から１５で、経路計算アプリケーション１４２が作成した出力４００に含まれている道路区分を表す道路区分データエンティティからのデータを含むエントリーのリスト４１０は、経路案内アプリケーション１４４の一部である経路プレビュー機能１５０への入力としても用いられる。一つの実施例によれば、経路プレビュー機能１５０は随意的な機能である。経路プレビュー機能１５０はナビゲーションアプリケーションプログラム１１９の一部であり、特に、経路案内アプリケーション１４４の一部である。しかし、経路プレビュー機能１５０は、自動的に実行する、選択された時のみ実行する、全く実行しないの何れにも設定することができる。経路プレビュー機能のデフォルト作動はエンドユーザーが構成してもよく、替わりに、ナビゲーションシステム製造者が構成してもよい。例えば、ナビゲーションシステムの製造者は、例えばメモリなどのハードウェアリソースは異なるが同じソフトウェアを有するシステムを販売してもよい。製造者は、十分なリソースを有するシステム上だけで作動する高速のプレビュー機能を設定してもよい。
【００８３】経路プレビュー機能１５０は、機能１５１が経路計算アプリケーション１４２の出力４００を提供すると同時に又は前に、経路案内アプリケーション１４４の一部でもある詳細な操縦指示と解説を受け取る。経路プレビューアプリケーション１５０は、経路プレビューデータ構成のリスト４１２を作成するために、リスト４１０内のデータを用いる（経路プレビューデータ構成４１３の構成要素は図１５に関連させて以下に述べる）。経路プレビューデータ構成４１３のリスト４１２は経路プレビュー機能１５０の出力４１４として提供される。出力４１４は、計算された経路のプレビューを提供するために、マネージャーアプリケーション１５５に戻される。詳細な操縦指示を提供する経路案内アプリケーション１４４内の機能１５１とは異なり、経路プレビュー機能１５０は、出力をマネージャーアプリケーション１５５へ戻すまで、地理的データベース１６２にアクセスしない。
【００８４】図１３は、マネージャーアプリケーション１５５に戻される経路プレビューデータ構成４１３のリスト４１２を含む出力４１４を作成するために経路プレビュー機能１５０が実行する段階を示す。図１３で、経路プレビュー機能１５０はリスト４１０を経路計算機能１４２から受け取る（段階５００）。リスト４１０のエントリーは、推奨経路内の道路区分を表す道路区分データエンティティ２５８からのデータを含んでいる。経路プレビュー機能１５０は、経路計算アプリケーション１４２からのリスト４１０のエントリーを調べる。経路計算機能１４２の出力リスト４１０内のエントリーを、リスト４１０内の第一エントリーから調べ始め、次のエントリーへ進み、リスト内の最後のエントリーまで調べ続ける。
【００８５】経路出力リスト４１０内の各エントリーをエントリー内のデータに一連のテストを実行することにより調べる（段階５１２）。図１４は、この実施例の経路プレビュー機能１５０が実行するテスト５１３を示す。図１４の何れかのテストが経路出力リスト４１０のエントリーを満たす場合、経路プレビュー機能１５０はエントリー用の経路プレビューデータ構成４１３を形成する。テスト５１３のいずれのテストも経路出力リスト４１０のエントリーを満たさない場合は、経路プレビュー機能１５０は、エントリー用の経路プレビューデータ構成４１３を形成しない。
【００８６】第一テスト５１３Ａは、推奨経路内の道路の名称が変わるか否かに関係する。この決定を助けるため、経路プレビュー機能１５０は表される名称のセットを形成する。推奨経路内の第一エントリーを経路プレビュー機能１５０により調べる場合、第一エントリーに関連する道路標識リファレンス２５８（６）上の名称からの全ての名称ＩＤは、提示された名称セットに含まれる。従って、推奨経路リスト４１０内の後続の各エントリーを調べる時、新しいエントリーに関連する道路標識リファレンス２５８（６）上の名称からの全ての名称ＩＤは、既存の提示された名称セット内の名称ＩＤと比較される。提示されている名称セット内の全ての名称ＩＤが新しいエントリーに既に含まれている場合、このテストは満たされず、新しいエントリーに対し、解決の名目の変更に基づく経路プレビューデータ構成は示されない。提示されている名称セット内の全ての名称ＩＤが新しいエントリーにまだ含まれていない場合、このテストは満たされ、新しいエントリーに対し、解決の名目の変更に基づき、経路プレビューデータ構成が示される。次に、提示されている名称セット内の名称ＩＤは、新しいエントリーの名称ＩＤに取って代わられる。
【００８７】管理されているアクセス道路からの出入りに関するテスト５１３Ｂも、テスト５１３に含まれる。調査中のリスト４１０のエントリーが、前記エントリーに関連する道路区分が管理されたアクセス道路であることを示すデータ２５８（４）を含み、且つ、先のエントリーからのデータが、先のエントリーに関連する道路区分が管理されたアクセス道路ではなかったことを示していた場合、テスト５１３Ｂは満たされ、管理されたアクセス道路への進入に基づき、新しいエントリーに対して経路プレビューデータ構成が示される。同様に、調査中のリスト４１０のエントリーが、前記エントリーに関連する道路区分が管理されたアクセス道路でないことを示すデータ２５８（４）を含み、且つ、先のエントリーからのデータが、エントリーに関連する道路区分が管理されたアクセス道路であったことを示していた場合は、テスト５１３Ｂは満たされ、管理されているアクセス道路からの進出に基づき、新しいエントリーに対して経路プレビューデータ構成が示される。しかし、調査中のエントリーの道路分類データ２５８（４）が先のエントリーの道路分類データ２５８（４）と同じならば、テスト５１３Ｂは満たされず、管理されたアクセス道路への出入りに基づく新しいエントリーに対し、経路プレビューデータ構成は示されない。
【００８８】テスト５１３Ｃは、迂回路への出入りに関する別の一連のテストである。調査中のリスト４１０内のエントリーが、前記エントリーに関連する道路区分が迂回路の一部であることを示すデータ２５８（１０）を含み、且つ、先のエントリーからのデータ２５８（１０）が、先のエントリーに関連する道路区分が迂回路の一部でないことを示す場合、テスト５１３Ｃは満たされ、経路プレビューデータ構成が迂回路への進入に基づく新しいエントリーに対して示される。同様に、調査中のリスト４１０内のエントリーが、前記エントリーに関連する道路区分が迂回路の一部でないことを示すデータ２５８（１０）を含み、且つ、先のエントリーからのデータ２５８（１０）が先のエントリーに関連する道路区分が迂回路の一部であることを示す場合、テスト５１３Ｃは満たされ、経路プレビューデータ構成が迂回路の離脱に基づく新しいエントリーに対して示される。しかし、調査中のエントリー内の迂回路データ２５８（１０）が、先のエントリー内の迂回路データ２５８（１０）と同じであれば、テスト５１３Ｃは満たされず、迂回路への出入りに基づく新しいエントリーに対して、経路プレビューデータ構成は示されない。
【００８９】テスト５１３Ｄは、特別解説がある区分用の一連の別テストである。表された区分の態様が特別な指示が必要なことを示唆する場合、区分に特別解説区分のマ－クを付ける。これは、特別なレーンでの走行が必要な場合に起こる。調査中のリスト４１０内のエントリーが、道路区分が特別解説に関連することを示すデータ２５８（９）を含む場合、テスト５１３Ｄは満たされ、経路プレビューデータ構成が特別解説の存在に基づき新しいエントリーに対して示される。しかし、調査中のエントリー内のデータ２５８（９）が特別解説を示さない場合、テスト５１３Ｄは満たされず、特別解説の存在に基づく新しいエントリーに対して、経路プレビューデータ構成は示されない。
【００９０】リスト４１０からのエントリー内の区分が港の一部であるか否かを評価するため、同様のテスト５１３Ｅが含まれている。別のテスト５１３Ｅを使い、区分が特別な交通状況の一部であるか否かを評価する【００９１】別のテスト５１３Ｇを使って、推奨経路が市又は州の境界線をいつ越えるかを決定する。調査中のリスト４１０のエントリーが前記エントリーに関連する道路区分が一つの行政区域（例えば市、州など）に位置していることを示す行政区域データ２５８（１４）を含み、且つ、先のエントリーからの行政区域データ２５８（１４）が先のエントリーに関連する道路区分が別の行政区域に位置していることを示す場合、テスト５１３Ｇは満たされ、行政区域の境界線越えることに基づいて、経路プレビューデータ構成が新しいエントリーに対して示される。しかし、調査中のエントリーの行政区域データ２５８（１４）が先のエントリーの行政区域データ２５８（１４）と同じである場合は、テスト５１３Ｇは満たされず、行政区域の境界線越えに基づく新しいエントリーに対して、経路プレビューデータ構成は示されない。
【００９２】テスト５１３Ｈは、経路の開始に関する別の一連のテストである。調査中のエントリーがリスト４１０の第一エントリーである場合、テスト５１３Ｈが満たされ、経路プレビューデータ構成が経路の開始に対して示される。調査中のエントリーがリスト４１０の第一エントリーでない場合、テスト５１３Ｈは満たされない。
【００９３】テスト５１３Ｉは、経路中間地点に関する別の一連のテストである。中間地点は出発地と目的地との間の推奨経路沿いの位置であり、推奨経路は前記位置を走行するように制約されている。中間地点は、推奨経路沿いの中間停車地であってもよい。推奨経路は、一つ又はそれ以上の中間地点を含んでいてもよく、又んでいなくてもよい。リスト４１０内の調査中のエントリーが中間地点に続く場合、テスト５１３Ｉは満たされ、経路プレビューデータ構成が経路の中間地点に対して示される。調査中のエントリーがリスト４１０内の中間地点へのエントリーでない場合、テスト５１３Ｉは満たされない。
【００９４】テスト５１３Ｊは、経路の終点に関する別の一連テストである。調査中のエントリーがリスト４１０内の最終エントリーである場合、テスト５１３Ｊは満たされ、経路プレビューデータ構成が経路の終点に対して示される。調査中のエントリーがリスト４１０内の最終エントリーでない場合、テスト５１３Ｊは満たされない。
【００９５】テスト５１３Ｋは、高速道路インターチェンジへの進入に関する別のテストである。調査中の４１０内のエントリーが、前記エントリーに関連する道路区分が高速道路インターチェンジの一部であることを示すデータ２５８（１３）を含み、且つ、先のエントリーからのデータ２５８（１３）が、先のエントリーに関連する道路区分が高速道路インターチェンジの一部ではないことを示す場合、テスト５１３Ｋは満たされ、経路プレビューデータ構成が高速道路インターチェンジへの進入に基づき、新しいエントリーに対して示される。しかし、調査中のエントリー内のデータ２５８（１３）が、先のエントリー内の高速道路インターチェンジデータ２５８（１３）と同じである場合、テスト５１３Ｋは満たされず、経路プレビューデータ構成は、高速道路インターチェンジへの進入に基づく新しいエントリーに対して示されない。
【００９６】テスト５１３Ｌは、車両規制のある道路区分への進入に関する別のテストである。調査中の４１０内のエントリーが、前記エントリーに関連する道路区分が車両規制（例えば、トラックやタクシーの乗り入れ禁止）を有することを示すデータ２５８（１５）を含む場合、テスト５１３Ｌは満たされ、経路プレビューデータ構成が車両規制のある道路への進入に基づき、新しいエントリーに対して示される。しかし、車両規制データ２５８（１３）が車両規制を示さない場合、テスト５１３Ｌは満たされず、車両規制道路への進入に基づく新しいエントリーに対して、経路プレビューデータ構成は示されない。
【００９７】図１３で、あるエントリーに対して行われる何れかのテストが満足されると、経路プレビューデータ構成４１３が前記エントリーに対して形成される（段階５１６及び５２０）。形成された経路プレビューデータ構成は、既に形成された経路プレビューデータ構成を含むリストに加えられる（段階５２４）。
【００９８】経路プレビューデータ構成４１３の構成要素を図１５に示す。経路プレビューデータ構成４１３は、テスト５１３（図１４）を満たしたデータに基づく特定項目のデータを含んでいる。経路プレビューデータ構成４１３の形成は一つ又はそれ以上のテスト５１３（図１４）を満たす度合いに左右されるので、経路プレビューデータ構成４１３は図１５が示す構成要素全てを必ずしも含まない。経路プレビューデータ構成４１３は一つの構成要素だけを含んでもよいし、又は二つ以上のテスト５１３が推奨経路からのエントリーに関して満たされる場合は二つ以上の構成要素を含んでいる。
【００９９】図１５では、経路プレビューデータ構成４１３は以下の二つ以上の項目を含んでいる。こうした項目として、経路沿いの区分が管理されたアクセス道路からの出入口であるという表示５３３Ｂ、経路沿いの区分が迂回路の一部であるという表示５３３Ｃ、経路沿いの区分が特別解説と関連するという表示５３３Ｄ、経路沿いの区分が船着場の一部であるという表示５３３Ｅ、経路沿いの区分が特別な交通状況の一部であるという表示５３３Ｆ、経路沿いの区分が行政区域の境界線であるという表示５３３Ｇ、区分が経路の始まりであるという表示５３３Ｈ、区分が経路の中間地点であるという表示５３３Ｉ、区分が経路の終点であるという表示５３３Ｊ、区分が高速道路インターチェンジの一部であるという表示５３３Ｋ、様々なクラスの車両（例えばタクシー、トラックなど）が走行可能な区分であるか否かという表示５３３Ｌが挙げられる。（一つの実施例では、上記の各構成要素５３３Ｂ－５３３Ｌは単一ビットで提供される。）
【０１００】経路プレビューデータ構成４１３は追加情報を含んでいてもよい。一つの実施例では、経路プレビューデータ構成４１３は、適当であるなら、先の区分からのターン角度５３３Ｍを含んでいてもよく、又、経路プレビュー出力４１２内の次のエントリーへの距離５３３Ｎを含んでいてもよい。経路プレビューデータ構成４１３は、一つ又はそれ以上の名称ＩＤ（即ち、２５８（６））を含むリスト５３３Ａを含んでいる。推奨経路からのエントリー４１０が名称変更テスト５１３Ａを満たす場合、上記のように、推奨経路のエントリー４１０に関連する区分に関連する全名称ＩＤ２５８（６）は、名称変更テスト５１３Ａを満たす結果として形成された、対応する経路プレビューデータ構成４１３内に含まれている。
【０１０１】図１３では、全テスト５１３が経路計算出力リスト４１０内のエントリーに対して実行された後、経路プレビュー機能１５０は経路判定出力リスト４１０内の次のエントリーを調べ、全エントリーを調べ終える（段階５３０）。経路計算アプリケーション１４２からの出力リスト４１０内のエントリーに対してテストが行われている間に形成された経路プレビュー構造４１３は、リスト４１２内に形成された順序で記憶され、このリスト４１２が経路プレビュー出力４１４となる。従って、経路プレビュー出力４１４を形成するリスト４１２は、経路計算機能１４２の出力リスト４１０からの一つ又はそれ以上のエントリーを調べることにより形成された、サイズの様々な複数のデータ構造４１３を含んでいる。経路プレビューデータ構成４１３のリスト４１２は、マネージャーアプリケーション１５５に提供される（段階５３６）。
【０１０２】（Ｄ）名称アクセス機能図１１と１６で、マネージャーアプリケーション１５５が経路プレビュー機能１５０からリスト４１２を受け取った後に、経路プレビューをエンドユーザーに提供することができる。マネージャーアプリケーション１５５が経路プレビュー機能の一部として道路名称を含むように構成されている場合、マネージャーアプリケーション１５５は名称ＩＤを与えられているナビゲーション特徴名称データ２４６から道路名称の実際のテキストにアクセスできる機能５５０（この明細書では「名称アクセス」機能５５０とされている）を呼び出すことにより名称を取得する。一つの実施例では、名称アクセス機能５５０は、インターフェース階層１５４（図２に示す）の一部である。本実施例では、名称アクセス機能５５０は、多数の名称ＩＤを含むリストを受け入れることができる。次に機能５５０は、名称ＩＤによって確認される名称記録２６２に効率良くアクセスできるように、マネージャーアプリケーション１５５から受け取ったリスト内の名称ＩＤを再配列する。機能５５０の作動を図１６と関連させて示す。
【０１０３】図１６では、マネージャーアプリケーション１５５は、名称ＩＤ経路プレビュー機能１５０によりマネージャーアプリケーション１５５へ提供されたリスト４１２からリスト４１２内の名称ＩＤを取り出し、リスト５５４内の名称ＩＤを名称アクセス機能５５０へ提供する。名称アクセス機能５５０は、名称ＩＤのリスト５５４をマネージャーアプリケーション１５５から受け取る（段階５６４）。リスト５５４の名称ＩＤの配列順序は、マネージャーアプリケーション１５５が経路プレビュー機能１５０から受け取ったリスト４１２内での順序と同じである。名称アクセス機能５５０は、リスト５５４内のＩＤが参照するナビゲーション特徴名称データ記録２６２へアクセスする合計時間を最小にするように、これらの名称ＩＤを再度順序付けする。例えば名称アクセス機能５５０は、全ナビゲーション特徴名称データ記録がナビゲーション特徴データ２４６の並ぶ順序と同じ順序でアクセスされるように、リスト５５４内のＩＤを再度順序付けしてもよい。一つの実施例では、ナビゲーション特徴名称データ記録を、ナビゲーション特徴データ記録ＩＤ（図７の２６２（１））の順序で記憶する。一つの実施例では、ナビゲーション特徴ＩＤ２６２（１）は、アルファベット順でナビゲーション特徴名称データ記録２６２に割り当てられる。従って、図１６の実施例では、名称アクセス機能５５０は、リスト５５４内の名称ＩＤ（ナビゲーション特徴名称記録２６２に対するリファレンス）を数字で（例えば小さい数から大きい数へ）再度順序付けする。これは結果的に、リファレンスにより参照されるナビゲーション特徴名称データ記録がアルファベット順となるような順序に、名称ＩＤを配列することになる。これも又結果的に、ＩＤにより参照されるナビゲーション特徴データ記録がデータベース１６２内及び媒体１６４上に記憶されている順序でアクセスされるような順序に、ＩＤを配列することになる。
【０１０４】代替実施例では、ナビゲーション特徴データ記録２６２の順序は、リスト５５４内に含まれるＩＤにより示唆されていない。この場合、名称アクセス機能５５０は、リスト５５４内に含まれるＩＤのデータからナビゲーション特徴名称データ記録の媒体順序を入手するために、相互参照索引（例えば図５に示す索引２５４の一つ）を照会する。
【０１０５】図１６では、リスト５５４から入手されたＩＤが再度順序付けされた後、ナビゲーション特徴名称データ記録２６２へのアクセスが行われ、データ記録２６２が地理的データベース１６２から入手される（段階５７２）。ナビゲーション特徴名称データ記録２６２へのアクセスが実行されると、各記録２６２から少なくとも名称情報（図７の２６２（２））が入手される。ナビゲーション特徴名称２６２【０１０６】（２）が地理的データベース１６２から入手される時、リストナビゲーション特徴名称は、マネージャーアプリケーションから受け取ったリスト５５４に規定されている順序に従ってリストへ入れられる（段階５７６）。名称アクセス機能５５０が地理的データベース１６２から全ナビゲーション特徴名称を入手した後に、ナビゲーション特徴名称は、名称アクセス機能５５０の出力を形成するリスト５８２内に提供される。リスト５８２は、名称アクセス機能５５０によりマネージャーアプリケーション１５５へ戻される。マネージャーアプリケーション１５５へ戻されたナビゲーション特徴名称のリスト５８２は、推奨経路のプレビューを提供するために、マネージャーアプリケーション１５５内のプログラミングにより、更に処理される。推奨経路のプレビューは、ユーザーインターフェース１３１を通し、音声指示、視覚的なテキスト指示、視覚的な図表指示、又は情報を提示するこれらのタイプの何れかの組み合わせの形態で、エンドユーザーに提示される。名称アクセス機能５５０からの出力中のナビゲーション特徴名称のリスト５８２を使えば、経路プレビューの際に推奨経路の道路名称をエンドユーザーに素早く提供できる。一つの実施例では、経路プレビューは、推奨経路の道路名称に、見出し、ターン角度、推奨経路が管理されたアクセス道路、特別な交通解説、迂回路、船着場等を含むか否かを示す表示のような追加情報を付けてエンドユーザーに提供する。経路計算機能１４２が推奨経路を計算した直後か又は暫く後、経路プレビューがエンドユーザーに提供される。計算された経路の走行を運転者が開始する前に、経路プレビューを提供するのが望ましい。
【０１０７】経路プレビューは、推奨経路の走行方法に関する詳しい操縦指示を含んではいない。上記のように、詳しい操縦指示は、経路案内アプリケーション１４４内の他の機能１５１により提供される。しかし、経路プレビュー機能１５０により提供される、道路、ターン角度、管理されたアクセス道路に関する表示などを要約したリストは、有益な情報をエンドユーザーに提供する。推奨経路内の一定の道路名称だけを提供し詳細な操縦指示は提供しないことは、経路プレビュー機能の利点である。一定の道路名称だけを提供することにより、エンドユーザーは、推奨経路について、道を走る際に必要な特定の操縦に関して情報過多に陥ることなく、推奨経路の全体を十分に理解できる程度の詳細レベルの情報を知ることになる。
【０１０８】計算された経路の走行を始める前に、道路名称のリストを経路プレビューでエンドユーザーに提供することにより、エンドユーザーは計算経路を拒否し、恐らくは代替経路の計算を要求する機会も与えられる。例えば、エンドユーザーは、推奨経路の一部では交通の流れが遅いことを知っている。従って、推奨経路内に含まれた道路のリストという形で推奨経路のプレビューをエンドユーザーに提供することにより、エンドユーザーは推奨経路を受け入れるかどうかできるだけ早く決めることができる。
【０１０９】（III）代替実施例（Ａ）第一代替実施例上記の実施例で、道路標識名称で照会される道路を表している経路指定データ２３６内の各道路区分データ記録２５８は、名称のテキスト記号列を含むナビゲーション特徴データ記録２６２に対して少なくとも一つのリファレンスＩＤ（図６の２５８（６））を含んでいる。これにより、推奨経路内の道路名称に対するリファレンスのリストを、推奨経路が計算される通りに形成することができる。第一代替実施例では、道路標識名称で照会される道路を表す経路指定データ２３６内の各道路区分データ記録は、名称の実際のテキストを、名称へのリファレンスとしてではなく、道路区分データ記録内の属性として含んでいる。図１７は、この第一代替実施例による道路区分データエンティティの構成要素を示す。
【０１１０】図１７は、幾つかの道路区分データエンティティ６５８を示す。道路区分データエンティティ６５８は、図６が示す道路区分データエンティティに類似している。図１７の道路区分データエンティティ６５８は、区分ＩＤ６５８（１）、制限方向の属性６５８（２）、速度制限又はカテゴリー属性６５８（３）、分類属性６５８（４）、等級属性６５８（５）、エンドポイント６５８（７）等を含んでいる。図１７に示す道路区分データエンティティ６５８の構成要素は、図６との関連で記載した対応する構成要素に類似しているか又は同一である。
【０１１１】図１７の道路区分データエンティティ６５８は道路標識属性６５８（６）に関する一つ又はそれ以上の名称を含んでいる。道路標識属性６５８（６）に関する名称は、表された道路区分沿いに置かれた一つ又はそれ以上の道路標識で表された道路区分を照会する時の名称の実際のテキスト記号列を含んでいる。例えば、「Ｈｉｇｇｉｎｓ」と名付けられた道路の一部を表す道路区分データ記録６５８は、テキスト記号列「ＨＩＧＧＩＮＳ」を含む道路標識属性６５８（６）に関する名称を構成要素として含んでいる。図１７の実施例の場合、道路区分データ記録６５８は、ナビゲーション特徴名称データ２４６に対するリファレンスを含んでいない。
【０１１２】図１７に示した道路区分データ記録６５８は、図６に示した道路区分データ記録６５８の実施例に同じように使われる。図１７に示した道路区分データ記録６５８は、経路計算に必要なデータ構成要素を含んでいる。図１７に示した道路区分データ記録６５８は、経路を計算する経路計算アプリケーション１４２（図２及び１１に示される）により使用することができる。経路計算アプリケーション１４２は、推奨経路の候補として含めるために道路区分を評価する。道路区分が推奨経路に含まれることが確認されると、推奨経路内に含まれることが確認された、表されている各道路区分の道路標識データ６５８（６）に関する名称は、表されている道路区分の名称と共に、仮のリストに記憶される。推奨経路が決定された後、この仮のリストは、推奨経路を形成する全道路区分の名称を含むことになる。この道路名称リストは、本ナビゲーションシステムのエンドユーザーに経路プレビュー特徴を提供するために使うことができる。この実施例によれば、リストが決定された後には、独立した名称アクセス機能５５０（図１６に記載されている）は、経路プレビューリスト内に含まれている道路区分の名称を入手するために、ナビゲーション特徴データ２４６に単独でアクセスする必要がない。替わりに、プレビューリスト内の全道路区分の名称に関する実際のテキストを経路プレビュー機能の出力に含めることができる。
【０１１３】道路標識上の名称により照会されている道路区分を表す各道路区分データ記録６５８が名称のテキストを属性６５８（６）として含んでいても、道路名称は、ナビゲーション特徴名称データ２４６（図５）内に含まれるナビゲーション特徴名称データ記録２６２（図７）にも含まれている。道路名称をナビゲーション特徴名称データ記録２６２内に含むことにより、名称はプログラム１１８内の他の機能によって照会することができる。従ってこの代替実施例によれば、道路名称は地理的データベース１６２内の少なくとも二つのロケーション内に含まれている。このデータの重複は地理的データベース１６２の全体のサイズを大きすることになるが、一定の機能（経路プレビュー機能のような）を素早く実行できる。
【０１１４】（Ｂ）第二代替実施例第二代替実施例を、図１８との関連で述べる。図１８は、経路指定データ２３６のパーセル７２０内に含まれている幾つかのデータを示す。図１８に示すパーセル７２０は、図９と関連して先に述べたパーセル３２０に類似している。図１８に示した経路指定データ２３６のパーセル７２０は、経路指定データ２３６に関する複数のパーセルの一つであり、各パーセルはパーセル７２０に類似か又は同一の構造を有している。第一実施例に関連して述べた経路指定データ２３６のパーセル３２０と同様に、図１８に示す経路指定データの２３６のパーセル７２０は、複数の道路区分データ記録７５８を含んでいる。各道路区分データ記録７５８は、上記の道路区分記録２５８に似ている。パーセル７２０の各道路区分データ記録７５８は、道路区分を表し、経路を計算する場合に経路計算アプリケーション１４２で使用できるナビゲーション関連属性（図１８には示さず）を含んでいる。
【０１１５】この実施例によれば、道路標識上の名称で知られている道路区分を表す各道路区分データ記録７５８は、一つ又はそれ以上のリファレンス７５８（６）を含んでいる。各リファレンス７５８（６）は、表された道路区分を照会する際の名称を示すデータを、表された道路区分沿いの標識により指している。リファレンス７５８（６）は、経路指定データ２３６内に配置されたテキストの記号列を指している。更に特定するならば、リファレンス７５８（６）はリファレンス７５８【０１１６】（６）を含む道路区分データ記録７５８として、経路指定データ２３６の同じパーセル７２０内に配置されているデータ７６６の一部分に存在するエントリーを指している。上記のように、パーセルは一般に多くの道路区分データ記録を含んでいる。パーセル内では、複数の道路区分データ記録７５８は、同じ名称の道路に関する別の部分を表している。図１８の実施例によれば、同じ名称の道路に関する別の部分を表すパーセル内の各道路区分データ記録７５８は、パーセル７２０内に位置するデータ７６６の部分内に存在する同じエントリーを照会する。
【０１１７】図１８の実施例は、経路プレビュー機能を提供するために、ナビゲーションシステムで使うことができる。図１８の実施例では、経路計算機能１４２は経路指定データ２３６を使って経路を計算する。推奨経路内の各道路区分について、経路計算機能１４２は、道路区分を表す道路区分データ記録によって照会される道路標識テキスト７６６に関する名称を記憶する。道路標識テキストに関する名称は、経路計算機能の出力を形成するリスト内に記憶することができる。道路標識データに関する名称は、経路計算の間にアクセスされている経路指定データ記録を含むデータの同じパーセル内で利用できる（すなわち部分７６６で）ので、経路計算プロセスの間は、道路区分の実際の名称をリスト内に含むことができる。推奨経路を計算し終わると、リストは推奨経路内に含まれる全道路区分の名称を含むことになる。図１８の場合、推奨経路内の実際の名称を得るためにナビゲーション特徴名称データ２４６内のデータ記録に個別にアクセスする必要はない。
【０１１８】この実施例の利点は、経路を経路計算機能１４２によって計算するので、各道路区分の名称を素早く得られることである。経路計算機能は、表される道路区分のナビゲーション関連属性を得るために経路指定データのパーセル７２０にアクセスするので、経路指定データのパーセル内に道路名称を含むことにより、推奨経路内の道路の名称リストを素早く作成できる。上記の実施例と同様に、各道路の名称も、ナビゲーション可能特徴名称データ２４６（図５）に含まれたナビゲーション可能特徴名称データ記録２６２（図７）によって表される。従って、この代替実施例によれば、幾つかの道路の名称は地理的データベース１６２内の少なくとも二つのロケーション内に含まれている。このデータ重複により地理的データベース１６２の全体サイズは大きくなるが、一定の機能（経路プレビュー機能のような）を素早く実行できる。
【０１１９】（Ｃ）他の代替上記の幾つかの実施例では、経路プレビュー機能により提供される名称は、道路沿いの標識により道路を照会する際の道路名称である。これは、最も良く知られている道路名称を経路プレビュー機能に含むことを意図している。経路プレビュー機能により提供される道路名称は、道路標識上の名称である必要はなく、道路を知ることのできる名前ならばよく、最も行き渡っている名称が好ましい。上記の実施例では、ナビゲーションアプリケーションを車載ナビゲーションシステムのようなナビゲーションシステムとの関連で述べた。本実施例は、パーソナルコンピューター、パーソナルデジタル用具、ネットワーク環境、インターネット、電話を基本としたシステム等を含む様々なプラットフォーム及び／又は環境で実行できることが理解される。
【０１２０】上記の詳細な説明は限定的でなく例示的にみなされるよう意図されており、全同等物を含む上記の請求の範囲が本発明の範囲を定めるよう意図されていることを理解されたい。

【出願人】	【識別番号】５９７０１１５４４【氏名又は名称】ナヴィゲイションテクノロジーズコーポレイション
【出願日】	平成１２年８月２日（２０００．８．２）
【代理人】	【識別番号】１０００５９９５９【弁理士】【氏名又は名称】中村稔（外９名）
【公開番号】	特開２００１－９１２８７（Ｐ２００１－９１２８７Ａ）
【公開日】	平成１３年４月６日（２００１．４．６）
【出願番号】	特願２０００－２３４４９１（Ｐ２０００－２３４４９１）