概略目的地地図
請求される主題は、地理に関連する目的地への道順を提供するために機能強化された概略目的地地図を自動的に作成するのを容易にするシステムおよび/または方法を提供する。インターフェースコンポーネントが、少なくとも1つの地理的目的地を受け取ることができる。地図ジェネレータが、地理的目的地への少なくとも1つの道路を含む少なくとも1つの経路を提供するために、道路セットの階層を利用して、機能強化された概略目的地地図を自動的に作成することができる。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、概略目的地地図(schematic destination map)に関する。
【背景技術】
【0002】
電子ストレージ機構は、大量のデータの蓄積を可能にしてきた。たとえば、以前には何冊もの本を必要としたデータを、現在は、紙を印刷する出費なしに、紙を格納するのに必要なスペースの何分の1かのスペースで、電子的に記憶することができる。1つの特定の例では、以前は大量の紙に記録された証書および抵当権証書を、現在は電子的に記憶することができる。さらに、センサおよび他の電子機構の進歩が、現在、大量のデータをリアルタイムで収集することを可能にする。たとえば、GPSシステムは、GPSレシーバを有するデバイスの位置を追跡する。それに接続された電子ストレージデバイスを使用して、そのようなレシーバに関連する位置を保持することができる。さまざまな他のセンサも、類似するセンシング機能およびデータ保持機能に関連付けられる。
【0003】
今日のコンピュータは、さまざまな地図を生成するためのデータの利用をも可能にする。たとえば、インターネット地図作成アプリケーション(mapping application)は、ユーザが、1つまたは複数の住所を入力することを可能にし、地図作成アプリケーションがトリガされると、入力された住所に関連する地図および/または入力された住所の間の地図が、そのような地図に関連する道順と一緒にユーザに表示される。これらの地図は、普通に静的であり、たとえば、地図がポータブル機構(たとえば、スマートホン、PDA等)に表示される場合に、それらの地図は、感知されたユーザの位置の変化に伴って変更はされない。さらに、表示を動的に変更し、かつ/または特定の経路をグラフィカルに横断(traverse)する地図作成アプリケーションは、そのようなビューの深度を変更しない。したがって、ユーザは、横断される経路に関する最適のコンテキストを与えられない。
【0004】
高い品質および使い易さに起因して、概略目的地地図は、多数の重要な実世界の目的に使用することができる。イベントオーガナイザ(たとえば、結婚式プランナ)は、イベント位置に達する方法を招待客に示すために専用の地図を提供する。フランチャイズチェーンおよびショッピング区域は、店の位置を強調した概略地図を提供する。空港および旅行代理店は、しばしば、よその町からの訪問者に町をめぐる最良の/最も簡単な方法を示すために単純化された地図を提供する。会社、大学、病院、動物園、および他のキャンパスベースの組織は、それぞれのキャンパスの重要な建物および経路の位置および関係を示すために地図を提供する。
【発明の開示】
【発明が解決しようとする課題】
【0005】
各タイプの地図に描かれる詳細の量を検討する。事実に忠実な目的地地図は、一方の極にあり、一定の密度の詳細を含む。通常、これらの地図を作るソフトウェアは、指定された目的地に到達することに関連するか否かに関わりなく、所与のズームレベルで可視のすべてのものを表示する。たとえば、従来の事実に忠実な目的地地図では、多数の地方道路、駐車場、および近隣が、そのような詳細が目的地の発見に関してユーザにほとんど又は全く助けを提供しない場合であっても示される。
【0006】
詳細の他方の極に、概略経路図がある。概略経路図は、単一の起点と単一の目的地との間の単一の経路を描写する。非常にわずかな追加のコンテキスト情報がこの地図で提供され、特定の経路がなんらかの理由(たとえば、工事、交通渋滞、事故など)で使用不能な場合に、またはユーザが経路から迷った場合に、またはユーザが目的地付近の追加情報(潜在的な駐車位置など)を必要とする場合に、入手できる助けはごくわずかである。
【0007】
考慮すべき地図設計のもう1つの次元は、空間的関係が表される忠実度である。事実に忠実な目的地地図は、単一の共通の縮尺で地理的特徴を表示し、その結果、これらの地理的特徴は、航空写真から直接にコピーされたかのように、互いに現実的に比例して見えるようになる。その結果、多くの重要な特徴(たとえば、目的地へのローカル連絡道路)は、完全に不可視であるか有用になるには小さすぎてレンダリングされるかのいずれかになる。
【0008】
さらに、特定の目的地の「LineDrive」概略経路図は、単一の起点から目的地への単一の経路だけを最小の追加テキストと共に描写する。事実に忠実な目的地地図は、ディスプレイを混乱させ、多数の他の重要な詳細を隠す関連しない詳細を含む可能性がある。しかし、「LineDrive」地図および他の従来の概略経路図は、しばしば重要な詳細を隠し、かつ/または多すぎる余分な特徴を含む一定の縮尺および詳細の密度を伴って、目的地を囲む領域を描写する。さらに、そのような地図を作るために、地図作成者は、どの道路および他の地理的特徴のサブセットが地図の目的をサポートするかを注意深く判定し、そのような地図を手作業で作成する。
【課題を解決するための手段】
【0009】
本明細書で説明されるいくつかの態様の基本的な理解を提供するために、本革新(the innovation)の単純化された要約を以下に提示する。この要約は、請求される主題の外延的な概要ではない。請求される主題の重要な要素を識別することおよび本革新の範囲を描写することは意図されていない。その唯一の目的は、後で提示されるより詳細な説明の前置きとして、単純化された形で請求される主題のいくつかの概念を提示することである。
【0010】
本革新は、機能強化された概略目的地地図の自動生成を容易にするシステムおよび/または方法に関する。自動概略地図ジェネレータ(automatic schematic map generator)が、道路の階層を利用して、特定の目的地への複数の経路を提供する機能強化された(enhanced)概略目的地地図を自動的に生成することができる。自動概略地図ジェネレータは、地理データおよび目的地に関連するデータをインターフェースを介して受け取ることができ、道路の階層を利用する選択的フィルタリングが、目的地への少なくとも1つの経路を提供することができる。目的地に関連するデータとしては、ユーザから受け取られる、地図上の位置、住所、街路(street)、交差点、店、市、郡、国、建物、地図上の点に関連する任意のデータなどとすることができる。さらに、自動概略地図ジェネレータは、目的地を囲む地理データを利用して、機能強化された概略目的地地図を自動的に生成することができ、地理データは、たとえば、世界、州、市、郡、地域の地理に関連する任意のデータ、および/または目的地を囲む任意の適切な地理データとすることができる。
【0011】
機能強化された概略目的地地図は、読みやすい経路、抑制された(de−emphasized)詳細、関連しないデータの除外、明瞭なかつ/または単純化された地理的特徴、混乱の除去、使い易さ、および/または目的地への複数の経路、という改善のうちの少なくとも1つを含む簡素化された地図とすることができる。機能強化された概略目的地地図を、目的地を囲む地理データの評価に少なくとも部分的に基づいて簡素化できることを了解されたい。言い換えると、第1の目的地に関連する機能強化された概略目的地地図は、第2の目的地に関連する機能強化された概略目的地地図106と比較して、異なる改善(たとえば、抑制された詳細、関連しないデータの除外、明瞭なかつ/または単純化された地理的特徴、混乱の除去、目的地への複数の経路など)を含むことができる。
【0012】
請求される主題の一態様によれば、自動概略地図ジェネレータは、機能強化された目的地地図を提供するためにデータを階層的に選択し、かつ/またはフィルタリングするデータ選択コンポーネントを含むことができる。データ選択コンポーネントは、道路セットを利用することができ、道路セットはたとえば、大道路セット、中道路セット、および地方道路セットとすることができ、これらのセットは、道路のサイズ、制限速度、道路内の車線数などに基づくものとすることができる。たとえば、大道路セットは、州間ハイウェイを含むことができ、中道路セットは、幹線道路、州道、および大道路セットの境界内の他の主要道を含むことができ、地方道路セットは、中道路セットの境界内の一般道路路を含むことができる。
【0013】
請求される主題の別の態様によれば、自動概略地図ジェネレータは、道路に関連するジオメトリおよび/またはデータ選択コンポーネントからの階層的に選択された地理データを単純化する形状コンポーネントを含むことができる。形状コンポーネントは、形状単純化(shape simplification)を利用して個々の道路のジオメトリを単純化することができる。さらに、自動概略地図ジェネレータは、たとえば確率的探索(stochastic search)として道路レイアウトを構造化できる道路レイアウトコンポーネントを含むことができる。検索空間は、異なる可能な、道路網データの2Dレイアウトからなる。検索は、シミュレーテッド・アニーリング・アルゴリズムを用いて行うことができる。さらに、道路レイアウトコンポーネントは、ソフト制約(soft constraint)を伴うさまざまな変形を利用することができ、そのようなソフト制約は、トポロジ、道路の曲がり角、および/または道路ジオメトリに基づくものとすることができる。さらに、さまざまな摂動を利用して、道路および目的地に関連するレイアウトを生成することができる。たとえば、関節点(articulation point)ベースのスケーリングを利用することができる。
【0014】
本明細書で説明される革新の別の態様によれば、自動概略地図ジェネレータは、機能強化された概略目的地地図に追加情報を投入し(populate)、かつ/または機能強化された概略目的地地図を追加情報によって装飾する(decorate)ラベルコンポーネントをさらに含むことができる。ラベルコンポーネントは、機能強化された概略目的地地図に、道路ラベル、プロンプト道路(prompt road)ラベル、吹き出し、およびランドマークのうちの少なくとも1つを投入すると同時に、そのようなラベルの明瞭さおよび可読性を提供することができる。請求される主題の他の態様では、目的地の機能強化された概略目的地地図の作成を容易にする方法が提供される。
【0015】
以下の説明および添付図面は、請求される主題のある例示的態様を詳細に示す。しかし、これらの態様は、本革新の原理を利用できるさまざまな形のうちの少数を示すに過ぎず、請求される主題は、そのような態様およびその同等物のすべてを含むことが意図されている。請求される主題の他の利益および新規の特徴は、添付図面と共に解釈されれば本革新の以下の詳細な説明から明らかになるだろう。
【発明を実施するための最良の形態】
【0016】
請求される主題を、図面を参照して説明するが、類似する符号は、図面全体を通して維持する要素を指すのに使用される。以下の説明では、説明において、本発明の完全な理解をもたらすために多数の具体的な詳細を示す。しかし、請求される主題を、これらの特定の詳細なしで実践できることは明白であろう。他の場合には、周知の構造およびデバイスは、本革新の説明を容易にするためにブロック図形式で示す。
【0017】
本明細書で利用される時に、用語「コンポーネント」、「システム」、「ジェネレータ」、「インターフェース」等は、ハードウェア、ソフトウェア(たとえば実行中の)、および/またはファームウェアのいずれであれ、コンピュータ関連のエンティティを指すことが意図されている。たとえば、コンポーネントは、プロセッサで動作中のプロセス、プロセッサ、オブジェクト、実行可能ファイル、プログラム、および/またはコンピュータとすることができる。たとえば、サーバで動作するアプリケーションとそのサーバとの両方を、コンポーネントとすることができる。1つまたは複数のコンポーネントが、1つのプロセス内に存在することができ、1つのコンポーネントを、1つのコンピュータにローカライズし、かつ/または複数のコンピュータの間で分散させることができる。
【0018】
さらに、請求される主題は、開示される主題を実施するためにコンピュータを制御するためにソフトウェア、ファームウェア、ハードウェア、またはその任意の組合せを作るために標準的なプログラミング技法および/またはエンジニアリング技法を使用して、方法、装置、または製造品として実施することができる。本明細書で使用される用語「製造品(article of manufacture)」は、任意のコンピュータ可読デバイス、担体(carrier)、または媒体からアクセス可能なコンピュータプログラムを含むことが意図されている。たとえば、コンピュータ可読媒体は、磁気ストレージデバイス(たとえば、ハードディスク、フロッピディスク、磁気ストライプ等)、光ディスク(たとえば、コンパクトディスク(CD)、ディジタル多用途ディスク(DVD)等)、スマートカード、およびフラッシュメモリデバイス(たとえば、カード、スティック、キードライブ等)を含むことができるが、これらに限定はされない。さらに、搬送波を使用して、電子メールの送信および受信に使用されるものまたはインターネットもしくはローカルエリアネットワーク(LAN)などのネットワークにアクセスするのに使用されるものなどのコンピュータ可読電子データを搬送することができることを了解されたい。もちろん、当業者は、請求される主題の範囲または趣旨から逸脱せずに、この構成に対して多数の変更を行えることを認めるであろう。さらに、単語「例示的(exemplary)」は、本明細書では、例、実例、または例示として働くことを意味するのに使用される。本明細書で「例示的」として説明される任意の態様または設計は、必ずしも、他の態様または設計より好ましいまたは有利とは解釈されてはならない。
【0019】
ここで図面に移ると、図1は、機能強化された概略目的地地図の自動生成を容易にするシステム100を示す。システム100は、少なくとも1つの目的地に関連するデータを受け取ることができる自動概略地図ジェネレータ102を含み、機能強化された概略目的地地図106を地理データに少なくとも部分的に基づいて作成することができる。機能強化された概略目的地地図106は、読みやすい経路、抑制された詳細、関連しないデータの除外、明瞭なかつ/または単純化された地理的特徴、混乱の除去、使い易さ、および/または目的地への複数の経路という改善のうちの少なくとも1つを含む簡素化された地図とすることができる。機能強化された概略目的地地図106を、目的地を囲む地理データの評価に少なくとも部分的に基づいて簡素化できることを了解されたい。言い換えると、第1の目的地に関連する機能強化された概略目的地地図106は、第2の目的地に関連する機能強化された概略目的地地図106と比較して、異なる改善(たとえば、抑制された詳細、関連しないデータの除外、明瞭なかつ/または単純化された地理的特徴、混乱の除去、目的地への複数の経路など)を含むことができる。
【0020】
自動概略地図ジェネレータ102は、目的地に関連するデータを受け取ることができ、そのようなデータは、たとえば、ユーザから受け取られる、地図上の位置、住所、街路、交差点、店、市、郡、国、建物、地図上の点に関連する任意のデータなどとすることができる。さらに、自動概略地図ジェネレータ102は、目的地を囲む地理データを利用して、機能強化された概略目的地地図106を自動的に生成することができ、地理データは、たとえば、世界、州、市、郡、地域の地理に関連する任意のデータ、および/または目的地を囲む任意の適切な地理データとすることができる。たとえば、目的地は、ワシントン州シアトル、Main Street 1234の結婚披露宴式場などのユーザ指定の位置とすることができる。自動概略地図ジェネレータ102は、受け取られた目的地に少なくとも部分的に基づいて機能強化された概略目的地地図106を自動的に作成することができ、この地図は、読みやすい経路、抑制された詳細、関連しないデータの除外、明瞭なかつ/または単純化された地理的特徴、混乱の除去、使い易さ、ならびに/あるいは目的地への複数の経路などのさまざまな改善を含むことができる。そのような改善が、従来の事実に忠実な目的地地図、ラインドライブ地図、および/または他の伝統的な地図と比較してのものであることを了解されたい。
【0021】
さらに、自動概略地図ジェネレータ102は、機能強化された概略目的地地図106を自動的に作る少なくとも1つの原理を利用する。たとえば、この原理は、1)関連するデータだけを機能強化された概略目的地地図106に含めることができるように地理データを選択的にフィルタリングすること、2)機能強化された概略目的地地図106を理解しやすく使い易くするために地理データを変形すること、および3)道路名ラベル、注釈、および目的地住所など(たとえば、下で述べる。)、有用性を改善するための追加情報を用いて機能強化された概略目的地地図106を装飾することとすることができるが、これらに限定はされない。さらに、自動概略地図ジェネレータ102は、そのような技法および/または原理を反映するさまざまなアルゴリズムを実施することができ、そのような原理は、機能強化された概略目的地地図106を作るための時間および技量を減らすことができる。
【0022】
自動概略地図ジェネレータ102によって利用される原理および/または技法は、従来の地図と概略経路図との両方(たとえば、ラインドライブ地図)より道を見つけるのに有用になり得る機能強化された概略目的地地図106の自動生成を容易にする。自動概略地図ジェネレータ102は、各地図に描写される詳細の量を、囲む領域から目的地および/または目的地のセットへ(そして、たとえばそこから戻って)移動するのに必要なものだけに減らすことができる。さらに、システム100は、代替経路およびコンテキストによって地図ユーザをサポートし、地図の明瞭さおよび有用性を最大にするために、選択された詳細をレンダリングする。
【0023】
自動生成される機能強化された概略目的地地図106は、地図を読みやすく使い易くするために、目的地への読みやすいさまざまな経路を含み、関連しない詳細の強調をやめ、かつ/または除外し、多数の地理的特徴を変形し、かつ/または単純化することができる。機能強化された概略目的地地図106は、1つまたは複数のユーザ指定の目的地の位置およびコンテキストを強調し、囲む場所からそのような目的地に到達する複数の道を示す。そのような機能強化された地図106は、自動的に生成され、ユーザが描写された目的地に達するのを助けるのに必要な地理的詳細だけを含みながら従来の経路図よりはるかに有用な情報を含むことができる。
【0024】
機能強化された概略目的地地図106を、ミーティング、パーティ、および参加者が複数の異なる方向から来るが、たとえば予算が従来の手作りの地図に投資することを許さないその他のイベントに利用できることを了解されたい。さらに、機能強化された概略目的地地図106は、複数の異なる経路を描写することができ、目的地の間の輸送の複数のモードさえ描写することができる、パーソナライズされた「複数経路」地図に利用することができる。さらに、一連の名所旧跡、ホテル、店、不動産などをそれに関連する経路と共に示す自動生成される機能強化された概略目的地地図106を、休暇、旅行、および使い走りに利用することができる。
【0025】
たとえば、機能強化された概略目的地地図は、目的地の周囲の地域を囲む地図とすることができ、囲む地域には、経路階層を投入することができる。経路階層は、道路のサイズに少なくとも部分的に基づくものとすることができる。たとえば、最大の道路は、州間ハイウェイとすることができる。次に、中サイズの道路を利用することができ、中サイズの道路は、大道路(たとえば、最大の地域の境界)によって囲まれるものとすることができる。中サイズの道路は、幹線道路、州道、および他の主要道とすることができる。次に、一般道路(local street)を利用することができ、一般道路は、中サイズの道路の中に含まれる。
【0026】
さらに、システム100は、任意の適切なおよび/または必要なインターフェースコンポーネント104(本明細書では「インターフェース104」と呼称する。)を含むことができ、インターフェース104は、自動概略地図ジェネレータ102を事実上すべてのオペレーティングシステムおよび/またはデータベースシステムに統合するために、さまざまなアダプタ、コネクタ、チャネル、通信パスなどを提供する。さらに、インターフェース104は、自動概略地図ジェネレータ102、地理データ、目的地、目的地のセット、および/またはシステム100に関連する任意の他のデータとの相互作用を提供する、さまざまなアダプタ、コネクタ、チャネル、通信パスなどを提供することができる。
【0027】
図2に、目的地に少なくとも部分的に基づく少なくとも2つの経路を有する機能強化された概略目的地地図の自動生成を容易にするシステム200を示す。システム200は、道路の階層および目的地に少なくとも部分的に基づいて機能強化された概略目的地地図206を自動的に作成する自動概略地図ジェネレータ202を含む。たとえば、自動概略地図ジェネレータ202は、ユーザから少なくとも1つの目的地を受け取ることができ、ここで、それぞれの機能強化された概略目的地地図206を、地理データを利用して作成することができる。機能強化された概略目的地地図206が、事実に忠実な経路図より少ない詳細および/またはより低い精度を含むことができ、なおかつユーザが階層道路セットから目的地に達することを可能にするのに十分な機能強化された特徴を含むことができることを了解されたい。
【0028】
自動概略地図ジェネレータ202は、データストア204を利用することができ、データストア204は、システム200に関連するさまざまなデータを格納することができる。データストア204は、道路、街路、高速道路、州間高速道路、橋、建物、駐車場、ランドマーク、水域、川、交差点、トンネル、料金所、高台、国境、境界、学校、消防署、警察署、刑務所、野生生物保護区域、および/または地理的地図上の表示に適する任意の他のデータなどであるがこれらに限定はされない地理データのストレージを提供することができる。データストア204は、たとえば、揮発性メモリまたは不揮発性メモリのいずれかとすることができ、あるいは、揮発性メモリと不揮発性メモリとの両方を含めることができる。限定ではなく例として、不揮発性メモリは、読取専用メモリ(ROM)、プログラマブルROM(PROM)、電気的プログラマブルROM(EPROM)、電気的消去可能プログラマブルROM(EEPROM)、またはフラッシュメモリを含むことができる。揮発性メモリは、ランダムアクセスメモリ(RAM)を含むことができ、このRAMは、外部キャッシュメモリとして働く。限定ではなく例として、RAMは、スタティックRAM(SRAM)、ダイナミックRAM(DRAM)、シンクロナスDRAM(SDRAM)、double data rate SDRAM(DDR SDRAM)、enhanced SDRAM(ESDRAM)、Synchlink DRAM(SLDRAM)、Rambus direct RAM(RDRAM)、direct Rambus dynamic RAM(DRDRAM)、およびRambus dynamic RAM(RDRAM)などの多数の形で入手可能である。本システムおよび方法のデータストア204は、上記および任意の他の適切なタイプのメモリを、これらに限定されずに含むことが意図されている。さらに、データストア204を、サーバ、データベース、ハードドライブなどとすることができることを了解されたい。
【0029】
自動概略地図ジェネレータ202は、道路階層が接続され、複数の経路を含むことを保証するために階層選択判断基準を利用するデータ選択コンポーネント204を含むことができる。それでも、機能強化された概略目的地地図206が、そのような目的地がそれに関連する単一の経路だけを有するときに、単一の経路を含むことができることを了解されたい。データ選択コンポーネント208は、目的地を囲む道路階層に基づいて地理データをフィルタリングすることができる。言い換えると、道路セットの階層を利用して、目的地への少なくとも1つの経路を作成することができる。道路セットは、たとえば、大道路セット、中道路セット、および地方道路セットとすることができ、そのようなセットは、道路サイズ、制限速度、道路内の車線数などに基づくものとすることができる。たとえば、大道路セットは、州間ハイウェイを含むことができ、中道路セットは、幹線道路、州道、および大道路セットの境界内の他の主要道を含むことができ、地方道路セットは、中道路セットの境界内の地方道路を含むことができる。
【0030】
自動概略地図ジェネレータ202は、さらに、道路に関連するジオメトリおよび/またはデータ選択コンポーネント208からの階層的に選択された地理データを単純化する形状コンポーネント210を含むことができる。形状コンポーネント210は、形状単純化を利用して個々の道路のジオメトリを単純化することができる。形状単純化が、LineDriveシステムでの形状単純化について概要を示したものに実質的に類似する手順、原理、および/または基本アルゴリズムを実施できることを了解されたい。形状単純化は、偽交差点(false intersection)の導入に関するより多くの可能性があるという事実によって、形状コンポーネント210ではより制約され得る。形状コンポーネント210は、反復最適化(iterating optimization)によって、SIGGRAPHタイムフレームでそのような偽交差点に対処することができる。言い換えると、形状コンポーネント210は、形状単純化を実行し、次に道路レイアウトを実行し、次に形状単純化をもう1ラウンドを実行し、以下同様に実行する。
【0031】
システム200の自動概略地図ジェネレータ202は、さらに、道路レイアウトコンポーネント212を含むことができる。道路レイアウトコンポーネント212は、たとえば確率的探索として道路レイアウトを構造化することができる。検索空間は、異なる可能な、道路網データの2Dレイアウトからなる。検索は、シミュレーテッド・アニーリング・アルゴリズムを用いて行うことができる。このアルゴリズムは、道路網の適当に初期化されたコピーから開始する。たとえば、図5(A)の502にある初期化された地図を参照されたい。このアルゴリズムに関連する各の反復(iteration)中に、道路のレイアウトを、道路レイアウトコンポーネント212によってある形で(図3でより詳細に述べる。)摂動させることができる。新しいレイアウトを、摂動に少なくとも部分的に基づいて評価することができる。レイアウトのスコア(score)が、摂動の結果として低くなる場合には、新しいレイアウトが、このアルゴリズムの新しい反復への入力として受け入れられる。スコアが、摂動の結果として高くなる場合には、そのレイアウトは、ある確率で受け入れられ、そうでない場合には拒絶され得る。より悪いレイアウトを受け入れる確率は、温度変数(temperature variable)に依存し、この温度変数は、諸ステージで経時的に低下することができる。
【0032】
自動概略地図ジェネレータ202は、機能強化された概略目的地地図206に関連する道路のラベル付けを容易にするラベルコンポーネント214を含むことができる。ラベルコンポーネント214は、自動化されたラベル配置技法を実施することができる。たとえば、アニーリング手法を利用することができ、ここで、そのような技法は、互いに干渉せず、高められた可読性を提供する、明瞭で簡潔なラベルを可能にする。たとえば、ラベルコンポーネント214は、配置、フォント、方位などを維持できるように、めいめいの可読性に干渉しない、道路のラベルを提供することができる。ラベルコンポーネントが、ラベル付けと機能強化された概略目的地地図206のさまざまな態様に対する変形との間で反復することができることを了解されたい。したがって、新しいレイオーバー(layover)をさらに変形し、その結果、ラベルがよりよくおさまるようにすることができる。次に、ラベル付けの第2の反復を、変形の後で使用して、ラベルのされなる洗練を可能にすることができる。ラベル付けと変形との間の任意の適切な回数の反復を理解されたい。
【0033】
図3に、目的地の機能強化された概略目的地地図の作成を容易にするシステム300を示す。システム300は、前の図で説明したデータ選択コンポーネント204を含み、ここで、データ選択コンポーネント204は、特定の目的地に関連する地理データの階層選択を提供する。データ選択コンポーネント204は、道路階層が接続され、複数の経路を含むことを保証するために、階層選択判断基準を利用することができる。
【0034】
ユーザが目的地を指定すると(たとえば、目的地を(A)オリジナル地図に見ることができる、図4の402を参照されたい。)、データ選択コンポーネント208は、どの道路を機能強化された概略目的地地図206に含めることができるかを選択する。「好ましい」道路のセットを決定するために変更された2次元(2D)幾何可視性アルゴリズムを利用することによって、道路選択に関する階層設計判断基準を使用することができる。データ選択コンポーネント208は、次のように3つの可視性パス(visibility pass)を実行する。第1のスイープ(sweep)では、地図内の他のすべての道路が不可視であるかのように、どの大ハイウェイが目的地から可視であるかに関する判定。手短に図4を参照すると、404で、これらのハイウェイを(B)可視性に見ることができる。次に、データ選択コンポーネント208は、大ハイウェイおよび/または最大検索地域の境界によって囲まれる地域(いずれか小さい方)内の中サイズの道路(たとえば、幹線道路、他の主要道)のもう1つのスイープを実行する。手短に図4を参照すると、404で、これらの中サイズの道路を(B)可視性に見ることができる。最後に、データ選択コンポーネント208は、中サイズの道路、大ハイウェイ、および最大検索地域によって囲まれる地域(いずれであれ、より小さいもの)内の一般道路だけのスイープを実行する。手短に図4を参照すると、404で、これらの一般道路を(B)可視的に見ることができる。最大検索地域を、たとえば目的地から10kmなど、予め定めた限度の半径の中に含まれるすべてのものと定義できることを了解されたい。
【0035】
集められた「好ましい」道路のセットが、経路を含まない場合があり、接続されてさえいない場合がある。したがって、データ選択コンポーネント208は、可能な時には必ず、好ましい道路を含む経路を構成する。データ選択コンポーネント208は、一連の変更されたA*スタイル経路発見パス(modified A*−style route finding pass)を利用することができる。A*アルゴリズムは、最適性判断基準(たとえば、最短経路、最速経路、最少の曲がり角など)に従って起点と目的地点との間の単一の最適な経路を見つける。このアルゴリズムを、最短経路を検索しながら好ましいセット内の道路を優先するように変更することができ、大ハイウェイ終点のセットを、経路起点のセットとして選択することができる。データ選択コンポーネント208は、各ハイウェイ終点(たとえば、ハイウェイが最大検索地域の境界と交差する場所)から目的地への1つの経路を計算し、目的地から各ハイウェイ終点への1つの経路を計算することができる。手短に図4を参照すると、406で、この計算を、(C)可視経路差に見ることができ、ここで、従来の地図からこのアルゴリズムによって追加されなければならならなかった相対的に少数の道路(たとえば、経路のみ)。可視性アルゴリズムおよび経路発見アルゴリズムを用いて識別されたすべての道路の和集合(union)が、機能強化された概略目的地地図206に関する道路のすべての選択物を構成する。手短に図4を参照すると、道路セットの階層を利用するこのすべての選択物が、408の(D)最終的な道路選択の下に示されている。
【0036】
複数の目的地を含む地図は、単一の目的地を含む地図が処理される方法の単純な一般化を用いてデータ選択コンポーネント208によって処理することができる。まず、各個々の目的地の可視性結果の和集合をとり、次に、すべての経路組み合わせの交差を見つける。
【0037】
データ選択コンポーネント208が、機能強化された概略目的地地図206に含めるべき道路の全セットを決定すると、様々なデータクリーニング手順を実行して、そのような地図が地図レイアウト設計原理を満足するのをより簡単にすることができる。まず、データ選択コンポーネント208は、すべてのオーバーパス(たとえば、ある道路が別の道路の上を通過するが交差しない場所)を識別することができる。次に、動的計画法アルゴリズムを使用して、道路のチェーンをマージし、チェーンのどのプロパティが最も関連するかを判定することができる。最後に、上下関係を共有する道路と、横並び関係を共有する道路とをグループ化することができ、その結果、そのような道路を、一緒に変形できるようにする(下で述べる)ことができる。
【0038】
データ選択コンポーネント204は、階層に基づく道路の選択を容易にするために道路階層コンポーネント302を含むことができる。道路階層コンポーネント302は、階層設計判断基準に従うために、上で説明した道路セットの階層を使用する。階層構造を前もって提供することによって、道路階層コンポーネントを、比例して使い易くすることができる。道路階層コンポーネント302は、目的地に関して階層的に道路を選択することができる。地図作成者に基づいて、目的地を囲む地域内の最大の道路(たとえば、州間ハイウェイ)は、一般に、ランドマークとして認識することができ、その地域に少ししか馴染みのない人々がこれを突き止めることができる。道路コンポーネント302は、地図ユーザが支援なしで大道路の1つを見つけることができるならば、その地図ユーザは機能強化された目的地地図を使用してそこから目的地に達することができるという推論を用いて、まず最大の道路を選択する。道路階層コンポーネント302は、大道路(および/または最大地域の境界)によって囲まれた地域内から中サイズの道路のセットを選択することができる。これは、幹線道路、州道、および他の主要道を含む。道路階層コンポーネント302は、中サイズの道路(および/または最大地域)によって形成される地域内から目的地を囲む一般道路をも選択することができる。
【0039】
道路階層コンポーネント302が、任意の適切な道路選択技法を利用できることを了解されたい。たとえば、可視性演算子(visibility operator)を利用して、あるクラス(たとえば、サイズなど)内の少なくとも1つの可視の道路を見つけることができる。その後、街路および幹線道路を機能強化された概略地図に含めることができるように(たとえば、ある経路と共に使用されるかどうかに無関係に)、可視の道路のクラスを使用することができる。可視の道路の最大のクラス(the largest class of visible roads)のエッジは、道路の最大のクラスが大道路(ハイウェイ、主要道など)であるかどうかにかかわりなく使用することができる。さらに、ソースプレート(source plate)を部分グラフ(たとえば、道路の接続された部分)から選択することができる。言い換えると、可視性は、可視エッジを識別し、エッジは部分グラフに属し、これらの部分グラフは、道路を含む。エッジを、最大の道路クラスから選択し、部分グラフを解明し、部分グラフの末端の点をとって、目的地へおよび目的地からの毛細経路(capillary route)のソース点にすることができる。道路階層コンポーネント302は、さらに、ソース点から目的地への経路(「to経路」とも称する。)を見つけるためにたどるべきおよび/または他の道路/経路と比較して部分的である可視エッジが属する部分グラフの特定の道路/経路を識別することができる(ブリーディング技法など)。道路階層コンポーネント302は、グラフ内の最大の道路のセットおよび経路(to経路)のセットを利用して、「from経路」すなわち、目的地から部分グラフソース点への経路を計算することができる。「from経路」は、可視性から最大の経路だけを優先するのではなく、最大の道路を優先することを可能にするために「to経路」をも優先する。この技法は、地図内の独立経路の量を減らすことができる(たとえば、経路をさらに単純化する)。「to経路」および「from経路」を、可視性から識別された街路および幹線道路と組み合わせ、次に、収集されたエッジから、目的地のすべてに関連する最大の接続するコンポーネントと組み合わせることができ、それを、道路の集合/選択物とすることができる。
【0040】
データ選択コンポーネント204は、さらに、経路コンポーネント304を含むことができる。データ選択コンポーネント204は、経路コンポーネント304によって実施できる次の3つの望ましい目標を反映する、地図内の「好ましい」道路のセットを確立する。第1に、地図は、目的地から大きい地域へ/大きい地域から目的地への効率的な道筋を記述することができ、これは、地図をより柔軟でより広い範囲のユーザに有用にすることができる。第2に、好ましい道路は、それ自体で使い易いものとすることができ、これは、地図作成者の重要な判断基準とすることができる。第3に、好ましい道路のセットを組み込むために偏らされた経路は、地図ユーザを最長の可能な時間の長さにわたって最大の可能な道路上に保つことができ、これは、比較的少数の旋回でたどりやすい経路をもたらす(地図作成者のもう1つの重要な目標)。
【0041】
経路コンポーネント304は、可能な時には必ず好ましいセットからの道路を使用し、そうでない時には事実に忠実な地図から補足して、経路を明示的に設計する。経路コンポーネント304は、経路発見の主要な設計目標を実施することができ、ここで、主要な設計は、すべての最大の道路の両側から各目的地へ/各目的地からすべての最大の道路の両側へ達する少なくとも1つの道を記述する複数の経路を確立することとすることができる。このようにして、経路コンポーネント304は、現在の状態(たとえば、交通、工事など)、地図ユーザがどこから来る可能性があるか、および地図ユーザが道に迷ったかどうかに応じて、地図ユーザが動的な形でそこから選択できる代替案を提供することができる。
【0042】
システム300は、さらに、道路レイアウトコンポーネント210を含む。道路レイアウトコンポーネント210は、変形コンポーネント306を含むことができる。変形コンポーネント306は、明瞭さおよび有用性を最大にするために、階層的に選択された地理データをレンダリングすることができる。道路選択に関して、概略目的地地図レイアウトを、人々の空間的知覚および記憶の独自の特性に配慮して設計することができる。たとえば、我々が空間の記憶に幾何学的変形を自然に導入することを示す十分な証拠がある。これは、理解がより単純であり記憶がより簡単である、あらかじめ考えられたモデルに知覚を合わせる試みにおいて自動的に行われる可能性がある。この知覚から、いくつかの地図特徴が、他の特徴より重要であり、より重要でない特徴は、地図の有用性に影響せずに安全に変更でき、より重要な特徴は、有用性を高めるために保存され、かつ/または強調されなければならない。
【0043】
地図作成者は、何世紀にもわたってこれを認識しており、地図作成法研究および認識研究は、地図描写のさまざまな態様が地図の有用性に関してどれほど重要であるかの順序付けを提案してきた。たとえば、最上位に、地図特徴(map feature)の存在(existence)および連結性(connectedness)を置くことができる。その次は、地図全体および個々の特徴の方位(orientation)とすることができる。その後は、お互いに関する地図特徴の局所化(localization)とすることができる。最後に、特徴の間の距離(distance)および特徴の形状(shape)は、従来の地図においてさえしばしば変形されるので、より低い重要性を有するものとすることができる。
【0044】
このフレームワーク内で、変形コンポーネント306は、2つの主な地図レイアウト目標すなわち、1)最終的な地図内のすべての道路が可視であることと、2)オリジナルの道路網トポロジが維持されることとを確実にすることとを有することができる。より少ない範囲まで、変形コンポーネント306は、ユーザの現実および一般的な知識の精神的モデルへの地図の全体的な対応をも維持することができ、特にそれによって描写される区域に馴染みがある人々にとって、プラニングデバイスとして使用することがより簡単になる。また、特に、後にある区域を通って移動する前にその区域に馴染みがない人々にとって、記憶の助けとして地図を使用することがより簡単になる。
【0045】
変形コンポーネント306は、ループを含むグラフの変形のより一般的なケースに対処することができる。変形コンポーネント306は、ソフト制約のセットにわたり最適化することによって、心理学的に意味のある変形目標を満足することができ、これらの制約の一部を完全には満足できない場合であっても妥当な結果を作ることができる。以下は、変形コンポーネント306によって地図変形を実行することによって満足できるソフト制約の各セットの説明である。
【0046】
変形コンポーネント306は、発生する交差点のセットおよび交差点での道路の相対順序付けを含む、地図の道路網の基本トポロジを維持することができる。実際には存在しない新しい交差点(たとえば、偽(false)交差点)の導入は、実際には存在しない経路を含むトポロジ的に不正確な地図をもたらすだろう。そのような交差点がトポロジに実際に発生する場所で交差点を表すことができないこと(たとえば、欠けている交差点)は、一般に、より低いリスクとすることができる。しかし、これも望ましくはない。というのは、我々の道路選択アルゴリズムによって選択される道路網は、それが含む経路に部分的に基づいて選択されるからであり、交差点の省略は、その網から1つまたは複数の経路を削除することと同等であるからである。
【0047】
さらに、変形コンポーネント306は、旋回方向を維持することができる。各交差点で、入射する道路のすべての対の間の旋回方向を維持することができる。ある道路から別の道路への右旋回は、右旋回のままにすることができ、左旋回は、左旋回のままにすることができる。道路の任意の対の間で旋回方向を変更することは、地図ユーザを激しく混乱させ、経路プラニングの誤りにつながり、地図に従っている間にユーザに道に迷わせる可能性がある。
【0048】
変形コンポーネント306は、旋回に関する正確な描写をも提供することができる。一般に、人々は、経路をナビゲートしている時に各旋回点で行うべきことに関する判断を行う必要があり、したがって、旋回点の正確な描写は極めて重要である。実際に、複数の研究は、そこでのユーザアクティビティをサポートするために判断点(旋回など)の周囲の情報に集中することが特に重要であると結論してきた。
【0049】
たとえば、変形コンポーネント306が、少なくともゲシュタルト心理学によって識別される3つの「ゾーン」すなわち鋭角、直角、および鈍角の範囲で、できる限り旋回角(たとえば、交差点で出会う時の道路セグメント間の相対角度)を維持することが重要である。すなわち、鋭角は、鋭角のままでなければならず、直角は、ほぼ直角のままでなければならず、鈍角は、鈍角のままでなければならない。それを行うことができないと、ユーザが実際に地図に従っている時にユーザを混乱させる可能性がある。それを行うことができないと、ユーザが、地図の詳細をその地図内に描写された曲がり角および道路のメンタルイメージに関連付けることがより困難になる可能性もあり、これは、地図と現実との間の基本的な対応を維持するという目標に反する。ユーザが、一般に、記憶の中でほとんどの曲がり角を直角に正規化することを示すいくつかの認識的証拠があり、したがって、最も極端な例について鋭さと鈍さとを維持することができる。
【0050】
関連する目標は、交差点を通って直線状に続く道路を変形コンポーネント306によってその交差点でまっすぐに保たなければならないこととすることができる。旋回角に関する状況に似て、交差点を通過する道路に関する3つの重要な「ゾーン」すなわち、左への方向転換、直進、右への方向転換がある。たとえば、ユーザが交差点に接近している時に、地図は、道路が(たとえば、現実において)その交差点を越えて続くときにどうなるか(たとえば、左に方向転換するのか、右に方向転換するのか、又は直進するのか)に関する知覚を反映することができる。道路が現実において左に方向転換するが、地図では右への方向転換として描写される場合に、これはユーザを混乱させ、ナビゲーションの助けとしての地図の有用性を下げる可能性がある。
【0051】
変形コンポーネント306は、さらに、道路ジオメトリを維持することができる。道路ジオメトリのいくつかの態様を維持することができ、他の態様を、地図の明瞭さおよび可読性を改善するために変更することができる。たとえば、変形コンポーネント306が、道路の長さの相対的な順序付けを維持することが重要である(たとえば、交差点の対の間の道路Aが、実際には交差点の別の対の間の別の道路Bより長い場合に、Aは、変形された地図内でもBより長く見えなければならない)。長さの相対的な順序付けが問題であって、別の長さに対するある長さの比率は問題でないことを了解されたい。さらに、これが、他の道路との交差点の間に走る道路にあてはまるのであって、次第に消える(たとえば、地図の境界に向かう)「尾(tail)」道路にはあてはまらないことにも留意されたい。
【0052】
エッジの長さの相対順序付けを維持することは、地図を通ってたどるべき経路がどれであるかに関する判断を行うのにユーザが利用できる基本的な情報を提供するので、重要である可能性がある。ユーザが、たどるべき経路がどれであるかに関する、情報を与えられた判断(informed decision)を行うために経路の文字どおりの長さを見ることが重要であるのではなく、ある経路が別の経路より長いことを見ることだけが重要である可能性がある。変形コンポーネント306が、特に類似するクラスの道路の間で、あまりに順序はずれで道路の相対長を配置する場合、これは、地図に従う時にユーザの知覚と矛盾し、したがって、地図をより混乱を招きより従いにくいものにする可能性がある。しかし、相対長の順序の変更は一般に、地図トポロジの変更と同じ態様で地図を使用不能にすることはできない。
【0053】
自動車内で運転中のユーザにとってはしばしば時間が距離より重要なので、変形コンポーネント306は、セグメントをトラバースするのに必要な時間の長さを表す道路長を採用することができる。したがって、州間ハイウェイの1マイル(1.6km)セグメントは、街路の1マイル(1.6km)セグメントよりはるかに短いものとして表される(たとば、より高い制限速度を有し、より高速でトラバースするのにより短い時間を要するので)。言い換えると、これを、文字どおりの長さの相対順序付けに加えて、変形コンポーネント306が維持できる長さの相対順序付けとすることができる。
【0054】
変形コンポーネント306によって維持できる道路ジオメトリのもう1つの重要な態様を、いくつかの別個の道路によって共有される関係とすることができる。たとえば、2つに分かれるハイウェイまたは大通りの別々の方向など、いくつかの道路は、互いに「横並び(side−by−side)」関係を共有する。他の道路は、「上下」関係を共有する。これらの関係を、情報を与えられたユーザの期待、および情報を与えられないユーザのあらかじめ考えていたモデルと一致するために維持することができる。それを行うことができないと、地図に描写される区域に馴染みのあるユーザの記憶と矛盾する可能性がある。さらに、地図ユーザがその区域に馴染みがない場合であっても、2つに分かれるハイウェイの2つの方面を、正しい相対幾何関係ではなく、非常に離れてまたは互いに関して異なる角度で描写する地図によって示される区域を見ることは、驚かせ、おそらくは混乱させるものである可能性がある。
【0055】
さらに、変形コンポーネント306は、道路方位を維持することができる。各道路は、たとえば北方向に関する、その主な方位をできる限り維持することができる。道路方位が大きく変化する(たとえば、主に南北から主に東西へ)場合、そのような変動は、ユーザによる地域の理解と矛盾する可能性があり、地図の詳細を実際の地理的特性と一致させることをより困難にする可能性がある。しかし、これを念頭において、人々が主要な軸に向かって地図内の図形を回転する傾向があることを示す認識心理学からの重要な証拠がある可能性がある。その結果、主な方位を維持することが重要ではあるが、変形コンポーネント306にとって、正確な方位を維持することはより重要でない。
【0056】
最後に、変形コンポーネント306は、正確な道路の長さおよび形状をゆるやかに維持することができる。人々は、道路にのったならば、次の旋回点に達するまで、たどられる道路の長さおよびジオメトリに関してあまり考えずにその道路をたどることができる。したがって、正確な長さおよび形状の描写は、変形コンポーネント306にとってさほど重要ではない可能性がある。この点では、考え抜かれた道路形状単純化は、実際に、地図の明瞭さおよび可読性を改善することができる。
【0057】
図3を継続すると、道路レイアウトコンポーネント210は、摂動コンポーネント308を含むことができる。摂動コンポーネント308は、ランダムなレイアウト摂動を生成することによって一般的な道路網(たとえば、ループを含むグラフ)の変形を容易にすることができる。設計原理に伴ってレイアウトプロセスに課せられる構造的制約をある意味で反映しない摂動は、不可避的に、多数の許容できないレイアウトを生成する可能性がある。その一方で、制約されすぎた摂動は、検索(search)を谷および悪い極小値に簡単にトラップさせる可能性がある。摂動コンポーネント308は、上で説明した原理を達成するために、さまざまな摂動を利用することができる。
【0058】
たとえば、摂動コンポーネント308は、「関節点ベースのスケーリング」と称する第1のスタイルの摂動を実施することができる。グラフ理論では、関節点は、除去された場合にグラフを複数の独立の連結成分に分離できる、連結グラフ内の頂点である。道路網では、これは、除去された場合に網を複数の別個の地図に分離できる交差点に対応する。我々の摂動コンポーネント308は、道路網内の関節点をランダムに選択するステップと、その点の付近で網を分解するステップと、結果の成分のうちの1つをランダムに選択するステップと、ランダムスケールファクタによって、選択された点の付近の選択された成分をスケーリングするステップと、あらかじめ指定された境界ボックスまで戻して、地図全体をセンタスケーリングするステップとを含むことができる。たとえば、それぞれ図5の502、504、および506を参照されたい。関節点ベースのスケーリング摂動は、道路レイアウトの構造的制約を反映することができる。摂動は、欠けている交差点を絶対にもたらすことができず、旋回角を絶対に変更せず、必ず道路方位を維持することができる。
【0059】
道路レイアウトコンポーネント210は、さらに、スコアリングコンポーネント310を含むことができる。新しい道路レイアウトが、摂動コンポーネント308によって実施される摂動によって生成されるたびに、スコアリングコンポーネント310は、上で概要を示し、述べた地図変形設計原理に従って、そのようなレイアウトを評価することができる。具体的に言うと、スコアリングコンポーネントは、次の諸態様を利用することができる。まず、新しい偽交差点が導入されたか否か、および真の交差点が欠けているか否かを判定する。これらは、摂動によって導入され得る最も甚だしいエラーの1つである。というのは、これらが、効果的にオリジナル(通常)の地図のトポロジを変更するからである。そのようなエラーのいずれかが発見される場合には、新しいレイアウトに非常に悪いスコアを与えることができる。次に、新しい地図内の道路のいずれかが、それ未満ではユーザがレイアウト内でその道路を見ることが難しい最小の長さしきい値未満になるか否かを判定する。道路網変形の全体的な目標は、地図内のすべての道路を可視にすることとすることができ、したがって、いずれかの道路が効果的に不可視であると判定される場合、そのレイアウトにそれ相応にペナルティを与えることができる。最後に、地図内の道路の相対長が、摂動の結果として順序はずれになったか否かを判定する。相対順序付けの変化は、顕著になるまでカウントしないものとすることができ、顕著になったならば変化のサイズに従ってペナルティを与えることができる。
【0060】
図6に、目的地に少なくとも部分的に基づく少なくとも2つの経路を有する機能強化された概略目的地地図の自動生成を容易にするシステム600を示す。ラベルコンポーネント214は、機能強化された概略目的地地図に関連する道路のラベル付けを容易にすることができる。ラベルコンポーネント214は、自動化されたラベル配置技法を実施することができる。たとえば、アニーリング手法を利用することができ、そのような技法は、互いに干渉せず、高められた可読性を提供する、明瞭で簡潔なラベルを可能にする。さらに、ラベルコンポーネント214は、各地図の特色である重要なプロパティを地図ユーザに知らせることができるラベルおよびその他の情報で地図を装飾することができる。
【0061】
手短に図7を参照すると、図示のラベル702は、ラベルレイアウト問題の簡潔な視覚的ステートメントを描写する。たとえば、ある道路のラベルを、その道路の上または下のいずれかの、その道路に「沿った」ある場所に配置し、ラベル位置での道路の曲線の接線まで傾けられるように制約することができる。図示のラベル704、発生し得る最悪なことの1つを、ラベル位置の摂動の結果として図示することができ、この結果は、ラベル−ラベル衝突である。ラベルコンポーネント214は、そのような問題の事例を防ぐことができ、特定の機能強化された概略目的地地図のラベルレイアウトを最適化できることを了解されたい。
【0062】
図6に戻ると、ラベルコンポーネント214は、道路ラベルコンポーネント602を含むことができる。道路ラベルコンポーネント602は、明瞭で有用なラベルレイアウト作成における次の伝統的な目標に焦点を合わせることができる。第1に、道路ラベルコンポーネント602は、ラベル−ラベル衝突を防ぐことができる。これは、特に2つの道路が交差する場合に発生する可能性があり、そのような衝突は、関わるラベルの可読性を大幅に下げる可能性がある。第2に、道路ラベルコンポーネント602は、ラベル−道路衝突を防ぐことができる。この種の衝突は、関わるラベルを読むことを混乱させるものにする可能性があり、重要な地図詳細(map details)を隠す可能性がある。最後に、道路ラベルコンポーネント602は、ラベルの間の距離を最大にすることを試みることができ、したがって、外見は、下にある道路網にまたがって均等に分散される。これは、地図の明瞭さおよび可読性を高めるのを助ける。
【0063】
さらに、道路ラベルコンポーネント602は、地図特徴ごとに関連するプロパティだけを表示することとすることができる、追加の設計考慮事項を実施することができる。機能強化された概略目的地地図の目的は、目的地(または目的地のセット)へ(およびそこから)どのように達するかをユーザに示すこととすることができ、したがって、表示できるのは、この目的に関連する情報だけであり、他のすべての情報は、混乱を減らすために隠すことができる。たとえば、道路選択の結果として、道路のチェーン(a chain of roads)(たとえば、他の交差する道路なしで、ある道路が別の道路につながるなど)が、地図に現れる場合があり、その場合には、チェーン内の道路の間にわずかな相違だけがある(たとえば、「65th NW」対「65th N」)。チェーン内の各個々の道路にラベル付けするのではなく、道路ラベルコンポーネント602は、より関連するプロパティ、たとえば、チェーンの始めにある道路の名前およびチェーンの終りにある道路の名前を含めることができる。これらは、ユーザが我々の地図内でそのチェーンに入ることのできる唯一の点なので、含めるべき最も重要な名前であり、他のすべての名前は、地図の有用性を犠牲にせずに混乱を減らすために安全に隠すことができる。
【0064】
図8に、機能強化された概略目的地地図の自動生成を容易にするのにインテリジェンスを使用するシステム800を示す。システム800は、自動概略地図ジェネレータ802、インターフェース104、機能強化された概略目的地地図804、データ、および地理データを含むことができ、これらのすべてを、前の図で説明したコンポーネント、ジェネレータ、地図、およびデータにそれぞれ実質的に類似するものとすることができる。システム800は、さらに、インテリジェントコンポーネント806を含む。インテリジェントコンポーネント806は、自動概略地図ジェネレータ802によって、地理データおよび目的地に基づいて機能強化された概略目的地地図804を自動作成するのを容易にするのに利用することができる。たとえば、インテリジェントコンポーネント806は、目的地、経路効率、交通、工事、最適化された旅行、機能強化された概略目的地地図804に関連するパーソナライズされたプリファレンスなどを推測することができる。
【0065】
インテリジェントコンポーネント806が、イベントおよび/またはデータを介して取り込まれた1組の観察結果からシステム、環境、および/またはユーザの状態に関する推論を提供し、またはこれを推測することができることを理解されたい。推測は、特定のコンテキストまたはアクションを識別するのに使用することができ、あるいは、たとえば状態にまたがる確率分布を生成することができる。推測は、確率的すなわち、データおよびイベントの考慮に基づく、該当する状態にまたがる確率分布の計算とすることができる。推測は、イベントおよび/またはデータのセットからより高いレベルのイベントを構成するのに使用される技法を指すこともできる。そのような推測は、イベントが密な時間的近接で相関するか否かに関わりなく、またイベント及びデータが1つ又は複数のイベントソース及びデータソースのどちらから来るかに関わりなく、観察されたイベントおよび/または格納されたイベントデータのセットからの新しいイベントまたはアクションの構成をもたらす。さまざまな分類(明示的にかつ/または暗黙のうちにトレーニングされた)方式および/またはシステム(たとえば、サポート・ベクトル・マシン、ニューラル・ネットワーク、エキスパート・システム、ベイジアン・ビリーフ・ネットワーク、ファジイ論理、データ・フュージョン・エンジン等)を、請求される主題に関連する自動的なかつ/または推測されたアクションの実行に関連して使用することができる。
【0066】
クラシファイヤ(clasifier)とは、入力属性ベクトルx=(x1,x2,x3,x4,xn)を、入力が、あるクラス(class)に属することの信頼度(confidence)に写像する関数、すなわちf(x)=confidence(class)である。そのような分類(classification)は、確率的および/または統計ベースの分析(たとえば、分析ユーティリティおよびコストへのファクタリング)を使用して、ユーザが自動的に実行されることを望むアクションを予知しまたは推測することができる。サポートベクトルマシン(SVM)が、使用できるクラシファイヤの例である。SVMは、可能な入力の空間(the space of possible inputs)内で超曲面を見つけることによって動作し、この超曲面は、トリガする判断基準を非トリガイベントから分離することを試みる。直観的に、これは、トレーニングデータと同一ではなく、トレーニングデータに近いテスティングデータに関して分類を正しいものにする。他の管理されたモデル分類手法および管理されないモデル分類手法(directed and undirected model classification approach)は、たとえば、ナイーブベイズ、ベイズネットワーク、決定木、ニューラル・ネットワーク、ファジイ論理モデルを含み、独立性の異なるパターンを提供する確率分類モデルを使用することができる。本明細書で使用される分類は、優先順位のモデルを展開するのに利用される統計的回帰をも包含する。
【0067】
プレゼンテーションコンポーネント808は、ユーザと自動概略地図ジェネレータ802に結合されたすべてのコンポーネントとの間の対話を容易にするために様々なタイプのユーザインターフェースを提供する。描写されているように、プレゼンテーションコンポーネント808は、自動概略地図ジェネレータ802と共に利用できる別々のエンティティである。しかし、プレゼンテーションコンポーネント808および/または類似するビューコンポーネントを、自動概略地図ジェネレータ802および/またはスタンドアローンユニットに組み込むことができることを了解されたい。プレゼンテーションコンポーネント808は、1つまたは複数のグラフィカルユーザインターフェース(GUI)、コマンドラインインターフェース等を提供することができる。たとえば、データのロード、インポート、読み取りなどのための領域または手段をユーザに与え、その結果を表す領域を含むことができるGUIを、レンダリングすることができる。これらの領域は、エディットコントロール、コンボボックス、ラジオボタン、チェックボックス、プッシュボタン、およびグラフィックボックスとしてダイアログボックス、スタティックコントロール、ドロップダウンメニュー、リストボックス、ポップアップメニューを含む既知のテキスト領域および/またはグラフィック領域を含むことができる。さらに、ナビゲーション用の垂直スクロールバーおよび/または水平スクロールバーならびに領域が可視になるかどうかを判定するためのツールバーボタンなどのプレゼンテーションを容易にするユーティリティを使用することができる。たとえば、ユーザは、自動概略地図ジェネレータ802に結合され、かつ/または組み込まれたコンポーネントのうちの1つまたは複数と対話することができる。
【0068】
ユーザは、たとえばマウス、ローラーボール、キーパッド、キーボード、ペン、および/または音声アクティベーションなどの様々なデバイスを介して情報を選択し、提供するために領域と対話することもできる。通常、検索を開始するために、プッシュボタンまたはキーボード上のエンターキーなどの機構を、情報を入力した後に使用することができる。しかし、請求される主題がそれに限定されないことを了解されたい。たとえば、チェックボックスを単に強調表示にすることにより、情報伝達を開始することができる。もう1つの例で、コマンドラインインターフェースを使用することができる。たとえば、コマンドラインインターフェースは、テキストメッセージの提供を介して情報についてユーザにプロンプトを出す(たとえば、ディスプレイ上のテキストメッセージおよびオーディオトーンを介して)ことができる。その後、ユーザは、インターフェースプロンプト内で提供されたオプションまたはプロンプトで提示された質問に対する回答に対応する英数字入力など、適切な情報を提供することができる。コマンドラインインターフェースを、GUIおよび/またはAPIに関連して使用できることを了解されたい。さらに、コマンドラインインターフェースを、限られたグラフィックサポートを有するハードウェア(たとえば、ビデオカード)および/もしくはディスプレイ(たとえば、白黒およびEGA)ならびに/または低帯域幅通信チャネルに関連して使用することができる。
【0069】
図9〜10に、請求される主題による方法論を示す。説明を単純にするために、これらの方法論は、一連の行為として描写され、説明される。本革新が、図示された行為および/または行為の順序によって限定はされず、たとえば、行為を、さまざまな順序でかつ/または同時に、本明細書で提示されず説明されない他の行為と共に行うことができることを理解し、了解されたい。さらに、図示されたすべての行為が、請求される主題による方法論を実施するのに必要とは限らない。さらに当業者は、これらの方法論を、状態図(state diagram)を介して相互に関係付けられた一連の状態として又はイベントとして代替的に表すことができることを理解し、了解するであろう。さらに、以下および本明細書全体を通じて開示される方法論が、そのような方法論のコンピュータへの輸送および転送を容易にするために製造品に格納されることが可能であることを、さらに了解されたい。本明細書で使用される製造品という用語は、任意のコンピュータ可読デバイス、担体、または媒体からアクセス可能なコンピュータプログラムを含むことが意図されている。
【0070】
図9に、目的地の機能強化された概略目的地地図の生成を容易にする方法論900を示す。符号902で、目的地を受け取ることができる。目的地は、たとえば、地図上の位置、住所、街路、交差点、店、市、建物、州、国、緯度および経度などとすることができる。さらに、目的地を、ユーザから受け取ることができる。方法論(methodology)900が、複数の目的地を受け取ることができることを了解されたい。
【0071】
符号904で、地理データを、少なくとも部分的に目的地に基づいて選択的にフィルタリングすることができる。データを階層的にフィルタリングして、目的地への適当な経路をフィルタリングすることができる。データは、少なくとも部分的に道路階層に基づいて選択することができる。たとえば、階層選択判断基準は、道路階層が接続され、複数の経路を含むことを保証することができる。言い換えると、道路セットの階層を利用して、目的地への少なくとも1つの経路を作成することができる。道路セットは、たとえば、大道路セット、中道路セット、および地方道路セットとすることができ、そのようなセットは、道路サイズ、速度制限、道路内の車線数などに基づくものとすることができる。たとえば、大道路セットは、州間ハイウェイを含むことができ、中道路セットは、幹線道路、州道、および大道路セットの境界内の他の主要道を含むことができ、地方道路セットは、中道路セットの境界内の一般道路を含むことができる。
【0072】
符号906で、機能強化された概略目的地地図を自動的に作ることができる。機能強化された概略目的地地図は、読みやすい経路、抑制された詳細、関連しないデータの除外、明瞭なおよび/または単純化された地理的特徴、混乱の除去、使い易さ、ならびに/あるいは目的地への複数の経路という改善のうちの少なくとも1つを含む簡素化された地図とすることができる。機能強化された概略目的地地図を、目的地を囲む地理データの評価に少なくとも部分的に基づいて簡素化できることを了解されたい。言い換えると、第1の目的地に関連する機能強化された概略目的地地図は、第2目的地に関連する機能強化された概略目的地地図106と比較して、異なる改善(たとえば、抑制された詳細、除外された関連しないデータ、明瞭なおよび/または単純化された地理的特徴、混乱の除去、目的地への複数の経路など)を含むことができる。
【0073】
さらに、機能強化された概略目的地地図を、少なくとも1つの原理および/または技法を利用することによって自動的に作ることができる。たとえば、この原理および/または技法は、1)関連するデータだけを機能強化された概略目的地地図106に含めることができるように地理データを選択的にフィルタリングすること、2)機能強化された概略目的地地図106を理解しやすく使い易くするために地理データを変形すること、および3)道路名ラベル、注釈、および目的地住所など(たとえば、下で述べる)、有用性を改善するための追加情報を用いて機能強化された概略目的地地図を装飾することとすることができるが、これらに限定はされない。さらに、そのような技法および/または原理を反映するさまざまなアルゴリズムを実施することができ、そのような原理は、機能強化された概略目的地地図を作るための時間および技量を減らすことができる。
【0074】
図10に、目的地に少なくとも部分的に基づく少なくとも2つの経路を有する機能強化された概略目的地地図を自動的に生成する方法論1000を示す。符号1002で、目的地に関連するデータを受け取ることができる。目的地は、たとえば、地図上の位置、住所、街路、交差点、店、市、建物、州、国、緯度および経度などとすることができる。さらに、目的地を、ユーザ、ソフトウェアプログラム、および/または適当なデータを有する任意の他の適切なマシンから受け取ることができる。
【0075】
符号1004で、地理データを選択することができる。地理データは、目的地位置および道路階層に少なくとも部分的に基づいて選択することができる。道路階層は、道路のセットを利用することができ、ここで目的地を囲む道路を、さまざまな特性に基づいてグループ化することができる。言い換えると、道路セットの階層を利用して、目的地への少なくとも1つの経路を作成することができる。道路セットは、たとえば、大道路セット、中道路セット、および地方道路セットとすることができ、そのようなセットは、道路サイズ、速度制限、道路内の車線数などに基づくものとすることができる。たとえば、大道路セットは、州間ハイウェイを含むことができ、中道路セットは、幹線道路、州道、および大道路セットの境界内の他の主要道を含むことができ、地方道路セットは、中道路セットの境界内の一般道路を含むことができる。
【0076】
符号1006に継続すると、変形を適用することができ、装飾を投入することができる。変形は、明瞭さおよび有用性を最大にするために、階層的に選択された地理データをレンダリングすることができる。さらに、適用される変形は、トポロジ、曲がり角(turn)、および道路ジオメトリに関するソフト制約を利用することができる(すべて上で述べた)。装飾を適用することができ、地図に、地図特徴のそれぞれの重要なプロパティをユーザに伝えるラベルおよび他の情報を投入することができる。たとえば、道路名ラベル、プロンプト道路(prompt roads)、吹き出し、ランドマーク、パーソナライズされたデータなどを投入することができる。符号1008で、機能強化された概略目的地地図を自動的に作成することができ、機能強化された概略目的地地図は、読みやすい経路、強調を解除された詳細、除外された関連しないデータ、明瞭なおよび/または単純化された地理的特徴、混乱の除去、使い易さ、ならびに/あるいは目的地への複数の経路という改善のうちの少なくとも1つを提供する。さらに、機能強化された概略目的地地図を、レンダリングし、かつ/またはユーザに表示することができる。
【0077】
図11に、本革新に従って利用される目的地に関する地理データ1100を示す。地理データ1100は、従来の混乱に満ちた事実に忠実な地図の例である。地理データ1100は、機能強化された概略目的地地図を自動的に作るために自動概略地図ジェネレータ(上で述べた)によりすることができる。目的地1102を利用することができ、それに関連する機能強化された概略地図を提供することができる。複数の目的地を地理データ1100に関連付けることができ、目的地1102が例のためのみのものであることを了解されたい。
【0078】
図12に、目的地に関する自動的に生成された機能強化された概略目的地地図1200を示す。機能強化された概略目的地地図1100が、図11の目的地1102に関連して図示されている。機能強化された概略目的地地図1200は、読みやすい経路、(図11の地理データ1100と比較して)抑制された詳細、(図11の地理データ1100と比較して)除外された関連しないデータ、(図11の地理データ1100と比較して)明瞭なかつ/または単純化された地理的特徴、(図11の地理データ1100と比較して)混乱の除去、使い易さ、ならびに/あるいは目的地への複数の経路という改善を含む簡素化された地図である。機能強化された概略目的地地図を、道路階層選択に少なくとも部分的に基づいて簡素化できることを了解されたい。
【0079】
請求される主題のさまざまな態様を実施する追加の文脈を提供するために、図13〜14および次の議論は、本革新のさまざまな態様を実施できる適切なコンピューティング環境の短い全般的な説明を提供することを意図されたものである。たとえば、前の図で説明した、機能強化された概略目的地地図を自動的に作る自動概略地図ジェネレータを、そのような適切なコンピューティング環境で実施することができる。請求される主題を、上ではローカルコンピュータおよび/またはリモートコンピュータで走行するコンピュータプログラムのコンピュータ実行可能命令の全般的な文脈で説明したが、当業者は、本革新を他のプログラムモジュールと組み合わせて実施できることを認めるであろう。一般に、プログラムモジュールは、特定のタスクを実行し、かつ/または特定の抽象データ型を実施するルーチン、プログラム、コンポーネント、データ構造などを含む。
【0080】
さらに、当業者は、本発明的方法を、シングルプロセッサまたはマルチプロセッサのコンピュータシステム、ミニコンピュータ、メインフレームコンピュータ、ならびにパーソナルコンピュータ、ハンドヘルドコンピューティングデバイス、マイクロプロセッサベースのおよび/またはプログラマブルな消費者エレクトロニクス等を含む他のコンピュータシステム構成を用いて実践することができ、これらのそれぞれが、1つまたは複数の関連するデバイスと動作可能に通信できることを了解するであろう。請求される主題の図示された諸態様は、ある種のタスクが通信ネットワークを介してリンクされたリモート処理デバイスによって実行される分散コンピューティング環境でも実践することができる。しかし、本革新の、すべてではないにしてもいくつかの態様を、スタンドアローンコンピュータで実践することができる。分散コンピューティング環境では、プログラムモジュールを、ローカルおよび/またはリモートのメモリストレージデバイスに配置することができる。
【0081】
図13は、請求される主題が相互作用できるサンプルのコンピューティング環境1300の概略ブロック図である。システム1300は、1つまたは複数のクライアント1310を含む。クライアント1310は、ハードウェアおよび/またはソフトウェア(たとえば、スレッド、プロセス、コンピューティングデバイス)とすることができる。システム1300は、1つまたは複数のサーバ1320を含む。サーバ1320は、ハードウェアおよび/またはソフトウェア(たとえば、スレッド、プロセス、コンピューティングデバイス)とすることができる。サーバ1320は、たとえば本革新を使用することによって変換(transformation)を実行するスレッドを収容することができる。
【0082】
クライアント1310とサーバ1320との間の1つの可能な通信は、複数のコンピュータプロセスの間で伝送されるように適合されたデータパケットの形とすることができる。システム1300は、クライアント1310とサーバ1320との間の通信を容易にするのに使用することができる通信フレームワーク1340を含む。クライアント1310は、クライアント1310にローカルな情報を格納するのに使用することができる1つまたは複数のクライアントデータストア1350に動作可能に接続される。同様に、サーバ1320は、サーバ1320にローカルな情報を格納するのに使用することができる1つまたは複数のサーバデータストア1330に動作可能に接続される。
【0083】
図14を参照すると、請求される主題のさまざまな態様を実施する例示的な環境1400は、コンピュータ1412を含む。コンピュータ1412は、処理ユニット1414、システムメモリ1416、およびシステムバス1418を含む。システムバス1418は、システムメモリ1416を含むがこれに限定されないシステムコンポーネントを処理ユニット1414に結合する。処理ユニット1414は、さまざまな入手可能なプロセッサのいずれかとすることができる。デュアルマイクロプロセッサアーキテクチャおよび他のマルチプロセッサアーキテクチャを処理ユニット1414として使用することもできる。
【0084】
システムバス1418は、メモリバスもしくはメモリコントローラ、周辺バスもしくは外部バス、ならびに/またはIndustrial Standard Architecture(ISA)、マイクロチャネルアーキテクチャ(MSA)、Extended ISA(EISA)、Intelligent Drive Electronics(IDE)、VESA Local Bus(VLB)、Peripheral Component Interconnect(PCI)、Card Bus、Universal Serial Bus(USB)、Advanced Graphics Port(AGP)、Personal Computer Memory Card International Associationバス(PCMCIA)、Firewire(IEEE 1394)、およびSmall Computer Systems Interface(SCSI)を含むがこれらに限定はされない任意のさまざまな使用可能なバスアーキテクチャを使用するローカルバスを含む複数のタイプのバス構造のいずれかとすることができる。
【0085】
システムメモリ1416は、揮発性メモリ1420および不揮発性メモリ1422を含む。スタートアップ中など、コンピュータ1412内の要素の間で情報を転送する基本ルーチンを含む基本入出力システム(BIOS)が、不揮発性メモリ1422に格納される。限定ではなく例として、不揮発性メモリ1422は、読取専用メモリ(ROM)、プログラマブルROM(PROM)、電気的プログラマブルROM(EPROM)、電気的消去可能プログラマブルROM(EEPROM)、またはフラッシュメモリを含むことができる。揮発性メモリ1420は、ランダムアクセスメモリ(RAM)を含み、このRAMは外部キャッシュメモリとして働く。限定ではなく例として、RAMは、スタティックRAM(SRAM)、ダイナミックRAM(DRAM)、シンクロナスDRAM(SDRAM)、double data rate SDRAM(DDR SDRAM)、enhanced SDRAM(ESDRAM)、Synchlink DRAM(SLDRAM)、Rambus direct RAM(RDRAM)、direct Rambus dynamic RAM(DRDRAM)、およびRambus dynamic RAM(RDRAM)などの多数の形で入手可能である。
【0086】
コンピュータ1412は、リムーバブル/ノンリムーバブルの揮発性/不揮発性コンピュータ記憶媒体をも含む。図14に、たとえば、ディスクストレージ1424を示す。ディスクストレージ1424は、磁気ディスクドライブ、フロッピディスクドライブ、テープドライブ、Jazドライブ、Zipドライブ、LS−100ドライブ、フラッシュメモリカード、またはメモリスティックなどのデバイスを含むが、これらに限定はされない。さらに、ディスクストレージ1424に、コンパクトディスクROMデバイス(CD−ROM)、CD recordableドライブ(CD−Rドライブ)、CD rewritableドライブ(CD−RWドライブ)、またはディジタル多用途ディスクROMドライブ(DVD−ROM)などの光学ディスクドライブを含むがこれに限定されない記憶媒体を、他の記憶媒体と別々にまたはこれらと組み合わせて含めることができる。システムバス1418へのディスクストレージデバイス1424の接続を容易にするために、インターフェース1426などのリムーバブルまたはノンリムーバブルのインターフェースが、通常は使用される。
【0087】
図14に、ユーザと、適切なオペレーティング環境1400で説明した基本的なコンピュータリソースとの間の媒介として働くソフトウェアが記載されていることを了解されたい。そのようなソフトウェアに、オペレーティングシステム1428が含まれる。オペレーティングシステム1428は、ディスクストレージ1424に格納することができるが、コンピュータシステム1412を制御し、そのリソースを割り当てるように働く。システムアプリケーション1430は、プログラムモジュール1432を介するオペレーティングシステム1428によるリソースの管理およびシステムメモリ1416内またはディスクストレージ1424上のいずれかに格納されたプログラムデータ1434を利用する。請求される主題を、さまざまなオペレーティングシステムまたはオペレーティングシステムの組み合わせを用いて実施できることを了解されたい。
【0088】
ユーザは、入力デバイス1436を介してコンピュータ1412にコマンドまたは情報を入力する。入力デバイス1436は、マウスなどのポインティングデバイス、トラックボール、スタイラス、タッチパッド、キーボード、マイクロホン、ジョイスティック、ゲームパッド、衛星パラボラアンテナ、スキャナ、TVチューナカード、ディジタルカメラ、ディジタルビデオカメラ、ウェブカメラ、および類似物を含むが、これらに限定はされない。これらおよび他の入力デバイスは、インターフェースポート1438を介し、システムバス1418を介して処理ユニット1414に接続される。インターフェースポート1438は、たとえば、シリアルポート、パラレルポート、ゲームポート、およびuniversal serial bus(USB)を含む。出力デバイス1440は、入力デバイス1436と同一タイプのポートのいくつかを使用する。したがって、たとえば、USBポートを使用して、コンピュータ1412に入力を提供し、コンピュータ1412から出力デバイス1440に情報を出力することができる。出力アダプタ1442が、モニタ、スピーカ、およびプリンタなど、他の出力デバイス1440の中でも特殊なアダプタを必要とするいくつかの出力デバイス1440があることを示すために提供される。出力アダプタ1442は、限定ではなく例として、出力デバイス1440とシステムバス1418との間の接続の手段を提供する、ビデオカードおよびサウンドカードを含む。リモートコンピュータ1444など、他のデバイスおよび/またはデバイスのシステムが、入力機能と出力機能との両方を提供することに留意されたい。
【0089】
コンピュータ1412は、リモートコンピュータ1444などの1つまたは複数のリモートコンピュータへの論理接続を使用して、ネットワーク化された環境で動作することができる。リモートコンピュータ1444は、パーソナルコンピュータ、サーバ、ルータ、ネットワークPC、ワークステーション、マイクロプロセッサベースの機器、ピアデバイス、または他の一般的なネットワークノードおよび類似物とすることができ、リモートコンピュータ1444は、通常は、コンピュータ1412に関して説明した要素の多数またはすべてを含む。図を簡単にするために、メモリストレージデバイス1446だけが、リモートコンピュータ1444と共に図示されている。リモートコンピュータ1444は、論理的にネットワークインターフェース1448を介してコンピュータ1412に接続され、次に、物理的に通信接続1450を介して接続される。ネットワークインターフェース1448は、ローカルエリアネットワーク(LAN)および広域ネットワーク(WAN)などの有線および/または無線の通信ネットワークを含む。LANテクノロジは、Fiber Distributed Data Interface(FDDI)、Copper Distributed Data Interface(CDDI)、イーサネット(登録商標)、トークンリング、および類似物を含む。WANテクノロジは、ポイントツーポイントリンク、サービス総合ディジタル網(ISDN)およびその変形形態などの回路交換網、パケット交換網、およびディジタル加入者回線(DSL)を含むが、これに限定はされない。
【0090】
通信接続1450は、ネットワークインターフェース1448をバス1418に接続するのに使用されるハードウェア/ソフトウェアを指す。通信接続1450は、図を明瞭にするためにコンピュータ1412の内部に図示されているが、コンピュータ1412の外部とすることもできる。ネットワークインターフェース1448への接続に必要なハードウェア/ソフトウェアは、例示のみとして、通常の電話等級モデム、ケーブルモデム、およびDSLモデムを含むモデム、ISDNアダプタ、ならびにイーサネット(登録商標)カードなどの、内蔵テクノロジおよび外付けテクノロジを含む。
【0091】
上で説明したものは、本革新の例を含む。もちろん、請求される主題の説明においてコンポーネントまたは方法論のすべての考えられる組合せを説明することは不可能であるが、当業者は、本革新の多数のさらなる組合せおよび置換が可能であることを認めるであろう。したがって、請求される主題は、添付の特許請求の範囲の趣旨および範囲に含まれるすべてのそのような代替形態、修正形態、および変形形態を含むことが意図されている。
【0092】
具体的には、上で説明したコンポーネント、デバイス、回路、システム、および類似物によって実行されるさまざまな機能に関して、そのようなコンポーネントを記述するのに使用される用語(「手段(means)」への言及を含む)は、そうではないと示されていない限り、開示された構造と構造的に同等ではないものであっても、請求される主題の本明細書で示された例示的諸態様の機能を実行する、説明されたコンポーネントの指定された機能を実行するすべてのコンポーネント(たとえば、機能的同等物)に対応することが意図されている。これに関して、本革新が、請求される主題のさまざまな方法の行為および/またはイベントを実行するコンピュータ実行可能命令を有するシステムならびにコンピュータ可読媒体を含むことも、認められるであろう。
【0093】
さらに、本革新の特定の特徴を、複数の実施態様のうちの1つだけに関して開示した場合があるが、そのような特徴は、任意の所与のまたは特定の応用例について望まれ、有利である可能性があるので、他の実施態様の1つまたは複数の他の特徴と組み合わせることができる。さらに、用語「含む」、「備える」(“includes”、“including”」、およびその変形が、詳細な説明または特許請求の範囲のいずれかで使用される範囲で、これらの用語は、用語「含む」、「備える」(“comprising”」に類似する形で包含的であることを意図されている。
【図面の簡単な説明】
【0094】
【図1】機能強化された概略目的地地図の自動生成を容易にする例示的システムを示すブロック図である。
【図2】目的地に少なくとも部分的に基づく少なくとも2つの経路を有する機能強化された概略目的地地図の自動生成を容易にする例示的システムを示すブロック図である。
【図3】目的地の機能強化された概略目的地地図の作成を容易にする例示的システムを示すブロック図である。
【図4】請求される主題の一態様に従う地理データの選択に関連する諸フェーズを示す図である。
【図5】本革新の一態様によるレイアウト摂動の生成を示す図である。
【図6】目的地に少なくとも部分的に基づく少なくとも2つの経路を有する機能強化された概略目的地地図の自動生成を容易にする例示的システムを示すブロック図である。
【図7】請求される主題による自動生成された機能強化された概略目的地地図に関連するラベルレイアウトを示す図である。
【図8】機能強化された概略目的地地図の自動生成を容易にする例示的システムを示すブロック図である。
【図9】目的地の機能強化された概略目的地地図の生成を容易にする例示的方法論を示す図である。
【図10】目的地に少なくとも部分的に基づく少なくとも2つの経路を有する機能強化された概略目的地地図を自動的に生成する例示的方法論を示す図である。
【図11】本革新による目的地に関する例示的地理データを示す図である。
【図12】目的地に関する自動的に生成された機能強化された概略目的地地図を示す図である。
【図13】請求される主題の新規の諸態様を使用できる例示的ネットワーキング環境を示す図である。
【図14】請求される主題に従って使用できる例示的オペレーティング環境を示す図である。
【技術分野】
【0001】
本発明は、概略目的地地図(schematic destination map)に関する。
【背景技術】
【0002】
電子ストレージ機構は、大量のデータの蓄積を可能にしてきた。たとえば、以前には何冊もの本を必要としたデータを、現在は、紙を印刷する出費なしに、紙を格納するのに必要なスペースの何分の1かのスペースで、電子的に記憶することができる。1つの特定の例では、以前は大量の紙に記録された証書および抵当権証書を、現在は電子的に記憶することができる。さらに、センサおよび他の電子機構の進歩が、現在、大量のデータをリアルタイムで収集することを可能にする。たとえば、GPSシステムは、GPSレシーバを有するデバイスの位置を追跡する。それに接続された電子ストレージデバイスを使用して、そのようなレシーバに関連する位置を保持することができる。さまざまな他のセンサも、類似するセンシング機能およびデータ保持機能に関連付けられる。
【0003】
今日のコンピュータは、さまざまな地図を生成するためのデータの利用をも可能にする。たとえば、インターネット地図作成アプリケーション(mapping application)は、ユーザが、1つまたは複数の住所を入力することを可能にし、地図作成アプリケーションがトリガされると、入力された住所に関連する地図および/または入力された住所の間の地図が、そのような地図に関連する道順と一緒にユーザに表示される。これらの地図は、普通に静的であり、たとえば、地図がポータブル機構(たとえば、スマートホン、PDA等)に表示される場合に、それらの地図は、感知されたユーザの位置の変化に伴って変更はされない。さらに、表示を動的に変更し、かつ/または特定の経路をグラフィカルに横断(traverse)する地図作成アプリケーションは、そのようなビューの深度を変更しない。したがって、ユーザは、横断される経路に関する最適のコンテキストを与えられない。
【0004】
高い品質および使い易さに起因して、概略目的地地図は、多数の重要な実世界の目的に使用することができる。イベントオーガナイザ(たとえば、結婚式プランナ)は、イベント位置に達する方法を招待客に示すために専用の地図を提供する。フランチャイズチェーンおよびショッピング区域は、店の位置を強調した概略地図を提供する。空港および旅行代理店は、しばしば、よその町からの訪問者に町をめぐる最良の/最も簡単な方法を示すために単純化された地図を提供する。会社、大学、病院、動物園、および他のキャンパスベースの組織は、それぞれのキャンパスの重要な建物および経路の位置および関係を示すために地図を提供する。
【発明の開示】
【発明が解決しようとする課題】
【0005】
各タイプの地図に描かれる詳細の量を検討する。事実に忠実な目的地地図は、一方の極にあり、一定の密度の詳細を含む。通常、これらの地図を作るソフトウェアは、指定された目的地に到達することに関連するか否かに関わりなく、所与のズームレベルで可視のすべてのものを表示する。たとえば、従来の事実に忠実な目的地地図では、多数の地方道路、駐車場、および近隣が、そのような詳細が目的地の発見に関してユーザにほとんど又は全く助けを提供しない場合であっても示される。
【0006】
詳細の他方の極に、概略経路図がある。概略経路図は、単一の起点と単一の目的地との間の単一の経路を描写する。非常にわずかな追加のコンテキスト情報がこの地図で提供され、特定の経路がなんらかの理由(たとえば、工事、交通渋滞、事故など)で使用不能な場合に、またはユーザが経路から迷った場合に、またはユーザが目的地付近の追加情報(潜在的な駐車位置など)を必要とする場合に、入手できる助けはごくわずかである。
【0007】
考慮すべき地図設計のもう1つの次元は、空間的関係が表される忠実度である。事実に忠実な目的地地図は、単一の共通の縮尺で地理的特徴を表示し、その結果、これらの地理的特徴は、航空写真から直接にコピーされたかのように、互いに現実的に比例して見えるようになる。その結果、多くの重要な特徴(たとえば、目的地へのローカル連絡道路)は、完全に不可視であるか有用になるには小さすぎてレンダリングされるかのいずれかになる。
【0008】
さらに、特定の目的地の「LineDrive」概略経路図は、単一の起点から目的地への単一の経路だけを最小の追加テキストと共に描写する。事実に忠実な目的地地図は、ディスプレイを混乱させ、多数の他の重要な詳細を隠す関連しない詳細を含む可能性がある。しかし、「LineDrive」地図および他の従来の概略経路図は、しばしば重要な詳細を隠し、かつ/または多すぎる余分な特徴を含む一定の縮尺および詳細の密度を伴って、目的地を囲む領域を描写する。さらに、そのような地図を作るために、地図作成者は、どの道路および他の地理的特徴のサブセットが地図の目的をサポートするかを注意深く判定し、そのような地図を手作業で作成する。
【課題を解決するための手段】
【0009】
本明細書で説明されるいくつかの態様の基本的な理解を提供するために、本革新(the innovation)の単純化された要約を以下に提示する。この要約は、請求される主題の外延的な概要ではない。請求される主題の重要な要素を識別することおよび本革新の範囲を描写することは意図されていない。その唯一の目的は、後で提示されるより詳細な説明の前置きとして、単純化された形で請求される主題のいくつかの概念を提示することである。
【0010】
本革新は、機能強化された概略目的地地図の自動生成を容易にするシステムおよび/または方法に関する。自動概略地図ジェネレータ(automatic schematic map generator)が、道路の階層を利用して、特定の目的地への複数の経路を提供する機能強化された(enhanced)概略目的地地図を自動的に生成することができる。自動概略地図ジェネレータは、地理データおよび目的地に関連するデータをインターフェースを介して受け取ることができ、道路の階層を利用する選択的フィルタリングが、目的地への少なくとも1つの経路を提供することができる。目的地に関連するデータとしては、ユーザから受け取られる、地図上の位置、住所、街路(street)、交差点、店、市、郡、国、建物、地図上の点に関連する任意のデータなどとすることができる。さらに、自動概略地図ジェネレータは、目的地を囲む地理データを利用して、機能強化された概略目的地地図を自動的に生成することができ、地理データは、たとえば、世界、州、市、郡、地域の地理に関連する任意のデータ、および/または目的地を囲む任意の適切な地理データとすることができる。
【0011】
機能強化された概略目的地地図は、読みやすい経路、抑制された(de−emphasized)詳細、関連しないデータの除外、明瞭なかつ/または単純化された地理的特徴、混乱の除去、使い易さ、および/または目的地への複数の経路、という改善のうちの少なくとも1つを含む簡素化された地図とすることができる。機能強化された概略目的地地図を、目的地を囲む地理データの評価に少なくとも部分的に基づいて簡素化できることを了解されたい。言い換えると、第1の目的地に関連する機能強化された概略目的地地図は、第2の目的地に関連する機能強化された概略目的地地図106と比較して、異なる改善(たとえば、抑制された詳細、関連しないデータの除外、明瞭なかつ/または単純化された地理的特徴、混乱の除去、目的地への複数の経路など)を含むことができる。
【0012】
請求される主題の一態様によれば、自動概略地図ジェネレータは、機能強化された目的地地図を提供するためにデータを階層的に選択し、かつ/またはフィルタリングするデータ選択コンポーネントを含むことができる。データ選択コンポーネントは、道路セットを利用することができ、道路セットはたとえば、大道路セット、中道路セット、および地方道路セットとすることができ、これらのセットは、道路のサイズ、制限速度、道路内の車線数などに基づくものとすることができる。たとえば、大道路セットは、州間ハイウェイを含むことができ、中道路セットは、幹線道路、州道、および大道路セットの境界内の他の主要道を含むことができ、地方道路セットは、中道路セットの境界内の一般道路路を含むことができる。
【0013】
請求される主題の別の態様によれば、自動概略地図ジェネレータは、道路に関連するジオメトリおよび/またはデータ選択コンポーネントからの階層的に選択された地理データを単純化する形状コンポーネントを含むことができる。形状コンポーネントは、形状単純化(shape simplification)を利用して個々の道路のジオメトリを単純化することができる。さらに、自動概略地図ジェネレータは、たとえば確率的探索(stochastic search)として道路レイアウトを構造化できる道路レイアウトコンポーネントを含むことができる。検索空間は、異なる可能な、道路網データの2Dレイアウトからなる。検索は、シミュレーテッド・アニーリング・アルゴリズムを用いて行うことができる。さらに、道路レイアウトコンポーネントは、ソフト制約(soft constraint)を伴うさまざまな変形を利用することができ、そのようなソフト制約は、トポロジ、道路の曲がり角、および/または道路ジオメトリに基づくものとすることができる。さらに、さまざまな摂動を利用して、道路および目的地に関連するレイアウトを生成することができる。たとえば、関節点(articulation point)ベースのスケーリングを利用することができる。
【0014】
本明細書で説明される革新の別の態様によれば、自動概略地図ジェネレータは、機能強化された概略目的地地図に追加情報を投入し(populate)、かつ/または機能強化された概略目的地地図を追加情報によって装飾する(decorate)ラベルコンポーネントをさらに含むことができる。ラベルコンポーネントは、機能強化された概略目的地地図に、道路ラベル、プロンプト道路(prompt road)ラベル、吹き出し、およびランドマークのうちの少なくとも1つを投入すると同時に、そのようなラベルの明瞭さおよび可読性を提供することができる。請求される主題の他の態様では、目的地の機能強化された概略目的地地図の作成を容易にする方法が提供される。
【0015】
以下の説明および添付図面は、請求される主題のある例示的態様を詳細に示す。しかし、これらの態様は、本革新の原理を利用できるさまざまな形のうちの少数を示すに過ぎず、請求される主題は、そのような態様およびその同等物のすべてを含むことが意図されている。請求される主題の他の利益および新規の特徴は、添付図面と共に解釈されれば本革新の以下の詳細な説明から明らかになるだろう。
【発明を実施するための最良の形態】
【0016】
請求される主題を、図面を参照して説明するが、類似する符号は、図面全体を通して維持する要素を指すのに使用される。以下の説明では、説明において、本発明の完全な理解をもたらすために多数の具体的な詳細を示す。しかし、請求される主題を、これらの特定の詳細なしで実践できることは明白であろう。他の場合には、周知の構造およびデバイスは、本革新の説明を容易にするためにブロック図形式で示す。
【0017】
本明細書で利用される時に、用語「コンポーネント」、「システム」、「ジェネレータ」、「インターフェース」等は、ハードウェア、ソフトウェア(たとえば実行中の)、および/またはファームウェアのいずれであれ、コンピュータ関連のエンティティを指すことが意図されている。たとえば、コンポーネントは、プロセッサで動作中のプロセス、プロセッサ、オブジェクト、実行可能ファイル、プログラム、および/またはコンピュータとすることができる。たとえば、サーバで動作するアプリケーションとそのサーバとの両方を、コンポーネントとすることができる。1つまたは複数のコンポーネントが、1つのプロセス内に存在することができ、1つのコンポーネントを、1つのコンピュータにローカライズし、かつ/または複数のコンピュータの間で分散させることができる。
【0018】
さらに、請求される主題は、開示される主題を実施するためにコンピュータを制御するためにソフトウェア、ファームウェア、ハードウェア、またはその任意の組合せを作るために標準的なプログラミング技法および/またはエンジニアリング技法を使用して、方法、装置、または製造品として実施することができる。本明細書で使用される用語「製造品(article of manufacture)」は、任意のコンピュータ可読デバイス、担体(carrier)、または媒体からアクセス可能なコンピュータプログラムを含むことが意図されている。たとえば、コンピュータ可読媒体は、磁気ストレージデバイス(たとえば、ハードディスク、フロッピディスク、磁気ストライプ等)、光ディスク(たとえば、コンパクトディスク(CD)、ディジタル多用途ディスク(DVD)等)、スマートカード、およびフラッシュメモリデバイス(たとえば、カード、スティック、キードライブ等)を含むことができるが、これらに限定はされない。さらに、搬送波を使用して、電子メールの送信および受信に使用されるものまたはインターネットもしくはローカルエリアネットワーク(LAN)などのネットワークにアクセスするのに使用されるものなどのコンピュータ可読電子データを搬送することができることを了解されたい。もちろん、当業者は、請求される主題の範囲または趣旨から逸脱せずに、この構成に対して多数の変更を行えることを認めるであろう。さらに、単語「例示的(exemplary)」は、本明細書では、例、実例、または例示として働くことを意味するのに使用される。本明細書で「例示的」として説明される任意の態様または設計は、必ずしも、他の態様または設計より好ましいまたは有利とは解釈されてはならない。
【0019】
ここで図面に移ると、図1は、機能強化された概略目的地地図の自動生成を容易にするシステム100を示す。システム100は、少なくとも1つの目的地に関連するデータを受け取ることができる自動概略地図ジェネレータ102を含み、機能強化された概略目的地地図106を地理データに少なくとも部分的に基づいて作成することができる。機能強化された概略目的地地図106は、読みやすい経路、抑制された詳細、関連しないデータの除外、明瞭なかつ/または単純化された地理的特徴、混乱の除去、使い易さ、および/または目的地への複数の経路という改善のうちの少なくとも1つを含む簡素化された地図とすることができる。機能強化された概略目的地地図106を、目的地を囲む地理データの評価に少なくとも部分的に基づいて簡素化できることを了解されたい。言い換えると、第1の目的地に関連する機能強化された概略目的地地図106は、第2の目的地に関連する機能強化された概略目的地地図106と比較して、異なる改善(たとえば、抑制された詳細、関連しないデータの除外、明瞭なかつ/または単純化された地理的特徴、混乱の除去、目的地への複数の経路など)を含むことができる。
【0020】
自動概略地図ジェネレータ102は、目的地に関連するデータを受け取ることができ、そのようなデータは、たとえば、ユーザから受け取られる、地図上の位置、住所、街路、交差点、店、市、郡、国、建物、地図上の点に関連する任意のデータなどとすることができる。さらに、自動概略地図ジェネレータ102は、目的地を囲む地理データを利用して、機能強化された概略目的地地図106を自動的に生成することができ、地理データは、たとえば、世界、州、市、郡、地域の地理に関連する任意のデータ、および/または目的地を囲む任意の適切な地理データとすることができる。たとえば、目的地は、ワシントン州シアトル、Main Street 1234の結婚披露宴式場などのユーザ指定の位置とすることができる。自動概略地図ジェネレータ102は、受け取られた目的地に少なくとも部分的に基づいて機能強化された概略目的地地図106を自動的に作成することができ、この地図は、読みやすい経路、抑制された詳細、関連しないデータの除外、明瞭なかつ/または単純化された地理的特徴、混乱の除去、使い易さ、ならびに/あるいは目的地への複数の経路などのさまざまな改善を含むことができる。そのような改善が、従来の事実に忠実な目的地地図、ラインドライブ地図、および/または他の伝統的な地図と比較してのものであることを了解されたい。
【0021】
さらに、自動概略地図ジェネレータ102は、機能強化された概略目的地地図106を自動的に作る少なくとも1つの原理を利用する。たとえば、この原理は、1)関連するデータだけを機能強化された概略目的地地図106に含めることができるように地理データを選択的にフィルタリングすること、2)機能強化された概略目的地地図106を理解しやすく使い易くするために地理データを変形すること、および3)道路名ラベル、注釈、および目的地住所など(たとえば、下で述べる。)、有用性を改善するための追加情報を用いて機能強化された概略目的地地図106を装飾することとすることができるが、これらに限定はされない。さらに、自動概略地図ジェネレータ102は、そのような技法および/または原理を反映するさまざまなアルゴリズムを実施することができ、そのような原理は、機能強化された概略目的地地図106を作るための時間および技量を減らすことができる。
【0022】
自動概略地図ジェネレータ102によって利用される原理および/または技法は、従来の地図と概略経路図との両方(たとえば、ラインドライブ地図)より道を見つけるのに有用になり得る機能強化された概略目的地地図106の自動生成を容易にする。自動概略地図ジェネレータ102は、各地図に描写される詳細の量を、囲む領域から目的地および/または目的地のセットへ(そして、たとえばそこから戻って)移動するのに必要なものだけに減らすことができる。さらに、システム100は、代替経路およびコンテキストによって地図ユーザをサポートし、地図の明瞭さおよび有用性を最大にするために、選択された詳細をレンダリングする。
【0023】
自動生成される機能強化された概略目的地地図106は、地図を読みやすく使い易くするために、目的地への読みやすいさまざまな経路を含み、関連しない詳細の強調をやめ、かつ/または除外し、多数の地理的特徴を変形し、かつ/または単純化することができる。機能強化された概略目的地地図106は、1つまたは複数のユーザ指定の目的地の位置およびコンテキストを強調し、囲む場所からそのような目的地に到達する複数の道を示す。そのような機能強化された地図106は、自動的に生成され、ユーザが描写された目的地に達するのを助けるのに必要な地理的詳細だけを含みながら従来の経路図よりはるかに有用な情報を含むことができる。
【0024】
機能強化された概略目的地地図106を、ミーティング、パーティ、および参加者が複数の異なる方向から来るが、たとえば予算が従来の手作りの地図に投資することを許さないその他のイベントに利用できることを了解されたい。さらに、機能強化された概略目的地地図106は、複数の異なる経路を描写することができ、目的地の間の輸送の複数のモードさえ描写することができる、パーソナライズされた「複数経路」地図に利用することができる。さらに、一連の名所旧跡、ホテル、店、不動産などをそれに関連する経路と共に示す自動生成される機能強化された概略目的地地図106を、休暇、旅行、および使い走りに利用することができる。
【0025】
たとえば、機能強化された概略目的地地図は、目的地の周囲の地域を囲む地図とすることができ、囲む地域には、経路階層を投入することができる。経路階層は、道路のサイズに少なくとも部分的に基づくものとすることができる。たとえば、最大の道路は、州間ハイウェイとすることができる。次に、中サイズの道路を利用することができ、中サイズの道路は、大道路(たとえば、最大の地域の境界)によって囲まれるものとすることができる。中サイズの道路は、幹線道路、州道、および他の主要道とすることができる。次に、一般道路(local street)を利用することができ、一般道路は、中サイズの道路の中に含まれる。
【0026】
さらに、システム100は、任意の適切なおよび/または必要なインターフェースコンポーネント104(本明細書では「インターフェース104」と呼称する。)を含むことができ、インターフェース104は、自動概略地図ジェネレータ102を事実上すべてのオペレーティングシステムおよび/またはデータベースシステムに統合するために、さまざまなアダプタ、コネクタ、チャネル、通信パスなどを提供する。さらに、インターフェース104は、自動概略地図ジェネレータ102、地理データ、目的地、目的地のセット、および/またはシステム100に関連する任意の他のデータとの相互作用を提供する、さまざまなアダプタ、コネクタ、チャネル、通信パスなどを提供することができる。
【0027】
図2に、目的地に少なくとも部分的に基づく少なくとも2つの経路を有する機能強化された概略目的地地図の自動生成を容易にするシステム200を示す。システム200は、道路の階層および目的地に少なくとも部分的に基づいて機能強化された概略目的地地図206を自動的に作成する自動概略地図ジェネレータ202を含む。たとえば、自動概略地図ジェネレータ202は、ユーザから少なくとも1つの目的地を受け取ることができ、ここで、それぞれの機能強化された概略目的地地図206を、地理データを利用して作成することができる。機能強化された概略目的地地図206が、事実に忠実な経路図より少ない詳細および/またはより低い精度を含むことができ、なおかつユーザが階層道路セットから目的地に達することを可能にするのに十分な機能強化された特徴を含むことができることを了解されたい。
【0028】
自動概略地図ジェネレータ202は、データストア204を利用することができ、データストア204は、システム200に関連するさまざまなデータを格納することができる。データストア204は、道路、街路、高速道路、州間高速道路、橋、建物、駐車場、ランドマーク、水域、川、交差点、トンネル、料金所、高台、国境、境界、学校、消防署、警察署、刑務所、野生生物保護区域、および/または地理的地図上の表示に適する任意の他のデータなどであるがこれらに限定はされない地理データのストレージを提供することができる。データストア204は、たとえば、揮発性メモリまたは不揮発性メモリのいずれかとすることができ、あるいは、揮発性メモリと不揮発性メモリとの両方を含めることができる。限定ではなく例として、不揮発性メモリは、読取専用メモリ(ROM)、プログラマブルROM(PROM)、電気的プログラマブルROM(EPROM)、電気的消去可能プログラマブルROM(EEPROM)、またはフラッシュメモリを含むことができる。揮発性メモリは、ランダムアクセスメモリ(RAM)を含むことができ、このRAMは、外部キャッシュメモリとして働く。限定ではなく例として、RAMは、スタティックRAM(SRAM)、ダイナミックRAM(DRAM)、シンクロナスDRAM(SDRAM)、double data rate SDRAM(DDR SDRAM)、enhanced SDRAM(ESDRAM)、Synchlink DRAM(SLDRAM)、Rambus direct RAM(RDRAM)、direct Rambus dynamic RAM(DRDRAM)、およびRambus dynamic RAM(RDRAM)などの多数の形で入手可能である。本システムおよび方法のデータストア204は、上記および任意の他の適切なタイプのメモリを、これらに限定されずに含むことが意図されている。さらに、データストア204を、サーバ、データベース、ハードドライブなどとすることができることを了解されたい。
【0029】
自動概略地図ジェネレータ202は、道路階層が接続され、複数の経路を含むことを保証するために階層選択判断基準を利用するデータ選択コンポーネント204を含むことができる。それでも、機能強化された概略目的地地図206が、そのような目的地がそれに関連する単一の経路だけを有するときに、単一の経路を含むことができることを了解されたい。データ選択コンポーネント208は、目的地を囲む道路階層に基づいて地理データをフィルタリングすることができる。言い換えると、道路セットの階層を利用して、目的地への少なくとも1つの経路を作成することができる。道路セットは、たとえば、大道路セット、中道路セット、および地方道路セットとすることができ、そのようなセットは、道路サイズ、制限速度、道路内の車線数などに基づくものとすることができる。たとえば、大道路セットは、州間ハイウェイを含むことができ、中道路セットは、幹線道路、州道、および大道路セットの境界内の他の主要道を含むことができ、地方道路セットは、中道路セットの境界内の地方道路を含むことができる。
【0030】
自動概略地図ジェネレータ202は、さらに、道路に関連するジオメトリおよび/またはデータ選択コンポーネント208からの階層的に選択された地理データを単純化する形状コンポーネント210を含むことができる。形状コンポーネント210は、形状単純化を利用して個々の道路のジオメトリを単純化することができる。形状単純化が、LineDriveシステムでの形状単純化について概要を示したものに実質的に類似する手順、原理、および/または基本アルゴリズムを実施できることを了解されたい。形状単純化は、偽交差点(false intersection)の導入に関するより多くの可能性があるという事実によって、形状コンポーネント210ではより制約され得る。形状コンポーネント210は、反復最適化(iterating optimization)によって、SIGGRAPHタイムフレームでそのような偽交差点に対処することができる。言い換えると、形状コンポーネント210は、形状単純化を実行し、次に道路レイアウトを実行し、次に形状単純化をもう1ラウンドを実行し、以下同様に実行する。
【0031】
システム200の自動概略地図ジェネレータ202は、さらに、道路レイアウトコンポーネント212を含むことができる。道路レイアウトコンポーネント212は、たとえば確率的探索として道路レイアウトを構造化することができる。検索空間は、異なる可能な、道路網データの2Dレイアウトからなる。検索は、シミュレーテッド・アニーリング・アルゴリズムを用いて行うことができる。このアルゴリズムは、道路網の適当に初期化されたコピーから開始する。たとえば、図5(A)の502にある初期化された地図を参照されたい。このアルゴリズムに関連する各の反復(iteration)中に、道路のレイアウトを、道路レイアウトコンポーネント212によってある形で(図3でより詳細に述べる。)摂動させることができる。新しいレイアウトを、摂動に少なくとも部分的に基づいて評価することができる。レイアウトのスコア(score)が、摂動の結果として低くなる場合には、新しいレイアウトが、このアルゴリズムの新しい反復への入力として受け入れられる。スコアが、摂動の結果として高くなる場合には、そのレイアウトは、ある確率で受け入れられ、そうでない場合には拒絶され得る。より悪いレイアウトを受け入れる確率は、温度変数(temperature variable)に依存し、この温度変数は、諸ステージで経時的に低下することができる。
【0032】
自動概略地図ジェネレータ202は、機能強化された概略目的地地図206に関連する道路のラベル付けを容易にするラベルコンポーネント214を含むことができる。ラベルコンポーネント214は、自動化されたラベル配置技法を実施することができる。たとえば、アニーリング手法を利用することができ、ここで、そのような技法は、互いに干渉せず、高められた可読性を提供する、明瞭で簡潔なラベルを可能にする。たとえば、ラベルコンポーネント214は、配置、フォント、方位などを維持できるように、めいめいの可読性に干渉しない、道路のラベルを提供することができる。ラベルコンポーネントが、ラベル付けと機能強化された概略目的地地図206のさまざまな態様に対する変形との間で反復することができることを了解されたい。したがって、新しいレイオーバー(layover)をさらに変形し、その結果、ラベルがよりよくおさまるようにすることができる。次に、ラベル付けの第2の反復を、変形の後で使用して、ラベルのされなる洗練を可能にすることができる。ラベル付けと変形との間の任意の適切な回数の反復を理解されたい。
【0033】
図3に、目的地の機能強化された概略目的地地図の作成を容易にするシステム300を示す。システム300は、前の図で説明したデータ選択コンポーネント204を含み、ここで、データ選択コンポーネント204は、特定の目的地に関連する地理データの階層選択を提供する。データ選択コンポーネント204は、道路階層が接続され、複数の経路を含むことを保証するために、階層選択判断基準を利用することができる。
【0034】
ユーザが目的地を指定すると(たとえば、目的地を(A)オリジナル地図に見ることができる、図4の402を参照されたい。)、データ選択コンポーネント208は、どの道路を機能強化された概略目的地地図206に含めることができるかを選択する。「好ましい」道路のセットを決定するために変更された2次元(2D)幾何可視性アルゴリズムを利用することによって、道路選択に関する階層設計判断基準を使用することができる。データ選択コンポーネント208は、次のように3つの可視性パス(visibility pass)を実行する。第1のスイープ(sweep)では、地図内の他のすべての道路が不可視であるかのように、どの大ハイウェイが目的地から可視であるかに関する判定。手短に図4を参照すると、404で、これらのハイウェイを(B)可視性に見ることができる。次に、データ選択コンポーネント208は、大ハイウェイおよび/または最大検索地域の境界によって囲まれる地域(いずれか小さい方)内の中サイズの道路(たとえば、幹線道路、他の主要道)のもう1つのスイープを実行する。手短に図4を参照すると、404で、これらの中サイズの道路を(B)可視性に見ることができる。最後に、データ選択コンポーネント208は、中サイズの道路、大ハイウェイ、および最大検索地域によって囲まれる地域(いずれであれ、より小さいもの)内の一般道路だけのスイープを実行する。手短に図4を参照すると、404で、これらの一般道路を(B)可視的に見ることができる。最大検索地域を、たとえば目的地から10kmなど、予め定めた限度の半径の中に含まれるすべてのものと定義できることを了解されたい。
【0035】
集められた「好ましい」道路のセットが、経路を含まない場合があり、接続されてさえいない場合がある。したがって、データ選択コンポーネント208は、可能な時には必ず、好ましい道路を含む経路を構成する。データ選択コンポーネント208は、一連の変更されたA*スタイル経路発見パス(modified A*−style route finding pass)を利用することができる。A*アルゴリズムは、最適性判断基準(たとえば、最短経路、最速経路、最少の曲がり角など)に従って起点と目的地点との間の単一の最適な経路を見つける。このアルゴリズムを、最短経路を検索しながら好ましいセット内の道路を優先するように変更することができ、大ハイウェイ終点のセットを、経路起点のセットとして選択することができる。データ選択コンポーネント208は、各ハイウェイ終点(たとえば、ハイウェイが最大検索地域の境界と交差する場所)から目的地への1つの経路を計算し、目的地から各ハイウェイ終点への1つの経路を計算することができる。手短に図4を参照すると、406で、この計算を、(C)可視経路差に見ることができ、ここで、従来の地図からこのアルゴリズムによって追加されなければならならなかった相対的に少数の道路(たとえば、経路のみ)。可視性アルゴリズムおよび経路発見アルゴリズムを用いて識別されたすべての道路の和集合(union)が、機能強化された概略目的地地図206に関する道路のすべての選択物を構成する。手短に図4を参照すると、道路セットの階層を利用するこのすべての選択物が、408の(D)最終的な道路選択の下に示されている。
【0036】
複数の目的地を含む地図は、単一の目的地を含む地図が処理される方法の単純な一般化を用いてデータ選択コンポーネント208によって処理することができる。まず、各個々の目的地の可視性結果の和集合をとり、次に、すべての経路組み合わせの交差を見つける。
【0037】
データ選択コンポーネント208が、機能強化された概略目的地地図206に含めるべき道路の全セットを決定すると、様々なデータクリーニング手順を実行して、そのような地図が地図レイアウト設計原理を満足するのをより簡単にすることができる。まず、データ選択コンポーネント208は、すべてのオーバーパス(たとえば、ある道路が別の道路の上を通過するが交差しない場所)を識別することができる。次に、動的計画法アルゴリズムを使用して、道路のチェーンをマージし、チェーンのどのプロパティが最も関連するかを判定することができる。最後に、上下関係を共有する道路と、横並び関係を共有する道路とをグループ化することができ、その結果、そのような道路を、一緒に変形できるようにする(下で述べる)ことができる。
【0038】
データ選択コンポーネント204は、階層に基づく道路の選択を容易にするために道路階層コンポーネント302を含むことができる。道路階層コンポーネント302は、階層設計判断基準に従うために、上で説明した道路セットの階層を使用する。階層構造を前もって提供することによって、道路階層コンポーネントを、比例して使い易くすることができる。道路階層コンポーネント302は、目的地に関して階層的に道路を選択することができる。地図作成者に基づいて、目的地を囲む地域内の最大の道路(たとえば、州間ハイウェイ)は、一般に、ランドマークとして認識することができ、その地域に少ししか馴染みのない人々がこれを突き止めることができる。道路コンポーネント302は、地図ユーザが支援なしで大道路の1つを見つけることができるならば、その地図ユーザは機能強化された目的地地図を使用してそこから目的地に達することができるという推論を用いて、まず最大の道路を選択する。道路階層コンポーネント302は、大道路(および/または最大地域の境界)によって囲まれた地域内から中サイズの道路のセットを選択することができる。これは、幹線道路、州道、および他の主要道を含む。道路階層コンポーネント302は、中サイズの道路(および/または最大地域)によって形成される地域内から目的地を囲む一般道路をも選択することができる。
【0039】
道路階層コンポーネント302が、任意の適切な道路選択技法を利用できることを了解されたい。たとえば、可視性演算子(visibility operator)を利用して、あるクラス(たとえば、サイズなど)内の少なくとも1つの可視の道路を見つけることができる。その後、街路および幹線道路を機能強化された概略地図に含めることができるように(たとえば、ある経路と共に使用されるかどうかに無関係に)、可視の道路のクラスを使用することができる。可視の道路の最大のクラス(the largest class of visible roads)のエッジは、道路の最大のクラスが大道路(ハイウェイ、主要道など)であるかどうかにかかわりなく使用することができる。さらに、ソースプレート(source plate)を部分グラフ(たとえば、道路の接続された部分)から選択することができる。言い換えると、可視性は、可視エッジを識別し、エッジは部分グラフに属し、これらの部分グラフは、道路を含む。エッジを、最大の道路クラスから選択し、部分グラフを解明し、部分グラフの末端の点をとって、目的地へおよび目的地からの毛細経路(capillary route)のソース点にすることができる。道路階層コンポーネント302は、さらに、ソース点から目的地への経路(「to経路」とも称する。)を見つけるためにたどるべきおよび/または他の道路/経路と比較して部分的である可視エッジが属する部分グラフの特定の道路/経路を識別することができる(ブリーディング技法など)。道路階層コンポーネント302は、グラフ内の最大の道路のセットおよび経路(to経路)のセットを利用して、「from経路」すなわち、目的地から部分グラフソース点への経路を計算することができる。「from経路」は、可視性から最大の経路だけを優先するのではなく、最大の道路を優先することを可能にするために「to経路」をも優先する。この技法は、地図内の独立経路の量を減らすことができる(たとえば、経路をさらに単純化する)。「to経路」および「from経路」を、可視性から識別された街路および幹線道路と組み合わせ、次に、収集されたエッジから、目的地のすべてに関連する最大の接続するコンポーネントと組み合わせることができ、それを、道路の集合/選択物とすることができる。
【0040】
データ選択コンポーネント204は、さらに、経路コンポーネント304を含むことができる。データ選択コンポーネント204は、経路コンポーネント304によって実施できる次の3つの望ましい目標を反映する、地図内の「好ましい」道路のセットを確立する。第1に、地図は、目的地から大きい地域へ/大きい地域から目的地への効率的な道筋を記述することができ、これは、地図をより柔軟でより広い範囲のユーザに有用にすることができる。第2に、好ましい道路は、それ自体で使い易いものとすることができ、これは、地図作成者の重要な判断基準とすることができる。第3に、好ましい道路のセットを組み込むために偏らされた経路は、地図ユーザを最長の可能な時間の長さにわたって最大の可能な道路上に保つことができ、これは、比較的少数の旋回でたどりやすい経路をもたらす(地図作成者のもう1つの重要な目標)。
【0041】
経路コンポーネント304は、可能な時には必ず好ましいセットからの道路を使用し、そうでない時には事実に忠実な地図から補足して、経路を明示的に設計する。経路コンポーネント304は、経路発見の主要な設計目標を実施することができ、ここで、主要な設計は、すべての最大の道路の両側から各目的地へ/各目的地からすべての最大の道路の両側へ達する少なくとも1つの道を記述する複数の経路を確立することとすることができる。このようにして、経路コンポーネント304は、現在の状態(たとえば、交通、工事など)、地図ユーザがどこから来る可能性があるか、および地図ユーザが道に迷ったかどうかに応じて、地図ユーザが動的な形でそこから選択できる代替案を提供することができる。
【0042】
システム300は、さらに、道路レイアウトコンポーネント210を含む。道路レイアウトコンポーネント210は、変形コンポーネント306を含むことができる。変形コンポーネント306は、明瞭さおよび有用性を最大にするために、階層的に選択された地理データをレンダリングすることができる。道路選択に関して、概略目的地地図レイアウトを、人々の空間的知覚および記憶の独自の特性に配慮して設計することができる。たとえば、我々が空間の記憶に幾何学的変形を自然に導入することを示す十分な証拠がある。これは、理解がより単純であり記憶がより簡単である、あらかじめ考えられたモデルに知覚を合わせる試みにおいて自動的に行われる可能性がある。この知覚から、いくつかの地図特徴が、他の特徴より重要であり、より重要でない特徴は、地図の有用性に影響せずに安全に変更でき、より重要な特徴は、有用性を高めるために保存され、かつ/または強調されなければならない。
【0043】
地図作成者は、何世紀にもわたってこれを認識しており、地図作成法研究および認識研究は、地図描写のさまざまな態様が地図の有用性に関してどれほど重要であるかの順序付けを提案してきた。たとえば、最上位に、地図特徴(map feature)の存在(existence)および連結性(connectedness)を置くことができる。その次は、地図全体および個々の特徴の方位(orientation)とすることができる。その後は、お互いに関する地図特徴の局所化(localization)とすることができる。最後に、特徴の間の距離(distance)および特徴の形状(shape)は、従来の地図においてさえしばしば変形されるので、より低い重要性を有するものとすることができる。
【0044】
このフレームワーク内で、変形コンポーネント306は、2つの主な地図レイアウト目標すなわち、1)最終的な地図内のすべての道路が可視であることと、2)オリジナルの道路網トポロジが維持されることとを確実にすることとを有することができる。より少ない範囲まで、変形コンポーネント306は、ユーザの現実および一般的な知識の精神的モデルへの地図の全体的な対応をも維持することができ、特にそれによって描写される区域に馴染みがある人々にとって、プラニングデバイスとして使用することがより簡単になる。また、特に、後にある区域を通って移動する前にその区域に馴染みがない人々にとって、記憶の助けとして地図を使用することがより簡単になる。
【0045】
変形コンポーネント306は、ループを含むグラフの変形のより一般的なケースに対処することができる。変形コンポーネント306は、ソフト制約のセットにわたり最適化することによって、心理学的に意味のある変形目標を満足することができ、これらの制約の一部を完全には満足できない場合であっても妥当な結果を作ることができる。以下は、変形コンポーネント306によって地図変形を実行することによって満足できるソフト制約の各セットの説明である。
【0046】
変形コンポーネント306は、発生する交差点のセットおよび交差点での道路の相対順序付けを含む、地図の道路網の基本トポロジを維持することができる。実際には存在しない新しい交差点(たとえば、偽(false)交差点)の導入は、実際には存在しない経路を含むトポロジ的に不正確な地図をもたらすだろう。そのような交差点がトポロジに実際に発生する場所で交差点を表すことができないこと(たとえば、欠けている交差点)は、一般に、より低いリスクとすることができる。しかし、これも望ましくはない。というのは、我々の道路選択アルゴリズムによって選択される道路網は、それが含む経路に部分的に基づいて選択されるからであり、交差点の省略は、その網から1つまたは複数の経路を削除することと同等であるからである。
【0047】
さらに、変形コンポーネント306は、旋回方向を維持することができる。各交差点で、入射する道路のすべての対の間の旋回方向を維持することができる。ある道路から別の道路への右旋回は、右旋回のままにすることができ、左旋回は、左旋回のままにすることができる。道路の任意の対の間で旋回方向を変更することは、地図ユーザを激しく混乱させ、経路プラニングの誤りにつながり、地図に従っている間にユーザに道に迷わせる可能性がある。
【0048】
変形コンポーネント306は、旋回に関する正確な描写をも提供することができる。一般に、人々は、経路をナビゲートしている時に各旋回点で行うべきことに関する判断を行う必要があり、したがって、旋回点の正確な描写は極めて重要である。実際に、複数の研究は、そこでのユーザアクティビティをサポートするために判断点(旋回など)の周囲の情報に集中することが特に重要であると結論してきた。
【0049】
たとえば、変形コンポーネント306が、少なくともゲシュタルト心理学によって識別される3つの「ゾーン」すなわち鋭角、直角、および鈍角の範囲で、できる限り旋回角(たとえば、交差点で出会う時の道路セグメント間の相対角度)を維持することが重要である。すなわち、鋭角は、鋭角のままでなければならず、直角は、ほぼ直角のままでなければならず、鈍角は、鈍角のままでなければならない。それを行うことができないと、ユーザが実際に地図に従っている時にユーザを混乱させる可能性がある。それを行うことができないと、ユーザが、地図の詳細をその地図内に描写された曲がり角および道路のメンタルイメージに関連付けることがより困難になる可能性もあり、これは、地図と現実との間の基本的な対応を維持するという目標に反する。ユーザが、一般に、記憶の中でほとんどの曲がり角を直角に正規化することを示すいくつかの認識的証拠があり、したがって、最も極端な例について鋭さと鈍さとを維持することができる。
【0050】
関連する目標は、交差点を通って直線状に続く道路を変形コンポーネント306によってその交差点でまっすぐに保たなければならないこととすることができる。旋回角に関する状況に似て、交差点を通過する道路に関する3つの重要な「ゾーン」すなわち、左への方向転換、直進、右への方向転換がある。たとえば、ユーザが交差点に接近している時に、地図は、道路が(たとえば、現実において)その交差点を越えて続くときにどうなるか(たとえば、左に方向転換するのか、右に方向転換するのか、又は直進するのか)に関する知覚を反映することができる。道路が現実において左に方向転換するが、地図では右への方向転換として描写される場合に、これはユーザを混乱させ、ナビゲーションの助けとしての地図の有用性を下げる可能性がある。
【0051】
変形コンポーネント306は、さらに、道路ジオメトリを維持することができる。道路ジオメトリのいくつかの態様を維持することができ、他の態様を、地図の明瞭さおよび可読性を改善するために変更することができる。たとえば、変形コンポーネント306が、道路の長さの相対的な順序付けを維持することが重要である(たとえば、交差点の対の間の道路Aが、実際には交差点の別の対の間の別の道路Bより長い場合に、Aは、変形された地図内でもBより長く見えなければならない)。長さの相対的な順序付けが問題であって、別の長さに対するある長さの比率は問題でないことを了解されたい。さらに、これが、他の道路との交差点の間に走る道路にあてはまるのであって、次第に消える(たとえば、地図の境界に向かう)「尾(tail)」道路にはあてはまらないことにも留意されたい。
【0052】
エッジの長さの相対順序付けを維持することは、地図を通ってたどるべき経路がどれであるかに関する判断を行うのにユーザが利用できる基本的な情報を提供するので、重要である可能性がある。ユーザが、たどるべき経路がどれであるかに関する、情報を与えられた判断(informed decision)を行うために経路の文字どおりの長さを見ることが重要であるのではなく、ある経路が別の経路より長いことを見ることだけが重要である可能性がある。変形コンポーネント306が、特に類似するクラスの道路の間で、あまりに順序はずれで道路の相対長を配置する場合、これは、地図に従う時にユーザの知覚と矛盾し、したがって、地図をより混乱を招きより従いにくいものにする可能性がある。しかし、相対長の順序の変更は一般に、地図トポロジの変更と同じ態様で地図を使用不能にすることはできない。
【0053】
自動車内で運転中のユーザにとってはしばしば時間が距離より重要なので、変形コンポーネント306は、セグメントをトラバースするのに必要な時間の長さを表す道路長を採用することができる。したがって、州間ハイウェイの1マイル(1.6km)セグメントは、街路の1マイル(1.6km)セグメントよりはるかに短いものとして表される(たとば、より高い制限速度を有し、より高速でトラバースするのにより短い時間を要するので)。言い換えると、これを、文字どおりの長さの相対順序付けに加えて、変形コンポーネント306が維持できる長さの相対順序付けとすることができる。
【0054】
変形コンポーネント306によって維持できる道路ジオメトリのもう1つの重要な態様を、いくつかの別個の道路によって共有される関係とすることができる。たとえば、2つに分かれるハイウェイまたは大通りの別々の方向など、いくつかの道路は、互いに「横並び(side−by−side)」関係を共有する。他の道路は、「上下」関係を共有する。これらの関係を、情報を与えられたユーザの期待、および情報を与えられないユーザのあらかじめ考えていたモデルと一致するために維持することができる。それを行うことができないと、地図に描写される区域に馴染みのあるユーザの記憶と矛盾する可能性がある。さらに、地図ユーザがその区域に馴染みがない場合であっても、2つに分かれるハイウェイの2つの方面を、正しい相対幾何関係ではなく、非常に離れてまたは互いに関して異なる角度で描写する地図によって示される区域を見ることは、驚かせ、おそらくは混乱させるものである可能性がある。
【0055】
さらに、変形コンポーネント306は、道路方位を維持することができる。各道路は、たとえば北方向に関する、その主な方位をできる限り維持することができる。道路方位が大きく変化する(たとえば、主に南北から主に東西へ)場合、そのような変動は、ユーザによる地域の理解と矛盾する可能性があり、地図の詳細を実際の地理的特性と一致させることをより困難にする可能性がある。しかし、これを念頭において、人々が主要な軸に向かって地図内の図形を回転する傾向があることを示す認識心理学からの重要な証拠がある可能性がある。その結果、主な方位を維持することが重要ではあるが、変形コンポーネント306にとって、正確な方位を維持することはより重要でない。
【0056】
最後に、変形コンポーネント306は、正確な道路の長さおよび形状をゆるやかに維持することができる。人々は、道路にのったならば、次の旋回点に達するまで、たどられる道路の長さおよびジオメトリに関してあまり考えずにその道路をたどることができる。したがって、正確な長さおよび形状の描写は、変形コンポーネント306にとってさほど重要ではない可能性がある。この点では、考え抜かれた道路形状単純化は、実際に、地図の明瞭さおよび可読性を改善することができる。
【0057】
図3を継続すると、道路レイアウトコンポーネント210は、摂動コンポーネント308を含むことができる。摂動コンポーネント308は、ランダムなレイアウト摂動を生成することによって一般的な道路網(たとえば、ループを含むグラフ)の変形を容易にすることができる。設計原理に伴ってレイアウトプロセスに課せられる構造的制約をある意味で反映しない摂動は、不可避的に、多数の許容できないレイアウトを生成する可能性がある。その一方で、制約されすぎた摂動は、検索(search)を谷および悪い極小値に簡単にトラップさせる可能性がある。摂動コンポーネント308は、上で説明した原理を達成するために、さまざまな摂動を利用することができる。
【0058】
たとえば、摂動コンポーネント308は、「関節点ベースのスケーリング」と称する第1のスタイルの摂動を実施することができる。グラフ理論では、関節点は、除去された場合にグラフを複数の独立の連結成分に分離できる、連結グラフ内の頂点である。道路網では、これは、除去された場合に網を複数の別個の地図に分離できる交差点に対応する。我々の摂動コンポーネント308は、道路網内の関節点をランダムに選択するステップと、その点の付近で網を分解するステップと、結果の成分のうちの1つをランダムに選択するステップと、ランダムスケールファクタによって、選択された点の付近の選択された成分をスケーリングするステップと、あらかじめ指定された境界ボックスまで戻して、地図全体をセンタスケーリングするステップとを含むことができる。たとえば、それぞれ図5の502、504、および506を参照されたい。関節点ベースのスケーリング摂動は、道路レイアウトの構造的制約を反映することができる。摂動は、欠けている交差点を絶対にもたらすことができず、旋回角を絶対に変更せず、必ず道路方位を維持することができる。
【0059】
道路レイアウトコンポーネント210は、さらに、スコアリングコンポーネント310を含むことができる。新しい道路レイアウトが、摂動コンポーネント308によって実施される摂動によって生成されるたびに、スコアリングコンポーネント310は、上で概要を示し、述べた地図変形設計原理に従って、そのようなレイアウトを評価することができる。具体的に言うと、スコアリングコンポーネントは、次の諸態様を利用することができる。まず、新しい偽交差点が導入されたか否か、および真の交差点が欠けているか否かを判定する。これらは、摂動によって導入され得る最も甚だしいエラーの1つである。というのは、これらが、効果的にオリジナル(通常)の地図のトポロジを変更するからである。そのようなエラーのいずれかが発見される場合には、新しいレイアウトに非常に悪いスコアを与えることができる。次に、新しい地図内の道路のいずれかが、それ未満ではユーザがレイアウト内でその道路を見ることが難しい最小の長さしきい値未満になるか否かを判定する。道路網変形の全体的な目標は、地図内のすべての道路を可視にすることとすることができ、したがって、いずれかの道路が効果的に不可視であると判定される場合、そのレイアウトにそれ相応にペナルティを与えることができる。最後に、地図内の道路の相対長が、摂動の結果として順序はずれになったか否かを判定する。相対順序付けの変化は、顕著になるまでカウントしないものとすることができ、顕著になったならば変化のサイズに従ってペナルティを与えることができる。
【0060】
図6に、目的地に少なくとも部分的に基づく少なくとも2つの経路を有する機能強化された概略目的地地図の自動生成を容易にするシステム600を示す。ラベルコンポーネント214は、機能強化された概略目的地地図に関連する道路のラベル付けを容易にすることができる。ラベルコンポーネント214は、自動化されたラベル配置技法を実施することができる。たとえば、アニーリング手法を利用することができ、そのような技法は、互いに干渉せず、高められた可読性を提供する、明瞭で簡潔なラベルを可能にする。さらに、ラベルコンポーネント214は、各地図の特色である重要なプロパティを地図ユーザに知らせることができるラベルおよびその他の情報で地図を装飾することができる。
【0061】
手短に図7を参照すると、図示のラベル702は、ラベルレイアウト問題の簡潔な視覚的ステートメントを描写する。たとえば、ある道路のラベルを、その道路の上または下のいずれかの、その道路に「沿った」ある場所に配置し、ラベル位置での道路の曲線の接線まで傾けられるように制約することができる。図示のラベル704、発生し得る最悪なことの1つを、ラベル位置の摂動の結果として図示することができ、この結果は、ラベル−ラベル衝突である。ラベルコンポーネント214は、そのような問題の事例を防ぐことができ、特定の機能強化された概略目的地地図のラベルレイアウトを最適化できることを了解されたい。
【0062】
図6に戻ると、ラベルコンポーネント214は、道路ラベルコンポーネント602を含むことができる。道路ラベルコンポーネント602は、明瞭で有用なラベルレイアウト作成における次の伝統的な目標に焦点を合わせることができる。第1に、道路ラベルコンポーネント602は、ラベル−ラベル衝突を防ぐことができる。これは、特に2つの道路が交差する場合に発生する可能性があり、そのような衝突は、関わるラベルの可読性を大幅に下げる可能性がある。第2に、道路ラベルコンポーネント602は、ラベル−道路衝突を防ぐことができる。この種の衝突は、関わるラベルを読むことを混乱させるものにする可能性があり、重要な地図詳細(map details)を隠す可能性がある。最後に、道路ラベルコンポーネント602は、ラベルの間の距離を最大にすることを試みることができ、したがって、外見は、下にある道路網にまたがって均等に分散される。これは、地図の明瞭さおよび可読性を高めるのを助ける。
【0063】
さらに、道路ラベルコンポーネント602は、地図特徴ごとに関連するプロパティだけを表示することとすることができる、追加の設計考慮事項を実施することができる。機能強化された概略目的地地図の目的は、目的地(または目的地のセット)へ(およびそこから)どのように達するかをユーザに示すこととすることができ、したがって、表示できるのは、この目的に関連する情報だけであり、他のすべての情報は、混乱を減らすために隠すことができる。たとえば、道路選択の結果として、道路のチェーン(a chain of roads)(たとえば、他の交差する道路なしで、ある道路が別の道路につながるなど)が、地図に現れる場合があり、その場合には、チェーン内の道路の間にわずかな相違だけがある(たとえば、「65th NW」対「65th N」)。チェーン内の各個々の道路にラベル付けするのではなく、道路ラベルコンポーネント602は、より関連するプロパティ、たとえば、チェーンの始めにある道路の名前およびチェーンの終りにある道路の名前を含めることができる。これらは、ユーザが我々の地図内でそのチェーンに入ることのできる唯一の点なので、含めるべき最も重要な名前であり、他のすべての名前は、地図の有用性を犠牲にせずに混乱を減らすために安全に隠すことができる。
【0064】
図8に、機能強化された概略目的地地図の自動生成を容易にするのにインテリジェンスを使用するシステム800を示す。システム800は、自動概略地図ジェネレータ802、インターフェース104、機能強化された概略目的地地図804、データ、および地理データを含むことができ、これらのすべてを、前の図で説明したコンポーネント、ジェネレータ、地図、およびデータにそれぞれ実質的に類似するものとすることができる。システム800は、さらに、インテリジェントコンポーネント806を含む。インテリジェントコンポーネント806は、自動概略地図ジェネレータ802によって、地理データおよび目的地に基づいて機能強化された概略目的地地図804を自動作成するのを容易にするのに利用することができる。たとえば、インテリジェントコンポーネント806は、目的地、経路効率、交通、工事、最適化された旅行、機能強化された概略目的地地図804に関連するパーソナライズされたプリファレンスなどを推測することができる。
【0065】
インテリジェントコンポーネント806が、イベントおよび/またはデータを介して取り込まれた1組の観察結果からシステム、環境、および/またはユーザの状態に関する推論を提供し、またはこれを推測することができることを理解されたい。推測は、特定のコンテキストまたはアクションを識別するのに使用することができ、あるいは、たとえば状態にまたがる確率分布を生成することができる。推測は、確率的すなわち、データおよびイベントの考慮に基づく、該当する状態にまたがる確率分布の計算とすることができる。推測は、イベントおよび/またはデータのセットからより高いレベルのイベントを構成するのに使用される技法を指すこともできる。そのような推測は、イベントが密な時間的近接で相関するか否かに関わりなく、またイベント及びデータが1つ又は複数のイベントソース及びデータソースのどちらから来るかに関わりなく、観察されたイベントおよび/または格納されたイベントデータのセットからの新しいイベントまたはアクションの構成をもたらす。さまざまな分類(明示的にかつ/または暗黙のうちにトレーニングされた)方式および/またはシステム(たとえば、サポート・ベクトル・マシン、ニューラル・ネットワーク、エキスパート・システム、ベイジアン・ビリーフ・ネットワーク、ファジイ論理、データ・フュージョン・エンジン等)を、請求される主題に関連する自動的なかつ/または推測されたアクションの実行に関連して使用することができる。
【0066】
クラシファイヤ(clasifier)とは、入力属性ベクトルx=(x1,x2,x3,x4,xn)を、入力が、あるクラス(class)に属することの信頼度(confidence)に写像する関数、すなわちf(x)=confidence(class)である。そのような分類(classification)は、確率的および/または統計ベースの分析(たとえば、分析ユーティリティおよびコストへのファクタリング)を使用して、ユーザが自動的に実行されることを望むアクションを予知しまたは推測することができる。サポートベクトルマシン(SVM)が、使用できるクラシファイヤの例である。SVMは、可能な入力の空間(the space of possible inputs)内で超曲面を見つけることによって動作し、この超曲面は、トリガする判断基準を非トリガイベントから分離することを試みる。直観的に、これは、トレーニングデータと同一ではなく、トレーニングデータに近いテスティングデータに関して分類を正しいものにする。他の管理されたモデル分類手法および管理されないモデル分類手法(directed and undirected model classification approach)は、たとえば、ナイーブベイズ、ベイズネットワーク、決定木、ニューラル・ネットワーク、ファジイ論理モデルを含み、独立性の異なるパターンを提供する確率分類モデルを使用することができる。本明細書で使用される分類は、優先順位のモデルを展開するのに利用される統計的回帰をも包含する。
【0067】
プレゼンテーションコンポーネント808は、ユーザと自動概略地図ジェネレータ802に結合されたすべてのコンポーネントとの間の対話を容易にするために様々なタイプのユーザインターフェースを提供する。描写されているように、プレゼンテーションコンポーネント808は、自動概略地図ジェネレータ802と共に利用できる別々のエンティティである。しかし、プレゼンテーションコンポーネント808および/または類似するビューコンポーネントを、自動概略地図ジェネレータ802および/またはスタンドアローンユニットに組み込むことができることを了解されたい。プレゼンテーションコンポーネント808は、1つまたは複数のグラフィカルユーザインターフェース(GUI)、コマンドラインインターフェース等を提供することができる。たとえば、データのロード、インポート、読み取りなどのための領域または手段をユーザに与え、その結果を表す領域を含むことができるGUIを、レンダリングすることができる。これらの領域は、エディットコントロール、コンボボックス、ラジオボタン、チェックボックス、プッシュボタン、およびグラフィックボックスとしてダイアログボックス、スタティックコントロール、ドロップダウンメニュー、リストボックス、ポップアップメニューを含む既知のテキスト領域および/またはグラフィック領域を含むことができる。さらに、ナビゲーション用の垂直スクロールバーおよび/または水平スクロールバーならびに領域が可視になるかどうかを判定するためのツールバーボタンなどのプレゼンテーションを容易にするユーティリティを使用することができる。たとえば、ユーザは、自動概略地図ジェネレータ802に結合され、かつ/または組み込まれたコンポーネントのうちの1つまたは複数と対話することができる。
【0068】
ユーザは、たとえばマウス、ローラーボール、キーパッド、キーボード、ペン、および/または音声アクティベーションなどの様々なデバイスを介して情報を選択し、提供するために領域と対話することもできる。通常、検索を開始するために、プッシュボタンまたはキーボード上のエンターキーなどの機構を、情報を入力した後に使用することができる。しかし、請求される主題がそれに限定されないことを了解されたい。たとえば、チェックボックスを単に強調表示にすることにより、情報伝達を開始することができる。もう1つの例で、コマンドラインインターフェースを使用することができる。たとえば、コマンドラインインターフェースは、テキストメッセージの提供を介して情報についてユーザにプロンプトを出す(たとえば、ディスプレイ上のテキストメッセージおよびオーディオトーンを介して)ことができる。その後、ユーザは、インターフェースプロンプト内で提供されたオプションまたはプロンプトで提示された質問に対する回答に対応する英数字入力など、適切な情報を提供することができる。コマンドラインインターフェースを、GUIおよび/またはAPIに関連して使用できることを了解されたい。さらに、コマンドラインインターフェースを、限られたグラフィックサポートを有するハードウェア(たとえば、ビデオカード)および/もしくはディスプレイ(たとえば、白黒およびEGA)ならびに/または低帯域幅通信チャネルに関連して使用することができる。
【0069】
図9〜10に、請求される主題による方法論を示す。説明を単純にするために、これらの方法論は、一連の行為として描写され、説明される。本革新が、図示された行為および/または行為の順序によって限定はされず、たとえば、行為を、さまざまな順序でかつ/または同時に、本明細書で提示されず説明されない他の行為と共に行うことができることを理解し、了解されたい。さらに、図示されたすべての行為が、請求される主題による方法論を実施するのに必要とは限らない。さらに当業者は、これらの方法論を、状態図(state diagram)を介して相互に関係付けられた一連の状態として又はイベントとして代替的に表すことができることを理解し、了解するであろう。さらに、以下および本明細書全体を通じて開示される方法論が、そのような方法論のコンピュータへの輸送および転送を容易にするために製造品に格納されることが可能であることを、さらに了解されたい。本明細書で使用される製造品という用語は、任意のコンピュータ可読デバイス、担体、または媒体からアクセス可能なコンピュータプログラムを含むことが意図されている。
【0070】
図9に、目的地の機能強化された概略目的地地図の生成を容易にする方法論900を示す。符号902で、目的地を受け取ることができる。目的地は、たとえば、地図上の位置、住所、街路、交差点、店、市、建物、州、国、緯度および経度などとすることができる。さらに、目的地を、ユーザから受け取ることができる。方法論(methodology)900が、複数の目的地を受け取ることができることを了解されたい。
【0071】
符号904で、地理データを、少なくとも部分的に目的地に基づいて選択的にフィルタリングすることができる。データを階層的にフィルタリングして、目的地への適当な経路をフィルタリングすることができる。データは、少なくとも部分的に道路階層に基づいて選択することができる。たとえば、階層選択判断基準は、道路階層が接続され、複数の経路を含むことを保証することができる。言い換えると、道路セットの階層を利用して、目的地への少なくとも1つの経路を作成することができる。道路セットは、たとえば、大道路セット、中道路セット、および地方道路セットとすることができ、そのようなセットは、道路サイズ、速度制限、道路内の車線数などに基づくものとすることができる。たとえば、大道路セットは、州間ハイウェイを含むことができ、中道路セットは、幹線道路、州道、および大道路セットの境界内の他の主要道を含むことができ、地方道路セットは、中道路セットの境界内の一般道路を含むことができる。
【0072】
符号906で、機能強化された概略目的地地図を自動的に作ることができる。機能強化された概略目的地地図は、読みやすい経路、抑制された詳細、関連しないデータの除外、明瞭なおよび/または単純化された地理的特徴、混乱の除去、使い易さ、ならびに/あるいは目的地への複数の経路という改善のうちの少なくとも1つを含む簡素化された地図とすることができる。機能強化された概略目的地地図を、目的地を囲む地理データの評価に少なくとも部分的に基づいて簡素化できることを了解されたい。言い換えると、第1の目的地に関連する機能強化された概略目的地地図は、第2目的地に関連する機能強化された概略目的地地図106と比較して、異なる改善(たとえば、抑制された詳細、除外された関連しないデータ、明瞭なおよび/または単純化された地理的特徴、混乱の除去、目的地への複数の経路など)を含むことができる。
【0073】
さらに、機能強化された概略目的地地図を、少なくとも1つの原理および/または技法を利用することによって自動的に作ることができる。たとえば、この原理および/または技法は、1)関連するデータだけを機能強化された概略目的地地図106に含めることができるように地理データを選択的にフィルタリングすること、2)機能強化された概略目的地地図106を理解しやすく使い易くするために地理データを変形すること、および3)道路名ラベル、注釈、および目的地住所など(たとえば、下で述べる)、有用性を改善するための追加情報を用いて機能強化された概略目的地地図を装飾することとすることができるが、これらに限定はされない。さらに、そのような技法および/または原理を反映するさまざまなアルゴリズムを実施することができ、そのような原理は、機能強化された概略目的地地図を作るための時間および技量を減らすことができる。
【0074】
図10に、目的地に少なくとも部分的に基づく少なくとも2つの経路を有する機能強化された概略目的地地図を自動的に生成する方法論1000を示す。符号1002で、目的地に関連するデータを受け取ることができる。目的地は、たとえば、地図上の位置、住所、街路、交差点、店、市、建物、州、国、緯度および経度などとすることができる。さらに、目的地を、ユーザ、ソフトウェアプログラム、および/または適当なデータを有する任意の他の適切なマシンから受け取ることができる。
【0075】
符号1004で、地理データを選択することができる。地理データは、目的地位置および道路階層に少なくとも部分的に基づいて選択することができる。道路階層は、道路のセットを利用することができ、ここで目的地を囲む道路を、さまざまな特性に基づいてグループ化することができる。言い換えると、道路セットの階層を利用して、目的地への少なくとも1つの経路を作成することができる。道路セットは、たとえば、大道路セット、中道路セット、および地方道路セットとすることができ、そのようなセットは、道路サイズ、速度制限、道路内の車線数などに基づくものとすることができる。たとえば、大道路セットは、州間ハイウェイを含むことができ、中道路セットは、幹線道路、州道、および大道路セットの境界内の他の主要道を含むことができ、地方道路セットは、中道路セットの境界内の一般道路を含むことができる。
【0076】
符号1006に継続すると、変形を適用することができ、装飾を投入することができる。変形は、明瞭さおよび有用性を最大にするために、階層的に選択された地理データをレンダリングすることができる。さらに、適用される変形は、トポロジ、曲がり角(turn)、および道路ジオメトリに関するソフト制約を利用することができる(すべて上で述べた)。装飾を適用することができ、地図に、地図特徴のそれぞれの重要なプロパティをユーザに伝えるラベルおよび他の情報を投入することができる。たとえば、道路名ラベル、プロンプト道路(prompt roads)、吹き出し、ランドマーク、パーソナライズされたデータなどを投入することができる。符号1008で、機能強化された概略目的地地図を自動的に作成することができ、機能強化された概略目的地地図は、読みやすい経路、強調を解除された詳細、除外された関連しないデータ、明瞭なおよび/または単純化された地理的特徴、混乱の除去、使い易さ、ならびに/あるいは目的地への複数の経路という改善のうちの少なくとも1つを提供する。さらに、機能強化された概略目的地地図を、レンダリングし、かつ/またはユーザに表示することができる。
【0077】
図11に、本革新に従って利用される目的地に関する地理データ1100を示す。地理データ1100は、従来の混乱に満ちた事実に忠実な地図の例である。地理データ1100は、機能強化された概略目的地地図を自動的に作るために自動概略地図ジェネレータ(上で述べた)によりすることができる。目的地1102を利用することができ、それに関連する機能強化された概略地図を提供することができる。複数の目的地を地理データ1100に関連付けることができ、目的地1102が例のためのみのものであることを了解されたい。
【0078】
図12に、目的地に関する自動的に生成された機能強化された概略目的地地図1200を示す。機能強化された概略目的地地図1100が、図11の目的地1102に関連して図示されている。機能強化された概略目的地地図1200は、読みやすい経路、(図11の地理データ1100と比較して)抑制された詳細、(図11の地理データ1100と比較して)除外された関連しないデータ、(図11の地理データ1100と比較して)明瞭なかつ/または単純化された地理的特徴、(図11の地理データ1100と比較して)混乱の除去、使い易さ、ならびに/あるいは目的地への複数の経路という改善を含む簡素化された地図である。機能強化された概略目的地地図を、道路階層選択に少なくとも部分的に基づいて簡素化できることを了解されたい。
【0079】
請求される主題のさまざまな態様を実施する追加の文脈を提供するために、図13〜14および次の議論は、本革新のさまざまな態様を実施できる適切なコンピューティング環境の短い全般的な説明を提供することを意図されたものである。たとえば、前の図で説明した、機能強化された概略目的地地図を自動的に作る自動概略地図ジェネレータを、そのような適切なコンピューティング環境で実施することができる。請求される主題を、上ではローカルコンピュータおよび/またはリモートコンピュータで走行するコンピュータプログラムのコンピュータ実行可能命令の全般的な文脈で説明したが、当業者は、本革新を他のプログラムモジュールと組み合わせて実施できることを認めるであろう。一般に、プログラムモジュールは、特定のタスクを実行し、かつ/または特定の抽象データ型を実施するルーチン、プログラム、コンポーネント、データ構造などを含む。
【0080】
さらに、当業者は、本発明的方法を、シングルプロセッサまたはマルチプロセッサのコンピュータシステム、ミニコンピュータ、メインフレームコンピュータ、ならびにパーソナルコンピュータ、ハンドヘルドコンピューティングデバイス、マイクロプロセッサベースのおよび/またはプログラマブルな消費者エレクトロニクス等を含む他のコンピュータシステム構成を用いて実践することができ、これらのそれぞれが、1つまたは複数の関連するデバイスと動作可能に通信できることを了解するであろう。請求される主題の図示された諸態様は、ある種のタスクが通信ネットワークを介してリンクされたリモート処理デバイスによって実行される分散コンピューティング環境でも実践することができる。しかし、本革新の、すべてではないにしてもいくつかの態様を、スタンドアローンコンピュータで実践することができる。分散コンピューティング環境では、プログラムモジュールを、ローカルおよび/またはリモートのメモリストレージデバイスに配置することができる。
【0081】
図13は、請求される主題が相互作用できるサンプルのコンピューティング環境1300の概略ブロック図である。システム1300は、1つまたは複数のクライアント1310を含む。クライアント1310は、ハードウェアおよび/またはソフトウェア(たとえば、スレッド、プロセス、コンピューティングデバイス)とすることができる。システム1300は、1つまたは複数のサーバ1320を含む。サーバ1320は、ハードウェアおよび/またはソフトウェア(たとえば、スレッド、プロセス、コンピューティングデバイス)とすることができる。サーバ1320は、たとえば本革新を使用することによって変換(transformation)を実行するスレッドを収容することができる。
【0082】
クライアント1310とサーバ1320との間の1つの可能な通信は、複数のコンピュータプロセスの間で伝送されるように適合されたデータパケットの形とすることができる。システム1300は、クライアント1310とサーバ1320との間の通信を容易にするのに使用することができる通信フレームワーク1340を含む。クライアント1310は、クライアント1310にローカルな情報を格納するのに使用することができる1つまたは複数のクライアントデータストア1350に動作可能に接続される。同様に、サーバ1320は、サーバ1320にローカルな情報を格納するのに使用することができる1つまたは複数のサーバデータストア1330に動作可能に接続される。
【0083】
図14を参照すると、請求される主題のさまざまな態様を実施する例示的な環境1400は、コンピュータ1412を含む。コンピュータ1412は、処理ユニット1414、システムメモリ1416、およびシステムバス1418を含む。システムバス1418は、システムメモリ1416を含むがこれに限定されないシステムコンポーネントを処理ユニット1414に結合する。処理ユニット1414は、さまざまな入手可能なプロセッサのいずれかとすることができる。デュアルマイクロプロセッサアーキテクチャおよび他のマルチプロセッサアーキテクチャを処理ユニット1414として使用することもできる。
【0084】
システムバス1418は、メモリバスもしくはメモリコントローラ、周辺バスもしくは外部バス、ならびに/またはIndustrial Standard Architecture(ISA)、マイクロチャネルアーキテクチャ(MSA)、Extended ISA(EISA)、Intelligent Drive Electronics(IDE)、VESA Local Bus(VLB)、Peripheral Component Interconnect(PCI)、Card Bus、Universal Serial Bus(USB)、Advanced Graphics Port(AGP)、Personal Computer Memory Card International Associationバス(PCMCIA)、Firewire(IEEE 1394)、およびSmall Computer Systems Interface(SCSI)を含むがこれらに限定はされない任意のさまざまな使用可能なバスアーキテクチャを使用するローカルバスを含む複数のタイプのバス構造のいずれかとすることができる。
【0085】
システムメモリ1416は、揮発性メモリ1420および不揮発性メモリ1422を含む。スタートアップ中など、コンピュータ1412内の要素の間で情報を転送する基本ルーチンを含む基本入出力システム(BIOS)が、不揮発性メモリ1422に格納される。限定ではなく例として、不揮発性メモリ1422は、読取専用メモリ(ROM)、プログラマブルROM(PROM)、電気的プログラマブルROM(EPROM)、電気的消去可能プログラマブルROM(EEPROM)、またはフラッシュメモリを含むことができる。揮発性メモリ1420は、ランダムアクセスメモリ(RAM)を含み、このRAMは外部キャッシュメモリとして働く。限定ではなく例として、RAMは、スタティックRAM(SRAM)、ダイナミックRAM(DRAM)、シンクロナスDRAM(SDRAM)、double data rate SDRAM(DDR SDRAM)、enhanced SDRAM(ESDRAM)、Synchlink DRAM(SLDRAM)、Rambus direct RAM(RDRAM)、direct Rambus dynamic RAM(DRDRAM)、およびRambus dynamic RAM(RDRAM)などの多数の形で入手可能である。
【0086】
コンピュータ1412は、リムーバブル/ノンリムーバブルの揮発性/不揮発性コンピュータ記憶媒体をも含む。図14に、たとえば、ディスクストレージ1424を示す。ディスクストレージ1424は、磁気ディスクドライブ、フロッピディスクドライブ、テープドライブ、Jazドライブ、Zipドライブ、LS−100ドライブ、フラッシュメモリカード、またはメモリスティックなどのデバイスを含むが、これらに限定はされない。さらに、ディスクストレージ1424に、コンパクトディスクROMデバイス(CD−ROM)、CD recordableドライブ(CD−Rドライブ)、CD rewritableドライブ(CD−RWドライブ)、またはディジタル多用途ディスクROMドライブ(DVD−ROM)などの光学ディスクドライブを含むがこれに限定されない記憶媒体を、他の記憶媒体と別々にまたはこれらと組み合わせて含めることができる。システムバス1418へのディスクストレージデバイス1424の接続を容易にするために、インターフェース1426などのリムーバブルまたはノンリムーバブルのインターフェースが、通常は使用される。
【0087】
図14に、ユーザと、適切なオペレーティング環境1400で説明した基本的なコンピュータリソースとの間の媒介として働くソフトウェアが記載されていることを了解されたい。そのようなソフトウェアに、オペレーティングシステム1428が含まれる。オペレーティングシステム1428は、ディスクストレージ1424に格納することができるが、コンピュータシステム1412を制御し、そのリソースを割り当てるように働く。システムアプリケーション1430は、プログラムモジュール1432を介するオペレーティングシステム1428によるリソースの管理およびシステムメモリ1416内またはディスクストレージ1424上のいずれかに格納されたプログラムデータ1434を利用する。請求される主題を、さまざまなオペレーティングシステムまたはオペレーティングシステムの組み合わせを用いて実施できることを了解されたい。
【0088】
ユーザは、入力デバイス1436を介してコンピュータ1412にコマンドまたは情報を入力する。入力デバイス1436は、マウスなどのポインティングデバイス、トラックボール、スタイラス、タッチパッド、キーボード、マイクロホン、ジョイスティック、ゲームパッド、衛星パラボラアンテナ、スキャナ、TVチューナカード、ディジタルカメラ、ディジタルビデオカメラ、ウェブカメラ、および類似物を含むが、これらに限定はされない。これらおよび他の入力デバイスは、インターフェースポート1438を介し、システムバス1418を介して処理ユニット1414に接続される。インターフェースポート1438は、たとえば、シリアルポート、パラレルポート、ゲームポート、およびuniversal serial bus(USB)を含む。出力デバイス1440は、入力デバイス1436と同一タイプのポートのいくつかを使用する。したがって、たとえば、USBポートを使用して、コンピュータ1412に入力を提供し、コンピュータ1412から出力デバイス1440に情報を出力することができる。出力アダプタ1442が、モニタ、スピーカ、およびプリンタなど、他の出力デバイス1440の中でも特殊なアダプタを必要とするいくつかの出力デバイス1440があることを示すために提供される。出力アダプタ1442は、限定ではなく例として、出力デバイス1440とシステムバス1418との間の接続の手段を提供する、ビデオカードおよびサウンドカードを含む。リモートコンピュータ1444など、他のデバイスおよび/またはデバイスのシステムが、入力機能と出力機能との両方を提供することに留意されたい。
【0089】
コンピュータ1412は、リモートコンピュータ1444などの1つまたは複数のリモートコンピュータへの論理接続を使用して、ネットワーク化された環境で動作することができる。リモートコンピュータ1444は、パーソナルコンピュータ、サーバ、ルータ、ネットワークPC、ワークステーション、マイクロプロセッサベースの機器、ピアデバイス、または他の一般的なネットワークノードおよび類似物とすることができ、リモートコンピュータ1444は、通常は、コンピュータ1412に関して説明した要素の多数またはすべてを含む。図を簡単にするために、メモリストレージデバイス1446だけが、リモートコンピュータ1444と共に図示されている。リモートコンピュータ1444は、論理的にネットワークインターフェース1448を介してコンピュータ1412に接続され、次に、物理的に通信接続1450を介して接続される。ネットワークインターフェース1448は、ローカルエリアネットワーク(LAN)および広域ネットワーク(WAN)などの有線および/または無線の通信ネットワークを含む。LANテクノロジは、Fiber Distributed Data Interface(FDDI)、Copper Distributed Data Interface(CDDI)、イーサネット(登録商標)、トークンリング、および類似物を含む。WANテクノロジは、ポイントツーポイントリンク、サービス総合ディジタル網(ISDN)およびその変形形態などの回路交換網、パケット交換網、およびディジタル加入者回線(DSL)を含むが、これに限定はされない。
【0090】
通信接続1450は、ネットワークインターフェース1448をバス1418に接続するのに使用されるハードウェア/ソフトウェアを指す。通信接続1450は、図を明瞭にするためにコンピュータ1412の内部に図示されているが、コンピュータ1412の外部とすることもできる。ネットワークインターフェース1448への接続に必要なハードウェア/ソフトウェアは、例示のみとして、通常の電話等級モデム、ケーブルモデム、およびDSLモデムを含むモデム、ISDNアダプタ、ならびにイーサネット(登録商標)カードなどの、内蔵テクノロジおよび外付けテクノロジを含む。
【0091】
上で説明したものは、本革新の例を含む。もちろん、請求される主題の説明においてコンポーネントまたは方法論のすべての考えられる組合せを説明することは不可能であるが、当業者は、本革新の多数のさらなる組合せおよび置換が可能であることを認めるであろう。したがって、請求される主題は、添付の特許請求の範囲の趣旨および範囲に含まれるすべてのそのような代替形態、修正形態、および変形形態を含むことが意図されている。
【0092】
具体的には、上で説明したコンポーネント、デバイス、回路、システム、および類似物によって実行されるさまざまな機能に関して、そのようなコンポーネントを記述するのに使用される用語(「手段(means)」への言及を含む)は、そうではないと示されていない限り、開示された構造と構造的に同等ではないものであっても、請求される主題の本明細書で示された例示的諸態様の機能を実行する、説明されたコンポーネントの指定された機能を実行するすべてのコンポーネント(たとえば、機能的同等物)に対応することが意図されている。これに関して、本革新が、請求される主題のさまざまな方法の行為および/またはイベントを実行するコンピュータ実行可能命令を有するシステムならびにコンピュータ可読媒体を含むことも、認められるであろう。
【0093】
さらに、本革新の特定の特徴を、複数の実施態様のうちの1つだけに関して開示した場合があるが、そのような特徴は、任意の所与のまたは特定の応用例について望まれ、有利である可能性があるので、他の実施態様の1つまたは複数の他の特徴と組み合わせることができる。さらに、用語「含む」、「備える」(“includes”、“including”」、およびその変形が、詳細な説明または特許請求の範囲のいずれかで使用される範囲で、これらの用語は、用語「含む」、「備える」(“comprising”」に類似する形で包含的であることを意図されている。
【図面の簡単な説明】
【0094】
【図1】機能強化された概略目的地地図の自動生成を容易にする例示的システムを示すブロック図である。
【図2】目的地に少なくとも部分的に基づく少なくとも2つの経路を有する機能強化された概略目的地地図の自動生成を容易にする例示的システムを示すブロック図である。
【図3】目的地の機能強化された概略目的地地図の作成を容易にする例示的システムを示すブロック図である。
【図4】請求される主題の一態様に従う地理データの選択に関連する諸フェーズを示す図である。
【図5】本革新の一態様によるレイアウト摂動の生成を示す図である。
【図6】目的地に少なくとも部分的に基づく少なくとも2つの経路を有する機能強化された概略目的地地図の自動生成を容易にする例示的システムを示すブロック図である。
【図7】請求される主題による自動生成された機能強化された概略目的地地図に関連するラベルレイアウトを示す図である。
【図8】機能強化された概略目的地地図の自動生成を容易にする例示的システムを示すブロック図である。
【図9】目的地の機能強化された概略目的地地図の生成を容易にする例示的方法論を示す図である。
【図10】目的地に少なくとも部分的に基づく少なくとも2つの経路を有する機能強化された概略目的地地図を自動的に生成する例示的方法論を示す図である。
【図11】本革新による目的地に関する例示的地理データを示す図である。
【図12】目的地に関する自動的に生成された機能強化された概略目的地地図を示す図である。
【図13】請求される主題の新規の諸態様を使用できる例示的ネットワーキング環境を示す図である。
【図14】請求される主題に従って使用できる例示的オペレーティング環境を示す図である。
【特許請求の範囲】
【請求項1】
地理に関連する目的地への道順の提供を容易にするシステムであって、
少なくとも1つの地理的目的地を受け取るインターフェースコンポーネントと、
前記地理的目的地への少なくとも1つの道路を含む少なくとも1つの経路を提供するために、道路セットの階層を利用して、機能強化された概略目的地地図を自動的に作成する地図ジェネレータと
を含むことを特徴とするシステム。
【請求項2】
前記地理的目的地は、ユーザ入力であることを特徴とする請求項1に記載のシステム。
【請求項3】
前記地理的目的地は、地図上の位置、住所、街路、交差点、店、市、州、郡、国、および建物のうちの少なくとも1つであることを特徴とする請求項1に記載のシステム。
【請求項4】
前記地理的目的地を囲む地域に関連する地理データを選択的にフィルタリングするために、道路セットの前記階層を実施するデータ選択コンポーネントをさらに含むことを特徴とする請求項1に記載のシステム。
【請求項5】
前記地理的目的地に関する前記地理データを階層的にフィルタリングする道路階層コンポーネントをさらに含むことを特徴とする請求項4に記載のシステム。
【請求項6】
道路セットの前記階層は、大サイズ道路セット、前記大サイズ道路セットによって囲まれた地域内の中サイズ道路セット、および前記中サイズ道路セットによって囲まれた地域内の地方サイズ(local−sized)道路セットを含むことを特徴とする請求項5に記載のシステム。
【請求項7】
前記大サイズ道路セットは、州間ハイウェイを含むことを特徴とする請求項6に記載のシステム。
【請求項8】
前記中サイズ道路セットは、幹線道路、州道、および主要道を含むことを特徴とする請求項6に記載のシステム。
【請求項9】
前記地方サイズ道路セットは、一般道路を含むことを特徴とする請求項6に記載のシステム。
【請求項10】
選択的にフィルタリングされた前記地理データからの道路を使用することと、追加経路を作成するために前記地理データからの前記道路を補足することとによって、前記地理的目的地への経路の指定を容易にする経路コンポーネントをさらに含むことを特徴とする請求項4に記載のシステム。
【請求項11】
少なくとも1つの道路の一部に関連するジオメトリを単純化する形状コンポーネントをさらに含むことを特徴とする請求項1に記載のシステム。
【請求項12】
確率的探索を利用して前記地理的目的地に関する道路レイアウトの作成を容易にする道路レイアウトコンポーネントをさらに含むことを特徴とする請求項1に記載のシステム。
【請求項13】
交差点のセット、交差点に関する順序、道路の間の旋回方向、旋回角、道路通過のゾーン、道路の長さの順序、2つに分かれる道路の別々の方向、道路の間の横並び関係、道路の上下関係、および道路方位のうちの少なくとも1つを維持することによって、明瞭さを最大にするために前記機能強化された概略目的地地図をレンダリングする変形コンポーネントをさらに含むことを特徴とする請求項1に記載のシステム。
【請求項14】
関節点ベースのスケーリングを利用してレイアウト摂動を生成する摂動コンポーネントをさらに含むことを特徴とする請求項13に記載のシステム。
【請求項15】
スコアランクを提供するために前記レイアウト摂動を評価するスコアリングコンポーネントをさらに含むことを特徴とする請求項14に記載のシステム。
【請求項16】
道路ラベル、プロンプト道路ラベル、吹き出し、およびランドマークのうちの少なくとも1つを前記機能強化された概略目的地地図に投入するラベルコンポーネントをさらに含むことを特徴とする請求項1に記載のシステム。
【請求項17】
前記ラベルコンポーネントは、ラベル−ラベル衝突の回避、ラベル−道路衝突の回避、および第1のラベルと第2のラベルとの間の距離の最大化のうちの少なくとも1つを実施することを特徴とする請求項16に記載のシステム。
【請求項18】
地図の作成を容易にする、機械により実施される方法であって、
目的地を受け取るステップと、
前記目的地および道路階層に基づいて地理データを選択的にフィルタリングするステップと、
概略目的地地図を自動的に作るステップと
を含むことを特徴とする方法。
【請求項19】
ソフト制約に基づいて変形を適用するステップと、
前記概略目的地地図にラベルを投入するステップと
をさらに含むことを特徴とする請求項18に記載の方法。
【請求項20】
地理に関連する目的地への道順の提供を容易にする、機械により実施されるシステムであって、
少なくとも1つの地理的目的地を受け取る手段と、
前記地理的目的地への少なくとも1つの道路を含む少なくとも1つの経路を提供するために、道路セットの階層を利用して、機能強化された概略目的地地図を自動的に作成する手段と
を含むことを特徴とするシステム。
【請求項1】
地理に関連する目的地への道順の提供を容易にするシステムであって、
少なくとも1つの地理的目的地を受け取るインターフェースコンポーネントと、
前記地理的目的地への少なくとも1つの道路を含む少なくとも1つの経路を提供するために、道路セットの階層を利用して、機能強化された概略目的地地図を自動的に作成する地図ジェネレータと
を含むことを特徴とするシステム。
【請求項2】
前記地理的目的地は、ユーザ入力であることを特徴とする請求項1に記載のシステム。
【請求項3】
前記地理的目的地は、地図上の位置、住所、街路、交差点、店、市、州、郡、国、および建物のうちの少なくとも1つであることを特徴とする請求項1に記載のシステム。
【請求項4】
前記地理的目的地を囲む地域に関連する地理データを選択的にフィルタリングするために、道路セットの前記階層を実施するデータ選択コンポーネントをさらに含むことを特徴とする請求項1に記載のシステム。
【請求項5】
前記地理的目的地に関する前記地理データを階層的にフィルタリングする道路階層コンポーネントをさらに含むことを特徴とする請求項4に記載のシステム。
【請求項6】
道路セットの前記階層は、大サイズ道路セット、前記大サイズ道路セットによって囲まれた地域内の中サイズ道路セット、および前記中サイズ道路セットによって囲まれた地域内の地方サイズ(local−sized)道路セットを含むことを特徴とする請求項5に記載のシステム。
【請求項7】
前記大サイズ道路セットは、州間ハイウェイを含むことを特徴とする請求項6に記載のシステム。
【請求項8】
前記中サイズ道路セットは、幹線道路、州道、および主要道を含むことを特徴とする請求項6に記載のシステム。
【請求項9】
前記地方サイズ道路セットは、一般道路を含むことを特徴とする請求項6に記載のシステム。
【請求項10】
選択的にフィルタリングされた前記地理データからの道路を使用することと、追加経路を作成するために前記地理データからの前記道路を補足することとによって、前記地理的目的地への経路の指定を容易にする経路コンポーネントをさらに含むことを特徴とする請求項4に記載のシステム。
【請求項11】
少なくとも1つの道路の一部に関連するジオメトリを単純化する形状コンポーネントをさらに含むことを特徴とする請求項1に記載のシステム。
【請求項12】
確率的探索を利用して前記地理的目的地に関する道路レイアウトの作成を容易にする道路レイアウトコンポーネントをさらに含むことを特徴とする請求項1に記載のシステム。
【請求項13】
交差点のセット、交差点に関する順序、道路の間の旋回方向、旋回角、道路通過のゾーン、道路の長さの順序、2つに分かれる道路の別々の方向、道路の間の横並び関係、道路の上下関係、および道路方位のうちの少なくとも1つを維持することによって、明瞭さを最大にするために前記機能強化された概略目的地地図をレンダリングする変形コンポーネントをさらに含むことを特徴とする請求項1に記載のシステム。
【請求項14】
関節点ベースのスケーリングを利用してレイアウト摂動を生成する摂動コンポーネントをさらに含むことを特徴とする請求項13に記載のシステム。
【請求項15】
スコアランクを提供するために前記レイアウト摂動を評価するスコアリングコンポーネントをさらに含むことを特徴とする請求項14に記載のシステム。
【請求項16】
道路ラベル、プロンプト道路ラベル、吹き出し、およびランドマークのうちの少なくとも1つを前記機能強化された概略目的地地図に投入するラベルコンポーネントをさらに含むことを特徴とする請求項1に記載のシステム。
【請求項17】
前記ラベルコンポーネントは、ラベル−ラベル衝突の回避、ラベル−道路衝突の回避、および第1のラベルと第2のラベルとの間の距離の最大化のうちの少なくとも1つを実施することを特徴とする請求項16に記載のシステム。
【請求項18】
地図の作成を容易にする、機械により実施される方法であって、
目的地を受け取るステップと、
前記目的地および道路階層に基づいて地理データを選択的にフィルタリングするステップと、
概略目的地地図を自動的に作るステップと
を含むことを特徴とする方法。
【請求項19】
ソフト制約に基づいて変形を適用するステップと、
前記概略目的地地図にラベルを投入するステップと
をさらに含むことを特徴とする請求項18に記載の方法。
【請求項20】
地理に関連する目的地への道順の提供を容易にする、機械により実施されるシステムであって、
少なくとも1つの地理的目的地を受け取る手段と、
前記地理的目的地への少なくとも1つの道路を含む少なくとも1つの経路を提供するために、道路セットの階層を利用して、機能強化された概略目的地地図を自動的に作成する手段と
を含むことを特徴とするシステム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【公表番号】特表2009−516202(P2009−516202A)
【公表日】平成21年4月16日(2009.4.16)
【国際特許分類】
【出願番号】特願2008−541399(P2008−541399)
【出願日】平成18年11月16日(2006.11.16)
【国際出願番号】PCT/US2006/044858
【国際公開番号】WO2007/059339
【国際公開日】平成19年5月24日(2007.5.24)
【出願人】(500046438)マイクロソフト コーポレーション (3,165)
【Fターム(参考)】
【公表日】平成21年4月16日(2009.4.16)
【国際特許分類】
【出願日】平成18年11月16日(2006.11.16)
【国際出願番号】PCT/US2006/044858
【国際公開番号】WO2007/059339
【国際公開日】平成19年5月24日(2007.5.24)
【出願人】(500046438)マイクロソフト コーポレーション (3,165)
【Fターム(参考)】
[ Back to top ]