地図データを作成する方法及び装置
本発明は、特徴を表す地図データを形成する複数の点に円弧をフィッティングするように適切にプログラムされたコンピュータを使用する方法に関する。方法は、第１の点及び少なくとも１つの中点の周囲の領域を通る円の中心が位置する領域が第１の点及び第２の点を通る線の垂直二等分線と交差するかを判定することを含む。方法は、ナビゲーション地図の作成に適しており、ナビゲーションソフトウェアを実行するように構成されたあらゆる処理装置に適用可能である。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ナビゲーション装置及びナビゲーション装置用のナビゲーション地図を作成する方法に関する。本発明の例示する実施形態は、ポータブルナビゲーション装置（いわゆるＰＮＤ）に関し、特に全地球測位システム（ＧＰＳ）信号の受信及び処理機能、並びにそれと共に使用する地図データを備えるＰＮＤに関する。更に一般的には、他の実施形態は、地図データを使用する経路計画及び好ましくはナビゲーションの機能性を提供するためにナビゲーションソフトウェアを実行するように構成されるあらゆる種類の処理装置に関する。
【背景技術】
【０００２】
ＧＰＳ（全地球測位システム）信号の受信及び処理機能を備えるポータブルナビゲーション装置（ＰＮＤ）はよく知られており、車両搭載型又は他の車両ナビゲーションシステムとして広く採用されている。
【０００３】
一般的に、現在のＰＮＤは、プロセッサ、メモリ（揮発性及び不揮発性のうちの少なくとも一方、並びに一般的にはその双方）及び前記メモリ内に格納された地図データを含む。プロセッサ及びメモリは、ソフトウェアオペレーティングシステムが設置されうる実行環境を提供するように協働し、また、ＰＮＤの機能の制御を可能にし、且つ種々の他の機能を提供するために１以上の追加のソフトウェアプログラムが提供されることは一般的なことである。
【０００４】
通常、これらの装置は、ユーザが装置とインタラクションし、且つ装置を制御できるようにする１以上の入力インタフェース、及びユーザに情報を中継する１以上の出力インタフェースとを更に備える。出力インタフェースの例には、表示装置及び可聴出力用スピーカが含まれる。入力インタフェースの例には、オン／オフ動作又は装置の他の特徴を制御する１以上の物理ボタン（ボタンは必ずしも装置自体にある必要はなく、装置が車両に内蔵されている場合はステアリングホイール上にあってもよい）及びユーザ音声を検出するマイクが含まれる。特定の好適な１つの構成において、出力インタフェースディスプレイは、ユーザが触れることで装置を動作させる際に使用する入力インタフェースを更に提供するためにタッチセンシティブディスプレイとして（又はタッチセンシティブオーバレイ等を使用して）構成されてもよい。
【０００５】
多くの場合、この種の装置は、電力及びオプションとしてデータ信号を装置に対して送受信する際に使用する１以上の物理コネクタインタフェースを含み、オプションとして、セルラ電気通信、並びに例えばＷｉ−Ｆｉ及びＷｉ−Ｍａｘ ＧＳＭ等の他の信号及びデータネットワークを介する通信を可能にする１以上の無線送信機／受信機を含む。
【０００６】
この種のＰＮＤ装置は、場所データを含む衛星放送信号を受信し、且つその後装置の現在地を判定するために処理する際に使用するＧＰＳアンテナを更に含む。
【０００７】
ＰＮＤ装置は、現在の角度及び直線加速度、また、ＧＰＳ信号から導出された位置情報とともに速さ、並びに装置及び当該装置が搭載される車両の相対的な変位を判定するために処理される信号を生成する電子ジャイロスコープ及び加速度計を更に含んでもよい。通常、そのような機能は車両搭載型のナビゲーションシステムに提供されるのが最も一般的であるが、ＰＮＤ装置に備えることが得策である場合にはＰＮＤ装置に備えてもよい。
【０００８】
そのようなＰＮＤの有用性は、主に、第１の場所（一般に、出発地又は現在地）と第２の場所（一般に、目的地）との間の経路を判定する機能にある。装置のユーザは、多種多様な種々の方法、例えば郵便番号、道路名及び番地、以前に格納した「既知」の目的地（有名な場所、公共の場所（運動場又は水泳プール等）又は他の地点情報等）、並びにお気に入りの目的地又は最近訪れた目的地のいずれかにより、これらの場所を入力する。
【０００９】
一般にＰＮＤは、地図データから出発地の住所の場所と目的地の住所の場所との間の「最善」又は「最適」な経路を算出することがソフトウェアにより可能になる。「最善」又は「最適」な経路は、所定の基準に基づいて判定され、必ずしも最速又は最短の経路である必要はない。運転者を案内する経路の選択は非常に複雑となり得、選択された経路は、既存の予測された動的に且つ／又は無線で受信された交通及び道路情報、道路速度に関する履歴情報、並びに道路選択を判定する要因に対する運転者自身の好みを考慮してもよい（例えば運転者は、経路が高速道路又は有料道路を含むべきでないことを指定してもよい）。
【００１０】
更に装置は、道路及び交通状況を継続的に監視し、状況変化によりとられる残りの行路に対して経路を変更することを提案又は選択してもよい。種々の技術（例えば、移動電話データ交換、固定カメラ、ＧＰＳ車両追跡）に基づくリアルタイム交通監視システムは、交通遅滞を識別し、その情報を通知システムに供給するために使用されている。
【００１１】
この種のＰＮＤは、一般に、車両のダッシュボード又はフロントガラスに搭載されてもよいが、車両のラジオの内蔵コンピュータの一部又は実際には車両自体の制御システムの一部として形成されてもよい。ナビゲーション装置は、ＰＤＡ（ポータブルデジタルアシスタント）、メディアプレーヤ又は移動電話等のハンドヘルドシステムの一部であってもよい。これらの場合、ハンドヘルドシステムの標準的な機能は、経路計算及び計算された経路に沿ったナビゲーションの双方を実行するためにソフトウェアを装置にインストールすることにより拡張される。
【００１２】
経路計画及びナビゲーション機能は、適切なソフトウェアを実行するデスクトップ又は移動計算リソースにより提供されてもよい。例えば、ロイヤル・オートモービルクラブ（ＲＡＣ：Royal Automobile Club）は、http://www.rac.co.ukにおいてオンライン経路計画及びナビゲーション機能を提供する。この機能により、ユーザは出発地及び目的地を入力でき、その後ユーザのＰＣが接続されるサーバは、経路（経路の様子はユーザにより指定されてもよい）を計算し、地図を生成し、選択した出発地から選択した目的地までユーザを案内するための包括的なナビゲーション命令の集合を生成する。また当該機能は、計算経路の擬似３次元レンダリングを提供し、ユーザが経路に沿って移動することをシミュレートし、且つそれにより計算された経路のプレビューをユーザに提供する経路プレビュー機能を提供する。
【００１３】
ＰＮＤにおいて、経路が計算されると、ユーザはオプションとして提案された経路のリストから所望の計算された経路を選択するためにナビゲーション装置とインタラクションする。オプションとして、ユーザは、例えば特定の経路、道路、場所又は基準が特定の行程に対して回避されること又は必須であることを指定することにより経路選択処理を仲介又は誘導してもよい。ＰＮＤの経路計算の側面は１つの主要機能を形成し、そのような経路に沿ったナビゲーションは別の主要機能である。
【００１４】
計算された経路に沿ったナビゲーションがなされている間、このようなＰＮＤは、経路の終点、すなわち所望の目的地まで選択した経路に沿ってユーザを案内するための視覚的命令及び可聴命令の少なくともいずれかを提供するのが一般的である。また、ＰＮＤは、ナビゲーション中に画面上に地図情報を表示するのが一般的である。このような情報は、表示された地図情報が装置の現在地及び従って装置が車両搭載型のナビゲーションに使用されている場合はユーザの現在地又はユーザの車両の現在地を表すように画面上で定期的に更新される。
【００１５】
一般に画面上に表示されたアイコンは、装置の現在地を示し、装置の現在地近傍の現在の道路及び周囲の道路の地図情報と共に中央に置かれ、他の地図の特徴も表示される。更にナビゲーション情報は、オプションとして表示された地図情報の上側、下側又は片側のステータスバーに表示されてもよく、ナビゲーション情報の例には、ユーザが走行する必要のある現在の道路から次の進路変更までの距離が含まれ、場合によってはその進路変更の特性は、例えば左折又は右折である特定の種類の進路変更を示す更なるアイコンで表される。またナビゲーション機能は、経路に沿ってユーザを案内する際に使用される可聴命令の内容、継続時間及びタイミングを判定する。理解されるように、「１００ｍ先を左折」等の単純な命令は、かなりの処理及び分析を必要とする。上述したように、装置とのユーザインタラクションは、タッチスクリーンによって行われてもよく、更に又はあるいはステアリングコラムリモコン、音声起動又は他の適切なあらゆる方法によって行われてもよい。
【００１６】
装置により提供された更なる重要な機能は、ユーザがナビゲーション中に事前に計算された経路から外れた（偶然又は意図的に）場合、別の経路の方が適切であることをリアルタイム交通状況が指示し、且つ装置がそのような状況を自動的に認識することを適切に可能にされる場合、又はユーザが何らかの理由で能動的に装置に経路を再計算させる場合の自動経路再計算である。
【００１７】
またユーザが規定した基準で経路を計算できることは既知である。例えばユーザは、装置により景色のよい経路が計算されることを好んでもよく、あるいは交通渋滞が起こる可能性が高いか、起こることが予想されるか又は現在起こっているあらゆる道路を回避することを要求してもよい。次に、装置のソフトウェアは種々の経路を計算し、例えば景色が美しい所としてタグ付けされた地点情報（ＰＯＩとして既知である）を経路に沿って最も多く含む経路をより有利に重み付けするか、あるいは特定の道路上の交通状況を示す格納情報を使用することにより、起こる可能性のある渋滞又はそのために起こる遅滞のレベルに関して計算経路を順序付けする。更に他のＰＯＩに基づく経路計算及びナビゲーション基準、並びに交通情報に基づく経路計算及びナビゲーション基準が可能である。
【００１８】
経路計算及びナビゲーション機能はＰＮＤの全体的な有用性に対して必須であるが、装置を純粋に情報表示に使用できる。すなわち、装置の現在地に関連する地図情報のみが表示され、経路が全く計算されておらず、装置が現在ナビゲーションを全く実行していない「フリードライビング」用に使用できる。多くの場合、このような動作モードは、移動するのに使用するように要求される経路をユーザが既に認識しており、ナビゲーション支援を必要としない場合に適用可能である。
【００１９】
上述のこの種の装置、例えばＴｏｍＴｏｍ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｂ．Ｖ．が製造及び供給する７２０Ｔモデルは、ユーザがある位置から別の位置まで運転できるようにする信頼できる手段を提供する。
【００２０】
ナビゲーション装置と共に使用する地図データは、一般に道路形状を示す数十万又は数百万もの点を含む。例えば１つの道路は、道路の進路を示す複数の中間点により表される。しかし、地図データを格納するのに必要なメモリは、サイズが大きく且つ高価である場合が多く、それによりナビゲーション装置又はデータ記憶装置又は新しい地図データを含む媒体のコストは高くなる。
【００２１】
本発明の目的は、この問題に対処することであり、特に道路等の実際の物理的実体の忠実な表現を保持しつつ地図データのサイズを減少することである。
【発明の概要】
【課題を解決するための手段】
【００２２】
この目的のために、本発明の現在の好適な実施形態は、複数の点に円弧をフィッティングするように適切にプログラムされたコンピュータを使用する方法であって、第１の点と少なくとも１つの中点の周囲の領域とを通る円の中心が位置する領域が、第１の点及び第２の点を通る線の垂直二等分線と交差するかを判定する構成を有する方法を提供する。
【００２３】
本発明の別の実施形態は、実行環境で実行された時に第１の点と少なくとも１つの中間点の周囲の領域とを通る円の中心が位置する領域が、第１の点及び第２の点を通る線の垂直二等分線と交差するか否かをプロセッサに判定させるように動作可能である１以上のソフトウェアモジュールを含むコンピュータソフトウェアに関する。
【００２４】
本発明の更に別の実施形態は、プロセッサと、プロセッサに動作可能に接続されたメモリと、を備え、メモリは複数の点を含み、プロセッサは、第１の点と少なくとも１つの中間点の周囲の領域とを通る円の中心が位置する領域が、第１の点及び第２の点を通る線の垂直二等分線と交差するか否かを判定するように構成されることを特徴とする装置に関する。
【００２５】
これらの実施形態の利点については以下に説明する。これらの実施形態の各々の更なる詳細及び特徴は、添付の従属請求項及び以下の詳細な説明の中で規定される。
【００２６】
本発明の教示の種々の態様及びそれらの教示を採用する構成について、添付の図面を参照して例として以下に説明する。
【図面の簡単な説明】
【００２７】
【図１】全地球測位システム（ＧＰＳ）を示す概略図である。
【図２】ナビゲーション装置を提供するように構成された電子構成要素を示す概略図である。
【図３】ナビゲーション装置が無線通信チャネルを介して情報を受信できる方法を示す概略図である。
【図４Ａ】、
【図４Ｂ】ナビゲーション装置を示した透視図である。
【図５】線分群、並びに第１の点及び終点を通る円弧を形成する３つの点と、中間点を囲む誤差円を示す図である。
【図６】１つの点、別の点を囲む誤差円、並びに誤差円の内側に接する円の集合及び誤差円の外側に接する円の集合により形成された軌跡を示す図である。
【図７】複数の点の間に形成された複数の双曲線の交差を示す図である。
【図８】本発明の一実施形態を形成する方法を示すフローチャートである。
【図９】第１の点及び第２の点を通る線と弧との間の距離の値を計算する方法を示すフローチャートである。
【図１０】双曲線に対する近似を示す図である。
【図１１】最大線形偏差を示す近似によりフィッティングされた線分群を形成する複数の点を示す図である。
【図１２】最大角偏差を示す近似によりフィッティングされた線形群を形成する複数の点を示す図である。
【図１３】複数の点により形成された線形群と線形群を近似する円弧との比較を示す図である。
【発明を実施するための形態】
【００２８】
次に、本発明の好適な実施形態について、特にＰＮＤを参照して説明する。しかし、本発明の教示はＰＮＤに限定されず、経路計画及びナビゲーション機能を提供するためにナビゲーションソフトウェアを実行するように構成されるいかなる種類の処理装置にも例外なく適用可能である。故に、本出願において、ナビゲーション装置は、ＰＮＤ、車両に内蔵されたナビゲーション装置、あるいは実際には経路計画及びナビゲーションソフトウェアを実行するコンピューティング資源（デスクトップ又はポータブルパーソナルコンピュータ（ＰＣ）、移動電話、あるいはポータブルデジタルアシスタント（ＰＤＡ））として実装されるか否かにかかわらず、いかなる種類の経路計画及びナビゲーション装置も（無制限に）含むことを意図する。
【００２９】
本発明の教示は、ユーザが１つの地点から別の地点までの運転方法に関する指示を要求していないが単に所定の場所のビューを提供してほしい状況においても有用であることが以下から明らかとなるだろう。このような状況において、ユーザが選択した「目的地」の場所は、ユーザが運転を開始したい対応する出発地を有する必要はないため、本明細書で「目的地」の場所又は実際には「目的地」のビューを参照することは、経路の生成が不可欠であること、「目的地」まで移動する必要があること又は実際には目的地の存在が対応する出発地の名称を必要とすることを意味すると解釈されるべきではない。
【００３０】
上記を踏まえ、図１はナビゲーション装置により使用可能な全地球測位システム（ＧＰＳ）の一例を示す図である。そのようなシステムは周知であり、種々の目的に使用される。一般に、ＧＰＳは、連続的な位置、速度、時間及びいくつかの例においては方向情報を無数のユーザに対して判定できる衛星無線ナビゲーションシステムである。
【００３１】
以前はＮＡＶＳＴＡＲとして周知であったが、ＧＰＳは極めて正確な軌道で地球と共に動作する複数の衛星を使用する。これらの正確な軌道に基づいて、ＧＰＳ衛星は、それらの場所を任意の数の受信装置に中継できる。
【００３２】
ＧＰＳデータを受信する能力を特別に備える装置がＧＰＳ衛星信号に対する無線周波数の走査を開始する場合、ＧＰＳシステムは実現される。ＧＰＳ衛星から無線信号を受信すると、装置は、複数の異なる従来の方法のうちの１つを用いて、その衛星の正確な場所を判定する。殆どの例において、装置は、少なくとも３つの異なる衛星信号を取得するまで信号の走査を継続する（尚、位置は、通常は２つの信号のみでは判定されないが、他の三角測量技術を使用して２つの信号から判定することもできる）。幾何学的三角測量を実現する場合、受信機は、３つの既知の位置を利用して、衛星に対する自身の２次元位置を判定する。これは、周知の方法で行われる。更に、第４の衛星信号を取得することにより、受信装置は、同一の幾何学計算によって周知の方法でその３次元位置を計算できる。位置及び速度データは、無数のユーザにより連続的にリアルタイムで更新可能である。
【００３３】
図１に示すように、ＧＰＳシステム全体を参照番号１００で示す。複数の衛星１２０は、地球１２４の周囲の軌道上にある。各衛星１２０の軌道は、他の衛星１２０の軌道と必ずしも同期せず、実際には非同期であることが多い。ＧＰＳ受信機１４０は、種々の衛星１２０からスペクトル拡散ＧＰＳ衛星信号１６０を受信するように示される。
【００３４】
各衛星１２０から連続的に送信されるスペクトル拡散信号１６０は、極めて正確な原子時計を用いて達成される非常に正確な周波数標準を利用する。各衛星１２０は、そのデータ信号送信１６０の一部として、その特定の衛星１２０を示すデータストリームを送信する。一般に、ＧＰＳ受信機１４０が三角測量によりその２次元位置を計算するために、ＧＰＳ受信機１４０は少なくとも３つの衛星１２０からスペクトル拡散ＧＰＳ衛星信号１６０を取得することが当業者には理解される。更なる信号を取得すると、全部で４つの衛星１２０から信号１６０を取得する結果となり、これによってＧＰＳ受信機１４０は、その３次元位置を周知の方法で計算できる。
【００３５】
図２は、本発明の好適な実施形態に係るナビゲーション装置２００の電子構成要素の実例となる図である。尚、ナビゲーション装置２００のブロック図は、ナビゲーション装置の全ての構成要素を含むものではなく、構成要素の多くの例を表すにすぎない。
【００３６】
ナビゲーション装置２００は、筐体（不図示）内に位置付けられる。筐体は、入力装置２２０及び表示画面２４０に接続されるプロセッサ２１０を含む。入力装置２２０は、キーボード装置、音声入力装置、タッチパネル、及び情報を入力するために利用される他の任意の周知の入力装置のうちの少なくとも１つを含むことができ、表示画面２４０は、例えばＬＣＤディスプレイ等の任意の種類の表示画面を含むことができる。特定の好適な構成において、入力装置２２０及び表示画面２４０は、タッチパッド又はタッチスクリーン入力を含む一体型入力表示装置に一体化され、その場合、ユーザは、複数の表示選択肢のうちの１つを選択するか又は複数の仮想ボタンのうちの１つを操作するために、表示画面２４０の一部分に接触するだけでよい。
【００３７】
ナビゲーション装置は、出力装置２６０、例えば可聴出力装置（例えばスピーカ）を含みうる。出力装置２６０がナビゲーション装置２００のユーザに対して可聴情報を生成できるため、同様に、入力装置２４０は入力音声コマンドを受信するマイク及びソフトウェアを更に含むことができると理解されるべきである。
【００３８】
ナビゲーション装置２００において、プロセッサ２１０は、接続２２５を介して入力装置２４０に動作可能に接続され且つ入力装置２２０から入力情報を受信するように設定される。また、プロセッサ２１０は、情報を出力するために、表示画面２４０及び出力装置２６０のうちの少なくとも一方に出力接続２４５を介して動作可能に接続される。更に、プロセッサ２１０は、接続２３５を介してメモリ２３０に動作可能に接続され、接続２７５を介して入出力（Ｉ／Ｏ）ポート２７０との間で情報を送受信するように更に構成される。この場合、Ｉ／Ｏポート２７０は、ナビゲーション装置２００の外部のＩ／Ｏ装置２８０に接続可能である。外部Ｉ／Ｏ装置２８０は、例えばイヤホン等の外部聴音装置を含んでもよいが、これに限定されない。更に、Ｉ／Ｏ装置２８０への接続は、例えばハンズフリー動作と音声起動動作との少なくとも一方のため、イヤホン又はヘッドフォンへの接続のため、並びに／あるいは例えば移動電話への接続のためのカーステレオユニット等の他の任意の外部装置への有線接続又は無線接続であってもよい。この場合、移動電話接続は、ナビゲーション装置２００とインターネット又は例えば他の任意のネットワークとの間のデータ接続を確立するためと、インターネット又は例えば他の任意のネットワークを介するサーバへの接続を確立するためとの少なくとも一方のために使用されてもよい。
【００３９】
図２は、接続２５５を介するプロセッサ２１０とアンテナ／受信機２５０との間の動作可能な接続を更に示す。この場合、アンテナ／受信機２５０は、例えばＧＰＳアンテナ／受信機であってもよい。参照番号２５０で示されるアンテナ及び受信機は、図示のために概略的に組み合わされるが、アンテナ及び受信機は、別個に位置する構成要素であってもよく、アンテナは、例えばＧＰＳパッチアンテナ又はヘリカルアンテナであってもよいことが理解されるだろう。
【００４０】
更に、図２に示す電子構成要素が従来の方法で電源（不図示）により電力を供給されることが当業者には理解されるだろう。当業者により理解されるように、図２に示す構成要素の異なる構成が本願の範囲内で考えられる。例えば、図２に示す構成要素は、有線接続と無線接続との少なくとも一方等を介して互いに通信状態にあってもよい。従って、本願のナビゲーション装置２００の範囲は、ポータブル又はハンドヘルドナビゲーション装置２００を含む。
【００４１】
更に、図２のポータブル又はハンドヘルドナビゲーション装置２００は、例えば自転車、オートバイ、自動車又は船舶等の乗物に周知の方法で接続されるか又は「ドッキング」される。その場合、そのようなナビゲーション装置２００は、ポータブル又はハンドヘルドナビゲーションとして使用するために、ドッキング場所から取り外し可能である。
【００４２】
図３を参照すると、ナビゲーション装置２００は、デジタル接続（例えば、周知のＢｌｕｅｔｏｏｔｈ技術を介するデジタル接続）を確立する移動装置（図示せず）（移動電話、ＰＤＡ、及び移動電話技術を用いる任意の装置のうちの少なくとも１つ等）を介して、サーバ３０２との「モバイル」あるいは電気通信ネットワーク接続を確立してもよい。そうして、そのネットワークサービスプロバイダを介して、移動装置は、サーバ３０２とのネットワーク接続を（例えば、インターネットを介して）確立できる。そのため、「モバイル」ネットワーク接続は、情報に対する「リアルタイム」又は少なくとも非常に「最新」のゲートウェイを提供するために、ナビゲーション装置２００（単体時、及び車載走行時の少なくとも一方において移動可能であり且つ多くの場合移動している）とサーバ３０２との間に確立される。
【００４３】
例えばインターネット（ワールドワイドウェブ等）を使用して、移動装置（サービスプロバイダを介する）とサーバ３０２等の別の装置との間にネットワーク接続を確立することは、周知の方法で行われうる。これは、例えばＴＣＰ／ＩＰ層プロトコルの使用を含む。移動装置は、ＣＤＭＡ、ＧＳＭ、ＷＡＮ等の任意の数の通信規格を利用できる。
【００４４】
そのため、例えば移動電話又はナビゲーション装置２００内の移動電話技術を介するデータ接続を介して達成されるインターネット接続が利用されてもよい。この接続の場合、サーバ３０２とナビゲーション装置２００との間のインターネット接続が確立される。これは、例えば、移動電話又は他の移動装置及びＧＰＲＳ（汎用パケット無線サービス）接続（ＧＰＲＳ接続は、通信会社により提供される移動装置用高速データ接続であり、ＧＰＲＳはインターネットへの接続方法である）を介して行われうる。
【００４５】
更に、ナビゲーション装置２００は、移動装置とのデータ接続を完成し、例えば既存のＢｌｕｅｔｏｏｔｈ技術を介して周知の方法でインターネット及びサーバ３０２とのデータ接続を最終的に完成する。この場合、例えばデータプロトコルは、ＧＳＭ規格に対するデータプロトコル規格であるＧＳＲＭ１等の任意の数の規格を利用できる。
【００４６】
ナビゲーション装置２００は、ナビゲーション装置２００自身の中に、自身の移動電話技術を含んでもよい（例えばアンテナを含む、あるいはオプションとしてナビゲーション装置２００の内部アンテナを用いる）。ナビゲーション装置２００内の移動電話技術は、上述のような内部構成要素を含むことができ、且つ／又は例えば必要な移動電話技術とアンテナとの少なくとも一方を備える挿入可能なカード（例えば加入者識別モジュールあるいはＳＩＭカード）を含むことができる。そのため、ナビゲーション装置２００内の移動電話技術は、任意の移動装置の方法と同様の方法で、例えばインターネットを介して、ナビゲーション装置２００とサーバ３０２との間にネットワーク接続を同様に確立できる。
【００４７】
ＧＲＰＳ電話設定の場合、移動電話の機種、製造業者等の多様な範囲に関して正しく動作するために、Ｂｌｕｅｔｏｏｔｈ対応のナビゲーション装置が使用されてもよく、機種／製造業者専用設定は、例えばナビゲーション装置２００に格納されてもよい。この情報のために格納されたデータは更新されうる。
【００４８】
図３において、ナビゲーション装置２００は、多くの異なる、いずれの装置により実装されうる汎用通信チャネル３１８を介して、サーバ３０２と通信するものとして示されている。通信チャネル３１８を介する接続がサーバ３０２とナビゲーション装置２００との間に確立される場合、本願のサーバ３０２及びナビゲーション装置２００は通信可能である（尚、そのような接続は、移動装置を介するデータ接続、インターネットを介するパーソナルコンピュータを介する直接接続等である）。
【００４９】
サーバ３０２は、図示しない他の構成要素に加えて、メモリ３０６に動作可能に接続され且つ有線又は無線接続３１４を介して大容量データ記憶装置３１２に動作可能に更に接続されるプロセッサ３０４を含む。更に、プロセッサ３０４は、通信チャネル３１８を介してナビゲーション装置２００と情報の送受信を行うために、送信機３０８及び受信機３１０に動作可能に接続される。送受信される信号は、データ信号、通信信号及び又は他の伝搬信号を含んでもよい。送信機３０８及び受信機３１０は、ナビゲーション装置２００の通信設計において使用される通信条件及び通信技術に従って選択又は設計されてもよい。尚、送信機３０８及び受信機３１０の機能は、信号送受信機に組み合わされてもよい。
【００５０】
サーバ３０２は、大容量記憶装置３１２に更に接続される（又は、大容量記憶装置３１２を含む）。尚、大容量記憶装置３１２は、通信リンク３１４を介してサーバ３０２に結合されてもよい。大容量記憶装置３１２は、ナビゲーションデータ及び地図情報のストアを含む。また、大容量記憶装置３１２は、サーバ３０２とは別個の装置であってもよく、サーバ３０２に組み込まれてもよい。
【００５１】
ナビゲーション装置２００は、通信チャネル３１８を介してサーバ３０２と通信するように構成され、図２に関して上述したように、プロセッサ、メモリ等を含み、更に、通信チャネル３１８を介して信号及び／又はデータを送出する送信機３２０及び受信する受信機３２２を含む。尚、これらの装置は、サーバ３０２以外の装置と通信するためにも使用される。更に、送信機３２０及び受信機３２２は、ナビゲーション装置２００の通信設計において使用される通信条件及び通信技術に従って選択又は設計され、送信機３２０及び受信機３２２の機能は、単一の送受信機に組み合わされてもよい。
【００５２】
サーバメモリ３０６に格納されるソフトウェアは、プロセッサ３０４に命令を提供し、サーバ３０２がナビゲーション装置２００にサービスを提供できるようにする。サーバ３０２により提供される１つのサービスは、ナビゲーション装置２００からの要求の処理及び大容量データ記憶装置３１２からナビゲーション装置２００へのナビゲーションデータの送信を含む。サーバ３０２により提供される別のサービスは、所望のアプリケーションに対する種々のアルゴリズムを使用したナビゲーションデータの処理及びナビゲーション装置２００へのこれらの計算の結果の送出を含む。
【００５３】
一般に、通信チャネル３１８は、ナビゲーション装置２００とサーバ３０２とを接続する伝搬媒体又はパスを表す。サーバ３０２及びナビゲーション装置２００の双方は、通信チャネルを介してデータを送信する送信機及び通信チャネルを介して送信されたデータを受信する受信機を含む。
【００５４】
通信チャネル３１８は、特定の通信技術に限定されない。更に、通信チャネル３１８は、単一の通信技術に限定されない。すなわち、チャネル３１８は、種々の技術を使用する複数の通信リンクを含んでもよい。例えば、通信チャネル３１８は、電気通信、光通信、及び電磁通信のうちの少なくとも１つ等のためのパスを提供するように構成されることができる。そのため、通信チャネル３１８は、電気回路、ワイヤ及び同軸ケーブル等の電気導体、光ファイバケーブル、コンバータ、無線周波数（ＲＦ）波、大気、空間等のうちの１つ又はそれらの組み合わせを含むが、それらに限定されない。更に、通信チャネル３１８は例えば、ルータ、リピータ、バッファ、送信機及び受信機等の中間装置を含むことができる。
【００５５】
１つの例示的な装置において、通信チャネル３１８は、電話及びコンピュータネットワークを含む。更に、通信チャネル３１８は、無線周波数、マイクロ波周波数、赤外線通信等の無線通信に適応できてもよい。更に、通信チャネル３１８は衛星通信に適応できる。
【００５６】
通信チャネル３１８を介して送信される通信信号は、所定の通信技術に必要とされるか又は望まれる信号を含むが、それらに限定されない。例えば、信号は、時分割多元接続（ＴＤＭＡ）、周波数分割多元接続（ＦＤＭＡ）、符号分割多元接続（ＣＤＭＡ）、グローバル・システム・フォー・モバイル・コミュニケーションズ(Global System for Mobile Communications)（ＧＳＭ）等のセルラ通信技術において使用されるように構成されてもよい。デジタル信号及びアナログ信号の双方が通信チャネル３１８を介して送信できる。これらの信号は、通信技術にとって望ましい変調信号、暗号化信号、及び圧縮信号のうちの少なくとも１つであってもよい。
【００５７】
サーバ３０２は、無線チャネルを介してナビゲーション装置２００によりアクセス可能なリモートサーバを含む。サーバ３０２は、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、仮想プライベートネットワーク（ＶＰＮ）等に位置するネットワークサーバを含んでもよい。
【００５８】
サーバ３０２は、デスクトップ又はラップトップコンピュータ等のパーソナルコンピュータを含んでもよく、通信チャネル３１８は、パーソナルコンピュータとナビゲーション装置２００との間に接続されるケーブルであってもよい。あるいは、パーソナルコンピュータは、ナビゲーション装置２００とサーバ３０２との間に接続されて、サーバ３０２とナビゲーション装置２００との間にインターネット接続を確立してもよい。あるいは、インターネットを介してナビゲーション装置２００をサーバ３０２に接続するために、移動電話又は他のハンドヘルド装置がインターネットへの無線接続を確立してもよい。
【００５９】
ナビゲーション装置２００は、情報ダウンロードを介してサーバ３０２から情報を与えられてもよい。情報は、自動的あるいはユーザがナビゲーション装置２００をサーバ３０２に接続する場合に周期的に更新されてもよく、且つ／又は例えば無線移動接続装置及びＴＣＰ／ＩＰ接続を介してサーバ３０２とナビゲーション装置２００との間に接続がより継続して又は頻繁に確立される場合に更に動的に更新されてもよい。多くの動的計算のために、サーバ３０２内のプロセッサ３０４が大量の処理要求を処理するために使用されてもよい。しかし、ナビゲーション装置２００のプロセッサ２１０も同様に、多くの場合においてはサーバ３０２への接続に関係なく、多くの処理及び計算を処理できる。
【００６０】
図２に示す様に、ナビゲーション装置２００はプロセッサ２１０、入力装置２２０、表示画面２４０を含む。入力装置２２０及び表示画面２４０は、例えばタッチパネルスクリーンを介して情報（直接入力、メニュー選択など）を入力すること及び情報を表示することとの両方を可能にするために、一体型入力表示装置に統合される。このようなスクリーンは、当業者には周知のものであるように、例えばタッチ入力ＬＣＤスクリーンであってもよい。更に、ナビゲーション装置２００は、例えばオーディオ入力／出力装置などの、更なる任意の入力装置２２０と更なる任意の出力装置２４１との少なくとも一方を有しても良い。
【００６１】
図４Ａ及び図４Ｂは、ナビゲーション装置２００の斜視図を示している。図４Ａに示すように、ナビゲーション装置２００は、一体型入力表示装置２９０（例えばタッチパネル画面）と図２の他の構成要素（内蔵ＧＰＳ受信機２５０、マイクロプロセッサ２１０、電源、メモリシステム２３０などを含むがこれに限定されない）を含むユニットであっても良い。
【００６２】
ナビゲーション装置２００は、アーム２９２上に備え付けられても良い。このアーム２９２は、吸着カップ２９４を用いて、車両のダッシュボード／窓／等に固定されても良い。このアーム２９２は、ナビゲーション装置２００がドッキング可能なドッキングステーションの一例である。
【００６３】
図４Ｂに示すように、ナビゲーション装置２００は、例えば、アーム２９２に対してナビゲーション装置２９２をスナップ接続することで、ドッキングステーションのアーム２９２にドッキング若しくは接続することができる。図４Ｂにおける矢印で示すように、ナビゲーション装置２００は、アーム２９２上で回転可能である。ナビゲーション装置２００とドッキングステーションとの間の接続を解除するためには、例えば、ナビゲーション装置２００上のボタンを押下すればよい。ドッキングステーションに対してナビゲーション装置を結合及び分離する他の同等の適切な構成は当業者には既知である。
【００６４】
上述したように、地図データは、道路等の実際の特徴を表すために折れ線又は線形群を形成する複数の点を含む。しかし、地図データを簡略化して地図データを圧縮することにより地図データに必要な記憶容量を減少することが望ましい。更に、道路等の実際の特徴の表現を改善することにより地図データを更に視覚的に魅力的にすることが望ましい。
【００６５】
本発明の実施形態は、円弧を使用して地図データを簡略化しようとする。特に本発明の実施形態は、複数の点と交差する進路を近似する円弧によりそれらの点を置換することにより地図データを簡略化する。
【００６６】
以下の式を使用して線形群及び弧を形成する各点からの平方距離Ｒの合計を最小にしようとする最小二乗フィッティングを使用して円弧を点の集合にフィッティングできる。
式中、
は点ｐ０とｐｎとの間の円弧を示す。
【００６７】
しかし、最小二乗フィッティングの主な欠点は、線形群に対して可能な全てのショートカットを見つけることは計算的に非効率的であることである。例えば点ｐｉ，．．．，ｐｊの集合に対して、弧がｐｉとｐｋとの間で可能であるかを設定することは、弧がｐｉとｐｋ＋１との間で可能であるかを設定しないため、最小二乗フィッティングアルゴリズムは、線形群の可能な各小区分を計算的に評価することを必要とし、計算コストは高くなり且つ遅い。しかし、本発明の実施形態は、始点、終点、及び全ての中間点のそれぞれを囲む誤差円を通る弧の形成が可能であるかを事前に判定でき、それにより計算リソースの浪費を回避する。
【００６８】
本発明の一実施形態について説明する。本発明の実施形態は、以下に説明するように、可能な場合には、第１の点から開始して第２の点で終了し、且つ第１の点及び第２の点の間に存在する１以上の点の誤差円を通過する円弧で線形群を置換することを目的とする。
【００６９】
図５を参照すると、元の地図データでは線分４００、４０１により連結される３つの点ｐ０、ｐ１及びｐ２が示される。本発明の実施形態により生成された改訂版地図データにおいて、点ｐ０及びｐ２は点ｐ１の誤差円Ｄ１と交差する曲線の弧４１０により連結される。誤差円は半径εの円であり、点の周囲の所定の最大誤差範囲を表す。点を回避する全ての有効なショートカットは、その誤差円を通過する必要がある。
【００７０】
次に、図５のように第１の点、第２の点の誤差円、及び第３の点を通る弧の中心の設定方法を説明する。
【００７１】
紀元前３世紀の哲学者であるペルゲのアポロニウスの研究によると、２つの点及び円を通過可能な円は２つ存在する。従って、２つに分岐した軌跡が存在し、一方の分岐は円の内側に接する円の集合に対するものであり、他方の分岐は外側に接する円の集合に対するものである。これを図６に示す。図６（ａ）は、２つに分岐した軌跡を示す。図６（ｂ）は円の内側に接する円を示す。図６（ｃ）は、円の外側に接する円を示す。
【００７２】
軌跡の２つの分岐により記述された領域内に中心を有する全ての円は、その点及び円を通過する。２つに分岐した軌跡は双曲線として表され、ｐ０及びＤ１を通過する双曲線の２つの分岐の間の領域は本明細書において
で示される。
【００７３】
ここで、３つの点ｐ０、ｐ１及びｐ２の状況を考慮した場合、本発明者によると、ｐ０及びＤ１を通る全ての円が
内に中心を有する一方で、ｐ０及びＤ２を通る全ての円は
内に中心を有する。従って、ｐ０、Ｄ１及びＤ２を通る全ての円は
及び
内に中心を有する。これは、
で書くことができる。故に、複数の点ｐｉ，．．．，ｐｊから成る線形群を仮定すると、ｐ１及び他の全ての点の誤差円Ｄｉ＋１，．．．，Ｄｊを通る円の中心は領域Ａ内である必要がある。
【００７４】
円が点ｐｉ，．．．，ｐｊの既存の集合及び別の点ｐｊ＋１を通ることが可能である場合、Ａと
との共通集合のみを計算する必要があり、全ての可能性を評価する不要な計算時間を節約できる。以下の場合に円が可能である。
【００７５】
しかし、弧
は、点の誤差円Ｄｊ＋１を通るのではなく終点ｐｊ＋１で正確に終了する場合にのみ可能であることが認識されるだろう。これを設定するためにｐｉ及びｐｊ＋１の垂直二等分線
とＡとの交差が考慮される。ｐｉ、ｐｊ＋１、及び全ての中間点の誤差円を通る弧の中心は、
とＡとの交差により規定された線分上にある必要がある。
【００７６】
図７（ａ）は、双曲線
の交差を示す。図７（ｂ）は、
上に中心を有する点ｐ１〜ｐ５の誤差円と交差するｐ０からｐ６への可能な最小及び最大の弧を示す。
【００７７】
ｐ０及びｐ６等の２つの点が与えられると、数ｄはベクトル
とｐ０、ｐ６及び点ｐ１〜ｐ５の誤差円を通る弧との間の距離を表す。しかし、一方は正、他方は負である２つの値のｄが存在する。これらは点及び誤差円を通り、最短経路を見つけるためにそれらを区別する必要がある。
【００７８】
図８は、本発明の一実施形態に係る方法を示す。方法は、円弧により複数の点ｐｉ，．．．，ｐｊを近似できるかを判定し、近似できる場合はその弧に対する値ｄを計算する。
【００７９】
方法は、ステップ８００で開始する。ステップ８１０において、領域値Ａは、第１の点ｐｉと第２の点の誤差円Ｄｉ＋１との間の双曲線の２つの分岐間の領域に設定される。ステップ８２０において、値ｋは第２の点への指標の値ｉ＋１に設定される。８３０において、領域Ａが０でない値を有しており、かつｋがｊより小さい、即ち複数の点の最後の点に到達したか否かを判定する。双方の条件が満たされる場合、ステップ８５０に進む。しかし、一方又は双方の条件が満たされない場合、方法はステップ８４０で終了する。ステップ８５０において、ｋの値はインクリメントされる。ステップ８６０において、計算された領域Ａと垂直二等分線
との交差が計算される。ステップ８７０において、ｌが０でないこと、すなわち垂直二等分線
が領域Ａを通過することが判定される。この場合、ステップ８８０においてｄの値が計算される。値ｄは、垂直二等分線
と円弧との間の距離である。ステップ８７０においてｌ＝０である場合、あるいはｄがステップ８８０で計算された場合、ステップ８９０において、Ａの新しい値はｐｉと誤差円Ｄｉ＋１との間の新しい双曲線とＡの既存の値との共通集合により計算される。
【００８０】
方法は、更なる点を順次導入することにより再帰的に実行されることが図８から分かる。更なる点を導入した後、全ての中間点の誤差円を通る始点と終点との間の円弧をフィッティングできるかが判定される。フィッティングできない場合、ｌ＝０であり、円弧は最後の繰り返しで考慮された複数の点を表すために使用される。
【００８１】
ステップ８８０でｄを計算する方法について、図９を参照して説明する。
【００８２】
値ｄを判定するために、円弧上の３つの点、すなわち第１の点ｐｉ、終点ｐｋ及び好適な実施形態においては中点ｐｍ＝ｐ（ｉ＋ｋ）／２である第３の点が使用される。この中点は、図８のステップ８８０で実行される図９に示す方法のステップ９０１で判定される。
【００８３】
円弧は円の小区分であり、ステップ９０２において、その円の中心ｐｃが計算される。ｐｉ又はｐｋとｐｃとの間の距離は円の半径であり、その一方でｄはｐｉ及びｐｋを二等分する線
と円弧との間の距離である。従って、線
のどちら側に中心ｐｃが位置するかを計算する必要がある。これは、ステップ９０３で実行される。
【００８４】
ｐｃが線
の下側にあるとステップ９０３で判定された場合、以下の式が得られる。
換言すると、ｄは、円の半径から円の中心とｐｉ及びｐｋと交差する線との距離を減算した値である。しかし、ｐｃが線の上側にある場合、以下の式が得られる。
すなわち、ｄは、円の半径に円の中心とｐｉ及びｐｋと交差する線との距離を加算した値である。
【００８５】
ｐｘが線
のどちら側にあると判定されるかによって１又は−１を返す関数
が使用される場合、上記計算は以下のように書ける。
【００８６】
上記式において、SideOfLineはｐｃが線
の上側にあるか又は下側にあるかに依存して関連した距離の加算又は減算を行うために使用される。このように、ｄの値はステップ９０４で計算される。
【００８７】
上述した方法において、点と点の誤差円との間の双曲線を判定する必要がある。円錐多角形の交差を使用して双曲線の計算を行うことも可能であるが、本発明の好適な一実施形態は双曲線ｈの多角形近似ｈ’を使用する。
【００８８】
図１０（ａ）は一対の双曲線を示す。図１０（ｂ）は、（ａ）に示した一対の双曲線に対する漸近線及び接線を示す。図１０（ｃ）は、一対の双曲線に対する近似ｈ’を示す。
【００８９】
双曲線の重要な特性に対して図１０（ａ）に示した一対の双曲線を近似することが利用される。全ての双曲線は、(0, 0)を通る２つの漸近線、ｙ軸に平行でありｘ切片を有する２つの接線を有する。座標は双曲線に関係し、(0, 0)は焦点Ｆ１とＦ２との間の点である。漸近線及び接線は以下のように計算される。
漸近線：
接線：
【００９０】
漸近線及び接線は図１０（ｂ）に示され、図１０（ｃ）に示す近似が計算されることを可能にする。
【００９１】
このような近似は、実際の双曲線より僅かに小さい領域を呈するため、いくつかのショートカットは理論的には拒否される可能性があるが、誤判定がなされることはない。近似の誤差は、３つ以上の接線を使用することにより低減されてもよい。図９（ｃ）に示すように、多角形近似は無限サイズを有する。変数λは近似の長さを制限するために導入されてもよい。長さは１つの漸近線に沿って測定されてもよく、その長さは漸近線が互いに交差する点から開始する。
【００９２】
更に多角形交差を計算する必要があり、この目的のために掃引線アルゴリズム（sweep line algorithm）等のいかなる多角形交差アルゴリズムが使用されてもよい。
【００９３】
弧が複数の点に対する適切な近似であることを保証するために、本発明の実施形態は、距離の閾値及び角度の閾値の一方又は双方を使用する。
【００９４】
距離の閾値は、弧が連続した点の間の線分から離れてもよい最大距離である。即ち、それらの点の間の直線線分
と円弧
との間の最大許容距離である最大偏差値εが導入される。距離は、
が
と同一の傾きを有する時の
と
との間の距離である。弧及び線分が始点及び終点の双方を共有しない場合、距離ｄｋは、円弧
及び線分
により近似された点ｐ０，ｐ１．．．ｐ８から成る線形群に対して図１１に示すように、線分
とその線分を回避する弧との間の最大距離である。
【００９５】
角度の閾値は、入力弧及び線分のなす角度が非常に大きく異ならないように使用されてもよい。角度αｋは、
と線分を回避する弧とのなす角度であると考えられる。図１２は、図１１と同一の点の集合を示し、考慮された角度の閾値により近似される。角度αｋは最大近似角度未満であることが判定される。
【００９６】
図１３は、円弧近似が計算された種々のテストデータを示し、多くの場合、点の間の円弧近似を使用すると、元のポリデータの集合が非常に少ない点で表せることを実証している。
【００９７】
本発明の教示は、地図データを形成する点の数を減少する方法を提供することが上記より明らかとなる。本発明の実施形態の結果、ある領域に対する地図データは減少した記憶容量で保持され、ナビゲーション装置のコストを低減する。
【００９８】
本発明の種々の態様及び実施形態を説明したが、本発明の範囲は本明細書で説明した特定の構成に限定されず、添付の請求の範囲の範囲内の全ての構成、並びにそれらに対する変形例及び変更例を含むことが理解されるだろう。
【００９９】
例えば上記の詳細な説明で説明した実施形態はＧＰＳを参照するが、ナビゲーション装置はＧＰＳの代わりに（又は実際にはＧＰＳに加えて）どんな種類の位置検出技術を利用してもよい。例えばナビゲーション装置は、欧州のGalileoシステム等の他のグローバルナビゲーション衛星システムを用いることにより有用であってもよい。同様に、ナビゲーション装置は、衛星を用いたものに限定されないが、地上ビーコン又は装置が地理的な場所を判定することを可能にする他の何らかの種類のシステムを使用して容易に機能できる。
【０１００】
好適な実施形態はソフトウェアにより特定の機能性を実現するが、機能性はハードウェアのみで（例えば、１つ以上のＡＳＩＣ（特定用途向け集積回路）を使用して）又は実際にはハードウェア及びソフトウェアの組合せにより同等に実現可能であることが当業者にはよく理解されるだろう。従って、本発明の範囲は、ソフトウェアでのみ実現されることに限定されると解釈されるべきではない。
【０１０１】
最後に、添付の請求の範囲は本明細書で説明した特徴の特定の組合せを説明するが、本発明の範囲は以下に請求される特定の組合せに限定されず、特定の組合せが添付の請求の範囲において特に列挙されているかいないかに関わらず本明細書で開示された特徴又は実施形態のいかなる組合せも含む。
【技術分野】
【０００１】
本発明は、ナビゲーション装置及びナビゲーション装置用のナビゲーション地図を作成する方法に関する。本発明の例示する実施形態は、ポータブルナビゲーション装置（いわゆるＰＮＤ）に関し、特に全地球測位システム（ＧＰＳ）信号の受信及び処理機能、並びにそれと共に使用する地図データを備えるＰＮＤに関する。更に一般的には、他の実施形態は、地図データを使用する経路計画及び好ましくはナビゲーションの機能性を提供するためにナビゲーションソフトウェアを実行するように構成されるあらゆる種類の処理装置に関する。
【背景技術】
【０００２】
ＧＰＳ（全地球測位システム）信号の受信及び処理機能を備えるポータブルナビゲーション装置（ＰＮＤ）はよく知られており、車両搭載型又は他の車両ナビゲーションシステムとして広く採用されている。
【０００３】
一般的に、現在のＰＮＤは、プロセッサ、メモリ（揮発性及び不揮発性のうちの少なくとも一方、並びに一般的にはその双方）及び前記メモリ内に格納された地図データを含む。プロセッサ及びメモリは、ソフトウェアオペレーティングシステムが設置されうる実行環境を提供するように協働し、また、ＰＮＤの機能の制御を可能にし、且つ種々の他の機能を提供するために１以上の追加のソフトウェアプログラムが提供されることは一般的なことである。
【０００４】
通常、これらの装置は、ユーザが装置とインタラクションし、且つ装置を制御できるようにする１以上の入力インタフェース、及びユーザに情報を中継する１以上の出力インタフェースとを更に備える。出力インタフェースの例には、表示装置及び可聴出力用スピーカが含まれる。入力インタフェースの例には、オン／オフ動作又は装置の他の特徴を制御する１以上の物理ボタン（ボタンは必ずしも装置自体にある必要はなく、装置が車両に内蔵されている場合はステアリングホイール上にあってもよい）及びユーザ音声を検出するマイクが含まれる。特定の好適な１つの構成において、出力インタフェースディスプレイは、ユーザが触れることで装置を動作させる際に使用する入力インタフェースを更に提供するためにタッチセンシティブディスプレイとして（又はタッチセンシティブオーバレイ等を使用して）構成されてもよい。
【０００５】
多くの場合、この種の装置は、電力及びオプションとしてデータ信号を装置に対して送受信する際に使用する１以上の物理コネクタインタフェースを含み、オプションとして、セルラ電気通信、並びに例えばＷｉ−Ｆｉ及びＷｉ−Ｍａｘ ＧＳＭ等の他の信号及びデータネットワークを介する通信を可能にする１以上の無線送信機／受信機を含む。
【０００６】
この種のＰＮＤ装置は、場所データを含む衛星放送信号を受信し、且つその後装置の現在地を判定するために処理する際に使用するＧＰＳアンテナを更に含む。
【０００７】
ＰＮＤ装置は、現在の角度及び直線加速度、また、ＧＰＳ信号から導出された位置情報とともに速さ、並びに装置及び当該装置が搭載される車両の相対的な変位を判定するために処理される信号を生成する電子ジャイロスコープ及び加速度計を更に含んでもよい。通常、そのような機能は車両搭載型のナビゲーションシステムに提供されるのが最も一般的であるが、ＰＮＤ装置に備えることが得策である場合にはＰＮＤ装置に備えてもよい。
【０００８】
そのようなＰＮＤの有用性は、主に、第１の場所（一般に、出発地又は現在地）と第２の場所（一般に、目的地）との間の経路を判定する機能にある。装置のユーザは、多種多様な種々の方法、例えば郵便番号、道路名及び番地、以前に格納した「既知」の目的地（有名な場所、公共の場所（運動場又は水泳プール等）又は他の地点情報等）、並びにお気に入りの目的地又は最近訪れた目的地のいずれかにより、これらの場所を入力する。
【０００９】
一般にＰＮＤは、地図データから出発地の住所の場所と目的地の住所の場所との間の「最善」又は「最適」な経路を算出することがソフトウェアにより可能になる。「最善」又は「最適」な経路は、所定の基準に基づいて判定され、必ずしも最速又は最短の経路である必要はない。運転者を案内する経路の選択は非常に複雑となり得、選択された経路は、既存の予測された動的に且つ／又は無線で受信された交通及び道路情報、道路速度に関する履歴情報、並びに道路選択を判定する要因に対する運転者自身の好みを考慮してもよい（例えば運転者は、経路が高速道路又は有料道路を含むべきでないことを指定してもよい）。
【００１０】
更に装置は、道路及び交通状況を継続的に監視し、状況変化によりとられる残りの行路に対して経路を変更することを提案又は選択してもよい。種々の技術（例えば、移動電話データ交換、固定カメラ、ＧＰＳ車両追跡）に基づくリアルタイム交通監視システムは、交通遅滞を識別し、その情報を通知システムに供給するために使用されている。
【００１１】
この種のＰＮＤは、一般に、車両のダッシュボード又はフロントガラスに搭載されてもよいが、車両のラジオの内蔵コンピュータの一部又は実際には車両自体の制御システムの一部として形成されてもよい。ナビゲーション装置は、ＰＤＡ（ポータブルデジタルアシスタント）、メディアプレーヤ又は移動電話等のハンドヘルドシステムの一部であってもよい。これらの場合、ハンドヘルドシステムの標準的な機能は、経路計算及び計算された経路に沿ったナビゲーションの双方を実行するためにソフトウェアを装置にインストールすることにより拡張される。
【００１２】
経路計画及びナビゲーション機能は、適切なソフトウェアを実行するデスクトップ又は移動計算リソースにより提供されてもよい。例えば、ロイヤル・オートモービルクラブ（ＲＡＣ：Royal Automobile Club）は、http://www.rac.co.ukにおいてオンライン経路計画及びナビゲーション機能を提供する。この機能により、ユーザは出発地及び目的地を入力でき、その後ユーザのＰＣが接続されるサーバは、経路（経路の様子はユーザにより指定されてもよい）を計算し、地図を生成し、選択した出発地から選択した目的地までユーザを案内するための包括的なナビゲーション命令の集合を生成する。また当該機能は、計算経路の擬似３次元レンダリングを提供し、ユーザが経路に沿って移動することをシミュレートし、且つそれにより計算された経路のプレビューをユーザに提供する経路プレビュー機能を提供する。
【００１３】
ＰＮＤにおいて、経路が計算されると、ユーザはオプションとして提案された経路のリストから所望の計算された経路を選択するためにナビゲーション装置とインタラクションする。オプションとして、ユーザは、例えば特定の経路、道路、場所又は基準が特定の行程に対して回避されること又は必須であることを指定することにより経路選択処理を仲介又は誘導してもよい。ＰＮＤの経路計算の側面は１つの主要機能を形成し、そのような経路に沿ったナビゲーションは別の主要機能である。
【００１４】
計算された経路に沿ったナビゲーションがなされている間、このようなＰＮＤは、経路の終点、すなわち所望の目的地まで選択した経路に沿ってユーザを案内するための視覚的命令及び可聴命令の少なくともいずれかを提供するのが一般的である。また、ＰＮＤは、ナビゲーション中に画面上に地図情報を表示するのが一般的である。このような情報は、表示された地図情報が装置の現在地及び従って装置が車両搭載型のナビゲーションに使用されている場合はユーザの現在地又はユーザの車両の現在地を表すように画面上で定期的に更新される。
【００１５】
一般に画面上に表示されたアイコンは、装置の現在地を示し、装置の現在地近傍の現在の道路及び周囲の道路の地図情報と共に中央に置かれ、他の地図の特徴も表示される。更にナビゲーション情報は、オプションとして表示された地図情報の上側、下側又は片側のステータスバーに表示されてもよく、ナビゲーション情報の例には、ユーザが走行する必要のある現在の道路から次の進路変更までの距離が含まれ、場合によってはその進路変更の特性は、例えば左折又は右折である特定の種類の進路変更を示す更なるアイコンで表される。またナビゲーション機能は、経路に沿ってユーザを案内する際に使用される可聴命令の内容、継続時間及びタイミングを判定する。理解されるように、「１００ｍ先を左折」等の単純な命令は、かなりの処理及び分析を必要とする。上述したように、装置とのユーザインタラクションは、タッチスクリーンによって行われてもよく、更に又はあるいはステアリングコラムリモコン、音声起動又は他の適切なあらゆる方法によって行われてもよい。
【００１６】
装置により提供された更なる重要な機能は、ユーザがナビゲーション中に事前に計算された経路から外れた（偶然又は意図的に）場合、別の経路の方が適切であることをリアルタイム交通状況が指示し、且つ装置がそのような状況を自動的に認識することを適切に可能にされる場合、又はユーザが何らかの理由で能動的に装置に経路を再計算させる場合の自動経路再計算である。
【００１７】
またユーザが規定した基準で経路を計算できることは既知である。例えばユーザは、装置により景色のよい経路が計算されることを好んでもよく、あるいは交通渋滞が起こる可能性が高いか、起こることが予想されるか又は現在起こっているあらゆる道路を回避することを要求してもよい。次に、装置のソフトウェアは種々の経路を計算し、例えば景色が美しい所としてタグ付けされた地点情報（ＰＯＩとして既知である）を経路に沿って最も多く含む経路をより有利に重み付けするか、あるいは特定の道路上の交通状況を示す格納情報を使用することにより、起こる可能性のある渋滞又はそのために起こる遅滞のレベルに関して計算経路を順序付けする。更に他のＰＯＩに基づく経路計算及びナビゲーション基準、並びに交通情報に基づく経路計算及びナビゲーション基準が可能である。
【００１８】
経路計算及びナビゲーション機能はＰＮＤの全体的な有用性に対して必須であるが、装置を純粋に情報表示に使用できる。すなわち、装置の現在地に関連する地図情報のみが表示され、経路が全く計算されておらず、装置が現在ナビゲーションを全く実行していない「フリードライビング」用に使用できる。多くの場合、このような動作モードは、移動するのに使用するように要求される経路をユーザが既に認識しており、ナビゲーション支援を必要としない場合に適用可能である。
【００１９】
上述のこの種の装置、例えばＴｏｍＴｏｍ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｂ．Ｖ．が製造及び供給する７２０Ｔモデルは、ユーザがある位置から別の位置まで運転できるようにする信頼できる手段を提供する。
【００２０】
ナビゲーション装置と共に使用する地図データは、一般に道路形状を示す数十万又は数百万もの点を含む。例えば１つの道路は、道路の進路を示す複数の中間点により表される。しかし、地図データを格納するのに必要なメモリは、サイズが大きく且つ高価である場合が多く、それによりナビゲーション装置又はデータ記憶装置又は新しい地図データを含む媒体のコストは高くなる。
【００２１】
本発明の目的は、この問題に対処することであり、特に道路等の実際の物理的実体の忠実な表現を保持しつつ地図データのサイズを減少することである。
【発明の概要】
【課題を解決するための手段】
【００２２】
この目的のために、本発明の現在の好適な実施形態は、複数の点に円弧をフィッティングするように適切にプログラムされたコンピュータを使用する方法であって、第１の点と少なくとも１つの中点の周囲の領域とを通る円の中心が位置する領域が、第１の点及び第２の点を通る線の垂直二等分線と交差するかを判定する構成を有する方法を提供する。
【００２３】
本発明の別の実施形態は、実行環境で実行された時に第１の点と少なくとも１つの中間点の周囲の領域とを通る円の中心が位置する領域が、第１の点及び第２の点を通る線の垂直二等分線と交差するか否かをプロセッサに判定させるように動作可能である１以上のソフトウェアモジュールを含むコンピュータソフトウェアに関する。
【００２４】
本発明の更に別の実施形態は、プロセッサと、プロセッサに動作可能に接続されたメモリと、を備え、メモリは複数の点を含み、プロセッサは、第１の点と少なくとも１つの中間点の周囲の領域とを通る円の中心が位置する領域が、第１の点及び第２の点を通る線の垂直二等分線と交差するか否かを判定するように構成されることを特徴とする装置に関する。
【００２５】
これらの実施形態の利点については以下に説明する。これらの実施形態の各々の更なる詳細及び特徴は、添付の従属請求項及び以下の詳細な説明の中で規定される。
【００２６】
本発明の教示の種々の態様及びそれらの教示を採用する構成について、添付の図面を参照して例として以下に説明する。
【図面の簡単な説明】
【００２７】
【図１】全地球測位システム（ＧＰＳ）を示す概略図である。
【図２】ナビゲーション装置を提供するように構成された電子構成要素を示す概略図である。
【図３】ナビゲーション装置が無線通信チャネルを介して情報を受信できる方法を示す概略図である。
【図４Ａ】、
【図４Ｂ】ナビゲーション装置を示した透視図である。
【図５】線分群、並びに第１の点及び終点を通る円弧を形成する３つの点と、中間点を囲む誤差円を示す図である。
【図６】１つの点、別の点を囲む誤差円、並びに誤差円の内側に接する円の集合及び誤差円の外側に接する円の集合により形成された軌跡を示す図である。
【図７】複数の点の間に形成された複数の双曲線の交差を示す図である。
【図８】本発明の一実施形態を形成する方法を示すフローチャートである。
【図９】第１の点及び第２の点を通る線と弧との間の距離の値を計算する方法を示すフローチャートである。
【図１０】双曲線に対する近似を示す図である。
【図１１】最大線形偏差を示す近似によりフィッティングされた線分群を形成する複数の点を示す図である。
【図１２】最大角偏差を示す近似によりフィッティングされた線形群を形成する複数の点を示す図である。
【図１３】複数の点により形成された線形群と線形群を近似する円弧との比較を示す図である。
【発明を実施するための形態】
【００２８】
次に、本発明の好適な実施形態について、特にＰＮＤを参照して説明する。しかし、本発明の教示はＰＮＤに限定されず、経路計画及びナビゲーション機能を提供するためにナビゲーションソフトウェアを実行するように構成されるいかなる種類の処理装置にも例外なく適用可能である。故に、本出願において、ナビゲーション装置は、ＰＮＤ、車両に内蔵されたナビゲーション装置、あるいは実際には経路計画及びナビゲーションソフトウェアを実行するコンピューティング資源（デスクトップ又はポータブルパーソナルコンピュータ（ＰＣ）、移動電話、あるいはポータブルデジタルアシスタント（ＰＤＡ））として実装されるか否かにかかわらず、いかなる種類の経路計画及びナビゲーション装置も（無制限に）含むことを意図する。
【００２９】
本発明の教示は、ユーザが１つの地点から別の地点までの運転方法に関する指示を要求していないが単に所定の場所のビューを提供してほしい状況においても有用であることが以下から明らかとなるだろう。このような状況において、ユーザが選択した「目的地」の場所は、ユーザが運転を開始したい対応する出発地を有する必要はないため、本明細書で「目的地」の場所又は実際には「目的地」のビューを参照することは、経路の生成が不可欠であること、「目的地」まで移動する必要があること又は実際には目的地の存在が対応する出発地の名称を必要とすることを意味すると解釈されるべきではない。
【００３０】
上記を踏まえ、図１はナビゲーション装置により使用可能な全地球測位システム（ＧＰＳ）の一例を示す図である。そのようなシステムは周知であり、種々の目的に使用される。一般に、ＧＰＳは、連続的な位置、速度、時間及びいくつかの例においては方向情報を無数のユーザに対して判定できる衛星無線ナビゲーションシステムである。
【００３１】
以前はＮＡＶＳＴＡＲとして周知であったが、ＧＰＳは極めて正確な軌道で地球と共に動作する複数の衛星を使用する。これらの正確な軌道に基づいて、ＧＰＳ衛星は、それらの場所を任意の数の受信装置に中継できる。
【００３２】
ＧＰＳデータを受信する能力を特別に備える装置がＧＰＳ衛星信号に対する無線周波数の走査を開始する場合、ＧＰＳシステムは実現される。ＧＰＳ衛星から無線信号を受信すると、装置は、複数の異なる従来の方法のうちの１つを用いて、その衛星の正確な場所を判定する。殆どの例において、装置は、少なくとも３つの異なる衛星信号を取得するまで信号の走査を継続する（尚、位置は、通常は２つの信号のみでは判定されないが、他の三角測量技術を使用して２つの信号から判定することもできる）。幾何学的三角測量を実現する場合、受信機は、３つの既知の位置を利用して、衛星に対する自身の２次元位置を判定する。これは、周知の方法で行われる。更に、第４の衛星信号を取得することにより、受信装置は、同一の幾何学計算によって周知の方法でその３次元位置を計算できる。位置及び速度データは、無数のユーザにより連続的にリアルタイムで更新可能である。
【００３３】
図１に示すように、ＧＰＳシステム全体を参照番号１００で示す。複数の衛星１２０は、地球１２４の周囲の軌道上にある。各衛星１２０の軌道は、他の衛星１２０の軌道と必ずしも同期せず、実際には非同期であることが多い。ＧＰＳ受信機１４０は、種々の衛星１２０からスペクトル拡散ＧＰＳ衛星信号１６０を受信するように示される。
【００３４】
各衛星１２０から連続的に送信されるスペクトル拡散信号１６０は、極めて正確な原子時計を用いて達成される非常に正確な周波数標準を利用する。各衛星１２０は、そのデータ信号送信１６０の一部として、その特定の衛星１２０を示すデータストリームを送信する。一般に、ＧＰＳ受信機１４０が三角測量によりその２次元位置を計算するために、ＧＰＳ受信機１４０は少なくとも３つの衛星１２０からスペクトル拡散ＧＰＳ衛星信号１６０を取得することが当業者には理解される。更なる信号を取得すると、全部で４つの衛星１２０から信号１６０を取得する結果となり、これによってＧＰＳ受信機１４０は、その３次元位置を周知の方法で計算できる。
【００３５】
図２は、本発明の好適な実施形態に係るナビゲーション装置２００の電子構成要素の実例となる図である。尚、ナビゲーション装置２００のブロック図は、ナビゲーション装置の全ての構成要素を含むものではなく、構成要素の多くの例を表すにすぎない。
【００３６】
ナビゲーション装置２００は、筐体（不図示）内に位置付けられる。筐体は、入力装置２２０及び表示画面２４０に接続されるプロセッサ２１０を含む。入力装置２２０は、キーボード装置、音声入力装置、タッチパネル、及び情報を入力するために利用される他の任意の周知の入力装置のうちの少なくとも１つを含むことができ、表示画面２４０は、例えばＬＣＤディスプレイ等の任意の種類の表示画面を含むことができる。特定の好適な構成において、入力装置２２０及び表示画面２４０は、タッチパッド又はタッチスクリーン入力を含む一体型入力表示装置に一体化され、その場合、ユーザは、複数の表示選択肢のうちの１つを選択するか又は複数の仮想ボタンのうちの１つを操作するために、表示画面２４０の一部分に接触するだけでよい。
【００３７】
ナビゲーション装置は、出力装置２６０、例えば可聴出力装置（例えばスピーカ）を含みうる。出力装置２６０がナビゲーション装置２００のユーザに対して可聴情報を生成できるため、同様に、入力装置２４０は入力音声コマンドを受信するマイク及びソフトウェアを更に含むことができると理解されるべきである。
【００３８】
ナビゲーション装置２００において、プロセッサ２１０は、接続２２５を介して入力装置２４０に動作可能に接続され且つ入力装置２２０から入力情報を受信するように設定される。また、プロセッサ２１０は、情報を出力するために、表示画面２４０及び出力装置２６０のうちの少なくとも一方に出力接続２４５を介して動作可能に接続される。更に、プロセッサ２１０は、接続２３５を介してメモリ２３０に動作可能に接続され、接続２７５を介して入出力（Ｉ／Ｏ）ポート２７０との間で情報を送受信するように更に構成される。この場合、Ｉ／Ｏポート２７０は、ナビゲーション装置２００の外部のＩ／Ｏ装置２８０に接続可能である。外部Ｉ／Ｏ装置２８０は、例えばイヤホン等の外部聴音装置を含んでもよいが、これに限定されない。更に、Ｉ／Ｏ装置２８０への接続は、例えばハンズフリー動作と音声起動動作との少なくとも一方のため、イヤホン又はヘッドフォンへの接続のため、並びに／あるいは例えば移動電話への接続のためのカーステレオユニット等の他の任意の外部装置への有線接続又は無線接続であってもよい。この場合、移動電話接続は、ナビゲーション装置２００とインターネット又は例えば他の任意のネットワークとの間のデータ接続を確立するためと、インターネット又は例えば他の任意のネットワークを介するサーバへの接続を確立するためとの少なくとも一方のために使用されてもよい。
【００３９】
図２は、接続２５５を介するプロセッサ２１０とアンテナ／受信機２５０との間の動作可能な接続を更に示す。この場合、アンテナ／受信機２５０は、例えばＧＰＳアンテナ／受信機であってもよい。参照番号２５０で示されるアンテナ及び受信機は、図示のために概略的に組み合わされるが、アンテナ及び受信機は、別個に位置する構成要素であってもよく、アンテナは、例えばＧＰＳパッチアンテナ又はヘリカルアンテナであってもよいことが理解されるだろう。
【００４０】
更に、図２に示す電子構成要素が従来の方法で電源（不図示）により電力を供給されることが当業者には理解されるだろう。当業者により理解されるように、図２に示す構成要素の異なる構成が本願の範囲内で考えられる。例えば、図２に示す構成要素は、有線接続と無線接続との少なくとも一方等を介して互いに通信状態にあってもよい。従って、本願のナビゲーション装置２００の範囲は、ポータブル又はハンドヘルドナビゲーション装置２００を含む。
【００４１】
更に、図２のポータブル又はハンドヘルドナビゲーション装置２００は、例えば自転車、オートバイ、自動車又は船舶等の乗物に周知の方法で接続されるか又は「ドッキング」される。その場合、そのようなナビゲーション装置２００は、ポータブル又はハンドヘルドナビゲーションとして使用するために、ドッキング場所から取り外し可能である。
【００４２】
図３を参照すると、ナビゲーション装置２００は、デジタル接続（例えば、周知のＢｌｕｅｔｏｏｔｈ技術を介するデジタル接続）を確立する移動装置（図示せず）（移動電話、ＰＤＡ、及び移動電話技術を用いる任意の装置のうちの少なくとも１つ等）を介して、サーバ３０２との「モバイル」あるいは電気通信ネットワーク接続を確立してもよい。そうして、そのネットワークサービスプロバイダを介して、移動装置は、サーバ３０２とのネットワーク接続を（例えば、インターネットを介して）確立できる。そのため、「モバイル」ネットワーク接続は、情報に対する「リアルタイム」又は少なくとも非常に「最新」のゲートウェイを提供するために、ナビゲーション装置２００（単体時、及び車載走行時の少なくとも一方において移動可能であり且つ多くの場合移動している）とサーバ３０２との間に確立される。
【００４３】
例えばインターネット（ワールドワイドウェブ等）を使用して、移動装置（サービスプロバイダを介する）とサーバ３０２等の別の装置との間にネットワーク接続を確立することは、周知の方法で行われうる。これは、例えばＴＣＰ／ＩＰ層プロトコルの使用を含む。移動装置は、ＣＤＭＡ、ＧＳＭ、ＷＡＮ等の任意の数の通信規格を利用できる。
【００４４】
そのため、例えば移動電話又はナビゲーション装置２００内の移動電話技術を介するデータ接続を介して達成されるインターネット接続が利用されてもよい。この接続の場合、サーバ３０２とナビゲーション装置２００との間のインターネット接続が確立される。これは、例えば、移動電話又は他の移動装置及びＧＰＲＳ（汎用パケット無線サービス）接続（ＧＰＲＳ接続は、通信会社により提供される移動装置用高速データ接続であり、ＧＰＲＳはインターネットへの接続方法である）を介して行われうる。
【００４５】
更に、ナビゲーション装置２００は、移動装置とのデータ接続を完成し、例えば既存のＢｌｕｅｔｏｏｔｈ技術を介して周知の方法でインターネット及びサーバ３０２とのデータ接続を最終的に完成する。この場合、例えばデータプロトコルは、ＧＳＭ規格に対するデータプロトコル規格であるＧＳＲＭ１等の任意の数の規格を利用できる。
【００４６】
ナビゲーション装置２００は、ナビゲーション装置２００自身の中に、自身の移動電話技術を含んでもよい（例えばアンテナを含む、あるいはオプションとしてナビゲーション装置２００の内部アンテナを用いる）。ナビゲーション装置２００内の移動電話技術は、上述のような内部構成要素を含むことができ、且つ／又は例えば必要な移動電話技術とアンテナとの少なくとも一方を備える挿入可能なカード（例えば加入者識別モジュールあるいはＳＩＭカード）を含むことができる。そのため、ナビゲーション装置２００内の移動電話技術は、任意の移動装置の方法と同様の方法で、例えばインターネットを介して、ナビゲーション装置２００とサーバ３０２との間にネットワーク接続を同様に確立できる。
【００４７】
ＧＲＰＳ電話設定の場合、移動電話の機種、製造業者等の多様な範囲に関して正しく動作するために、Ｂｌｕｅｔｏｏｔｈ対応のナビゲーション装置が使用されてもよく、機種／製造業者専用設定は、例えばナビゲーション装置２００に格納されてもよい。この情報のために格納されたデータは更新されうる。
【００４８】
図３において、ナビゲーション装置２００は、多くの異なる、いずれの装置により実装されうる汎用通信チャネル３１８を介して、サーバ３０２と通信するものとして示されている。通信チャネル３１８を介する接続がサーバ３０２とナビゲーション装置２００との間に確立される場合、本願のサーバ３０２及びナビゲーション装置２００は通信可能である（尚、そのような接続は、移動装置を介するデータ接続、インターネットを介するパーソナルコンピュータを介する直接接続等である）。
【００４９】
サーバ３０２は、図示しない他の構成要素に加えて、メモリ３０６に動作可能に接続され且つ有線又は無線接続３１４を介して大容量データ記憶装置３１２に動作可能に更に接続されるプロセッサ３０４を含む。更に、プロセッサ３０４は、通信チャネル３１８を介してナビゲーション装置２００と情報の送受信を行うために、送信機３０８及び受信機３１０に動作可能に接続される。送受信される信号は、データ信号、通信信号及び又は他の伝搬信号を含んでもよい。送信機３０８及び受信機３１０は、ナビゲーション装置２００の通信設計において使用される通信条件及び通信技術に従って選択又は設計されてもよい。尚、送信機３０８及び受信機３１０の機能は、信号送受信機に組み合わされてもよい。
【００５０】
サーバ３０２は、大容量記憶装置３１２に更に接続される（又は、大容量記憶装置３１２を含む）。尚、大容量記憶装置３１２は、通信リンク３１４を介してサーバ３０２に結合されてもよい。大容量記憶装置３１２は、ナビゲーションデータ及び地図情報のストアを含む。また、大容量記憶装置３１２は、サーバ３０２とは別個の装置であってもよく、サーバ３０２に組み込まれてもよい。
【００５１】
ナビゲーション装置２００は、通信チャネル３１８を介してサーバ３０２と通信するように構成され、図２に関して上述したように、プロセッサ、メモリ等を含み、更に、通信チャネル３１８を介して信号及び／又はデータを送出する送信機３２０及び受信する受信機３２２を含む。尚、これらの装置は、サーバ３０２以外の装置と通信するためにも使用される。更に、送信機３２０及び受信機３２２は、ナビゲーション装置２００の通信設計において使用される通信条件及び通信技術に従って選択又は設計され、送信機３２０及び受信機３２２の機能は、単一の送受信機に組み合わされてもよい。
【００５２】
サーバメモリ３０６に格納されるソフトウェアは、プロセッサ３０４に命令を提供し、サーバ３０２がナビゲーション装置２００にサービスを提供できるようにする。サーバ３０２により提供される１つのサービスは、ナビゲーション装置２００からの要求の処理及び大容量データ記憶装置３１２からナビゲーション装置２００へのナビゲーションデータの送信を含む。サーバ３０２により提供される別のサービスは、所望のアプリケーションに対する種々のアルゴリズムを使用したナビゲーションデータの処理及びナビゲーション装置２００へのこれらの計算の結果の送出を含む。
【００５３】
一般に、通信チャネル３１８は、ナビゲーション装置２００とサーバ３０２とを接続する伝搬媒体又はパスを表す。サーバ３０２及びナビゲーション装置２００の双方は、通信チャネルを介してデータを送信する送信機及び通信チャネルを介して送信されたデータを受信する受信機を含む。
【００５４】
通信チャネル３１８は、特定の通信技術に限定されない。更に、通信チャネル３１８は、単一の通信技術に限定されない。すなわち、チャネル３１８は、種々の技術を使用する複数の通信リンクを含んでもよい。例えば、通信チャネル３１８は、電気通信、光通信、及び電磁通信のうちの少なくとも１つ等のためのパスを提供するように構成されることができる。そのため、通信チャネル３１８は、電気回路、ワイヤ及び同軸ケーブル等の電気導体、光ファイバケーブル、コンバータ、無線周波数（ＲＦ）波、大気、空間等のうちの１つ又はそれらの組み合わせを含むが、それらに限定されない。更に、通信チャネル３１８は例えば、ルータ、リピータ、バッファ、送信機及び受信機等の中間装置を含むことができる。
【００５５】
１つの例示的な装置において、通信チャネル３１８は、電話及びコンピュータネットワークを含む。更に、通信チャネル３１８は、無線周波数、マイクロ波周波数、赤外線通信等の無線通信に適応できてもよい。更に、通信チャネル３１８は衛星通信に適応できる。
【００５６】
通信チャネル３１８を介して送信される通信信号は、所定の通信技術に必要とされるか又は望まれる信号を含むが、それらに限定されない。例えば、信号は、時分割多元接続（ＴＤＭＡ）、周波数分割多元接続（ＦＤＭＡ）、符号分割多元接続（ＣＤＭＡ）、グローバル・システム・フォー・モバイル・コミュニケーションズ(Global System for Mobile Communications)（ＧＳＭ）等のセルラ通信技術において使用されるように構成されてもよい。デジタル信号及びアナログ信号の双方が通信チャネル３１８を介して送信できる。これらの信号は、通信技術にとって望ましい変調信号、暗号化信号、及び圧縮信号のうちの少なくとも１つであってもよい。
【００５７】
サーバ３０２は、無線チャネルを介してナビゲーション装置２００によりアクセス可能なリモートサーバを含む。サーバ３０２は、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、仮想プライベートネットワーク（ＶＰＮ）等に位置するネットワークサーバを含んでもよい。
【００５８】
サーバ３０２は、デスクトップ又はラップトップコンピュータ等のパーソナルコンピュータを含んでもよく、通信チャネル３１８は、パーソナルコンピュータとナビゲーション装置２００との間に接続されるケーブルであってもよい。あるいは、パーソナルコンピュータは、ナビゲーション装置２００とサーバ３０２との間に接続されて、サーバ３０２とナビゲーション装置２００との間にインターネット接続を確立してもよい。あるいは、インターネットを介してナビゲーション装置２００をサーバ３０２に接続するために、移動電話又は他のハンドヘルド装置がインターネットへの無線接続を確立してもよい。
【００５９】
ナビゲーション装置２００は、情報ダウンロードを介してサーバ３０２から情報を与えられてもよい。情報は、自動的あるいはユーザがナビゲーション装置２００をサーバ３０２に接続する場合に周期的に更新されてもよく、且つ／又は例えば無線移動接続装置及びＴＣＰ／ＩＰ接続を介してサーバ３０２とナビゲーション装置２００との間に接続がより継続して又は頻繁に確立される場合に更に動的に更新されてもよい。多くの動的計算のために、サーバ３０２内のプロセッサ３０４が大量の処理要求を処理するために使用されてもよい。しかし、ナビゲーション装置２００のプロセッサ２１０も同様に、多くの場合においてはサーバ３０２への接続に関係なく、多くの処理及び計算を処理できる。
【００６０】
図２に示す様に、ナビゲーション装置２００はプロセッサ２１０、入力装置２２０、表示画面２４０を含む。入力装置２２０及び表示画面２４０は、例えばタッチパネルスクリーンを介して情報（直接入力、メニュー選択など）を入力すること及び情報を表示することとの両方を可能にするために、一体型入力表示装置に統合される。このようなスクリーンは、当業者には周知のものであるように、例えばタッチ入力ＬＣＤスクリーンであってもよい。更に、ナビゲーション装置２００は、例えばオーディオ入力／出力装置などの、更なる任意の入力装置２２０と更なる任意の出力装置２４１との少なくとも一方を有しても良い。
【００６１】
図４Ａ及び図４Ｂは、ナビゲーション装置２００の斜視図を示している。図４Ａに示すように、ナビゲーション装置２００は、一体型入力表示装置２９０（例えばタッチパネル画面）と図２の他の構成要素（内蔵ＧＰＳ受信機２５０、マイクロプロセッサ２１０、電源、メモリシステム２３０などを含むがこれに限定されない）を含むユニットであっても良い。
【００６２】
ナビゲーション装置２００は、アーム２９２上に備え付けられても良い。このアーム２９２は、吸着カップ２９４を用いて、車両のダッシュボード／窓／等に固定されても良い。このアーム２９２は、ナビゲーション装置２００がドッキング可能なドッキングステーションの一例である。
【００６３】
図４Ｂに示すように、ナビゲーション装置２００は、例えば、アーム２９２に対してナビゲーション装置２９２をスナップ接続することで、ドッキングステーションのアーム２９２にドッキング若しくは接続することができる。図４Ｂにおける矢印で示すように、ナビゲーション装置２００は、アーム２９２上で回転可能である。ナビゲーション装置２００とドッキングステーションとの間の接続を解除するためには、例えば、ナビゲーション装置２００上のボタンを押下すればよい。ドッキングステーションに対してナビゲーション装置を結合及び分離する他の同等の適切な構成は当業者には既知である。
【００６４】
上述したように、地図データは、道路等の実際の特徴を表すために折れ線又は線形群を形成する複数の点を含む。しかし、地図データを簡略化して地図データを圧縮することにより地図データに必要な記憶容量を減少することが望ましい。更に、道路等の実際の特徴の表現を改善することにより地図データを更に視覚的に魅力的にすることが望ましい。
【００６５】
本発明の実施形態は、円弧を使用して地図データを簡略化しようとする。特に本発明の実施形態は、複数の点と交差する進路を近似する円弧によりそれらの点を置換することにより地図データを簡略化する。
【００６６】
以下の式を使用して線形群及び弧を形成する各点からの平方距離Ｒの合計を最小にしようとする最小二乗フィッティングを使用して円弧を点の集合にフィッティングできる。
式中、
は点ｐ０とｐｎとの間の円弧を示す。
【００６７】
しかし、最小二乗フィッティングの主な欠点は、線形群に対して可能な全てのショートカットを見つけることは計算的に非効率的であることである。例えば点ｐｉ，．．．，ｐｊの集合に対して、弧がｐｉとｐｋとの間で可能であるかを設定することは、弧がｐｉとｐｋ＋１との間で可能であるかを設定しないため、最小二乗フィッティングアルゴリズムは、線形群の可能な各小区分を計算的に評価することを必要とし、計算コストは高くなり且つ遅い。しかし、本発明の実施形態は、始点、終点、及び全ての中間点のそれぞれを囲む誤差円を通る弧の形成が可能であるかを事前に判定でき、それにより計算リソースの浪費を回避する。
【００６８】
本発明の一実施形態について説明する。本発明の実施形態は、以下に説明するように、可能な場合には、第１の点から開始して第２の点で終了し、且つ第１の点及び第２の点の間に存在する１以上の点の誤差円を通過する円弧で線形群を置換することを目的とする。
【００６９】
図５を参照すると、元の地図データでは線分４００、４０１により連結される３つの点ｐ０、ｐ１及びｐ２が示される。本発明の実施形態により生成された改訂版地図データにおいて、点ｐ０及びｐ２は点ｐ１の誤差円Ｄ１と交差する曲線の弧４１０により連結される。誤差円は半径εの円であり、点の周囲の所定の最大誤差範囲を表す。点を回避する全ての有効なショートカットは、その誤差円を通過する必要がある。
【００７０】
次に、図５のように第１の点、第２の点の誤差円、及び第３の点を通る弧の中心の設定方法を説明する。
【００７１】
紀元前３世紀の哲学者であるペルゲのアポロニウスの研究によると、２つの点及び円を通過可能な円は２つ存在する。従って、２つに分岐した軌跡が存在し、一方の分岐は円の内側に接する円の集合に対するものであり、他方の分岐は外側に接する円の集合に対するものである。これを図６に示す。図６（ａ）は、２つに分岐した軌跡を示す。図６（ｂ）は円の内側に接する円を示す。図６（ｃ）は、円の外側に接する円を示す。
【００７２】
軌跡の２つの分岐により記述された領域内に中心を有する全ての円は、その点及び円を通過する。２つに分岐した軌跡は双曲線として表され、ｐ０及びＤ１を通過する双曲線の２つの分岐の間の領域は本明細書において
で示される。
【００７３】
ここで、３つの点ｐ０、ｐ１及びｐ２の状況を考慮した場合、本発明者によると、ｐ０及びＤ１を通る全ての円が
内に中心を有する一方で、ｐ０及びＤ２を通る全ての円は
内に中心を有する。従って、ｐ０、Ｄ１及びＤ２を通る全ての円は
及び
内に中心を有する。これは、
で書くことができる。故に、複数の点ｐｉ，．．．，ｐｊから成る線形群を仮定すると、ｐ１及び他の全ての点の誤差円Ｄｉ＋１，．．．，Ｄｊを通る円の中心は領域Ａ内である必要がある。
【００７４】
円が点ｐｉ，．．．，ｐｊの既存の集合及び別の点ｐｊ＋１を通ることが可能である場合、Ａと
との共通集合のみを計算する必要があり、全ての可能性を評価する不要な計算時間を節約できる。以下の場合に円が可能である。
【００７５】
しかし、弧
は、点の誤差円Ｄｊ＋１を通るのではなく終点ｐｊ＋１で正確に終了する場合にのみ可能であることが認識されるだろう。これを設定するためにｐｉ及びｐｊ＋１の垂直二等分線
とＡとの交差が考慮される。ｐｉ、ｐｊ＋１、及び全ての中間点の誤差円を通る弧の中心は、
とＡとの交差により規定された線分上にある必要がある。
【００７６】
図７（ａ）は、双曲線
の交差を示す。図７（ｂ）は、
上に中心を有する点ｐ１〜ｐ５の誤差円と交差するｐ０からｐ６への可能な最小及び最大の弧を示す。
【００７７】
ｐ０及びｐ６等の２つの点が与えられると、数ｄはベクトル
とｐ０、ｐ６及び点ｐ１〜ｐ５の誤差円を通る弧との間の距離を表す。しかし、一方は正、他方は負である２つの値のｄが存在する。これらは点及び誤差円を通り、最短経路を見つけるためにそれらを区別する必要がある。
【００７８】
図８は、本発明の一実施形態に係る方法を示す。方法は、円弧により複数の点ｐｉ，．．．，ｐｊを近似できるかを判定し、近似できる場合はその弧に対する値ｄを計算する。
【００７９】
方法は、ステップ８００で開始する。ステップ８１０において、領域値Ａは、第１の点ｐｉと第２の点の誤差円Ｄｉ＋１との間の双曲線の２つの分岐間の領域に設定される。ステップ８２０において、値ｋは第２の点への指標の値ｉ＋１に設定される。８３０において、領域Ａが０でない値を有しており、かつｋがｊより小さい、即ち複数の点の最後の点に到達したか否かを判定する。双方の条件が満たされる場合、ステップ８５０に進む。しかし、一方又は双方の条件が満たされない場合、方法はステップ８４０で終了する。ステップ８５０において、ｋの値はインクリメントされる。ステップ８６０において、計算された領域Ａと垂直二等分線
との交差が計算される。ステップ８７０において、ｌが０でないこと、すなわち垂直二等分線
が領域Ａを通過することが判定される。この場合、ステップ８８０においてｄの値が計算される。値ｄは、垂直二等分線
と円弧との間の距離である。ステップ８７０においてｌ＝０である場合、あるいはｄがステップ８８０で計算された場合、ステップ８９０において、Ａの新しい値はｐｉと誤差円Ｄｉ＋１との間の新しい双曲線とＡの既存の値との共通集合により計算される。
【００８０】
方法は、更なる点を順次導入することにより再帰的に実行されることが図８から分かる。更なる点を導入した後、全ての中間点の誤差円を通る始点と終点との間の円弧をフィッティングできるかが判定される。フィッティングできない場合、ｌ＝０であり、円弧は最後の繰り返しで考慮された複数の点を表すために使用される。
【００８１】
ステップ８８０でｄを計算する方法について、図９を参照して説明する。
【００８２】
値ｄを判定するために、円弧上の３つの点、すなわち第１の点ｐｉ、終点ｐｋ及び好適な実施形態においては中点ｐｍ＝ｐ（ｉ＋ｋ）／２である第３の点が使用される。この中点は、図８のステップ８８０で実行される図９に示す方法のステップ９０１で判定される。
【００８３】
円弧は円の小区分であり、ステップ９０２において、その円の中心ｐｃが計算される。ｐｉ又はｐｋとｐｃとの間の距離は円の半径であり、その一方でｄはｐｉ及びｐｋを二等分する線
と円弧との間の距離である。従って、線
のどちら側に中心ｐｃが位置するかを計算する必要がある。これは、ステップ９０３で実行される。
【００８４】
ｐｃが線
の下側にあるとステップ９０３で判定された場合、以下の式が得られる。
換言すると、ｄは、円の半径から円の中心とｐｉ及びｐｋと交差する線との距離を減算した値である。しかし、ｐｃが線の上側にある場合、以下の式が得られる。
すなわち、ｄは、円の半径に円の中心とｐｉ及びｐｋと交差する線との距離を加算した値である。
【００８５】
ｐｘが線
のどちら側にあると判定されるかによって１又は−１を返す関数
が使用される場合、上記計算は以下のように書ける。
【００８６】
上記式において、SideOfLineはｐｃが線
の上側にあるか又は下側にあるかに依存して関連した距離の加算又は減算を行うために使用される。このように、ｄの値はステップ９０４で計算される。
【００８７】
上述した方法において、点と点の誤差円との間の双曲線を判定する必要がある。円錐多角形の交差を使用して双曲線の計算を行うことも可能であるが、本発明の好適な一実施形態は双曲線ｈの多角形近似ｈ’を使用する。
【００８８】
図１０（ａ）は一対の双曲線を示す。図１０（ｂ）は、（ａ）に示した一対の双曲線に対する漸近線及び接線を示す。図１０（ｃ）は、一対の双曲線に対する近似ｈ’を示す。
【００８９】
双曲線の重要な特性に対して図１０（ａ）に示した一対の双曲線を近似することが利用される。全ての双曲線は、(0, 0)を通る２つの漸近線、ｙ軸に平行でありｘ切片を有する２つの接線を有する。座標は双曲線に関係し、(0, 0)は焦点Ｆ１とＦ２との間の点である。漸近線及び接線は以下のように計算される。
漸近線：
接線：
【００９０】
漸近線及び接線は図１０（ｂ）に示され、図１０（ｃ）に示す近似が計算されることを可能にする。
【００９１】
このような近似は、実際の双曲線より僅かに小さい領域を呈するため、いくつかのショートカットは理論的には拒否される可能性があるが、誤判定がなされることはない。近似の誤差は、３つ以上の接線を使用することにより低減されてもよい。図９（ｃ）に示すように、多角形近似は無限サイズを有する。変数λは近似の長さを制限するために導入されてもよい。長さは１つの漸近線に沿って測定されてもよく、その長さは漸近線が互いに交差する点から開始する。
【００９２】
更に多角形交差を計算する必要があり、この目的のために掃引線アルゴリズム（sweep line algorithm）等のいかなる多角形交差アルゴリズムが使用されてもよい。
【００９３】
弧が複数の点に対する適切な近似であることを保証するために、本発明の実施形態は、距離の閾値及び角度の閾値の一方又は双方を使用する。
【００９４】
距離の閾値は、弧が連続した点の間の線分から離れてもよい最大距離である。即ち、それらの点の間の直線線分
と円弧
との間の最大許容距離である最大偏差値εが導入される。距離は、
が
と同一の傾きを有する時の
と
との間の距離である。弧及び線分が始点及び終点の双方を共有しない場合、距離ｄｋは、円弧
及び線分
により近似された点ｐ０，ｐ１．．．ｐ８から成る線形群に対して図１１に示すように、線分
とその線分を回避する弧との間の最大距離である。
【００９５】
角度の閾値は、入力弧及び線分のなす角度が非常に大きく異ならないように使用されてもよい。角度αｋは、
と線分を回避する弧とのなす角度であると考えられる。図１２は、図１１と同一の点の集合を示し、考慮された角度の閾値により近似される。角度αｋは最大近似角度未満であることが判定される。
【００９６】
図１３は、円弧近似が計算された種々のテストデータを示し、多くの場合、点の間の円弧近似を使用すると、元のポリデータの集合が非常に少ない点で表せることを実証している。
【００９７】
本発明の教示は、地図データを形成する点の数を減少する方法を提供することが上記より明らかとなる。本発明の実施形態の結果、ある領域に対する地図データは減少した記憶容量で保持され、ナビゲーション装置のコストを低減する。
【００９８】
本発明の種々の態様及び実施形態を説明したが、本発明の範囲は本明細書で説明した特定の構成に限定されず、添付の請求の範囲の範囲内の全ての構成、並びにそれらに対する変形例及び変更例を含むことが理解されるだろう。
【００９９】
例えば上記の詳細な説明で説明した実施形態はＧＰＳを参照するが、ナビゲーション装置はＧＰＳの代わりに（又は実際にはＧＰＳに加えて）どんな種類の位置検出技術を利用してもよい。例えばナビゲーション装置は、欧州のGalileoシステム等の他のグローバルナビゲーション衛星システムを用いることにより有用であってもよい。同様に、ナビゲーション装置は、衛星を用いたものに限定されないが、地上ビーコン又は装置が地理的な場所を判定することを可能にする他の何らかの種類のシステムを使用して容易に機能できる。
【０１００】
好適な実施形態はソフトウェアにより特定の機能性を実現するが、機能性はハードウェアのみで（例えば、１つ以上のＡＳＩＣ（特定用途向け集積回路）を使用して）又は実際にはハードウェア及びソフトウェアの組合せにより同等に実現可能であることが当業者にはよく理解されるだろう。従って、本発明の範囲は、ソフトウェアでのみ実現されることに限定されると解釈されるべきではない。
【０１０１】
最後に、添付の請求の範囲は本明細書で説明した特徴の特定の組合せを説明するが、本発明の範囲は以下に請求される特定の組合せに限定されず、特定の組合せが添付の請求の範囲において特に列挙されているかいないかに関わらず本明細書で開示された特徴又は実施形態のいかなる組合せも含む。
【特許請求の範囲】
【請求項１】
複数の点に円弧をフィッティングさせるように適切にプログラムされたコンピュータを用いる方法であって、
第１の点と少なくとも１つの中間点の周囲の領域とを通る円の中心が位置する領域が、前記第１の点及び第２の点を通る線の垂直二等分線と交差するか否かを判定する工程を備えることを特徴とする方法。
【請求項２】
前記第１及び第２の点の座標、及び前記第１及び第２の点を通る線と前記円弧との距離ｄを用いて前記複数の点を表す工程をさらに備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記判定する工程は再帰的に実行され、それぞれの再帰において前記第２の点はさらなる中間点となり、新たな第２の点が設定されることを特徴とする請求項１または２に記載の方法。
【請求項４】
前記距離ｄは、前記円の半径、及び前記円の中心と前記第１及び第２の点を通る線との距離を計算することにより判定されることを特徴とする請求項２または３に記載の方法。
【請求項５】
前記領域は、複数の双曲線の交点により形成される領域を判定することにより判定されることを特徴とする請求項１乃至４のいずれか１項に記載の方法。
【請求項６】
それぞれの双曲線は、一対の線状を呈す軌跡により形成され、当該線状を呈す軌跡上には前記第１の点及び更なる点の周囲の領域を通り、前記更なる点の周囲の円領域の内側及び外側のそれぞれに接する円の中心が位置することを特徴とする請求項５に記載の方法。
【請求項７】
前記複数の双曲線のそれぞれの近似を判定する工程をさらに備えることを特徴とする請求項５または６に記載の方法。
【請求項８】
前記近似は、一対の漸近線と接線との交点を含むことを特徴とする請求項７に記載の方法。
【請求項９】
前記近似を、前記漸近線のうちの１つに沿って、所定の長さに制限する工程をさらに備えることを特徴とする請求項７または８に記載の方法。
【請求項１０】
前記円弧と前記複数の点間で形成された線分群との最大偏差が、所定の距離より短いか否かを判定する工程をさらに備えることを特徴とする請求項１乃至９のいずれか１項に記載の方法。
【請求項１１】
前記円弧と、前記第１の点及び終点の間の前記複数の点間のそれぞれにおいて形成された線分群との最大角が、所定の角度より小さいか否かを判定する工程をさらに備えることを特徴とする請求項１乃至１０のいずれか１項に記載の方法。
【請求項１２】
前記複数の点は、地物を示す地図情報を形成することを特徴とする請求項１乃至１１のいずれか１項に記載の方法。
【請求項１３】
プロセッサにより実行された場合に、当該プロセッサに請求項１乃至１２のいずれか１項に記載の方法を実行させるためのコンピュータ実行可能命令が格納されたデータ記憶媒体。
【請求項１４】
プロセッサと、
前記プロセッサに動作可能に接続されたメモリと、を備え、
前記メモリは、複数の点の座標を有し、
前記プロセッサは、第１の点と少なくとも１つの中間点の周囲の領域とを通る円の中心が位置する領域が、前記第１の点及び第２の点を通る線の垂直二等分線と交差するか否かを判定する
ことを特徴とする装置。
【請求項１５】
前記プロセッサは、前記第１及び第２の点の座標により形成された前記複数の点の表示、及び前記第１及び第２の点を通る線と円弧との距離ｄを、前記メモリに格納することを特徴とする請求項１４に記載の装置。
【請求項１】
複数の点に円弧をフィッティングさせるように適切にプログラムされたコンピュータを用いる方法であって、
第１の点と少なくとも１つの中間点の周囲の領域とを通る円の中心が位置する領域が、前記第１の点及び第２の点を通る線の垂直二等分線と交差するか否かを判定する工程を備えることを特徴とする方法。
【請求項２】
前記第１及び第２の点の座標、及び前記第１及び第２の点を通る線と前記円弧との距離ｄを用いて前記複数の点を表す工程をさらに備えることを特徴とする請求項１に記載の方法。
【請求項３】
前記判定する工程は再帰的に実行され、それぞれの再帰において前記第２の点はさらなる中間点となり、新たな第２の点が設定されることを特徴とする請求項１または２に記載の方法。
【請求項４】
前記距離ｄは、前記円の半径、及び前記円の中心と前記第１及び第２の点を通る線との距離を計算することにより判定されることを特徴とする請求項２または３に記載の方法。
【請求項５】
前記領域は、複数の双曲線の交点により形成される領域を判定することにより判定されることを特徴とする請求項１乃至４のいずれか１項に記載の方法。
【請求項６】
それぞれの双曲線は、一対の線状を呈す軌跡により形成され、当該線状を呈す軌跡上には前記第１の点及び更なる点の周囲の領域を通り、前記更なる点の周囲の円領域の内側及び外側のそれぞれに接する円の中心が位置することを特徴とする請求項５に記載の方法。
【請求項７】
前記複数の双曲線のそれぞれの近似を判定する工程をさらに備えることを特徴とする請求項５または６に記載の方法。
【請求項８】
前記近似は、一対の漸近線と接線との交点を含むことを特徴とする請求項７に記載の方法。
【請求項９】
前記近似を、前記漸近線のうちの１つに沿って、所定の長さに制限する工程をさらに備えることを特徴とする請求項７または８に記載の方法。
【請求項１０】
前記円弧と前記複数の点間で形成された線分群との最大偏差が、所定の距離より短いか否かを判定する工程をさらに備えることを特徴とする請求項１乃至９のいずれか１項に記載の方法。
【請求項１１】
前記円弧と、前記第１の点及び終点の間の前記複数の点間のそれぞれにおいて形成された線分群との最大角が、所定の角度より小さいか否かを判定する工程をさらに備えることを特徴とする請求項１乃至１０のいずれか１項に記載の方法。
【請求項１２】
前記複数の点は、地物を示す地図情報を形成することを特徴とする請求項１乃至１１のいずれか１項に記載の方法。
【請求項１３】
プロセッサにより実行された場合に、当該プロセッサに請求項１乃至１２のいずれか１項に記載の方法を実行させるためのコンピュータ実行可能命令が格納されたデータ記憶媒体。
【請求項１４】
プロセッサと、
前記プロセッサに動作可能に接続されたメモリと、を備え、
前記メモリは、複数の点の座標を有し、
前記プロセッサは、第１の点と少なくとも１つの中間点の周囲の領域とを通る円の中心が位置する領域が、前記第１の点及び第２の点を通る線の垂直二等分線と交差するか否かを判定する
ことを特徴とする装置。
【請求項１５】
前記プロセッサは、前記第１及び第２の点の座標により形成された前記複数の点の表示、及び前記第１及び第２の点を通る線と円弧との距離ｄを、前記メモリに格納することを特徴とする請求項１４に記載の装置。
【図１】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公表番号】特表２０１１−５２４００９（Ｐ２０１１−５２４００９Ａ）
【公表日】平成２３年８月２５日（２０１１．８．２５）
【国際特許分類】
【出願番号】特願２０１１−５１１９８０（Ｐ２０１１−５１１９８０）
【出願日】平成２０年６月４日（２００８．６．４）
【国際出願番号】ＰＣＴ／ＥＰ２００８／００４５５８
【国際公開番号】ＷＯ２００９／１４６７２７
【国際公開日】平成２１年１２月１０日（２００９．１２．１０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＧＳＭ
２．Ｂｌｕｅｔｏｏｔｈ
【出願人】（３０７０４３２２３）トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【Ｆターム（参考）】
【公表日】平成２３年８月２５日（２０１１．８．２５）
【国際特許分類】
【出願日】平成２０年６月４日（２００８．６．４）
【国際出願番号】ＰＣＴ／ＥＰ２００８／００４５５８
【国際公開番号】ＷＯ２００９／１４６７２７
【国際公開日】平成２１年１２月１０日（２００９．１２．１０）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．ＧＳＭ
２．Ｂｌｕｅｔｏｏｔｈ
【出願人】（３０７０４３２２３）トムトム インターナショナル ベスローテン フエンノートシャップ (144)
【Ｆターム（参考）】
[ Back to top ]