(57)【特許請求の範囲】
【請求項１】
地理上の領域における出発地から目的地へ移動する最適ルートを判定するために動作するナビゲーションシステムであって、
地理上の領域における道路を表わすデータを含む地理的データベースと、
選択された間隔の緯度に対する卯酉線曲率半径値、選択された間隔の緯度に対する子午線曲率半径値、及び選択された間隔の緯度に対する余弦関数値を含むルックアップテーブルと、
プロセッサと、
データ記憶装置と、
前記データ記憶装置に記憶された、前記プロセッサによって実行可能な経路計算アプリケーションであって、前記地理的データベース中のデータを使用して前記出発地から前記目的地への少なくとも１つの経路を特定し、前記ルックアップテーブル中に記憶されたデータを使用して前記少なくとも１つの経路の距離を決定する経路計算アプリケーションであって、前記経路計算アプリケーションは、線形補間を使用して前記経路上の第１の点から前記経路上の第２の点への距離を計算し、前記第１の点及び前記第２の点は第１緯度及び第２緯度の間にあるような経路計算アプリケーションと、を含み、
前記経路計算アプリケーションは、前記ルックアップテーブル中に記憶された前記第１緯度についての第１卯酉線曲率半径値と前記ルックアップテーブル中に記憶された前記第２の緯度についての第２卯酉線曲率半径値とに基づいて、前記第１の点と前記第２の点との間にある点についての補間された卯酉線曲率半径の値を前記プロセッサに計算させ、
前記経路計算アプリケーションは、前記ルックアップテーブル中に記憶された前記第１緯度についての第１子午線曲率半径値と前記ルックアップテーブル中に記憶された前記第２緯度についての第２子午線曲率半径値とに基づいて、前記第１の点と前記第２の点との間にある前記点についての補間された子午線曲率半径の値を前記プロセッサに計算させ、
前記経路計算アプリケーションは、前記ルックアップテーブル中に記憶された前記第１緯度の余弦を表わす値と前記ルックアップテーブル中に記憶された前記第２緯度の余弦を表わす値とに基づいて、前記第１の点と前記第２の点との間にある前記点についての補間された余弦の値を前記プロセッサに計算させ、
前記経路計算アプリケーションは、前記補間された卯酉線曲率半径値、前記補間された子午線曲率半径値、及び前記補間された余弦値に基づいて、前記第１の点と前記第２の点の間の距離を計算することを前記プロセッサに実行させることを特徴とするナビゲーションシステム。
【請求項２】
請求項１に記載のナビゲーションシステムにおいて、前記経路計算アプリケーションは、ｄΦ＝φ1−Φ1、φ1を前記第１の点の緯度、Φ1を前記第１緯度、ＮΦ1を前記ルックアップテーブル中に記憶された前記第１緯度についての第１卯酉線曲率半径値、ＮΦ2を前記ルックアップテーブル中に記憶された前記第２緯度についての第２卯酉線曲率半径値として、
ＮΦ＝ＮΦ1＋（ＮΦ2−ＮΦ1）ｄΦ
の式を使用して前記補間された卯酉線曲率半径を前記プロセッサに計算させることを特徴とするナビゲーションシステム。
【請求項３】
請求項１に記載のナビゲーションシステムにおいて、前記経路計算アプリケーションは、ｄΦ＝φ1−Φ1、φ1を前記第１の点の緯度、Φ1を前記第１緯度、ＭΦ1を前記ルックアップテーブル中に記憶された前記第１緯度についての第１子午線曲率半径値、ＭΦ2を前記ルックアップテーブル中に記憶された前記第２緯度についての第２子午線曲率半径値として、
ＭΦ＝ＭΦ1＋（ＭΦ2−ＭΦ1）ｄΦ
の式を使用して前記補間された子午線曲率半径を前記プロセッサに計算させることを特徴とするナビゲーションシステム。
【請求項４】
請求項１に記載のナビゲーションシステムにおいて、前記経路計算アプリケーションは、ｄΦ＝φ1−Φ1、φ1を前記第１の点の緯度、Φ1を前記第１緯度、ＣｏｓΦ1を前記ルックアップテーブル中に記憶された前記第１緯度の余弦を表わす値、ＣｏｓΦ2を前記ルックアップテーブル中に記憶された前記第２緯度の余弦を表わす値として、
ＣｏｓΦ＝ＣｏｓΦ1＋（ＣｏｓΦ2−ＣｏｓΦ1）ｄΦ
の式を使用して前記補間された余弦値を前記プロセッサに計算させることを特徴とするナビゲーションシステム。
【請求項５】
請求項１に記載のナビゲーションシステムにおいて、前記経路計算アプリケーションは、ＤE＝ＮΦ ＣｏｓΦ Δλ、ＤN＝ＭΦ Δφ、ＮΦを前記補間された卯酉線曲率半径値、ＭΦを前記補間された子午線曲率半径値、ＣｏｓΦを前記補間された余弦値、Δλを前記第２の点の経度と前記第１の点の経度の差、Δφを前記第２の点の緯度と前記第１の点の緯度の差として、
0004684333.tif 000027
の式を使用して前記第１の点と前記第２の点の間の距離を前記プロセッサに計算させることを特徴とするナビゲーションシステム。
【請求項６】
請求項１に記載のナビゲーションシステムにおいて、前記第１の点と前記第２の点の間の前記点は、前記第１の点と前記第２の点の中間点であるナビゲーションシステム。
【請求項７】
請求項１に記載のナビゲーションシステムにおいて、前記第１緯度と前記第２緯度は、ほぼ１度の整数倍数だけ分離されていることを特徴とするナビゲーションシステム。
【請求項８】
請求項１に記載のナビゲーションシステムにおいて、前記経路計算アプリケーションは、前記第１の点から前記第２の点への前記距離を、前記少なくとも１つの経路上の複数の点の間の計算された他の距離に加えることによって、前記少なくとも１つの経路を前記プロセッサが得るようにすることを特徴とするナビゲーションシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、２つの点間の距離を計算する方法に関する。この方法は、正確で効率的な距離計算が求められるナビゲーション・システムの分野に、特に有用である。
【背景技術】
【０００２】
ナビゲーション・システムは、道路上を移動する（乗用車、トラック、バス等の）車両に利用可能である。これら車載式ナビゲーション・システムは、有用な様々なナビゲーション機能を（ナビゲーション・システムが装備された車両内の運転者及び／又は乗客等の）末端利用者に提供する。例えば、ナビゲーション・システムのいくつかは最適ルートを判定し、地理上の領域における位置間の道路に従って移動させることができる。末端利用者からの入力、そして随意的には、自分の物理的位置を判定できる（ＧＰＳシステムのような）装置からの入力を用いて、ナビゲーション・システムのプログラムが２つの位置間の様々なルートを調べ、地理上の領域における出発地から目的地に移動する最適ルートを判定することができる。次いで、ナビゲーション・システムは、最適ルートについての情報を、出発地から目的地に移動するために末端利用者がとることを求められる運転計画を示す指令の形態で、該末端利用者に提示する。指示には、視覚及び／又は音声指示の形式を採用することができ、末端利用者がそのルートを移動するのに伴って、道筋に沿って提示し続けることができる。
【０００３】
ナビゲーション・システムのいくつかは、ナビゲーション・システム装置の一部をなすコンピュータ・ディスプレイ上に、目的地までのルート、該ルート上の様々な位置に沿ってとるべき行動の形式、ある種の施設及び／又は特徴の位置等を強調表示する詳細地図を示すことができる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
この種の機能を提供するために、ナビゲーション・システムは地理的データを用いる。地理的データは、地理的な領域の物理的地形を表わすデータを含む１つ又はそれ以上のデータベース形式にすることができる。地理的データベースは、地理的な領域における道路及び交差点を表わすデータ、更には交差点における方向制限、道路上の速度制限、様々な道路の街路名、道路沿いの住所区域等のような道路及び交差点についての情報を含む。
【０００５】
ナビゲーション・システムは、多くの有用で重要な機能を提供するものであるが、これらの機能については、引き続き改良の余地がある。改良の余地がある領域の１つは、２つの点間の距離を正確に一貫性をもって判定する簡単な方法を用いることである。ナビゲーションのデータベースが基礎にする地球は、形状が球形ではなく、むしろ楕円体の幾何学的形状を有しているため、２つの点間の距離計算において困難が生じる。
【０００６】
従来の距離計算技術には、２つの点間の正確な距離計算を提供することができる測地方程式の利用を含むものがある。例えば、道路及び交差点を表わすデータは、ＷＧＳ８４楕円体座標システムにおいて角単位で表現することができる。２つの点（φ1、λ1）および（φ2、λ2）の緯度と経度とが与えられれば、下記の１−１２の方程式を用いて、２００キロメートルにもなる直線長さについて、数ミリメートルのオーダーの距離精度を得ることができる。これは、次の刊行物、すなわち、Ｇｅｏｍｅｔｒｉｃ  Ｇｅｏｄｅｓｙ  Ｉ，Ｒｉｃｈａｒｄ  Ｈ．Ｒａｐｐ，  Ｔｈｅ  Ｏｈｉｏ  Ｓｔａｔｅ  Ｕｎｉｖｅｒｓｉｔｙ，Ａｐｒｉｌ  １９９１，  ｐｐ１１４−１１５に見出すことができる。方程式１２は、方程式１−１１に示されるように異なる量を評価した後に、２つの点間の所望の距離を与える。符号「ａ」は楕円体の半長径（半長軸、semi-major axis）を表わし、符合「ｅ」は楕円体の離心率（eccentricity）を表わし、残りの符号は自明のものである。
【数１】
0004684333.tif 000002
【数２】
0004684333.tif 000003
【数３】
0004684333.tif 000004
【数４】
0004684333.tif 000005
【数５】
0004684333.tif 000006
【数６】
0004684333.tif 000007
【０００７】
【数７】
0004684333.tif 000008
【数８】
0004684333.tif 000009
【数９】
0004684333.tif 000010
【数１０】
0004684333.tif 000011
【数１１】
0004684333.tif 000012
【数１２】
0004684333.tif 000013
【０００８】
上記のように、方程式１−１２は、多数の非線形数学的関数を評価して、点間距離を計算する。ナビゲーション・システムの場合のような、点の緯度及び経度が常に変化するある種の用途においては、これらの非線形数学的関数による評価を実行することはできない。また、通常は、こうした用途においては、数ミリメートルの正確さの範囲内で点間の距離計算を行うことは必要でない。むしろ、唯一の要求事項は、ナビゲーション・システムの用途にとって十分に正確な距離であり、その距離の計算が効率的であるべきことである。
【０００９】
効率については、可能な範囲まで非線形数学的関数の使用を少なくする必要がある。従来のナビゲーション・システムの用途において判定される距離は、非常に長くはないのが普通であるので、簡単な式及びピタゴラスの定理が利用されてきており、かつ、利用可能であり、それでも尚、要求されるレベルの効率及び精度が維持される。こうした簡単な式は、以下の方程式１３−１５で与えられ、こうした方程式を用いることにはある種の欠点があるが、その点は後で説明する。
【００１０】
【数１３】
0004684333.tif 000014
【数１４】
0004684333.tif 000015
【数１５】
0004684333.tif 000016
ここで、
【数１６】
0004684333.tif 000017
【数１７】
0004684333.tif 000018
【数１８】
0004684333.tif 000019
【００１１】
ＤE及びＤNは、２つの点（φ1、λ1）、（φ2、λ2）間の距離の東方成分及び北方成分であり、Δφは上記方程式６で得られる緯度の差であり、Δλは上記方程式７で得られる経度の差である。卯酉線の曲率半径（Ｎ）及び子午線の曲率半径（Ｍ）は、方程式１７及び１８から求められ、その結果として、地球が上記式における緯度及び経度の値から楕円体の幾何学的形状を有すると推定される。これは、与えられた点の組について、緯度及び経度の値が楕円体の幾何学的形状を有する地球に基づいていることから必要となるものである。従って、卯酉線及び子午線の曲率半径（Ｎ，Ｍ）の評価が、上記式における与えられた点について実施される。ここでも、符号「ａ」は楕円体の半長径（半長軸）を表わし、一方符合「ｅ」は楕円体の離心率を表わす。卯酉線曲率半径（Ｎ）及び子午線曲率半径（Ｍ）は緯度の関数であり、それらの０°から９０°までの変化を図１に示す。
その結果として、方程式１３及び１４を、球面幾何学を有する地球であるとするモデルに置換することはできない。更に、方程式１３に示されるように、２つの点の間の距離の東方成分を求めるのに余弦値が必要であるので、余弦についての評価も行う必要がある。これらの値は、緯度座標が変化するときは何時でも必要とされ、これらの量を計算するのに浮動点演算が必然であり、それは非常に時間を費やす演算であり、ナビゲーション・システムにおいて膨大な回数を実施しなければならない。
【課題を解決するための手段】
【００１２】
従って、ナビゲーション・システムにおいて、上記不利益を克服するのに用いられる２つの点間の距離を計算する方法を提供することが望まれる。
【００１３】
ナビゲーション・システムにおいて使用するための、上記欠点を克服した２つの点間の距離を計算する改良された方法を提供するために、本発明の１つの実施の形態は、線形補間法を用いて第１点と第２つの点との距離を計算する方法を提供する。第１点と第２つの点は、第１及び第２の緯度の間にある。第１点と第２つの点との間の点についての補間された卯酉線曲率半径の値が、第１の緯度についての所定の第１卯酉線曲率半径値と第２の緯度についての所定の第２卯酉線曲率半径値とに基づいて計算される。第１点と第２つの点との間の点についての補間された子午線曲率半径の値が、第１の緯度についての所定の第１子午線曲率半径値と第２の緯度についての所定の第２子午線曲率半径値とに基づいて計算される。最後に、第１点と第２つの点との間の点についての補間された余弦の値が、第１緯度の余弦を表わす所定値と第２緯度の余弦を表わす所定値とに基づいて計算される。補間された卯酉線補間曲率半径値、子午線曲率半径値及び余弦値を、線形方程式において使用して、２つの点間の距離を求めることができる。
【００１４】
本発明の別の実施の形態は、コンピュータの読み取り可能な媒体を提供するものであり、その媒体は、線形補間法を用いて第１点と第２の点との間の距離を計算するプログラムを含む。第１点及び第２つの点は、第１及び第２の緯度の間にある。プログラムは、コンピュータ読み取り可能なプログラム・コードを含み、それによって、第１点と第２つの点との間の点についての補間された卯酉線曲率半径の値が、第１の緯度についての第１卯酉線曲率半径値と第２の緯度についての第２卯酉線曲率半径値とに基づいて、計算される。プログラムは又、コンピュータ読み取り可能なプログラム・コードを含み、それによって、第１点と第２つの点との間の点についての補間された子午線曲率半径の値が、第１の緯度についての第１子午線曲率半径値と第２の緯度についての第２子午線曲率半径値とに基づいて、計算される。更に、プログラムはコンピュータ読み取り可能なプログラム・コードを含み、それによって、第１点と第２つの点との間の点についての補間された余弦の値が、第１緯度の余弦を表わす値と第２緯度の余弦を表わす値とに基づいて、計算される。最後に、プログラムは、コンピュータの読み取り可能なプログラム・コードを含み、それによって、第１及び第２つの点間の距離が、補間された卯酉線曲率半径値、子午線曲率半径値及び余弦値に基づいて、計算される。
【発明の効果】
【００１５】
本発明の方法は、非線形関数の評価を省き、それによって効率を向上させ、精度をも維持する。
【００１６】
本発明は前記及びその他の機能を提供するものであり、本発明の利点は、現在のところ好ましい実施の形態についての以下の詳細な説明を、添付図面を参照して読むことにより、更に明らかになるであろう。詳細な説明及び図面は、本発明の単なる例示的なものであり、本発明の特許請求の範囲及びそれと同等のものにより定義される範囲を制限するものではない。
【発明を実施するための形態】
【００１７】
上述のように、上記方程式１３−１８を評価することによって２つの点間の距離を計算することの主要な欠点の１つは、卯酉線曲率半径（Ｎ）、子午線曲率半径（Ｍ）、及び余弦関数が非線形パラメータであり、緯度座標が変化するときは何時でも、時間のかかる浮動点演算を介して計算されなければならないということにある。その結果として、方程式１３−１８の評価は、ナビゲーション・システムにおいて使用するための効率的な距離計算手段を提供するものではなくなる。
【００１８】
ここで図２を参照して、各距離計算について、及びあらゆる距離計算について、非線形パラメータ計算を必要とすることなく、２つの点（φ1、λ1）、（φ2、λ2）間の距離を求める方法を提供する本発明の実施の態様を示す。これは、ここで２つの既知の特定パラメータ値の間にあるパラメータを推定するものとして定義される区分毎の線形補間によって達成される。好ましい実施の態様において、卯酉線曲率半径（Ｎ）、子午線曲率半径（Ｍ）、及び余弦関数が、線形補間法によって計算される。これを達成するために、卯酉線曲率半径（Ｎ）、子午線曲率半径（Ｍ）、及び余弦関数は、異なる緯度間隔（例えば各々の０°から９０°までの緯度全て）について計算される。これらの数字は、テーブル化され、次に、適当なフォーマット、例えばルックアップ・テーブルの形式で格納される。
その後、これらの格納された数字が、以下に記載される線形方程式において用いられ、求められる点について、卯酉線曲率半径（Ｎ）、子午線曲率半径（Ｍ）、及び余弦関数の補間された値を計算することができる。
【００１９】
図２には、緯度及び経度（φ1、λ1）が関連付けられた第１点と緯度及び経度（φ2、λ2）が関連付けられた第２点との相対位置が図示される。示される実施の態様において、例えば、２つの点（φ1、λ1）、（φ2、λ2）は、第１緯度Φ1の上で第２緯度Φ2の下にある。詳細には、Φ1はφ1の南方の緯度を表わす。同様に、Φ2はφ2の北方の緯度を表わす。２つの点（φ1、λ1）、（φ2、λ2）は又、第１経度Λ1と第２経度Λ2との間に位置付けられる。詳細には、Λ1はλ1の西方の経度を表わす。同様に、Λ2はλ2の東方の経度を表わす。ＤEは、点（φ1、λ1）、（φ2、λ2）間の距離Ｄの東方成分であり、ＤNは、点（φ1、λ1）、（φ2、λ2）間の距離Ｄの北方成分である。本発明の好ましい実施の態様は、次の方程式を用いて図２に示される距離ＤE及びＤNを計算する。
【００２０】
【数１９】
0004684333.tif 000020
【数２０】
0004684333.tif 000021
点１２、１４間の距離Ｄは、次に、以下のピタゴラスの定理を用いて計算することができる。
【数２１】
0004684333.tif 000022
【００２１】
以下に更に十分に説明するように、方程式１９−２１が卯酉線曲率半径（Ｎ）、子午線曲率半径（Ｍ）、及び余弦関数についての補間された値を利用することを除くと、方程式１９−２１は、上記の方程式１３−１５と同じである。補間された値は、方程式１９−２１において、ＮΦ、ＭΦ、ＣｏｓΦとして示される。Δλの記号は、第２の点（φ2、λ2）の経度λ2と第１の点（φ1、λ1）の経度λ1との差を表わす。同様に、Δφは、第２の点（φ2、λ2）の緯度φ2と第１の点（φ1、λ1）の緯度φ1との差を表わす。
【００２２】
上記のように、卯酉線曲率半径（Ｎ）、子午線曲率半径（Ｍ）、及び余弦関数についての値が、各々の０°から９０°までの緯度全てについて計算され、適当なフォーマット、例えばルックアップ・テーブルの形式で格納される。好ましい実施形態においては、（Ｎ）、（Ｍ）の値、及び余弦関数が各々の緯度の全てにおいて評価されるが、これらの値は、緯度のどのような適当な間隔ででも計算できるものである。これらのテーブル化された値、即ち以下においてＮφ2、Ｎφ1、Ｍφ2、Ｍφ1、Ｃｏｓφ２及びＣｏｓΦ１として表わされる値が、次の簡単な式において用いられ、それによって、各時点において、精度及び効率性をもって非線形関数測定の評価を行うことを回避しながら、求められる点（Φ、Λ）についての各値を補間することができる。
【００２３】
【数２２】
0004684333.tif 000023
【数２３】
0004684333.tif 000024
【数２４】
0004684333.tif 000025
【数２５】
0004684333.tif 000026
【００２４】
ｄΦは、図２に示すように、第１の点（φ1、λ1）の緯度φ1とφ1の南方の緯度Φ1との差に等しい。これら補間された値ＮΦ，ＭΦ、及びＣｏｓΦは、次に上記簡単な式１９−２１にそれらを代入することによって、求める距離を計算するのに用いることができる。上述したように、方程式１９−２１がＮ、Ｍ、及び余弦関数の補間された値を用いることを除くと、方程式１９−２１は上記方程式１３−１５と同じである。方程式１９−２５において用いられる様々な記号を、図２に示す。
【００２５】
当業者であれば、上記の線形補間法を用いて２つの点間の距離を計算する方法は、非常に長いルートの距離計算に用いることが可能であることを認識するであろう。具体的には、ナビゲーション・データベースにおける場合がそうであるように、長いルートは、短いセグメントの組であることが好ましい。各々のセグメントの長さは、上記の線形補間を用いて求めることができる。次に、そのルートの総全長は、各々のセグメントの長さの総和によって、簡単に得ることができる。これによって精度と効率性の両方を達成する。
【００２６】
方程式１−１２について上述した測地方程式と対比して、方程式１９−２５に記述される線形補間法の精度が、図３に示される。テストとして、２組のサンプル点が評価された。各組の点は線を表し、この線は多数のセグメントを有する。
上記の測地式（方程式１−１２）及び線形補間式（方程式１９−２５）を用いて、個々の線のそれぞれについての、距離が計算された。個々の区分に関し計算された２つの方法の間の距離の差が導き出された。これらの結果が図３の上下のパネルに示される。結果が示すのは、上記の測地式（方程式１−１２）及び線形補間式（方程式１９−２５）を用いた距離の間の差が極めて僅かであるということである。それらの距離の全てについての総和も両方の方法において得られ、それらは又、図３に示されている。２つの方法の間の差は、両方法において、合計の線長が３００キロメートルを超える場合において、距離にして数メートル以内である。本線形補間法を用いて極めて正確な距離を得ることが可能であるということを、この結果が示している。
【００２７】
以上に示したように、本実施の態様によるＮφ2、Ｎφ1、Ｍφ2、Ｍφ1、Ｃｏｓφ２及びＣｏｓΦ１についてのテーブル化された値と求められる点（Φ、Λ）についてのＮΦ，ＭΦ、及びＣｏｓΦの値を取得する簡単な線形補間法とを用いることにより、非線形関数の計算を省くことができる（図２参照）。ナビゲーション・システムの使用について求められる距離計算の精度は、この方法を用いて維持することが可能である。求められる点（Φ、Λ）についてのＮΦ、ＭΦ、及びＣｏｓΦの値は、０°から９０°までの全ての緯度に基づきテーブル化されたＮ、Ｍ、及び余弦関数による上記線形補間法を用いて、十分な精度をもって得ることができる。十分に正確であり、容量において相対的に管理可能な余弦値表を維持するため、余弦値は、好ましくは、例えば小数点以下４、５又は６桁のような適当な桁数に端数を切り捨ててよい。
【００２８】
上記の線形補間法においては、好ましくはＷＧＳ８４楕円体座標パラメータを用いて、Ｍ及びＮについての曲率半径の値を計算してもよい。余弦値が小数点以下６桁で端数を切り捨てられる場合には又、テーブル化された余弦値に１００万を乗算することによって、整数演算を使用できる。
【００２９】
ここで開示された本発明の実施の態様は、現時点において好ましいものと考えられるものであるが、本発明の特許請求の範囲及び趣旨を逸脱することなく様々な変更及び修正が可能である。本発明の範囲は特許請求の範囲に示されており、均等の意味及び範囲内となる変更の全ては、本発明の範囲に包含されることを意図するものである。
【図面の簡単な説明】
【００３０】
【図１】卯酉線曲率半径（Ｎ）及び子午線曲率半径（Ｍ）間の変化を表わすグラフである。
【図２】本発明による線形補間法を用いて２つの点間の距離を計算するのに用いられる様々な量を表わす線図である。
【図３】方程式１−１２に記述した従来の測地式を用いる距離計算と本発明（上記方程式１９−２５）による線形補間法を用いる距離計算との精度における差を表わす線図である。
【図１】
0004684333.tif 000028
【図２】
0004684333.tif 000029
【図３】
0004684333.tif 000030