ナビゲーション地図生成システム
【課題】好適なナビゲーション地図生成システムを提供すること。
【解決手段】電子地図の地図的特徴をシミュレートするシステムが提供される。このシステムは、電子地図の地図的特徴を表すために、クロソイドのような１つ以上の幾何学形状を使用する。このシステムは、直線のシステムよりも正確で写実的に地図的特徴を記述することができる。このシステムは、データを直線システムからクロソイドシステムに変換するためのデータモデル及び方法を含むことができる。また、このシステムは、電子地図の地図的特徴を記述するために必要とされる記憶容量を低減することができる。電子地図は、広域ネットワーク、ローカルエリアネットワーク、無線又は有線ネットワーク、イントラネット又はインターネットのようなコンピュータネットワーク上で表示することができる。このシステムは、ナビゲーションシステムのような他のシステムと共に使用することもできる。
【解決手段】電子地図の地図的特徴をシミュレートするシステムが提供される。このシステムは、電子地図の地図的特徴を表すために、クロソイドのような１つ以上の幾何学形状を使用する。このシステムは、直線のシステムよりも正確で写実的に地図的特徴を記述することができる。このシステムは、データを直線システムからクロソイドシステムに変換するためのデータモデル及び方法を含むことができる。また、このシステムは、電子地図の地図的特徴を記述するために必要とされる記憶容量を低減することができる。電子地図は、広域ネットワーク、ローカルエリアネットワーク、無線又は有線ネットワーク、イントラネット又はインターネットのようなコンピュータネットワーク上で表示することができる。このシステムは、ナビゲーションシステムのような他のシステムと共に使用することもできる。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願）
本出願は、「ナビゲーション地図を生成するための装置及び方法」と題された米国特許出願番号１０／１４２，２７９号の部分継続出願として優先権を主張する。
【０００２】
（技術分野）
本発明は、地図的特徴のマッピングに関し、より具体的にはナビゲーションシステムと共に使用する、或いはコンピュータネットワーク上で表示することができる電子地図に関する。
【背景技術】
【０００３】
（背景技術）
電子地図を使用してユーザを目的地へ案内するのを支援するような道案内用ナビゲーションシステムの使用が、益々盛んになっている。このような道案内用ナビゲーションシステムは、典型的には道路、建物、公園、及び河川のような地図上の地図的特徴に関するデータを格納するために、コンパクトディスク（ＣＤ）又はデジタルビデオディスク（ＤＶＤ）のような媒体を使用する。ナビゲーションシステムと地球投影位置決定システム（ＧＰＳ）の結合により、多くの応用分野についてナビゲーションシステムの使用が実用化された。ＧＰＳベースのナビゲーションシステムは、種々の乗物において並びにユーザの携帯装置においても見ることができる。
【０００４】
公知のナビゲーションシステムは、典型的には電子地図を使用して、直線によって接続された一連の点を保存して呼び出すことにより地図的特徴を表す。しかしながらこの形式の表現は、多くの欠点を含む。例えば、道路や河川は実際には一連の直線から構成されておらず、むしろ一連の滑らかな曲線から構成されている。その結果、ユーザに対してディスプレイ装置上で図形情報を表示するナビゲーション地図は、通常は地図細部の特徴を高度に正確には示していない。地図詳細部をより正確に表現することを企図して、地図細部を表現するために使用される直線線分の数を増すことができる。しかしながら、線分数の増加は、地図的特徴を正確に表現するために格納されなくてはならないデータの量を大幅に増大させることになる。従って、大容量の記憶装置を必要とすることなく、地図的特徴の表示情報を正確にモデル化し表示する、ナビゲーションシステム用のマッピングシステムに対する必要性が存在する。
【発明の概要】
【課題を解決するための手段】
【０００５】
（発明の開示）
地図上の地図的特徴を電子的な形態で表すために、クロソイドのような幾何学形状を使用することができる。地図は、分散型のナビゲーションシステムと接続されて、或いは通信ネットワークに接続されたナビゲーションシステムによって使用されることができる。このシステムは、クロソイドを用いて地図的特徴を表すナビゲーション用地図データを含むことができる。道路、鉄道線路、河川、湖等のような地図的特徴は、１つ又はそれ以上のクロソイドによって表すことができる。
【０００６】
一連の直線によって地図的特徴を表すのではなく、点によって接続された一連のクロソイドによって地図的特徴を表すことができる。クロソイドは、始点と始点曲率と終点と終点曲率とにより表すことができる。従って、一連の直線を用いて地図的特徴を表す公知のシステムと比べた時に、ナビゲーション用地図のパラメータを格納するのに要する記憶装置の量を低減することができる。同様に、システムに必要な記憶装置容量を増やす必要性を最少化すると共に、ナビゲーション用地図の精度を向上させることができる。
【０００７】
ナビゲーションシステムは、複数のセンサからセンサデータを受け取って、該ナビゲーションシステムのディスプレイ装置上でユーザに対して地図を発生させることができる。ナビゲーションシステムは、記憶装置内に記憶された道路又は他の地図的特徴を、データモデルにおけるクロソイドの形態で表す地図データを含むことができる。また、このシステムは、ユーザの現在位置に対応するＧＰＳシステムからのデータのようなセンサデータを受け取るナビゲーション処理装置を含むことができる。システムは、センサデータと関係付けられた地図データを記憶装置に要求して、地図データから地図画像を計算することができる。地図上におけるユーザの現在位置を示すためにユーザに対し地図画像を表示することができる。
【０００８】
本発明の他のシステム、方法、特徴、及び利点は、添付図面と以下の詳細な説明を吟味することにより当業者には明らかになるであろう。本明細書に含まれるこのような追加的なシステム、方法、特徴、及び利点の全ては、本発明の範囲内に含まれ、添付の請求項によって保護されるべきである。
本発明は、例えば、以下を提供する。
（項目１） 電子地図の地図的特徴を表すことができるデータモデルであって、第１のクロソイド経路を含み、該経路が前記地図的特徴を表す少なくとも１つのクロソイド区分を有するデータモデル。
（項目２） 前記第１のクロソイド経路が、接続点において接続された少なくとも２つのクロソイド区分を含むことを特徴とする項目１に記載のデータモデル。
（項目３） 前記第１のクロソイド経路と第２のクロソイド経路との間の連結部に形成される交差点を更に含む項目１に記載のデータモデル。
（項目４） 前記第１のクロソイド経路が主要経路を含み、第２のクロソイド経路が補助経路を含むことを特徴とする項目３に記載のデータモデル。
（項目５） 前記主要経路が曲率を含み、前記補助経路が曲率を含むことを特徴とする項目４に記載のデータモデル。
（項目６） 前記主要経路の曲率が、交差点において前記補助経路の曲率を含むことを特徴とする項目５に記載のデータモデル。
（項目７） 前記第１のクロソイド経路が第１の主要経路を含み、前記第２のクロソイド経路が第２の主要経路を含むことを特徴とする項目３に記載のデータモデル。
（項目８） 前記第１の主要経路が曲率を含み、前記第２の主要経路が曲率を含むことを特徴とする項目７に記載のデータモデル。
（項目９） 交差点において、前記第１の主要経路の曲率が前記第２の主要経路の曲率と異なることを特徴とする項目８に記載のデータモデル。
（項目１０） 電子地図の地図的特徴を表す方法であって、少なくとも１つのクロソイド区分を含む第１のクロソイド経路を用いて地図的特徴を表す段階を含む方法。
（項目１１） 前記第１のクロソイド経路と第２のクロソイド経路との間の連結部において交差点を生成する段階を更に含む項目１０に記載の方法。
（項目１２） 第１のクロソイド経路が主要経路を含み、前記第２のクロソイド経路が補助経路を含むことを特徴とする項目１１に記載の方法。
（項目１３） 前記主要経路が曲率を含み、前記補助経路が曲率を含むことを特徴とする項目１２に記載の方法。
（項目１４） 前記主要経路の曲率が、交差点において前記補助経路の曲率と等しいことを特徴とする項目１３に記載の方法。
（項目１５） 前記第１のクロソイド経路が第１の主要経路を含み、前記第２のクロソイド経路が第２の主要経路を含むことを特徴とする項目１１に記載の方法。
（項目１６） 前記第１の主要経路が曲率を含み、前記第２の主要経路が曲率を含むことを特徴とする項目１５に記載の方法。
（項目１７） 前記第１の主要経路の曲率が、交差点において前記第２の主要経路の曲率と異なることを特徴とする項目１６に記載の方法。
（項目１８） 電子地図内で表される地図的特徴を変換する方法であって、
地図的特徴の少なくとも一部を少なくとも１つのクロソイド区分に変換する段階と、
前記クロソイド区分が前記地図的特徴の一部を表していることを確認する段階と、
を含む方法。
（項目１９） 前記変換する段階が、直線データモデルをクロソイドデータモデルに変換する段階を含む項目１８に記載の方法。
（項目２０） 前記確認する段階が、前記直線データモデルにおける少なくとも１つの点と、前記クロソイドデータモデルにおける最も近い点との間の距離を求める段階を含む項目１９に記載の方法。
（項目２１） 前記距離を求める段階が、元の空間内に位置する少なくとも１つの点を、単位クロソイド空間内に位置する変換された点に変換する段階を含む項目２０に記載の方法。
（項目２２） 前記距離を求める段階が、少なくとも１つの点と単位クロソイドとの間の距離を求める段階を更に含む項目２１に記載の方法。
（項目２３） 前記距離を求める段階が、
変換された点が位置する前記単位クロソイド空間内の領域を判定する段階と、
前記求められた領域に従って前記単位クロソイド上の境界を選択する段階と、
定められた距離を識別するために、前記境界を反復的に調節する段階と、
を含む項目２２に記載の方法。
（項目２４） 前記選択された境界に従ってサンプル境界を計算する段階と、
前記サンプル境界と前記変換された点との間の距離を計算する段階と、
前記サンプル境界を調節する段階と、
前記距離を計算する段階を続行すべきか否かを判定する段階と、
を更に含み、
計算が完了している場合には、前記サンプル境界と前記変換された点との間の計算された前記距離が前記定められた距離を含み、計算が完了していない場合には、新たなサンプル境界を計算して、新たな該サンプル境界と前記変換された点との間の距離を計算する項目２３に記載の方法。
（項目２５） 前記反復は、定められた量の反復が完了した時に完了する項目２３に記載の方法。
（項目２６） 前記反復は、前記サンプル境界と前記点との間の距離が定められた許容可能な誤差値内である時に完了する項目２３に記載の方法。
（項目２７） 距離を求める段階が、求められた前記距離を前記元の空間における距離に変換する段階を更に含む項目２３に記載の方法。
（項目２８） 距離を求める段階が、求められた前記距離を前記元の空間における距離に変換する段階を更に含む項目２３に記載の方法。
（項目２９） クロソイドと点との間の距離を計算するための方法であって、
元の空間内に位置する地図的特徴の少なくとも１つの点を、単位クロソイド空間内に位置する変換された点に変換する段階と、
前記変換された点が位置する前記単位クロソイドの領域の境界を選択する段階と、
前記境界と前記変換された点との間の距離の関数として前記境界を調節して、前記地図的特徴の少なくとも１つの点を表すクロソイド区分を識別する段階と、
を含む方法。
（項目３０） 前記計算は、定められた量の反復が完了した時に完了する項目２９に記載の方法。
（項目３１） 前記計算は、サンプル境界と前記点との間の距離が定められた許容可能な誤差値内である時に完了する項目２９に記載の方法。
（項目３２） 前記距離を前記元の空間における変換された距離に変換する段階を更に含む項目２９に記載の方法。
（項目３３） 前記距離がナディアを含むことを特徴とする項目２９に記載の方法。
（項目３４） 計算された前記距離を用いて、前記クロソイド区分が前記地図的特徴の少なくとも一部を正確に表していることを確認する段階を更に含む項目２９に記載の方法。
（項目３５） ナビゲーション用アプリケーションは、計算された前記距離を利用して、地図的特徴と特定位置との間の距離を求めることを特徴とする請求項３４に記載の方法。
（項目３６） ナビゲーション用アプリケーションを実行するために、プロセッサを設ける段階を更に含む項目３５に記載の方法。
（項目３７） 前記特定位置が、プロセッサの位置を含むことを特徴とする項目３５に記載の方法。
（項目３８） プロセッサが乗物内に配置さえていることを特徴とする請求項３７に記載の方法。
（項目３９） 電子地図の地図的特徴を表示することのできるナビゲーションシステムであって、
電子地図の地図的特徴を表すことができるデータモデルを処理し、該データモデルが前記地図的特徴を表す少なくとも１つのクロソイド区分を有するクロソイド経路を含む、プロセッサと、
電子地図上に地図的特徴を表示するためのディスプレイ装置と、
を含むことを特徴とするナビゲーションシステム。
（項目４０） 前記プロセッサによりアクセス可能なナビゲーション用アプリケーションを更に含むことを特徴とする項目３９に記載のナビゲーションシステム。
（項目４１） ナビゲーション用アプリケーションが、地図的特徴と特定位置との間の距離を求めることを特徴とする項目４０に記載のナビゲーションシステム。
（項目４２） 前記特定位置が、前記プロセッサの現在の地理的位置を含むことを特徴とする項目４１に記載のナビゲーションシステム。
（項目４３） 前記プロセッサが乗物内に配置されていることを特徴とする項目４２に記載のナビゲーションシステム。
（項目４４） ネットワークを介して地図データにアクセスするためのサーバコンピュータを更に含むことを特徴とする項目３９に記載のナビゲーションシステム。
（項目４５） 前記ディスプレイ装置を用いて、前記クロソイドに沿った経路、位置、及び軌道の内の少なくとも１つを動的に表示するために、前記プロセッサと共に作動可能なセンサを更に含むことを特徴とする項目３９に記載のナビゲーションシステム。
（項目４６） 地図的特徴の少なくとも一部を、該地図的特徴を表す少なくとも１つのクロソイド区分に変換するためのプロセッサと、
前記クロソイド区分を表すデータを含む記憶装置と、
を含み、
前記プロセッサが、前記記憶装置内の前記データをクロソイドデータモデルに構成することを特徴とするデータ処理装置。
（項目４７） 前記プロセッサは、前記クロソイド区分が前記地図的特徴の一部を正確に表していることを確認することを特徴とする項目４６に記載のデータ処理装置。
（項目４８） 前記プロセッサは、前記地図的特徴の直線データモデルを前記クロソイドデータモデルに変換することを特徴とする項目４６に記載のデータ処理装置。
（項目４９） 点とクロソイドとの間の最も近い距離を求めることができるデータ処理システムであって、
（ｉ）元の空間内に位置する点を単位クロソイド空間内に位置する変換された点に変換し、（ii）前記変換された点が位置する前記単位クロソイド空間内の領域を判定し、（iii）前記判定された領域に従って前記単位クロソイド上の境界を選択し、（iv）前記選択された境界に従ってサンプル境界を計算し、（ｖ）該サンプル境界と前記点との間の距離を計算し、（vi）前記サンプル境界を調節し、（vii）一連の反復が完了したか否かを判定し、（viii）一連の反復が完了した場合には、前記サンプル境界と前記点との間の計算された前記距離は定められた距離を含み、一連の反復作業が完了していない場合には、新たなサンプル境界を計算して（ｖ）へ戻るように構成されたプロセッサを含むことを特徴とするデータ処理システム。
（項目５０） 一連の前記反復は、定められた量の反復が完了した時に完了することを特徴とする項目４９に記載のデータ処理システム。
（項目５１） 一連の前記反復は、前記サンプル境界と前記点との間の距離が定められた許容可能な誤差値内である時に完了することを特徴とする項目４９に記載のデータ処理システム。
（項目５２） 前記プロセッサが、前記計算された距離を前記元の空間における変換された距離に変換することを特徴とする項目４９に記載のデータ処理システム。
（項目５３） ナビゲーション用アプリケーションを更に含むことを特徴とする項目４９に記載のデータ処理システム。
（項目５４） 前記ナビゲーション用アプリケーションが、前記計算された距離を利用して、地図的特徴と特定点との間の距離を求めることを特徴とする項目５３に記載のデータ処理システム。
（項目５５） 前記プロセッサが、前記ナビゲーション用アプリケーションを実行することを特徴とする項目５４に記載のデータ処理システム。
（項目５６） 前記特定点が、プロセッサの現在の地理的位置を含むことを特徴とする項目５５に記載のデータ処理システム。
（項目５７） 前記プロセッサが乗物と共に配置されていることを特徴とする項目５６に記載のデータ処理システム。
（項目５８） 電子地図上に地図的特徴を表示することができるコンピュータプログラムであって、
データモデルから電子地図の地図的特徴を表すためにプロセッサによって実行可能であり、前記データモデルが前記地図的特徴を表す少なくとも１つのクロソイド区分を有するクロソイド経路を含む、プログラムコードと、
前記電子地図上に地図的特徴を表示するためにプロセッサによって実行可能なプログラムコードと、
を含むことを特徴とするコンピュータプログラム。
（項目５９） 前記プログラムコードが、前記地図的特徴と特定点との間の距離を計算することができることを特徴とする項目５８に記載のコンピュータプログラム。
（項目６０） 前記特定点が、地球投影位置決定衛星装置によって提供される現在の地理的位置を含むことを特徴とする項目５９に記載のコンピュータプログラム。
（項目６１） 前記プロセッサが乗物と共に配置されていることを特徴とする項目６０に記載のコンピュータプログラム。
（項目６２） 電子地図内で具現化される地図的特徴であって、
前記地図的特徴の少なくとも一部を表す少なくとも１つのクロソイド区分を含むクロソイド経路を含み、前記クロソイド区分が、少なくとも１つのＸＹ座標と曲率とを使用して記述されることを特徴とする地図的特徴。
（項目６３） 前記クロソイド区分が、始点と始点曲率と終点と終点曲率とを含むことを特徴とする項目６２に記載の地図的特徴。
（項目６４） 前記クロソイド区分が、始点曲率と終点曲率と長さとを用いて記述されることを特徴とする項目６２に記載の地図的特徴。
（項目６５） 交差するクロソイド経路間の連結部に形成される交差点を更に含むことを特徴とする項目６４に記載の地図的特徴。
（項目６６） 主要経路と補助経路とを更に含むことを特徴とする項目６５に記載の地図的特徴。
（項目６７） 前記主要経路が曲率を含み、補助経路が曲率を含むことを特徴とする項目６６に記載の地図的特徴。
（項目６８） 前記主要経路の曲率が、前記交差点において前記補助経路の曲率を含むことを特徴とする項目６７に記載の地図的特徴。
（項目６９） 第１の主要経路と第２の主要経路とを更に含むことを特徴とする項目６５に記載の地図的特徴。
（項目７０） 前記第１の主要経路が曲率を含み、前記第２の主要経路が曲率を含むことを特徴とする項目６９に記載の地図的特徴。
（項目７１） 前記第１の主要経路の曲率が、前記交差点において前記第２の主要経路の曲率と異なることを特徴とする項目７０に記載の地図的特徴。
（項目７２） 前記クロソイド区分が、直線、曲線、円、及びスプラインの内の少なくとも１つのを表すことを特徴とする項目６２に記載の地図的特徴。
（項目７３） 複数のクロソイド区分が、円と直線との内の少なくとも１つを表すことを特徴とする項目６２に記載の地図的特徴。
（項目７４） 前記クロソイド経路が、接続点において接続された少なくとも２つのクロソイド区分を含み、前記クロソイド区分の各々の曲率と進行方向とが、前記接続点において等しいことを特徴とする項目６２に記載の地図的特徴。
（項目７５） 前記クロソイド経路が、少なくとも２つのクロソイド区分を含むことを特徴とする項目６２に記載の地図的特徴。
（項目７６） 複数のクロソイド区分が、連結されて地図的特徴を形成することを特徴とする項目７５に記載の地図的特徴。
（項目７７） 少なくとも１つの直線によって表される地図的特徴を含む電子地図を、少なくとも１つのクロソイド区分によって表される地図的特徴に変換するための手段を更に含むことを特徴とする項目６２に記載の地図的特徴。
【図面の簡単な説明】
【０００９】
添付図面を参照しながら以下の説明を読むことにより、本発明は一層よく理解することができる。図面中の構成要素は必ずしも縮尺通りではなく、本発明の原理を説明するために強調されている。更に全ての図面を通して、同じ参照符号は対応する部分を示している。
【図１】ディスプレイ装置上に地図を生成するために地図データを利用するナビゲーションシステムを示すブロック図である。
【図２】ディスプレイ装置上に地図を生成するために地図データを利用するコンピュータネットワークシステムを示すブロック図である。
【図３】クロソイドを示すグラフである。
【図４】移動距離に対する曲率の関係を示すグラフである。
【図５】地図的特徴を表すために点によって互いに連結された１対のクロソイド区分を示す図である。
【図６】図５に示す地図的特徴を直線線分により表した図である。
【図７】クロソイドを基準化するために、クロソイドのセカントに対するベクトルの関係を示すグラフである。
【図８】クロソイドの数学的に使用可能な部分を示すグラフである。
【図９】クロソイド経路を示すグラフである。
【図１０】クロソイドのグラフの幾つかの領域への分割を示すグラフである。
【図１１】交差した２つの経路を示す図である。
【図１２】交差した２つの主要経路と１つの補助経路とを示す図である。
【図１３】直線により接続された点によって道路を表した地図を示す図である。
【図１４】図１３の地図よりも少数の点によって道路を表し、該点は求められた曲率を含む線によって接続されている地図である。
【図１５】ナディアとクロソイドから１つの点までの距離の判定を表したフローチャートである。
【図１６】クロソイドのグラフを複数領域に分割することを用いて、点までの距離を求めることを示すグラフである。
【発明を実施するための形態】
【００１０】
（発明を実施するための最良の形態）
クロソイド（コルニュ螺旋又はオイラーの螺旋としても知られている）のような幾何学形状は、電子地図上の地図的特徴を表現するのに使用することができる。この地図は、ナビゲーションシステム、或いは携帯用情報端末（ＰＤＡ）又は家庭用コンピュータのような電子地図を用いる他のシステムと共に使用することができる。また、このような地図は、無線ネットワーク、広域ネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、イントラネット及びインターネットのようなコンピュータネットワークを介してアクセスすることも可能である。このナビゲーションシステムは、携帯用システム内で使用することができ、或いは自動車、トラック、農作業機械、鉱山機械、ゴルフカート、及び移動ロボットのような乗物用に使用することができる。また、これらのナビゲーションシステムは、船舶のための周知の航路、航空機のための周知の飛行経路を作図するのに使用することができ、或いは航空機又は宇宙船の自動操縦装置と共に使用してもよい。「地図的特徴」又は「地図特徴」という用語は、道路、鉄道線路、公園、建物、河川等のような電子地図上に描くことができるどのような属性をも含むものとして広義に解釈されるべきである。
【００１１】
図１は、地図を作成し及び発生させるために地図データを利用するナビゲーションシステム１００を示すブロック図である。このナビゲーションシステム１００は、単に説明の目的で使用されているに過ぎず、ナビゲーション地図システムとは異なる他のシステムを使用してもよい。ナビゲーションシステム１００は、ディスプレイ装置１１０、ナビゲーション処理装置１２０のようなプロセッサ、ナビゲーション地図データ１３０、入力装置１４０、及び少なくとも１つのセンサ１５０を含むことができる。ディスプレイ装置１１０は、ユーザに対して地図を発生させるのに使用することができる。ディスプレイ装置１１０には、液晶ディスプレイ（ＬＣＤ），陰極線管（ＣＲＴ）、ヘッドアップディスプレイ、又は他の形式のディスプレイ装置を含むことができる。
【００１２】
ディスプレイ装置１１０は、ナビゲーション地図データ１３０にアクセスして処理することができるナビゲーション処理装置１２０と接続されて、ユーザに対し地図を表示することができる。ユーザは、入力装置１４０を介して、情報を要求し、またナビゲーションシステム１００とインターフェースをとることができる。ナビゲーションシステム１００は、通信リンク、地球投影位置決定衛星（ＧＰＳ）、基地局、又は他の送信システムのような、他の機構及び装置を含むことができる。
【００１３】
ナビゲーション地図データ１３０は、クロソイドのような１つ又はそれ以上の幾何学形状によって表現することができる地図的特徴に関するデータを含むことができる。更に、一連のクロソイドを使用して、一連の直線の配列を用いた表現よりもより正確で写実的に道路や他の地図的特徴の実際のパターンを表すことができる。クロソイドを使用することにより、地図上の位置表示の正確さを向上させることができる。正確な位置は、２つの直線が連結する点だけでなく、道路のコース全体にわたって存在する。又、少なくとも１つのクロソイドによる地図的特徴の表は、地図的特徴を表現するために一連の直線を用いるシステムよりも少数のパラメータしか必要としないことから、従って記憶装置の記憶空間を節約することが可能である。
【００１４】
センサ１５０は、ナビゲーション地図データ１３０と関係付けて使用して、ユーザの軌道と位置（例えば、経路）とを感知した状態を自動的に維持することができる。センサ１５０は、タイヤの回転速度を測定するためのホイールカウンタ、乗物の位置を測定するためのＧＰＳ装置、乗物が方向を変えた時や、航空機のための飛行データや、船舶のための現在の航行方向及び速度に関するデータ等を測定するためのジャイロを含むことができる。また、ナビゲーション処理装置１２０は、センサ及びナビゲーション地図データ１３０からの情報にアクセスして、今後の予測経路を表すことができる予測経路データを計算することができる。例えば、ディスプレイ装置は、現在のデータに基づいて今後の移動範囲をある程度示すことができる。また、ナビゲーション処理装置１２０は、センサ１５０とナビゲーション地図データ１３０とを利用して、到着推定時間、経路に関する方向、又は乗物の動きに関する他の任意の動的パラメータのような、経路に関する他の機能を実行することもできる。
【００１５】
図２は、コンピュータネットワークシステム２００に接続されたナビゲーションシステムを示すブロック図である。このコンピュータネットワークシステム２００は、地図データを送受することができ、これによりユーザが少なくとも１つのクライアント２１０から地図にアクセスすることが可能となる。クライアント２１０は、ネットワークを介してサーバ２２０に接続されている。サーバ２２０は、コンピュータ読取り可能コードを実行するプロセッサ又はコンピュータを含むことができる。このネットワークは、ＷＡＮ、ＬＡＮ、イントラネット及び／又はインターネットのような、無線及び／又は有線の通信リンクを含むことができる。サーバ２２０は、データを送るためにネットワーク又は他の任意の通信路を介してナビゲーション処理装置１２０に接続されることができる。ナビゲーション処理装置１２０により、地図又は地図データをサーバ２２０と送受することができる。ナビゲーション処理装置１２０は記憶装置を含むことができ、ナビゲーション地図データ１３０を格納するために遠隔データ記憶装置１３０と通信することができる。
【００１６】
コンピュータ及びナビゲーションシステムは、上述の諸機能を行うための命令を実行するプロセッサを含むことができる。この命令は、プロセッサによってアクセス可能な記憶装置内に格納されたプロセッサ読取り可能コードの形態とすることができる。実行可能なコードは、ハードウエア、ソフトウエア、ファームウエア、又はこれらの任意の組合せを用いて実行することができる。プロセッサは、１つ又はそれ以上の記憶装置と双方向的に通信することができる。記憶装置とプロセッサとは、地図に関するデータ、及びコンピュータとナビゲーションシステムとの動作に関する他のデータを送受することができる。データは、無線通信及び／又は有線通信で送ることができ、コンピュータネットワークを介して通信することも可能である。
【００１７】
図３は、地図の地図的特徴に関するデータを生成するのに使用することができるクロソイド３００を示すグラフである。クロソイドは、典型的には曲率が線形に変化する幾何学形状である。従って、クロソイド区分を用いて、曲線、直線、円、及びスプラインのような地図の地図的特徴を表すことができる。直線と円とはクロソイドの特別な場合であって、クロソイドの異なる区分によって表すことができる。これにより、全ての地図的特徴がクロソイドを用いてモデル化することが可能になる。直線を表すためには、ゼロに等しい曲率を有するクロソイド区分が使用される。
【００１８】
図４は、曲率と移動距離の関係を示すグラフである。この曲率−距離グラフに関して、ユーザが点１から点２に移動する場合、曲率は一定値ゼロを保つ。従ってこれに対応するｘ−ｙグラフにおいては、点１から点２まで直線が横に延びる。点２から点３までの曲率−距離グラフに関して、曲率は定常的に増大する。従って、点２と点３との間のｘ−ｙグラフは、移動距離につれて曲率が増大することを示している。クロソイドの曲率は、移動距離に正比例させることができ、例えば、曲率は移動した距離と共に一定の割合で増大することができる。
【００１９】
例えば、点２と点３との間で移動した距離の１ｍ毎に、曲率は０．０００１（１／ｍ）だけ増加する。乗物のドライバーの場合、乗物が点２と点３との間を移動する時にドライバーはステアリング・ホイールを一定の速度で一様に回転させる。点３から点４までは、移動距離全体にわたり曲率が一定に保たれる。このようにして、クロソイド区分は、地図上の地図的特徴を表すために互いに連結される。クロソイドを適用する場合には、点と点の間の線分の曲率は線形的に表すことができる。更に、他の幾何学形状を適用する場合には、曲率と距離との間の比例関係は、線形的、対数的、指数関数的等とすることができる。
【００２０】
図５は、１対のクロソイド区分Ｓ１、Ｓ２を点Ｐ１、Ｐ２、及びＰ３により互いに連結して地図的特徴を形成するクロソイドデータモデルを示す図である。各々のクロソイド区分は、デカルト座標系のｘ−ｙ軸上に置かれ、曲率値Ｋを含む始点ノード又は始点と、曲率Ｋを有するｘ−ｙ軸上の終点とによって表される。図６は、図５のクロソイドデータモデルで示したのと同じ地図的特徴を、直線データモデルにおける直線線分によって表した図である。図５と図６とを比較すると、図５に示すクロソイドの使用により、曲線を表すために点ＳＰ１−ＳＰ６の間の一連の直線線分ＳＳ１−ＳＳ５を使用する方法よりも少いデータ点を用いて、地図的特徴をより正確に表示することが可能となる。地図的特徴の曲線を表すためにクロソイドを使用することは、現在走行している道路についてのより正確な表示をナビゲーションシステムのユーザに提供する。
【００２１】
クロソイドを表す数式
クロソイドは、曲率が弧長に比例する曲線である。クロソイドは、次の式で計算することができる。
【数１】
ここで、Ｉは弧長、Ｋは曲率、ａは比例定数を表す。パラメータの形では、クロソイドの方程式は、以下の座標として表すことができる。
【数２】
【数３】
この場合、
【数４】
である。
【００２２】
全てのクロソイドは同様であるから、１に等しいパラメータ値ａ（すなわちａ＝１）を有する単位クロソイドが存在する。計算速度を向上させるために、単位クロソイドのｘ−ｙ座標値を、表（例えば、ｓｉｎ−ｃｏｓ表）に格納することができ、実際のクロソイドは、これらの値から計算することができ、ここで、ｔは指数である。ａ＝１の場合の単位クロソイドは、
【数５】
【数６】
である。
【００２３】
これらの積分は容易には解けないので、ｘ軸値とｙ軸値とを計算するために、正弦関数及び余弦関数は、次式で表されるテイラー級数に変換することができ、
【数７】
【数８】
これを、方程式に挿入する。
【数９】
【数１０】
【００２４】
従って積分は以下のように解くことができる。
【数１１】
【数１２】
τ＝０からｔの境界を用いて、テイラー級数は次のように計算することができる。
【数１３】
【数１４】
【００２５】
上に示すように、級数は任意の項数以下を切り捨て、１つの多項式が残るようにすることができる。この多項式の各項も表に格納することができる。項の数は処理系に応じて決まる。つまり、例えば６４ビットの浮動小数点数を使用する典型的なコンピュータシステムを用いる場合には、９項多項式の最終項の階乗の精度は仮数部（５３ビット）の精度に等しいことから、この多項式は９番目の項で終結することができる。ここで、
【数１５】
である。
【００２６】
上記の積分を解くために、ニュートンの補間式、或いはラグランジェ又はエイトケン−ネヴィルの補間式の使用によるような、テイラー級数以外の方法も使用できることは当業者には分かるであろう。
【００２７】
進行方向を表すγは、元のｘとｙ積分から求めることができる。
【数１６】
【００２８】
曲率Ｋによっては、パラメータｔの代わりに、ｘ、ｙ、γを使用してもよい。
ここで、
【数１７】
である。
【００２９】
ｘ、ｙ、γに対する式は次のようになる。
【数１８】
【数１９】
ここで、
【数２０】
である。
【００３０】
地図に対するクロソイドの使用
データモデル内でクロソイドを記述する方法が幾つかある。第１に、クロソイドは、曲率Ｋ0で始まり、流さｌを含み、終点曲率Ｋ1を有することができる。従って比例定数ａは、次式で計算できる。
【数２１】
【００３１】
特定の場合においては、曲率の正負符号は進行方向すなわち線の向きを表すのに適している。曲率が正の場合にはその曲線は左に進み、曲率が負の場合にはその曲線は右に進む。比例定数ａと進行方向ｄとは、次のように計算できる。
【数２２】
【数２３】
【００３２】
曲率間の差がゼロである線又は円の場合には、ａは理論的には無限大であって、これは別個に取り扱われる。例えば、始点又は終点曲率の絶対値が、最小値より小さい場合には線が使用され、最小値より大きい場合には円が使用される。
【００３３】
第２に、クロソイドは、始点Ｘ0、Ｙ0と始点曲率Ｋ0と、終点Ｘ1、Ｙ1と終点曲率Ｋ1で表すことができる。比例定数ａと回転角βは、基準化され、回転され且つ位置付けされた単位クロソイドに対して計算することができる。ここで、
【数２４】
【数２５】
である。
【００３４】
図７は、クロソイドを基準化するための、クロソイドのセカント７１０（右側のグラフ）に対するベクトル７００（左側のグラフ）の関係を示すグラフである。式２４及び２５を用いると、式の左項は始点から終点まで延びるベクトル７００を表している。式の右項は曲線上の始点から終点までのクロソイドのセカント部分７１０を表している。セカント７１０は、基準化し、回転させることができる。これらの式を容易に読み取ることができるように、下記の項を代入する。
【数２６】
【数２７】
【数２８】
【数２９】
【００３５】
従って、これらの式は次のように書き換えられる。
【数３０】
【数３１】
【００３６】
比例定数は、次のように計算できる。
【数３２】
【数３３】
ピタゴラスの定理を使用することにより、
【数３４】
比例定数ａは、次のように計算できる。
【数３５】
【数３６】
【数３７】
【数３８】
【数３９】
【００３７】
即ち、クロソイドの基準化因子ａ2は、ベクトルの長さをセカントの長さで除算したものに等しいとすることができるので、
【数４０】
従って、式４０は、クロソイドのベクトルとセカントとの間の関係を示している。
【００３８】
従って、代入された項は、次のように計算できる。
【数４１】
【数４２】
【数４３】
【数４４】
【数４５】
結果として、次のようなゼロ交差式が得られる。
【数４６】
【００３９】
比例定数ａを計算するために、第１のゼロ交差が計算される。ニュートン法は急速に収束して、少数の反復段階しか必要としないので、第１のゼロ交差を計算するためにニュートンの方法を使用することができる。
【数４７】
【００４０】
ニュートンの方法の開始値はベクトルの長さ、すなわちベクトルの始点と終点との間の距離である。
【数４８】
【００４１】
複数のゼロ交差がこれを超えて生じる特異性の限界があるであろう。従って、クロソイドの使用可能な部分は次式のように減少する。
【数４９】
（これを言葉で表現すると、ｔはマイナスルート２からプラスルート２まで生じる可能性がある）
【数５０】
【００４２】
限界を数学的に超えることは、第１のゼロ交差が複素数を有することによって示すことができる。図８は、数学的に使用可能なクロソイドの部分８００を示すグラフである。ニュートン法から得られる結果は、以下の限界によって確かめられる。
【数５１】
及び
【数５２】
又、次のゼロ交差式を用いて確認することもできる。
【数５３】
結果が限界を超えている場合には、この結果は、線又は円と同一であるとみなすこともできる。
【００４３】
比例定数ａが計算された後、回転値βが次のように計算される。
【数５４】
そして進行方向ｄが次のように計算される。
【数５５】
【００４４】
クロソイド経路の計算
図９は、道路のような地図的特徴を表すクロソイド経路９００（クロソイドスプラインとしても知られている）を示すグラフである。クロソイド経路９００は、一連に接続されたクロソイド線分９１０ａ−９１０ｄから構成されることができる。クロソイド線分９１０ａ−９１０ｄの接続点ＸＹＺγは、追加的な制約を生じる可能性がある。接続点ＸＹＫγにおいて、接続しているクロソイド区分の曲率Ｋと進行方向γは、クロソイド経路の連続性を保証するために同一とすることができる（さもなければ、本質的に道路のような地図的特徴はねじれを含むことになるであろう）。
【００４５】
接続したクロソイド区分の進行方向は、複数の反復段階を用いて整列させることができる。接続したクロソイド区分の進行方向に基づいて、曲率の変化と共に進行方向差を計算することができる。進行方向差が正ならば、曲率は増大することができる。進行方向差が負ならば、曲率は減少する。従って、
【数５６】
であり、この場合、
【数５７】
である。
【００４６】
進行方向における変化は、接続したクロソイド区分の長さｌ0及びｌ1と、各反復段階の強化を最適化するために使用される定数ｃとにより基準化することができる。過度に小さな定数ｃが選ばれた場合には、計算に長い時間がかかり、定数ｃが大き過ぎる場合には、接続が振動する可能性がある。
【００４７】
クロソイドと点との間の距離の計算
アルゴリズムは、クロソイドと点との間の距離を計算するために様々なアプリケーションで使用することができる。アルゴリズムは、コンピュータにより実行することができる。このアルゴリズムは、例えば線データモデルをクロソイドデータモデルに変換するために、クロソイド回帰計算において使用することができる。また、このアルゴリズムは、例えばＧＰＳで求められた位置を道路上の位置に整合させるために、ナビゲーション中に使用することもできる。クロソイドが単位クロソイドでない場合には、式２４及び式２５に記述された変換の逆を使用して、点は単位クロソイド空間に変換することができる。
【００４８】
単位クロソイドと変換された点との間の距離を計算するために、反復法を用いてナディア（ｎａｄｉｒ、すなわち変換された点に最も近いクロソイド上の点）を計算することができる。単位クロソイドと変換された点との間の距離ｄは、次のように計算できる。
【数５８】
この場合、
【数５９】
である。ここで、距離ｄは、単位クロソイド上の点と変換された点との間の距離の関数である。距離関数の最小値は、最初に単位クロソイドを幾つかの領域に分割することによって位置付けられる。
【００４９】
図１０は、ｄの決定に役立つ、クロソイド８００の使用可能な部分のグラフを各領域（０、１、２ａ、２ｂ、３、４、５、６ａ、６ｂ、７とする）に分割するための１つの方法を示すグラフである。各領域内では、距離関数は単峰性である。従って、この距離関数は、この領域内で１つの極小値を含むことができる。この極小値は、黄金分割法を使用して求めることができる。例えば、領域４に関して距離関数は、ｔ＝０からｔ＝１及びｔ＝平方根（−２）から計算することができる。
【００５０】
領域２及び６を除いて、全ての領域は直線によって分割することができる。領域２及び６は、１つの曲線によって領域２ａ、２ｂ、６ａ、６ｂに分割することができる。この曲線は、全ての垂線の包絡線（すなわち、クロソイド上の直立線を取り囲む曲線）とすることができる。
【００５１】
垂線は次のように計算することができる。
【数６０】
【数６１】
パラメータｕを消去することによって、
【数６２】
ここで
【数６３】
微分計算すると、
【数６４】
この式は、ピタゴラスの定理を用いることにより次のように単純化できる。
【数６５】
原始関数と導関数とを組み合わせると、
【数６６】
これを再びピタゴラスの定理を用いて簡約すると、
【数６７】
垂線に関する元の式と比較することによって、
【数６８】
垂線の包絡線に関する式は、
【数６９】
【数７０】
とすることができる（ｘの代わりにｙを使用しても同じ結果が得られる）。ここで、パラメータｔは、消去することができない。この点が曲線のどちら側に位置しているかを判定するために、パラメータｔは、Ｘに関して、次にＹに関して計算することができる。この関数は単峰性であるので、黄金分割法をここでも使用することができる。更に、Ｘ値及びＹ値は表に格納することができる。
【００５２】
黄金分割法によれば、最初に、求められた境界を開始値として使用することができる。この境界は、図１０に示すようにクロソイド８００の領域に従って求めることができる。
【数７１】
【数７２】
【００５３】
区間内の結果は、境界に関する値を用いて計算することができる。
【数７３】
【数７４】
この場合、黄金分割によれば、
【数７５】
である。
【００５４】
クロソイド上の点ｔ2と変換された点との間の距離、並びにクロソイド上の点ｔ3と変換された点との間の距離の両方を計算することができる。どちらの距離がより大きいかに応じて、境界を以下のように調節することができる。
【数７６】
そして、式７３を用いて再計算して、
【数７７】
そして、式７４を用いて再計算することができる。
【００５５】
従って、黄金分割法を用いる場合には、後続する反復の各々は、値ｔ2又はｔ3、及び距離を再計算することを含む。この反復は、ｔ0とｔ1との間の差が、求められた値よりも小さい場合に終了することができる。例えば、１０ｋｍのクロソイドに対してこの差が１ｃｍに等しくなった場合である。反復を完了することが処理系に応じて決まる場合には、反復は一定量の反復を実行し終えた後に完了してもよい。クロソイド区分は境界値ｔ0（ｔ1）によって識別され、距離ｄは誤差である。クロソイド区分は、クロソイド経路を形成するために組み合わせることができる。
【００５６】
データモデル
再び図５及び６を参照すると、直線を使用するデータモデル（図６）とクロソイド区分を使用するデータモデル（図５）との間の１つの違いは、クロソイド区分が複数の点を介して接続されることを記述している点である。直線データモデルにおいては、全ての線は別々に考察されるが、クロソイドデータモデルにおいては、複数のクロソイド区分を接続して１本のクロソイド経路を形成することができる。クロソイド経路は、道路のような地図的特徴を連続的なモデルとして表すことを可能にする。位置、曲率、及び進行方向といったパラメータを、道路上のあらゆる地点において計算することができる。
【００５７】
クロソイドは、始点ＸＹと、始点曲率Ｋと、終点Ｘ′Ｙ′と、終点曲率Ｋ′とを含む。従ってクロソイド経路は、曲率Ｋを有する複数の点を含むことができる。クロソイドデータモデル内の点は、これらが複数の形式の情報を含むことができることから、直線データモデルと比べて頑強である。更にクロソイドモデルにおいては、地図的特徴を正確に表すために必要とされる点の数を、直線データモデルの場合よりも少なくすることができる。
【００５８】
図１１は、経路Ｐ２と交差した経路Ｐ１を示している。経路Ｐ１及び２は、交差する２つの道路のような地図的特徴とすることができる。複数のクロソイド経路が互いに交差する場合、交差点Ｉが形成される。交差点Ｉでの点の記述に関しては、経路Ｐ１及びＰ２の位置ＸＹは同じものとすることができる。しかしながら経路Ｐ１及びＰ２の曲率は、個別のままである。従って、交差点Ｉにおいて、どのクロソイド部分が経路Ｐ１に対応し、またどのクロソイド部分が経路Ｐ２に対応するかを判定することができる。両方の経路Ｐ１及びＰ２に対応するクロソイド部分は、交差点を横断する主要経路を形成することができる。図１１には１つの交差点Ｉのみが示されているが、複数の交差点Ｉが存在し得るということを理解されたい。
【００５９】
図１２は、第２の主要経路Ｐ２と交差し、更に補助経路Ｐ３を含む第１の主要経路Ｐ１を示している。例えば、１つの道路が別の道路と接続しているランプが道路上に存在する場合には、このランプが補助経路Ｐ３を形成することができる。補助経路Ｐ３は、これが接続している第１の主要経路Ｐ１と同一の曲率を含むことができる。位置Ｘ，Ｙに関するパラメータは、交差点の位置を表すのに使用することができる。曲率値Ｋ0は、主要経路Ｐ１及び補助経路Ｐ３の曲率を表すのに使用することができ、曲率値Ｋ1は、主要経路Ｐ２の曲率を表すのに使用することができる。
【００６０】
ＸＹデータのＸＹＫデータへの変換
図１３は、道路１３１０が、何本かの直線により接続された幾つかの点１３２０によって表された地図１３００を示している。地図１３００は、該地図で使用されている直線データモデルを、クロソイド又は他の幾何学データモデルに変換することにより改善することができる。図１４は、図１３の地図１３００をクロソイドデータモデルで示している。道路１４００は、図１３に示す地図におけるよりも少数の点１４１０で表され、これらの点は、求められた曲率を含むクロソイドにより接続されている。直線データモデルからクロソイドデータモデルへの変換は、図１５に示すように、上記に論じた技術を用いて直線をクロソイド区分で置き換えることにより達成することができる。直線を置き換えることに加えて、図１４に示す点１４１０は、図１３に示した点１３１０とは異なる可能性があり、従ってこれらの点１３１０と対応する場合もあれば、対応しない場合もある。
【００６１】
図１５は、例えばＸＹデータ点をＸＹＫ値を有するデータ点に変換するために、ナディアとクロソイドから１つの点までの距離とを求める反復プロセスを表したフローチャートである。始めに、主要経路と補助経路との交差点に関するＸＹＫデータ点を求める。複数の経路が接続して１つの交差点を形成することができる。各経路は、交差点上で、主要方向、補助方向、又は関係なしといった３つの可能性のある方法で互いに関係付けられる。例えば、これらの経路は、「Ｔ」字交差点として関連付けることができる。「Ｔ」字の水平方向を形成する２つの経路は、主要方向とみなすことができ、残りの経路は何らの関係も形成しない。更に、高速道路の出口ランプのように、１つの経路が補助方向を形成することができる。このランプは主要経路と接続するので、補助経路の方向は主要方向と関係付けられる。
【００６２】
ブロック１５００において、計算を簡単にするために、マップ化される点は単位クロソイド空間に変換される。図１６は、単位クロソイド空間内に位置する変換された点１６００を示すグラフである。ブロック１５１０において、変換された点が位置する領域が判定される（例えば、図１６の領域３）。ブロック１５２０において、変換された点１６００が位置する領域が、領域２又は６であるかが判定される。ブロック１５３０において、領域が領域２又は６であると判定された場合には、境界ｔの内の１つは未知である。従って、例えば垂線の包絡線を計算する式を用いて、曲線の一方の側を定めてこの未知の境界を決定する。ブロック１５４０において、始点境界ｔ0及びｔ1が選択される。
【００６３】
ブロック１５５０において、サンプル境界ｔ2及びｔ3が計算される。ブロック１５６０において、ｘ（ｔ2）、ｙ（ｔ2）と変換された点（＝ｄ（ｔ2））との間の距離、及びｘ（ｔ3）、ｙ（ｔ3）と変換された点（＝ｄ（ｔ3））との間の距離が計算される（図１６）。ブロック１５７０において、境界は式７６及び式７７に記述されたように調節される。ブロック１５８０において、反復を続行するか否か、すなわち例えばｔ1とｔ2との間の計算された距離が許容可能な誤差値内であるか、或いは定められた反復回数が完了したか否かが判定される。反復が完了していない場合には、ブロック１５５０において、調節されたサンプル境界が計算される。反復が完了している場合には、ブロック１５９０において、サンプル境界ｔ2又はｔ3がナディアとして使用される。ブロック１５９５において、ナディアと計算された距離とが元の空間に変換される。
【００６４】
このプロセスは、他の点と他のクロソイドとの間の距離を計算するために繰り返すことができる。交差点の間に接続された線上の点に対して、データ点ＸＹはＸＹＫデータ点に変換することができる。
【００６５】
最もよく適合するクロソイドを求めるために、例えばガウス誤差分布曲線のようなガウス誤差低減法を使用することができる。主要方向及び補助方向は、可能性のある方向の組合せをクロソイドに変換し、交差点に最もよく適合するクロソイド区分を使用することによって計算することができる。例えば、ランプが高速道路に連結しており、その逆ではないことを確実にするために、道路の種類のような追加的な属性が考慮される。その結果として、交差点の曲率と方向とが既知である場合、どの経路が主要方向で、どの経路が補助方向であるかを特定するデータを含むことになる。従って、交差点における計算された曲率と進行方向に関するデータは一定のまま維持されるが、交差点間の幾何学形状は、例えばクロソイド経路に変換することができる。
【００６６】
本発明の様々な実施形態を説明してきたが、本発明の範囲内で更に多くの実施形態及び実装が可能であることは当業者には明らかであろう。
【技術分野】
【０００１】
（関連出願）
本出願は、「ナビゲーション地図を生成するための装置及び方法」と題された米国特許出願番号１０／１４２，２７９号の部分継続出願として優先権を主張する。
【０００２】
（技術分野）
本発明は、地図的特徴のマッピングに関し、より具体的にはナビゲーションシステムと共に使用する、或いはコンピュータネットワーク上で表示することができる電子地図に関する。
【背景技術】
【０００３】
（背景技術）
電子地図を使用してユーザを目的地へ案内するのを支援するような道案内用ナビゲーションシステムの使用が、益々盛んになっている。このような道案内用ナビゲーションシステムは、典型的には道路、建物、公園、及び河川のような地図上の地図的特徴に関するデータを格納するために、コンパクトディスク（ＣＤ）又はデジタルビデオディスク（ＤＶＤ）のような媒体を使用する。ナビゲーションシステムと地球投影位置決定システム（ＧＰＳ）の結合により、多くの応用分野についてナビゲーションシステムの使用が実用化された。ＧＰＳベースのナビゲーションシステムは、種々の乗物において並びにユーザの携帯装置においても見ることができる。
【０００４】
公知のナビゲーションシステムは、典型的には電子地図を使用して、直線によって接続された一連の点を保存して呼び出すことにより地図的特徴を表す。しかしながらこの形式の表現は、多くの欠点を含む。例えば、道路や河川は実際には一連の直線から構成されておらず、むしろ一連の滑らかな曲線から構成されている。その結果、ユーザに対してディスプレイ装置上で図形情報を表示するナビゲーション地図は、通常は地図細部の特徴を高度に正確には示していない。地図詳細部をより正確に表現することを企図して、地図細部を表現するために使用される直線線分の数を増すことができる。しかしながら、線分数の増加は、地図的特徴を正確に表現するために格納されなくてはならないデータの量を大幅に増大させることになる。従って、大容量の記憶装置を必要とすることなく、地図的特徴の表示情報を正確にモデル化し表示する、ナビゲーションシステム用のマッピングシステムに対する必要性が存在する。
【発明の概要】
【課題を解決するための手段】
【０００５】
（発明の開示）
地図上の地図的特徴を電子的な形態で表すために、クロソイドのような幾何学形状を使用することができる。地図は、分散型のナビゲーションシステムと接続されて、或いは通信ネットワークに接続されたナビゲーションシステムによって使用されることができる。このシステムは、クロソイドを用いて地図的特徴を表すナビゲーション用地図データを含むことができる。道路、鉄道線路、河川、湖等のような地図的特徴は、１つ又はそれ以上のクロソイドによって表すことができる。
【０００６】
一連の直線によって地図的特徴を表すのではなく、点によって接続された一連のクロソイドによって地図的特徴を表すことができる。クロソイドは、始点と始点曲率と終点と終点曲率とにより表すことができる。従って、一連の直線を用いて地図的特徴を表す公知のシステムと比べた時に、ナビゲーション用地図のパラメータを格納するのに要する記憶装置の量を低減することができる。同様に、システムに必要な記憶装置容量を増やす必要性を最少化すると共に、ナビゲーション用地図の精度を向上させることができる。
【０００７】
ナビゲーションシステムは、複数のセンサからセンサデータを受け取って、該ナビゲーションシステムのディスプレイ装置上でユーザに対して地図を発生させることができる。ナビゲーションシステムは、記憶装置内に記憶された道路又は他の地図的特徴を、データモデルにおけるクロソイドの形態で表す地図データを含むことができる。また、このシステムは、ユーザの現在位置に対応するＧＰＳシステムからのデータのようなセンサデータを受け取るナビゲーション処理装置を含むことができる。システムは、センサデータと関係付けられた地図データを記憶装置に要求して、地図データから地図画像を計算することができる。地図上におけるユーザの現在位置を示すためにユーザに対し地図画像を表示することができる。
【０００８】
本発明の他のシステム、方法、特徴、及び利点は、添付図面と以下の詳細な説明を吟味することにより当業者には明らかになるであろう。本明細書に含まれるこのような追加的なシステム、方法、特徴、及び利点の全ては、本発明の範囲内に含まれ、添付の請求項によって保護されるべきである。
本発明は、例えば、以下を提供する。
（項目１） 電子地図の地図的特徴を表すことができるデータモデルであって、第１のクロソイド経路を含み、該経路が前記地図的特徴を表す少なくとも１つのクロソイド区分を有するデータモデル。
（項目２） 前記第１のクロソイド経路が、接続点において接続された少なくとも２つのクロソイド区分を含むことを特徴とする項目１に記載のデータモデル。
（項目３） 前記第１のクロソイド経路と第２のクロソイド経路との間の連結部に形成される交差点を更に含む項目１に記載のデータモデル。
（項目４） 前記第１のクロソイド経路が主要経路を含み、第２のクロソイド経路が補助経路を含むことを特徴とする項目３に記載のデータモデル。
（項目５） 前記主要経路が曲率を含み、前記補助経路が曲率を含むことを特徴とする項目４に記載のデータモデル。
（項目６） 前記主要経路の曲率が、交差点において前記補助経路の曲率を含むことを特徴とする項目５に記載のデータモデル。
（項目７） 前記第１のクロソイド経路が第１の主要経路を含み、前記第２のクロソイド経路が第２の主要経路を含むことを特徴とする項目３に記載のデータモデル。
（項目８） 前記第１の主要経路が曲率を含み、前記第２の主要経路が曲率を含むことを特徴とする項目７に記載のデータモデル。
（項目９） 交差点において、前記第１の主要経路の曲率が前記第２の主要経路の曲率と異なることを特徴とする項目８に記載のデータモデル。
（項目１０） 電子地図の地図的特徴を表す方法であって、少なくとも１つのクロソイド区分を含む第１のクロソイド経路を用いて地図的特徴を表す段階を含む方法。
（項目１１） 前記第１のクロソイド経路と第２のクロソイド経路との間の連結部において交差点を生成する段階を更に含む項目１０に記載の方法。
（項目１２） 第１のクロソイド経路が主要経路を含み、前記第２のクロソイド経路が補助経路を含むことを特徴とする項目１１に記載の方法。
（項目１３） 前記主要経路が曲率を含み、前記補助経路が曲率を含むことを特徴とする項目１２に記載の方法。
（項目１４） 前記主要経路の曲率が、交差点において前記補助経路の曲率と等しいことを特徴とする項目１３に記載の方法。
（項目１５） 前記第１のクロソイド経路が第１の主要経路を含み、前記第２のクロソイド経路が第２の主要経路を含むことを特徴とする項目１１に記載の方法。
（項目１６） 前記第１の主要経路が曲率を含み、前記第２の主要経路が曲率を含むことを特徴とする項目１５に記載の方法。
（項目１７） 前記第１の主要経路の曲率が、交差点において前記第２の主要経路の曲率と異なることを特徴とする項目１６に記載の方法。
（項目１８） 電子地図内で表される地図的特徴を変換する方法であって、
地図的特徴の少なくとも一部を少なくとも１つのクロソイド区分に変換する段階と、
前記クロソイド区分が前記地図的特徴の一部を表していることを確認する段階と、
を含む方法。
（項目１９） 前記変換する段階が、直線データモデルをクロソイドデータモデルに変換する段階を含む項目１８に記載の方法。
（項目２０） 前記確認する段階が、前記直線データモデルにおける少なくとも１つの点と、前記クロソイドデータモデルにおける最も近い点との間の距離を求める段階を含む項目１９に記載の方法。
（項目２１） 前記距離を求める段階が、元の空間内に位置する少なくとも１つの点を、単位クロソイド空間内に位置する変換された点に変換する段階を含む項目２０に記載の方法。
（項目２２） 前記距離を求める段階が、少なくとも１つの点と単位クロソイドとの間の距離を求める段階を更に含む項目２１に記載の方法。
（項目２３） 前記距離を求める段階が、
変換された点が位置する前記単位クロソイド空間内の領域を判定する段階と、
前記求められた領域に従って前記単位クロソイド上の境界を選択する段階と、
定められた距離を識別するために、前記境界を反復的に調節する段階と、
を含む項目２２に記載の方法。
（項目２４） 前記選択された境界に従ってサンプル境界を計算する段階と、
前記サンプル境界と前記変換された点との間の距離を計算する段階と、
前記サンプル境界を調節する段階と、
前記距離を計算する段階を続行すべきか否かを判定する段階と、
を更に含み、
計算が完了している場合には、前記サンプル境界と前記変換された点との間の計算された前記距離が前記定められた距離を含み、計算が完了していない場合には、新たなサンプル境界を計算して、新たな該サンプル境界と前記変換された点との間の距離を計算する項目２３に記載の方法。
（項目２５） 前記反復は、定められた量の反復が完了した時に完了する項目２３に記載の方法。
（項目２６） 前記反復は、前記サンプル境界と前記点との間の距離が定められた許容可能な誤差値内である時に完了する項目２３に記載の方法。
（項目２７） 距離を求める段階が、求められた前記距離を前記元の空間における距離に変換する段階を更に含む項目２３に記載の方法。
（項目２８） 距離を求める段階が、求められた前記距離を前記元の空間における距離に変換する段階を更に含む項目２３に記載の方法。
（項目２９） クロソイドと点との間の距離を計算するための方法であって、
元の空間内に位置する地図的特徴の少なくとも１つの点を、単位クロソイド空間内に位置する変換された点に変換する段階と、
前記変換された点が位置する前記単位クロソイドの領域の境界を選択する段階と、
前記境界と前記変換された点との間の距離の関数として前記境界を調節して、前記地図的特徴の少なくとも１つの点を表すクロソイド区分を識別する段階と、
を含む方法。
（項目３０） 前記計算は、定められた量の反復が完了した時に完了する項目２９に記載の方法。
（項目３１） 前記計算は、サンプル境界と前記点との間の距離が定められた許容可能な誤差値内である時に完了する項目２９に記載の方法。
（項目３２） 前記距離を前記元の空間における変換された距離に変換する段階を更に含む項目２９に記載の方法。
（項目３３） 前記距離がナディアを含むことを特徴とする項目２９に記載の方法。
（項目３４） 計算された前記距離を用いて、前記クロソイド区分が前記地図的特徴の少なくとも一部を正確に表していることを確認する段階を更に含む項目２９に記載の方法。
（項目３５） ナビゲーション用アプリケーションは、計算された前記距離を利用して、地図的特徴と特定位置との間の距離を求めることを特徴とする請求項３４に記載の方法。
（項目３６） ナビゲーション用アプリケーションを実行するために、プロセッサを設ける段階を更に含む項目３５に記載の方法。
（項目３７） 前記特定位置が、プロセッサの位置を含むことを特徴とする項目３５に記載の方法。
（項目３８） プロセッサが乗物内に配置さえていることを特徴とする請求項３７に記載の方法。
（項目３９） 電子地図の地図的特徴を表示することのできるナビゲーションシステムであって、
電子地図の地図的特徴を表すことができるデータモデルを処理し、該データモデルが前記地図的特徴を表す少なくとも１つのクロソイド区分を有するクロソイド経路を含む、プロセッサと、
電子地図上に地図的特徴を表示するためのディスプレイ装置と、
を含むことを特徴とするナビゲーションシステム。
（項目４０） 前記プロセッサによりアクセス可能なナビゲーション用アプリケーションを更に含むことを特徴とする項目３９に記載のナビゲーションシステム。
（項目４１） ナビゲーション用アプリケーションが、地図的特徴と特定位置との間の距離を求めることを特徴とする項目４０に記載のナビゲーションシステム。
（項目４２） 前記特定位置が、前記プロセッサの現在の地理的位置を含むことを特徴とする項目４１に記載のナビゲーションシステム。
（項目４３） 前記プロセッサが乗物内に配置されていることを特徴とする項目４２に記載のナビゲーションシステム。
（項目４４） ネットワークを介して地図データにアクセスするためのサーバコンピュータを更に含むことを特徴とする項目３９に記載のナビゲーションシステム。
（項目４５） 前記ディスプレイ装置を用いて、前記クロソイドに沿った経路、位置、及び軌道の内の少なくとも１つを動的に表示するために、前記プロセッサと共に作動可能なセンサを更に含むことを特徴とする項目３９に記載のナビゲーションシステム。
（項目４６） 地図的特徴の少なくとも一部を、該地図的特徴を表す少なくとも１つのクロソイド区分に変換するためのプロセッサと、
前記クロソイド区分を表すデータを含む記憶装置と、
を含み、
前記プロセッサが、前記記憶装置内の前記データをクロソイドデータモデルに構成することを特徴とするデータ処理装置。
（項目４７） 前記プロセッサは、前記クロソイド区分が前記地図的特徴の一部を正確に表していることを確認することを特徴とする項目４６に記載のデータ処理装置。
（項目４８） 前記プロセッサは、前記地図的特徴の直線データモデルを前記クロソイドデータモデルに変換することを特徴とする項目４６に記載のデータ処理装置。
（項目４９） 点とクロソイドとの間の最も近い距離を求めることができるデータ処理システムであって、
（ｉ）元の空間内に位置する点を単位クロソイド空間内に位置する変換された点に変換し、（ii）前記変換された点が位置する前記単位クロソイド空間内の領域を判定し、（iii）前記判定された領域に従って前記単位クロソイド上の境界を選択し、（iv）前記選択された境界に従ってサンプル境界を計算し、（ｖ）該サンプル境界と前記点との間の距離を計算し、（vi）前記サンプル境界を調節し、（vii）一連の反復が完了したか否かを判定し、（viii）一連の反復が完了した場合には、前記サンプル境界と前記点との間の計算された前記距離は定められた距離を含み、一連の反復作業が完了していない場合には、新たなサンプル境界を計算して（ｖ）へ戻るように構成されたプロセッサを含むことを特徴とするデータ処理システム。
（項目５０） 一連の前記反復は、定められた量の反復が完了した時に完了することを特徴とする項目４９に記載のデータ処理システム。
（項目５１） 一連の前記反復は、前記サンプル境界と前記点との間の距離が定められた許容可能な誤差値内である時に完了することを特徴とする項目４９に記載のデータ処理システム。
（項目５２） 前記プロセッサが、前記計算された距離を前記元の空間における変換された距離に変換することを特徴とする項目４９に記載のデータ処理システム。
（項目５３） ナビゲーション用アプリケーションを更に含むことを特徴とする項目４９に記載のデータ処理システム。
（項目５４） 前記ナビゲーション用アプリケーションが、前記計算された距離を利用して、地図的特徴と特定点との間の距離を求めることを特徴とする項目５３に記載のデータ処理システム。
（項目５５） 前記プロセッサが、前記ナビゲーション用アプリケーションを実行することを特徴とする項目５４に記載のデータ処理システム。
（項目５６） 前記特定点が、プロセッサの現在の地理的位置を含むことを特徴とする項目５５に記載のデータ処理システム。
（項目５７） 前記プロセッサが乗物と共に配置されていることを特徴とする項目５６に記載のデータ処理システム。
（項目５８） 電子地図上に地図的特徴を表示することができるコンピュータプログラムであって、
データモデルから電子地図の地図的特徴を表すためにプロセッサによって実行可能であり、前記データモデルが前記地図的特徴を表す少なくとも１つのクロソイド区分を有するクロソイド経路を含む、プログラムコードと、
前記電子地図上に地図的特徴を表示するためにプロセッサによって実行可能なプログラムコードと、
を含むことを特徴とするコンピュータプログラム。
（項目５９） 前記プログラムコードが、前記地図的特徴と特定点との間の距離を計算することができることを特徴とする項目５８に記載のコンピュータプログラム。
（項目６０） 前記特定点が、地球投影位置決定衛星装置によって提供される現在の地理的位置を含むことを特徴とする項目５９に記載のコンピュータプログラム。
（項目６１） 前記プロセッサが乗物と共に配置されていることを特徴とする項目６０に記載のコンピュータプログラム。
（項目６２） 電子地図内で具現化される地図的特徴であって、
前記地図的特徴の少なくとも一部を表す少なくとも１つのクロソイド区分を含むクロソイド経路を含み、前記クロソイド区分が、少なくとも１つのＸＹ座標と曲率とを使用して記述されることを特徴とする地図的特徴。
（項目６３） 前記クロソイド区分が、始点と始点曲率と終点と終点曲率とを含むことを特徴とする項目６２に記載の地図的特徴。
（項目６４） 前記クロソイド区分が、始点曲率と終点曲率と長さとを用いて記述されることを特徴とする項目６２に記載の地図的特徴。
（項目６５） 交差するクロソイド経路間の連結部に形成される交差点を更に含むことを特徴とする項目６４に記載の地図的特徴。
（項目６６） 主要経路と補助経路とを更に含むことを特徴とする項目６５に記載の地図的特徴。
（項目６７） 前記主要経路が曲率を含み、補助経路が曲率を含むことを特徴とする項目６６に記載の地図的特徴。
（項目６８） 前記主要経路の曲率が、前記交差点において前記補助経路の曲率を含むことを特徴とする項目６７に記載の地図的特徴。
（項目６９） 第１の主要経路と第２の主要経路とを更に含むことを特徴とする項目６５に記載の地図的特徴。
（項目７０） 前記第１の主要経路が曲率を含み、前記第２の主要経路が曲率を含むことを特徴とする項目６９に記載の地図的特徴。
（項目７１） 前記第１の主要経路の曲率が、前記交差点において前記第２の主要経路の曲率と異なることを特徴とする項目７０に記載の地図的特徴。
（項目７２） 前記クロソイド区分が、直線、曲線、円、及びスプラインの内の少なくとも１つのを表すことを特徴とする項目６２に記載の地図的特徴。
（項目７３） 複数のクロソイド区分が、円と直線との内の少なくとも１つを表すことを特徴とする項目６２に記載の地図的特徴。
（項目７４） 前記クロソイド経路が、接続点において接続された少なくとも２つのクロソイド区分を含み、前記クロソイド区分の各々の曲率と進行方向とが、前記接続点において等しいことを特徴とする項目６２に記載の地図的特徴。
（項目７５） 前記クロソイド経路が、少なくとも２つのクロソイド区分を含むことを特徴とする項目６２に記載の地図的特徴。
（項目７６） 複数のクロソイド区分が、連結されて地図的特徴を形成することを特徴とする項目７５に記載の地図的特徴。
（項目７７） 少なくとも１つの直線によって表される地図的特徴を含む電子地図を、少なくとも１つのクロソイド区分によって表される地図的特徴に変換するための手段を更に含むことを特徴とする項目６２に記載の地図的特徴。
【図面の簡単な説明】
【０００９】
添付図面を参照しながら以下の説明を読むことにより、本発明は一層よく理解することができる。図面中の構成要素は必ずしも縮尺通りではなく、本発明の原理を説明するために強調されている。更に全ての図面を通して、同じ参照符号は対応する部分を示している。
【図１】ディスプレイ装置上に地図を生成するために地図データを利用するナビゲーションシステムを示すブロック図である。
【図２】ディスプレイ装置上に地図を生成するために地図データを利用するコンピュータネットワークシステムを示すブロック図である。
【図３】クロソイドを示すグラフである。
【図４】移動距離に対する曲率の関係を示すグラフである。
【図５】地図的特徴を表すために点によって互いに連結された１対のクロソイド区分を示す図である。
【図６】図５に示す地図的特徴を直線線分により表した図である。
【図７】クロソイドを基準化するために、クロソイドのセカントに対するベクトルの関係を示すグラフである。
【図８】クロソイドの数学的に使用可能な部分を示すグラフである。
【図９】クロソイド経路を示すグラフである。
【図１０】クロソイドのグラフの幾つかの領域への分割を示すグラフである。
【図１１】交差した２つの経路を示す図である。
【図１２】交差した２つの主要経路と１つの補助経路とを示す図である。
【図１３】直線により接続された点によって道路を表した地図を示す図である。
【図１４】図１３の地図よりも少数の点によって道路を表し、該点は求められた曲率を含む線によって接続されている地図である。
【図１５】ナディアとクロソイドから１つの点までの距離の判定を表したフローチャートである。
【図１６】クロソイドのグラフを複数領域に分割することを用いて、点までの距離を求めることを示すグラフである。
【発明を実施するための形態】
【００１０】
（発明を実施するための最良の形態）
クロソイド（コルニュ螺旋又はオイラーの螺旋としても知られている）のような幾何学形状は、電子地図上の地図的特徴を表現するのに使用することができる。この地図は、ナビゲーションシステム、或いは携帯用情報端末（ＰＤＡ）又は家庭用コンピュータのような電子地図を用いる他のシステムと共に使用することができる。また、このような地図は、無線ネットワーク、広域ネットワーク（ＷＡＮ）、ローカルエリアネットワーク（ＬＡＮ）、イントラネット及びインターネットのようなコンピュータネットワークを介してアクセスすることも可能である。このナビゲーションシステムは、携帯用システム内で使用することができ、或いは自動車、トラック、農作業機械、鉱山機械、ゴルフカート、及び移動ロボットのような乗物用に使用することができる。また、これらのナビゲーションシステムは、船舶のための周知の航路、航空機のための周知の飛行経路を作図するのに使用することができ、或いは航空機又は宇宙船の自動操縦装置と共に使用してもよい。「地図的特徴」又は「地図特徴」という用語は、道路、鉄道線路、公園、建物、河川等のような電子地図上に描くことができるどのような属性をも含むものとして広義に解釈されるべきである。
【００１１】
図１は、地図を作成し及び発生させるために地図データを利用するナビゲーションシステム１００を示すブロック図である。このナビゲーションシステム１００は、単に説明の目的で使用されているに過ぎず、ナビゲーション地図システムとは異なる他のシステムを使用してもよい。ナビゲーションシステム１００は、ディスプレイ装置１１０、ナビゲーション処理装置１２０のようなプロセッサ、ナビゲーション地図データ１３０、入力装置１４０、及び少なくとも１つのセンサ１５０を含むことができる。ディスプレイ装置１１０は、ユーザに対して地図を発生させるのに使用することができる。ディスプレイ装置１１０には、液晶ディスプレイ（ＬＣＤ），陰極線管（ＣＲＴ）、ヘッドアップディスプレイ、又は他の形式のディスプレイ装置を含むことができる。
【００１２】
ディスプレイ装置１１０は、ナビゲーション地図データ１３０にアクセスして処理することができるナビゲーション処理装置１２０と接続されて、ユーザに対し地図を表示することができる。ユーザは、入力装置１４０を介して、情報を要求し、またナビゲーションシステム１００とインターフェースをとることができる。ナビゲーションシステム１００は、通信リンク、地球投影位置決定衛星（ＧＰＳ）、基地局、又は他の送信システムのような、他の機構及び装置を含むことができる。
【００１３】
ナビゲーション地図データ１３０は、クロソイドのような１つ又はそれ以上の幾何学形状によって表現することができる地図的特徴に関するデータを含むことができる。更に、一連のクロソイドを使用して、一連の直線の配列を用いた表現よりもより正確で写実的に道路や他の地図的特徴の実際のパターンを表すことができる。クロソイドを使用することにより、地図上の位置表示の正確さを向上させることができる。正確な位置は、２つの直線が連結する点だけでなく、道路のコース全体にわたって存在する。又、少なくとも１つのクロソイドによる地図的特徴の表は、地図的特徴を表現するために一連の直線を用いるシステムよりも少数のパラメータしか必要としないことから、従って記憶装置の記憶空間を節約することが可能である。
【００１４】
センサ１５０は、ナビゲーション地図データ１３０と関係付けて使用して、ユーザの軌道と位置（例えば、経路）とを感知した状態を自動的に維持することができる。センサ１５０は、タイヤの回転速度を測定するためのホイールカウンタ、乗物の位置を測定するためのＧＰＳ装置、乗物が方向を変えた時や、航空機のための飛行データや、船舶のための現在の航行方向及び速度に関するデータ等を測定するためのジャイロを含むことができる。また、ナビゲーション処理装置１２０は、センサ及びナビゲーション地図データ１３０からの情報にアクセスして、今後の予測経路を表すことができる予測経路データを計算することができる。例えば、ディスプレイ装置は、現在のデータに基づいて今後の移動範囲をある程度示すことができる。また、ナビゲーション処理装置１２０は、センサ１５０とナビゲーション地図データ１３０とを利用して、到着推定時間、経路に関する方向、又は乗物の動きに関する他の任意の動的パラメータのような、経路に関する他の機能を実行することもできる。
【００１５】
図２は、コンピュータネットワークシステム２００に接続されたナビゲーションシステムを示すブロック図である。このコンピュータネットワークシステム２００は、地図データを送受することができ、これによりユーザが少なくとも１つのクライアント２１０から地図にアクセスすることが可能となる。クライアント２１０は、ネットワークを介してサーバ２２０に接続されている。サーバ２２０は、コンピュータ読取り可能コードを実行するプロセッサ又はコンピュータを含むことができる。このネットワークは、ＷＡＮ、ＬＡＮ、イントラネット及び／又はインターネットのような、無線及び／又は有線の通信リンクを含むことができる。サーバ２２０は、データを送るためにネットワーク又は他の任意の通信路を介してナビゲーション処理装置１２０に接続されることができる。ナビゲーション処理装置１２０により、地図又は地図データをサーバ２２０と送受することができる。ナビゲーション処理装置１２０は記憶装置を含むことができ、ナビゲーション地図データ１３０を格納するために遠隔データ記憶装置１３０と通信することができる。
【００１６】
コンピュータ及びナビゲーションシステムは、上述の諸機能を行うための命令を実行するプロセッサを含むことができる。この命令は、プロセッサによってアクセス可能な記憶装置内に格納されたプロセッサ読取り可能コードの形態とすることができる。実行可能なコードは、ハードウエア、ソフトウエア、ファームウエア、又はこれらの任意の組合せを用いて実行することができる。プロセッサは、１つ又はそれ以上の記憶装置と双方向的に通信することができる。記憶装置とプロセッサとは、地図に関するデータ、及びコンピュータとナビゲーションシステムとの動作に関する他のデータを送受することができる。データは、無線通信及び／又は有線通信で送ることができ、コンピュータネットワークを介して通信することも可能である。
【００１７】
図３は、地図の地図的特徴に関するデータを生成するのに使用することができるクロソイド３００を示すグラフである。クロソイドは、典型的には曲率が線形に変化する幾何学形状である。従って、クロソイド区分を用いて、曲線、直線、円、及びスプラインのような地図の地図的特徴を表すことができる。直線と円とはクロソイドの特別な場合であって、クロソイドの異なる区分によって表すことができる。これにより、全ての地図的特徴がクロソイドを用いてモデル化することが可能になる。直線を表すためには、ゼロに等しい曲率を有するクロソイド区分が使用される。
【００１８】
図４は、曲率と移動距離の関係を示すグラフである。この曲率−距離グラフに関して、ユーザが点１から点２に移動する場合、曲率は一定値ゼロを保つ。従ってこれに対応するｘ−ｙグラフにおいては、点１から点２まで直線が横に延びる。点２から点３までの曲率−距離グラフに関して、曲率は定常的に増大する。従って、点２と点３との間のｘ−ｙグラフは、移動距離につれて曲率が増大することを示している。クロソイドの曲率は、移動距離に正比例させることができ、例えば、曲率は移動した距離と共に一定の割合で増大することができる。
【００１９】
例えば、点２と点３との間で移動した距離の１ｍ毎に、曲率は０．０００１（１／ｍ）だけ増加する。乗物のドライバーの場合、乗物が点２と点３との間を移動する時にドライバーはステアリング・ホイールを一定の速度で一様に回転させる。点３から点４までは、移動距離全体にわたり曲率が一定に保たれる。このようにして、クロソイド区分は、地図上の地図的特徴を表すために互いに連結される。クロソイドを適用する場合には、点と点の間の線分の曲率は線形的に表すことができる。更に、他の幾何学形状を適用する場合には、曲率と距離との間の比例関係は、線形的、対数的、指数関数的等とすることができる。
【００２０】
図５は、１対のクロソイド区分Ｓ１、Ｓ２を点Ｐ１、Ｐ２、及びＰ３により互いに連結して地図的特徴を形成するクロソイドデータモデルを示す図である。各々のクロソイド区分は、デカルト座標系のｘ−ｙ軸上に置かれ、曲率値Ｋを含む始点ノード又は始点と、曲率Ｋを有するｘ−ｙ軸上の終点とによって表される。図６は、図５のクロソイドデータモデルで示したのと同じ地図的特徴を、直線データモデルにおける直線線分によって表した図である。図５と図６とを比較すると、図５に示すクロソイドの使用により、曲線を表すために点ＳＰ１−ＳＰ６の間の一連の直線線分ＳＳ１−ＳＳ５を使用する方法よりも少いデータ点を用いて、地図的特徴をより正確に表示することが可能となる。地図的特徴の曲線を表すためにクロソイドを使用することは、現在走行している道路についてのより正確な表示をナビゲーションシステムのユーザに提供する。
【００２１】
クロソイドを表す数式
クロソイドは、曲率が弧長に比例する曲線である。クロソイドは、次の式で計算することができる。
【数１】
ここで、Ｉは弧長、Ｋは曲率、ａは比例定数を表す。パラメータの形では、クロソイドの方程式は、以下の座標として表すことができる。
【数２】
【数３】
この場合、
【数４】
である。
【００２２】
全てのクロソイドは同様であるから、１に等しいパラメータ値ａ（すなわちａ＝１）を有する単位クロソイドが存在する。計算速度を向上させるために、単位クロソイドのｘ−ｙ座標値を、表（例えば、ｓｉｎ−ｃｏｓ表）に格納することができ、実際のクロソイドは、これらの値から計算することができ、ここで、ｔは指数である。ａ＝１の場合の単位クロソイドは、
【数５】
【数６】
である。
【００２３】
これらの積分は容易には解けないので、ｘ軸値とｙ軸値とを計算するために、正弦関数及び余弦関数は、次式で表されるテイラー級数に変換することができ、
【数７】
【数８】
これを、方程式に挿入する。
【数９】
【数１０】
【００２４】
従って積分は以下のように解くことができる。
【数１１】
【数１２】
τ＝０からｔの境界を用いて、テイラー級数は次のように計算することができる。
【数１３】
【数１４】
【００２５】
上に示すように、級数は任意の項数以下を切り捨て、１つの多項式が残るようにすることができる。この多項式の各項も表に格納することができる。項の数は処理系に応じて決まる。つまり、例えば６４ビットの浮動小数点数を使用する典型的なコンピュータシステムを用いる場合には、９項多項式の最終項の階乗の精度は仮数部（５３ビット）の精度に等しいことから、この多項式は９番目の項で終結することができる。ここで、
【数１５】
である。
【００２６】
上記の積分を解くために、ニュートンの補間式、或いはラグランジェ又はエイトケン−ネヴィルの補間式の使用によるような、テイラー級数以外の方法も使用できることは当業者には分かるであろう。
【００２７】
進行方向を表すγは、元のｘとｙ積分から求めることができる。
【数１６】
【００２８】
曲率Ｋによっては、パラメータｔの代わりに、ｘ、ｙ、γを使用してもよい。
ここで、
【数１７】
である。
【００２９】
ｘ、ｙ、γに対する式は次のようになる。
【数１８】
【数１９】
ここで、
【数２０】
である。
【００３０】
地図に対するクロソイドの使用
データモデル内でクロソイドを記述する方法が幾つかある。第１に、クロソイドは、曲率Ｋ0で始まり、流さｌを含み、終点曲率Ｋ1を有することができる。従って比例定数ａは、次式で計算できる。
【数２１】
【００３１】
特定の場合においては、曲率の正負符号は進行方向すなわち線の向きを表すのに適している。曲率が正の場合にはその曲線は左に進み、曲率が負の場合にはその曲線は右に進む。比例定数ａと進行方向ｄとは、次のように計算できる。
【数２２】
【数２３】
【００３２】
曲率間の差がゼロである線又は円の場合には、ａは理論的には無限大であって、これは別個に取り扱われる。例えば、始点又は終点曲率の絶対値が、最小値より小さい場合には線が使用され、最小値より大きい場合には円が使用される。
【００３３】
第２に、クロソイドは、始点Ｘ0、Ｙ0と始点曲率Ｋ0と、終点Ｘ1、Ｙ1と終点曲率Ｋ1で表すことができる。比例定数ａと回転角βは、基準化され、回転され且つ位置付けされた単位クロソイドに対して計算することができる。ここで、
【数２４】
【数２５】
である。
【００３４】
図７は、クロソイドを基準化するための、クロソイドのセカント７１０（右側のグラフ）に対するベクトル７００（左側のグラフ）の関係を示すグラフである。式２４及び２５を用いると、式の左項は始点から終点まで延びるベクトル７００を表している。式の右項は曲線上の始点から終点までのクロソイドのセカント部分７１０を表している。セカント７１０は、基準化し、回転させることができる。これらの式を容易に読み取ることができるように、下記の項を代入する。
【数２６】
【数２７】
【数２８】
【数２９】
【００３５】
従って、これらの式は次のように書き換えられる。
【数３０】
【数３１】
【００３６】
比例定数は、次のように計算できる。
【数３２】
【数３３】
ピタゴラスの定理を使用することにより、
【数３４】
比例定数ａは、次のように計算できる。
【数３５】
【数３６】
【数３７】
【数３８】
【数３９】
【００３７】
即ち、クロソイドの基準化因子ａ2は、ベクトルの長さをセカントの長さで除算したものに等しいとすることができるので、
【数４０】
従って、式４０は、クロソイドのベクトルとセカントとの間の関係を示している。
【００３８】
従って、代入された項は、次のように計算できる。
【数４１】
【数４２】
【数４３】
【数４４】
【数４５】
結果として、次のようなゼロ交差式が得られる。
【数４６】
【００３９】
比例定数ａを計算するために、第１のゼロ交差が計算される。ニュートン法は急速に収束して、少数の反復段階しか必要としないので、第１のゼロ交差を計算するためにニュートンの方法を使用することができる。
【数４７】
【００４０】
ニュートンの方法の開始値はベクトルの長さ、すなわちベクトルの始点と終点との間の距離である。
【数４８】
【００４１】
複数のゼロ交差がこれを超えて生じる特異性の限界があるであろう。従って、クロソイドの使用可能な部分は次式のように減少する。
【数４９】
（これを言葉で表現すると、ｔはマイナスルート２からプラスルート２まで生じる可能性がある）
【数５０】
【００４２】
限界を数学的に超えることは、第１のゼロ交差が複素数を有することによって示すことができる。図８は、数学的に使用可能なクロソイドの部分８００を示すグラフである。ニュートン法から得られる結果は、以下の限界によって確かめられる。
【数５１】
及び
【数５２】
又、次のゼロ交差式を用いて確認することもできる。
【数５３】
結果が限界を超えている場合には、この結果は、線又は円と同一であるとみなすこともできる。
【００４３】
比例定数ａが計算された後、回転値βが次のように計算される。
【数５４】
そして進行方向ｄが次のように計算される。
【数５５】
【００４４】
クロソイド経路の計算
図９は、道路のような地図的特徴を表すクロソイド経路９００（クロソイドスプラインとしても知られている）を示すグラフである。クロソイド経路９００は、一連に接続されたクロソイド線分９１０ａ−９１０ｄから構成されることができる。クロソイド線分９１０ａ−９１０ｄの接続点ＸＹＺγは、追加的な制約を生じる可能性がある。接続点ＸＹＫγにおいて、接続しているクロソイド区分の曲率Ｋと進行方向γは、クロソイド経路の連続性を保証するために同一とすることができる（さもなければ、本質的に道路のような地図的特徴はねじれを含むことになるであろう）。
【００４５】
接続したクロソイド区分の進行方向は、複数の反復段階を用いて整列させることができる。接続したクロソイド区分の進行方向に基づいて、曲率の変化と共に進行方向差を計算することができる。進行方向差が正ならば、曲率は増大することができる。進行方向差が負ならば、曲率は減少する。従って、
【数５６】
であり、この場合、
【数５７】
である。
【００４６】
進行方向における変化は、接続したクロソイド区分の長さｌ0及びｌ1と、各反復段階の強化を最適化するために使用される定数ｃとにより基準化することができる。過度に小さな定数ｃが選ばれた場合には、計算に長い時間がかかり、定数ｃが大き過ぎる場合には、接続が振動する可能性がある。
【００４７】
クロソイドと点との間の距離の計算
アルゴリズムは、クロソイドと点との間の距離を計算するために様々なアプリケーションで使用することができる。アルゴリズムは、コンピュータにより実行することができる。このアルゴリズムは、例えば線データモデルをクロソイドデータモデルに変換するために、クロソイド回帰計算において使用することができる。また、このアルゴリズムは、例えばＧＰＳで求められた位置を道路上の位置に整合させるために、ナビゲーション中に使用することもできる。クロソイドが単位クロソイドでない場合には、式２４及び式２５に記述された変換の逆を使用して、点は単位クロソイド空間に変換することができる。
【００４８】
単位クロソイドと変換された点との間の距離を計算するために、反復法を用いてナディア（ｎａｄｉｒ、すなわち変換された点に最も近いクロソイド上の点）を計算することができる。単位クロソイドと変換された点との間の距離ｄは、次のように計算できる。
【数５８】
この場合、
【数５９】
である。ここで、距離ｄは、単位クロソイド上の点と変換された点との間の距離の関数である。距離関数の最小値は、最初に単位クロソイドを幾つかの領域に分割することによって位置付けられる。
【００４９】
図１０は、ｄの決定に役立つ、クロソイド８００の使用可能な部分のグラフを各領域（０、１、２ａ、２ｂ、３、４、５、６ａ、６ｂ、７とする）に分割するための１つの方法を示すグラフである。各領域内では、距離関数は単峰性である。従って、この距離関数は、この領域内で１つの極小値を含むことができる。この極小値は、黄金分割法を使用して求めることができる。例えば、領域４に関して距離関数は、ｔ＝０からｔ＝１及びｔ＝平方根（−２）から計算することができる。
【００５０】
領域２及び６を除いて、全ての領域は直線によって分割することができる。領域２及び６は、１つの曲線によって領域２ａ、２ｂ、６ａ、６ｂに分割することができる。この曲線は、全ての垂線の包絡線（すなわち、クロソイド上の直立線を取り囲む曲線）とすることができる。
【００５１】
垂線は次のように計算することができる。
【数６０】
【数６１】
パラメータｕを消去することによって、
【数６２】
ここで
【数６３】
微分計算すると、
【数６４】
この式は、ピタゴラスの定理を用いることにより次のように単純化できる。
【数６５】
原始関数と導関数とを組み合わせると、
【数６６】
これを再びピタゴラスの定理を用いて簡約すると、
【数６７】
垂線に関する元の式と比較することによって、
【数６８】
垂線の包絡線に関する式は、
【数６９】
【数７０】
とすることができる（ｘの代わりにｙを使用しても同じ結果が得られる）。ここで、パラメータｔは、消去することができない。この点が曲線のどちら側に位置しているかを判定するために、パラメータｔは、Ｘに関して、次にＹに関して計算することができる。この関数は単峰性であるので、黄金分割法をここでも使用することができる。更に、Ｘ値及びＹ値は表に格納することができる。
【００５２】
黄金分割法によれば、最初に、求められた境界を開始値として使用することができる。この境界は、図１０に示すようにクロソイド８００の領域に従って求めることができる。
【数７１】
【数７２】
【００５３】
区間内の結果は、境界に関する値を用いて計算することができる。
【数７３】
【数７４】
この場合、黄金分割によれば、
【数７５】
である。
【００５４】
クロソイド上の点ｔ2と変換された点との間の距離、並びにクロソイド上の点ｔ3と変換された点との間の距離の両方を計算することができる。どちらの距離がより大きいかに応じて、境界を以下のように調節することができる。
【数７６】
そして、式７３を用いて再計算して、
【数７７】
そして、式７４を用いて再計算することができる。
【００５５】
従って、黄金分割法を用いる場合には、後続する反復の各々は、値ｔ2又はｔ3、及び距離を再計算することを含む。この反復は、ｔ0とｔ1との間の差が、求められた値よりも小さい場合に終了することができる。例えば、１０ｋｍのクロソイドに対してこの差が１ｃｍに等しくなった場合である。反復を完了することが処理系に応じて決まる場合には、反復は一定量の反復を実行し終えた後に完了してもよい。クロソイド区分は境界値ｔ0（ｔ1）によって識別され、距離ｄは誤差である。クロソイド区分は、クロソイド経路を形成するために組み合わせることができる。
【００５６】
データモデル
再び図５及び６を参照すると、直線を使用するデータモデル（図６）とクロソイド区分を使用するデータモデル（図５）との間の１つの違いは、クロソイド区分が複数の点を介して接続されることを記述している点である。直線データモデルにおいては、全ての線は別々に考察されるが、クロソイドデータモデルにおいては、複数のクロソイド区分を接続して１本のクロソイド経路を形成することができる。クロソイド経路は、道路のような地図的特徴を連続的なモデルとして表すことを可能にする。位置、曲率、及び進行方向といったパラメータを、道路上のあらゆる地点において計算することができる。
【００５７】
クロソイドは、始点ＸＹと、始点曲率Ｋと、終点Ｘ′Ｙ′と、終点曲率Ｋ′とを含む。従ってクロソイド経路は、曲率Ｋを有する複数の点を含むことができる。クロソイドデータモデル内の点は、これらが複数の形式の情報を含むことができることから、直線データモデルと比べて頑強である。更にクロソイドモデルにおいては、地図的特徴を正確に表すために必要とされる点の数を、直線データモデルの場合よりも少なくすることができる。
【００５８】
図１１は、経路Ｐ２と交差した経路Ｐ１を示している。経路Ｐ１及び２は、交差する２つの道路のような地図的特徴とすることができる。複数のクロソイド経路が互いに交差する場合、交差点Ｉが形成される。交差点Ｉでの点の記述に関しては、経路Ｐ１及びＰ２の位置ＸＹは同じものとすることができる。しかしながら経路Ｐ１及びＰ２の曲率は、個別のままである。従って、交差点Ｉにおいて、どのクロソイド部分が経路Ｐ１に対応し、またどのクロソイド部分が経路Ｐ２に対応するかを判定することができる。両方の経路Ｐ１及びＰ２に対応するクロソイド部分は、交差点を横断する主要経路を形成することができる。図１１には１つの交差点Ｉのみが示されているが、複数の交差点Ｉが存在し得るということを理解されたい。
【００５９】
図１２は、第２の主要経路Ｐ２と交差し、更に補助経路Ｐ３を含む第１の主要経路Ｐ１を示している。例えば、１つの道路が別の道路と接続しているランプが道路上に存在する場合には、このランプが補助経路Ｐ３を形成することができる。補助経路Ｐ３は、これが接続している第１の主要経路Ｐ１と同一の曲率を含むことができる。位置Ｘ，Ｙに関するパラメータは、交差点の位置を表すのに使用することができる。曲率値Ｋ0は、主要経路Ｐ１及び補助経路Ｐ３の曲率を表すのに使用することができ、曲率値Ｋ1は、主要経路Ｐ２の曲率を表すのに使用することができる。
【００６０】
ＸＹデータのＸＹＫデータへの変換
図１３は、道路１３１０が、何本かの直線により接続された幾つかの点１３２０によって表された地図１３００を示している。地図１３００は、該地図で使用されている直線データモデルを、クロソイド又は他の幾何学データモデルに変換することにより改善することができる。図１４は、図１３の地図１３００をクロソイドデータモデルで示している。道路１４００は、図１３に示す地図におけるよりも少数の点１４１０で表され、これらの点は、求められた曲率を含むクロソイドにより接続されている。直線データモデルからクロソイドデータモデルへの変換は、図１５に示すように、上記に論じた技術を用いて直線をクロソイド区分で置き換えることにより達成することができる。直線を置き換えることに加えて、図１４に示す点１４１０は、図１３に示した点１３１０とは異なる可能性があり、従ってこれらの点１３１０と対応する場合もあれば、対応しない場合もある。
【００６１】
図１５は、例えばＸＹデータ点をＸＹＫ値を有するデータ点に変換するために、ナディアとクロソイドから１つの点までの距離とを求める反復プロセスを表したフローチャートである。始めに、主要経路と補助経路との交差点に関するＸＹＫデータ点を求める。複数の経路が接続して１つの交差点を形成することができる。各経路は、交差点上で、主要方向、補助方向、又は関係なしといった３つの可能性のある方法で互いに関係付けられる。例えば、これらの経路は、「Ｔ」字交差点として関連付けることができる。「Ｔ」字の水平方向を形成する２つの経路は、主要方向とみなすことができ、残りの経路は何らの関係も形成しない。更に、高速道路の出口ランプのように、１つの経路が補助方向を形成することができる。このランプは主要経路と接続するので、補助経路の方向は主要方向と関係付けられる。
【００６２】
ブロック１５００において、計算を簡単にするために、マップ化される点は単位クロソイド空間に変換される。図１６は、単位クロソイド空間内に位置する変換された点１６００を示すグラフである。ブロック１５１０において、変換された点が位置する領域が判定される（例えば、図１６の領域３）。ブロック１５２０において、変換された点１６００が位置する領域が、領域２又は６であるかが判定される。ブロック１５３０において、領域が領域２又は６であると判定された場合には、境界ｔの内の１つは未知である。従って、例えば垂線の包絡線を計算する式を用いて、曲線の一方の側を定めてこの未知の境界を決定する。ブロック１５４０において、始点境界ｔ0及びｔ1が選択される。
【００６３】
ブロック１５５０において、サンプル境界ｔ2及びｔ3が計算される。ブロック１５６０において、ｘ（ｔ2）、ｙ（ｔ2）と変換された点（＝ｄ（ｔ2））との間の距離、及びｘ（ｔ3）、ｙ（ｔ3）と変換された点（＝ｄ（ｔ3））との間の距離が計算される（図１６）。ブロック１５７０において、境界は式７６及び式７７に記述されたように調節される。ブロック１５８０において、反復を続行するか否か、すなわち例えばｔ1とｔ2との間の計算された距離が許容可能な誤差値内であるか、或いは定められた反復回数が完了したか否かが判定される。反復が完了していない場合には、ブロック１５５０において、調節されたサンプル境界が計算される。反復が完了している場合には、ブロック１５９０において、サンプル境界ｔ2又はｔ3がナディアとして使用される。ブロック１５９５において、ナディアと計算された距離とが元の空間に変換される。
【００６４】
このプロセスは、他の点と他のクロソイドとの間の距離を計算するために繰り返すことができる。交差点の間に接続された線上の点に対して、データ点ＸＹはＸＹＫデータ点に変換することができる。
【００６５】
最もよく適合するクロソイドを求めるために、例えばガウス誤差分布曲線のようなガウス誤差低減法を使用することができる。主要方向及び補助方向は、可能性のある方向の組合せをクロソイドに変換し、交差点に最もよく適合するクロソイド区分を使用することによって計算することができる。例えば、ランプが高速道路に連結しており、その逆ではないことを確実にするために、道路の種類のような追加的な属性が考慮される。その結果として、交差点の曲率と方向とが既知である場合、どの経路が主要方向で、どの経路が補助方向であるかを特定するデータを含むことになる。従って、交差点における計算された曲率と進行方向に関するデータは一定のまま維持されるが、交差点間の幾何学形状は、例えばクロソイド経路に変換することができる。
【００６６】
本発明の様々な実施形態を説明してきたが、本発明の範囲内で更に多くの実施形態及び実装が可能であることは当業者には明らかであろう。
【特許請求の範囲】
【請求項１】
本明細書に記載の発明。
【請求項１】
本明細書に記載の発明。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【公開番号】特開２０１１−２０９３０２（Ｐ２０１１−２０９３０２Ａ）
【公開日】平成２３年１０月２０日（２０１１．１０．２０）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−１５６１４３（Ｐ２０１１−１５６１４３）
【出願日】平成２３年７月１４日（２０１１．７．１４）
【分割の表示】特願２００４−５０３８９３（Ｐ２００４−５０３８９３）の分割
【原出願日】平成１５年５月７日（２００３．５．７）
【出願人】（５９２０５１４５３）ハーマン インターナショナル インダストリーズ インコーポレイテッド (91)
【Ｆターム（参考）】
【公開日】平成２３年１０月２０日（２０１１．１０．２０）
【国際特許分類】
【出願番号】特願２０１１−１５６１４３（Ｐ２０１１−１５６１４３）
【出願日】平成２３年７月１４日（２０１１．７．１４）
【分割の表示】特願２００４−５０３８９３（Ｐ２００４−５０３８９３）の分割
【原出願日】平成１５年５月７日（２００３．５．７）
【出願人】（５９２０５１４５３）ハーマン インターナショナル インダストリーズ インコーポレイテッド (91)
【Ｆターム（参考）】
[ Back to top ]