JP3386816B2 - 車両用の道路ネットワーク表示の複合ジャンクション及びリンクに要素を結合するシステム。 - Google Patents
車両用の道路ネットワーク表示の複合ジャンクション及びリンクに要素を結合するシステム。Info
- Publication number
- JP3386816B2 JP3386816B2 JP50283897A JP50283897A JP3386816B2 JP 3386816 B2 JP3386816 B2 JP 3386816B2 JP 50283897 A JP50283897 A JP 50283897A JP 50283897 A JP50283897 A JP 50283897A JP 3386816 B2 JP3386816 B2 JP 3386816B2
- Authority
- JP
- Japan
- Prior art keywords
- road
- junctions
- links
- junction
- basic
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 239000002131 composite material Substances 0.000 claims description 35
- 238000000034 method Methods 0.000 claims description 24
- 238000012545 processing Methods 0.000 claims description 8
- 238000013507 mapping Methods 0.000 claims description 6
- 230000000007 visual effect Effects 0.000 claims description 3
- 238000013500 data storage Methods 0.000 claims 4
- 230000008878 coupling Effects 0.000 claims 3
- 238000010168 coupling process Methods 0.000 claims 3
- 238000005859 coupling reaction Methods 0.000 claims 3
- 230000003213 activating effect Effects 0.000 claims 2
- 238000010200 validation analysis Methods 0.000 claims 1
- 150000001875 compounds Chemical class 0.000 description 20
- 230000008569 process Effects 0.000 description 5
- 230000002457 bidirectional effect Effects 0.000 description 4
- 230000008520 organization Effects 0.000 description 4
- 238000010586 diagram Methods 0.000 description 3
- 230000015572 biosynthetic process Effects 0.000 description 2
- 238000012937 correction Methods 0.000 description 2
- 238000000605 extraction Methods 0.000 description 2
- VKYKSIONXSXAKP-UHFFFAOYSA-N hexamethylenetetramine Chemical compound C1N(C2)CN3CN1CN2C3 VKYKSIONXSXAKP-UHFFFAOYSA-N 0.000 description 2
- 238000002372 labelling Methods 0.000 description 2
- 230000004913 activation Effects 0.000 description 1
- 238000013459 approach Methods 0.000 description 1
- 230000004888 barrier function Effects 0.000 description 1
- 230000005540 biological transmission Effects 0.000 description 1
- 230000010267 cellular communication Effects 0.000 description 1
- 230000008859 change Effects 0.000 description 1
- 238000012790 confirmation Methods 0.000 description 1
- 230000001419 dependent effect Effects 0.000 description 1
- 230000005484 gravity Effects 0.000 description 1
- 238000009940 knitting Methods 0.000 description 1
- 230000014759 maintenance of location Effects 0.000 description 1
- 230000003287 optical effect Effects 0.000 description 1
- 230000000717 retained effect Effects 0.000 description 1
- 238000012552 review Methods 0.000 description 1
- 239000004065 semiconductor Substances 0.000 description 1
- 238000000926 separation method Methods 0.000 description 1
- 239000000758 substrate Substances 0.000 description 1
- 238000012546 transfer Methods 0.000 description 1
Classifications
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/38—Electronic maps specially adapted for navigation; Updating thereof
- G01C21/3863—Structures of map data
- G01C21/387—Organisation of map data, e.g. version management or database structures
- G01C21/3878—Hierarchical structures, e.g. layering
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Databases & Information Systems (AREA)
- Automation & Control Theory (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Traffic Control Systems (AREA)
- Instructional Devices (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Description
表示を特徴づける、比較的低いレベルから複数の階層的
に組織されたレベルの地理的な道路データを格納し、比
較的範囲の広いレベルでこのような詳細な表示から抽出
された表示を得る地理的道路データ格納方法に関するも
のである。米国特許出願明細書第4,914,605号は、道路
マップの表示を記載している。このような道路マップの
種々の道路はレベル識別子を有し、高速道路はハイレベ
ルの識別子を有し、主要道路は中間レベルの識別子を有
し、二次的道路はローレベルの識別子を有する。原理的
にはレベルの数は任意である。視覚的に表示するため
に、表示スケールは可変である。大きい拡大率では、小
さい地理的な区域のみが表示され、全ての道路がそこに
示される。中間の拡大率では、比較的大きな地理的な区
域が表示され、二つのハイレベルの道路のみがそこに示
される。小さい拡大率では、比較的大きな地理的な区域
が表示され、トップレベルの道路のみがそこに示され
る。
ままで、道路だけでなく道路間の複雑な交差パターンも
簡単に表示する必要があることを痛感した。このような
表示は、必ずしも視覚的な表示を意味する必要がない
が、データベースの表現が制限されるおそれがある。抽
出したレベルでは、システムは、適切な数のリンクを有
する明確なレベルの交差として、複雑なインターチェン
ジ、交差、高架交差道又は同様な構造を、種々の要素の
正確な幾何学的表現に対して幾分正確さを犠牲にして表
示する。詳細な決定を要求する者に対して、システム
は、詳細なレベルに対する正確な基準を保持したままで
ある。例えば、抽出動作を行うと単一点に対して特定の
ループが縮み、これは、中間経路がループを通過すると
きに二つの地理的な位置の間の目に見える距離に影響を
及ぼす。実際には、正確な表示の距離を計算すると、抽
出した表示をその面で取り出すときに比べてしばしば値
が大きくなる。ある使用に対しては、長距離のルート設
定するように不一致がはなはだしい。もっとも近い交差
が何であるかを運転者に詳しく指示し及び車両の実際の
位置を決定するような他の用途に対して、地理的なデー
タを正確に表示するだけで十分である。第1に、本発明
は、高速道路にたいしても低い分類のレベルの道路に対
しても適用できることがわかる。
ルの表示をより領域の広いものに変換する安全装置の方
法を提供することである。したがって、態様のうちの一
つによれば、本発明は、a.このような低いレベルで、基
本ジャンクションのセットの間の予め設定された一致に
基づいて、前記基本ジャンクションのセットを複合ジャ
ンクションに結合するステップと、 b.全ての複合ジャンクションを見つけるまで前記ステッ
プaを繰り返すステップと、 c.基本外部道路リンク上の全ての許容された交通方向を
含む、特定のセットの境界要素及び全ての基本外部リン
クを、これら境界要素とある特定の他のセットの任意の
要素との間で確証し、前記外部道路リンク上の許容され
た交通方向をマップする間単一の複合外部道路リンクに
よって前記基本外部道路リンクを選択的に置換するステ
ップと、 d.このような対のセット間の全ての複合外部道路リンク
を見つけるまで前記ステップcを繰り返すステップと、 e.単一モードの各々によって残りの基本ジャンクション
の各々及び各複合ジャンクションを表し、かつ、オリジ
ナルに関連した又は交通方向をマップした単一の高レベ
ルの道路リンクにより、残りの基本外部道路リンクの各
々及び各複合外部道路リンクを表すステップとを具える
ことを特徴とするものである。
複合ジャンクションに集められ、同時に二つの基本ジャ
ンクション又は複合ジャンクションを結合する道路リン
クを結合することができ、したがって、要求される記憶
容量を非常に減少させる。格納されるデータを減少する
ことによりアクセスがより迅速になる、これも好適なも
のとなる。既に説明したように、基本ジャンクション
は、基本リンク間の相互接続点となる。これら基本リン
クは、記憶編成の背景として表示される。
証は、第1のハイレベル道路リンク上の許容された入力
交通方向を第2のハイレベル道路リンク上の許容された
出力交通方向に接続する許容しうる交通経路に対する基
本ジャンクションの関連のセットの検索を具え、許容さ
れない場合には、関連の複合ジャンクションの関連のハ
イレベル道路リンク対に対する禁止クオリファイヤーを
保持する。入口ジャンクションを以後規定する。広義に
は、それは、複合ジャンクションに近づくときの道路の
最初の分岐点を表す。逆に、出口ジャンクションは、複
合ジャンクションを去る時の最後の収束点を表す。入口
ジャンクションは、続くジャンクション(場合によって
は出口ジャンクション)に進む。出口ジャンクション
は、先行するジャンクション(場合によっては入口ジャ
ンクション)に続く。
憶するデータ処理システム、本発明の方法によって生じ
た格納データ構造を具える記憶媒体、このような媒体に
インタフェースする読出し装置、及びこのようなリーダ
を設けた車両に関するものである。本発明の他の種々の
好適態様を従属項に引用する。道路ネットワークの複数
レベル表示の記載を含む本発明者の先行技術は、1994年
のCarla Emmerink and Hans Schulute,Route Planning
and Route Guidance in the Philips In−Car Navigati
on System“CARIN",Proc.of the lst world congress o
n applications of transport telematics and intelli
gent vehicle highway systems(Paris,FR,ERTICO Brus
sels publ.)のVolume 1の240〜248頁に記載されてい
る。
実施の形態の開示、より詳しくは添付図面を参照して詳
細に説明する。
示す。
両を示す。
N,a car information and navigation system,Philips
Technical Review,Vol 43,No.11/12の317〜329頁に記載
されたように、CARINシステムは、コンパクトディスク
に格納されたデジタルマップを用いて運転者に目的地を
案内する自律カーナビゲーションシステムを含む。ルー
ト設定動作により、実際の車両位置から目的にまでの最
適ルートを迅速に見つけることができる。システムの動
作速度は、検査する必要がある道路の数及びコンパクト
ディスクから半導体基板のメモリへの検索速度によって
制限される。解決として、全てが同一地理区域をカバー
するが相違する量の細部を有する複数のバージョンでマ
ップが格納されている。これらバージョンは、特定の道
路の機能的な重要性によって決定された道路分類に基づ
くものである。したがって、各ネットワークは、次に低
い階層ネットワークのサブセットからなり、その間その
残りを抑制する。最低レベルネットワークは、高度の幾
何学的な正確さを有する全ての道路を具える。最高レベ
ルネットワークは、同程度の正確さを有する最重要道路
のみを具え、その正確さは、ルート設定者の動作以外の
他の種々の動作によって要求される。したがって、広域
ネットワークを、より詳しいものから自動的に発生させ
る。ある態様の広域ネットワークは、特に、複雑なジャ
ンクションを発生させることにより正確でなくなるおそ
れがある。これは、複雑な複数モードジャンクションか
ら単一モードに減少させることによって行われる。ま
た、これらノードを接合するとともに互いに逆の交通方
向を許容する二つのレーンからなる道路を、双方向交通
を許容する単一リンクに置き換える。このようにして、
コンパクトディスクに格納するのに必要なデータを少な
くすることができるとともに、特定タスクで検索すべき
リンクの数をより少なくする。
が続く。先ず、通りの名前、ジャンクションのタイプ、
物理形態及び交通の専属的な特性のようなデジタルマッ
プの地理的な特性の助けにより、複雑なジャンクション
を規定する。一般に、このような特性は、複雑なジャン
クションの基本ジャンクション間のある一致の形態を表
す。複雑なジャンクションを単一モードによって置き換
える。次いで、特定の複雑なジャンクションを他の特定
の複雑なジャンクションに接続する道路を見つける。一
つの道路のみの場合、外部の道路リンクはその一致を保
持する。二つ以上の道路の場合、これらを単一の複雑な
外部道路によって選択的に置き換える。交通の流れが互
いに逆方向の二つのレーンを有するような、互いにいず
れかの方向の交通を元の道路が許容する場合、複雑なリ
ンクが双方向の交通に対して開く。ジャンクションにお
いてある外部の接続道路から他の外部接続道路に折り返
すことができない場合、置換する複雑なジャンクション
に折り返しの制限を加える。元のリンクの平均長に複合
ジャンクションを表すノードの寸法を加えることにより
新たなリンクの長さを規定する。最後に、進行する又は
当業複雑なジャンクションから去るリンクのノードでの
他のネットワークへの接続を規定する。
が存在したままである。その理由は、一般に重要な道路
のみによって複雑なジャンクションが生じたからであ
る。これら道路は、最低レベルの道路の総数の一部のみ
を表す。ここで、最低レベルネットワークがルート設計
者のみでなく高い正確さを必要とする車両の他の動作に
よって用いられる場合、ネットワークの広域レベルと局
所レベルの両方が保持される。
ゆる「クローバ型(clover−leaf)」の詳細な表示及び
抽出した表示の第1例である。先ず、図1Aの詳細な表示
を考察する。実際の交差点から離れる、各方向に対する
二つの道路は、インターチェンジを許容するレーンから
なり、これを単一ラインで表示する。点で表した所定の
点(入口ジャンクション)からのように実際の交差点に
近づく際に、運転者は、中央レーンと横側のレーンとの
間で選択する必要があり、各区分を分離ラインで示す。
横側のレーンではわき道に入ることができるが、中央レ
ーンではできない。実際の交差点の重心に最も近づく
と、運転者は先ず、右側のわき道(2番目の点)にそれ
るか左側のわき道(4番目の点)にそれるかを選択する
ことができる。これら二つの各々は、交通を合流させる
ための対応したもの(わき道にそれない場合の5番目及
び3番目の点をそれぞれ表す。)を有する。最後に、横
側のレーンは中央レーンに再び合流する(出口ジャンク
ションを表す6番目の点)。
な交差を単一点で表す。交差点は、図示した四つの道路
を単一ラインとして終了させる。道路の各々は、クオリ
ファイヤー‘bidirectioanl'を有する。交差は、幹線道
路に通じる2次的道路から他の三つの道路のうちの一つ
を介して去ることができる複雑なクオリファイヤーを有
する。他の簡単化として、二つの道路の交差角を一般的
に、この場合90度の交差として表す。他の実現におい
て、この角を実際に応じて相違させることができる。交
差間の複雑なリンクを、一つの直線又は一つより多い直
線のシーケンスとして表すことができる。
2例である。実際には、この道路パターンにより、図1A
と全く同一の選択をすることができる。これは、図2Bの
抽出された表示が図1Bのものと同一であることを意味す
る。しかしながら、選択のシーケンスが相違し、その結
果、運転者に対する詳細な表示は図1Aのものと相違す
る。
な及び抽出した表示の第3例である。簡単のために、種
々の多重レベル交差を、基本的にのみ図示した。通り一
遍にみると、「運転者の洞察に反して」しばしば命令が
行われているのは明らかである。これは、このような複
雑な形態間のあり得る寸法的な変動が比較的大きい間は
真実であり、その結果、運転者の心の標準的な「イメー
ジ」がそれらを保持しない。図3Bの抽象的な表示は、規
格化された交差角度で三つの直線道路が交差したように
見える。この場合も、全ての道路及び交差点それ自体
は、図示しないクオリファイヤーを有する。
は、米国特許出願明細書第4,954,986号に対応する欧州
特許出願公開明細書第302547号、米国特許出願明細書第
4,962,458号に対応する欧州特許出願公開明細書第47936
4号、及び米国特許出願07/769,613号に対応する欧州特
許出願公開明細書第479364号を参照すればよく、これら
は本明細書として全て同一の譲受人により譲り受けら
れ、参照することによりここに組み込まれたものとな
る。データ構造の中枢要素を、二つのジャンクションす
なわちノードを相互接続する(チェーンとも称される)
リンクとする。二つのノードの各々に対して、リンク
は、当該ノードで終了した次に続くリンクを系統的に指
示するスレッドポインタを有する。リンクのシーケンス
は一様に右回りである。シーケンスがいわゆるバケット
の境界を通過する場合、代わりにダミースレッドポイン
タが存在する。バケットを、任意のサイズの地理的区域
をカバーすることができる標準サイズのデータとする。
バケット間を適切に参照することにより、データ構造の
検索中迅速な移転を行うことができる。ノード、リンク
及びスリッドポインタを正確に規定するためには、上記
引例を参照する必要がある。リンク又はチェーンはさら
に、高速道路や2次的道路のような種類、許容される交
通の方向及びその長さの情報を含む。他の追加のデータ
項目も実現可能である。
を、二重リンクチェーンに組み合わせたものとして示
す。バケット22に対してのみ詳細に示す。先ず、バケッ
トは編成部32を有し、それは、当該バケットの識別子を
含み、当該レベルの物理的に隣接するバケットに属し、
かつ、チェーンの論理的に隣接するバケット20,24も属
する。物理的に隣接するバケットに番号を付すものとす
る。バケットの地理的なサイズは任意の単一レベルで一
様でなく、種々のレベル間でも一様でない。バケットの
形成を従来のように考察する。したがって、バケットア
イテム28は、前方の先祖バケットに属し、先祖バケット
の照会ターゲットであるアイテム26と対をなし、アイテ
ム30は、後方の相続バケットに属し、相続バケットの照
会ターゲットであるアイテム31と対をなす。編成部は、
リンク構造42〜45及びノード構造38〜41に対する照会部
を有する。図示したように、後者の二つのデータ構造
も、二重リンクチェーンによって構成する。各ブロック
42〜45は一つのリンクを表し、各ブロック38〜41は一つ
のノードを表す。
又はリンクは、スレッドポインタにより、最大でも他の
チェーンに対する終了ノードの各々に属する。これら参
照の選択を、リンクデータ構造の右端に示す。さらに、
各リンクは、ノードデータ構造38〜41に格納される終了
ノードに属する。これら参照の選択を、リンクデータ構
造からノードデータ構造への矢印で表す。最後に、各ノ
ードは、当該ノードで終了する単一チェーンに属し、そ
のチェーンを、系統的に選択する。これら参照の選択
を、ノードデータ構造からチェーンデータ構造への矢印
によって表す。この編成により、最小の格納の要求と最
大の検索速度との間の好適な折衷案を可能にする。参照
を一例で示しただけである。
様を示す。表1は、バケット識別子、隣接するバケット
の参照、ノードリストの参照及びチェーンリストの参照
を含むバケットリストのバケットのデータベースエント
リを与える。表2は、ノード識別子、地理的な座標、隣
接するチェーンリストの参照、隣接するノードの参照を
含むノードリストのノードのデータベースエントリを与
える。表3は、有効標識、チェーン識別子、終了ノード
の参照、二つのスレッドポインタの参照、チェーンの長
さ、(複雑な)ジャンクションの参照、交通方向標識、
道路の種類の標識、道路標識の形態、通りの名前、折り
返し制限標識、及び隣接するチェーンの参照を含むチェ
ーンリストのチェーンのデータベースエントリを与え
る。
らジャンクションを、図6を参照した開示中で説明した
ように見つけることができ、各々を点で示し、各々に、
ジャンクションを相互接続する基本リンクを設ける。地
理的表示を一例として示したのみである。基本ジャンク
ションのうちの10個を、Aのラベルを付したセットに結
合する。その他の七つを、セットB及びCにそれぞれ結
合する。単一ジャンクションDを結合しない。セットA
及びBを、基本外部道路リンク100,102によって相互接
続し、このようにして、各々は当該セットの二つの境界
ジャンクションを相互接続する。抽出中、セットA,B及
びCをそれぞれ単一の複合ジャンクションによって表
す。このようにするに当たり、基本道路リンク100,102
を、ループ108で符号的に表したように、単一複合外部
道路リンク上にマップする。図示したように、二つのリ
ンク100,102は、互いに相違する交通方向を有する。こ
れは、結合の際に複合道路ジャンクションが双方向交通
表示を得ることができることを意味する。それに対し
て、基本ジャンクションのセットの他の対に相互接続す
る全ての基本道路は、同一の交通方向を有することがで
きる。これは、結合した複合道路ジャンクションが一方
向の交通表示を有することもできることを意味する。こ
の場合を図示しない。セットAとノードDとの間の道路
ジャンクションは、一方向の交通表示を保持する。この
例は、単一交通方向の基本リンクのみを有する。しかし
ながら、所定の場合には、所定の基本道路リンクは双方
向の交通方向を有することもできる。これは、複合外部
道路リンクの最終的なラベル付けに影響を及ぼす。さら
に複雑なことには、所定の基本道路リンクは、渋滞する
幹線のような特定の交通のカテゴリーに対してブロック
される。これは、三つ以上の値を有する交通方向標識と
解釈されるおそれがある。これも、複合外部道路リンク
のラベル付けに影響を及ぼすおそれがある。後者の状況
のいずれも図5において無視する。
を再発生させる必要がある。この最も簡単な状況では、
複合ジャンクションによってカバーされた区域のサイズ
を無視する。算出の際に好適であっても、これは、場合
によっては距離の過小評価が大いに行われることを意味
する。精緻な区別の次のレベルは以下の通りである。先
ず、複合ジャンクションの幅(106)及び高さ(104)
を、最も離れた基本ジャンクション間の水平距離及び垂
直距離としてそれぞれ見つける。上記表2のデータベー
スにより、それを簡単に算出することができる。これら
の平均値を、円形領域をカバーすると仮定される複合ジ
ャンクションの識別できる径としてとる。この値の半分
を、次に高いレベルの全ての単一又は複合道路ジャンク
ションの長さに加える。更に精緻に区別するために、基
本ジャンクションのセットが幾分長円形の領域をカバー
できることを考慮する。二つの複合ジャンクション間の
リンクに対して、当該リンクの両端に増大が生じる。
路が禁止される場合、基本ジャンクションのセット内に
このような基本リンク経路が存在しないという他の問題
が生じる。この場合、実現可能な経路が、第1の複合外
部道路リンクに結合すべき任意の基本入力道路リンクを
第2の複合外部道路リンクの任意の基本出力道路リンク
に相互接続しないよう(同様に、逆方向においても)
に、これを検出する。単一モードによって複合ジャンク
ションを表すに当たり、禁止クオリファイヤーを、関連
の複合ジャンクションの関連の高レベル道路リンク対に
対して保持する。例えば、セットBからノードDまで実
現可能な経路が存在しない。簡単なバージョンでは、こ
れを、複合道路リンク108上の「右折禁止」と解釈する
ことができる。このような状況は、外部リンク上の交通
方向が原理的に整合するときでさえ所定の状況で生じ
る。例えば、ノードDと外部道路リンク102との間に実
現可能な道路が存在しない場合、ノードDからの入来道
路リンクは、クオリファイヤー「左折禁止」を得る。
発明の方法のフローチャートである。ブロック60におい
て、システムは、ネットワークの低レベルの詳細な表示
から必要なデータをロードすることによって初期化され
る。ブロック62において、基本ジャンクションがロード
され、いわゆる入口ジャンクションとしてそれを検出す
る。対象は、二つの異なったものとなる。入口ジャンク
ションの第1タイプを、対象がノードに向かってくるの
を許容する一つのリンクを有するいわゆるスプリットと
し、それは、交通がノードから移動することができる少
なくとも二つの他のチェーンを有する。入口ジャンクシ
ョンの第2タイプを、各々が双方向交通を許容する少な
くとも三つのチェーンを接続する基本ジャンクションと
する。入口ジャンクションの第2のカテゴリーを、第1
のサブカテゴリーとして表すことができる。入口ジャン
クションの追加の状況としては、入ってくる交通を許容
する少なくとも一つのチェーンが、900〜1200mの範囲に
ような先行するジャンクションに対して測定した最小長
を有する。この値の設定は、道路ネットワークのキャラ
クターに依存する。非常に大きい場合、複合ジャンクシ
ョンの範囲を非常に広くすることにより、機能的なルー
トをマークし、又は複合ジャンクション全体を見えなく
することもできる。非常に小さい場合、結合が不完全な
ままであり、複合によって複数の複合サブジャンクショ
ンのみ減少させる。
うちの一つを「出口」としてマークする必要がある。そ
れだけで、「出口ジャンクション」を入口ジャンクショ
ンとは反対に規定する。ここで、第3の状況の第1の例
外は、高速道路が高速でない道路に接続するときであ
る。しかしながらこの状況は、当該リンクがこの特定の
カテゴリーで符号化されるときに正確に識別される。そ
の第2の例外は、基本スプリットが生じるときであり、
次の基本スプリットすなわちリンクの基本結合までのチ
ェーン長は、ネットワークのキャラクターに依存する18
00〜2300mの範囲とすることができる他の距離より短
い。この第2の例外により、複合ジャンクションを保持
するノードのセットにスプリットを含むことができる。
入口ジャンクションの識別を、全てのジャンクションが
考察されるまで続ける。ループは、全体に亘る方法での
み行われる。
た場合、それは複合ジャンクションを識別する開始点と
して用いられる。その任意のリンクがリストされるとと
もに格納され、以前に考察されなかったもののうちの一
つをアクセスする(64)。ここで、検索中にまだ考慮さ
れていない場合には、それの他の端末ノードを新たな開
始点としてとる。新たなノードが非入口ジャンクション
である場合、処理を繰り返す。しかしながら新たなノー
ドが入口ジャンクションである場合、それに続く経路の
データが格納され、最近格納されたノードを、上記処理
に関連させる(70)。入口ジャンクションの方向に更に
拡張することができない場合(64)、システムは図の下
半分に進む。
ることにより入口ジャンクションと同様に確定される。
その状況は、入口ジャンクションの状況を反映する。入
口ジャンクションの処理及びそれから得られる任意のジ
ャンクションは、入口ジャンクションとして見つけるこ
とができる他の未処理の基本ジャンクションが存在しな
くなるまで、既に説明したように進行する。
拡張を、リンクに沿った方向のみが相違する既に説明し
たものに相当する方法で実行し、新たな入口を見つけた
場合には停止する。他のあり得る出口ジャンクションが
図の上半分で見つけられない状態となるまでアクセスを
続ける。新たな入口ジャンクションを再び見つけること
ができる。これら新たな入口ノードは、図の上半分で第
1の入口ジャンクションに対して既に説明したようにし
て処理される。したがって処理は、入口ジャンクション
の検索と出口ジャンクションとの間で変わる。新たなジ
ャンクションが見つからない場合(80)、方法は終了す
る(82)。その後、この方法は、まだ考察されていない
新たな入口ジャンクションから開始することにより次の
当該複合ジャンクションに対する準備をする。全ての複
合ジャンクションを見つけるに当たり、全セットの全て
の基本ジャンクションを、これらジャンクションが最初
の入口ジャンクションであるか否かを見るために少なく
とも一度アクセスする必要がある。
界ノードであるか否かについて確証される。これは、当
該セットの外側又は基本ジャンクションの他のセットに
接続したノードである。先ず、セット中の二つ以上のノ
ードを他のセットのノードに接続した場合、中間リンク
上で許容された交通方向が確証され、中間外部道路リン
クが複合外部道路リンクに結合される。後者のリンク
は、二つのセット間で基本リンク上で許容された全ての
交通方向を得る。適切な場合には、同様な手順を、この
際結合された基本ジャンクションのセット間のリンク
と、複合ジャンクションにリンクされていない他の単一
基本ジャンクションで行う。
発明の方法のフローチャートである。種々のブロックに
以下のようにラベルを付す。
ない全てのジャンクションを一度アクセスする。
トが少なくとも一つのジャンクションを含むか否かを検
出する。62から来る場合、これはここで発見したものと
なる。
か又は出口ジャンクションであるかを検出する。62から
来る場合、これは、常にyesで答えられるダミーの問い
である。
ジャンクションに接続した他のジャンクションを格納す
る。
のバケットから来る。
対する検索として、同一形態(72,74,76,78)で非入口
ジャンクション又は先行ジャンクションに対して求めら
れる。72で否定の場合、80に進む。80で肯定の場合、70
に進む。通常、複合ジャンクションは、図6の上半分か
ら下半分まで一度だけ横切る。
クション又は図の下半分の新たな先行するジャンクショ
ンを検出する。否定である場合、複合ジャンクションの
全ての基本ジャンクションが見つけられ、プロセスが終
了する。
ロック70に戻る。当該単一のもの以外の複合ジャンクシ
ョンは図において考察されない。
クションクオリファイヤーに基づく処理に結合すること
ができる。例えば、このようなクオリファイヤーは、当
該基本リンクが迂回ジャンクションの一部であることを
表すことができる。これにより、迅速にアクセスすると
ともに容易に表示するために抽出して表示することがで
きる複合ジャンクションに対して簡単な方法でこのよう
な迂回ジャンクションを抽出するとこができる。さら
に、高レベルの複合ジャンクションに対してより近接し
た基本ジャンクションの迂回を結合することができる。
簡単な方法で、基本ジャンクションの一致を、相互に近
接させるだけで命令することができる。単一の複合ジャ
ンクションにより、更に大きな都市を表すをの回避する
ためにある対策が要求されるおそれがある。例えば、基
本ジャンクションのセットの全サイズは、基本ジャンク
ションの数又はセットを横切る距離で上側に境界を有す
ることができる。
ションシステムを有する車両を示す。この車両は、車体
120、前輪122、及び後輪124を有し、これら前輪122及び
後輪124は、モータ及びギヤボックス126の組み合わせに
よって駆動される。簡単のために、モータに対するユー
ザインタフェース及び車両の他の機械的な制御系を図示
しない。図示した車両は、その正確な位置を決定する種
々のシステムを有する。先ず、コンパス130が存在す
る。次に、車輪対の各々に個別の走行距離計を有するこ
とができる走行距離計の組み合わせ132が存在する。図
中、車輪を駆動する後方に対してこれを示したが、実際
には、非駆動輪を選択する。二つの走行距離計から信号
送信された平均移動をコンパスの読出しと組み合わせる
ことにより、走行した距離及び方向がわかる。二つの走
行距離計の読出し間の差を用いて折り返しを計算し、こ
れをコンパスと組み合わせることにより、走行した距離
に対する補正及び/又は修正を行うことができる。これ
ら及び他の計算をプロセッサ134で行うことができる。
必要な算術的な計算それ自体は通常のものとすることが
できる。
波形パターンを受信するディスクアンテナ150を有し、
プロセッサ148の波形パターンから実際の位置を計算す
る。システムを決定する第3の位置は、制限された伝送
範囲を有する道端のビーコンから位置コードを受信する
アンテナ154を有する。プロセッサ156でコードを認識す
ることによって実際の位置が確証される。
タベースを含む地理的データを有するランダムアクセス
光ディスクを含むCD−ROMプレーヤとする。このデータ
ベースを、複数の作動キーを含むユーザインタフェース
142からの選択的な制御の下でルート設定プロセッサ138
によって種々の目的に対してアクセスすることができ
る。開始位置及び目的地を入力すると、プレーヤ140か
ら適切なマップデータのアクセスを行う。それから、プ
ロセッサ138は最適ルート及び予期される到達時間を計
算する。プロセッサ158は、適切である間は、(センサ
によって決定される)プロセッサ134、(GSPによって決
定される)プロセッサ148及び(ビーコン信号による)
プロセッサ156によって生じた位置データを結合し、計
算されたような以前の実際の位置に関連するプレーヤ14
0からの地理的なデータにアクセスし、これらを実際の
マップ上にマップする。オフロード動作を無視すること
ができる場合、位置推測動作により、計算された以前の
位置を最もあり得る実際の道路位置上にマップする。実
際の位置及び実際の位置に隣接する設定されたルート
を、マップ形態で表示素子146上に表示することができ
る。実時間、予期される到達時間、矢印のような瞬時の
案内表示、目的地のような運転者に関連する他のデータ
も表示することができる。
るわけではない。例えば、高層ビルのような障壁がほと
んどなく、かつ、GSPの精度が良好である場合には、GSP
システムはそれ自体で十分となることができる。しかし
ながら、実際には、不正確なセンサから生じるドリフト
を回避するために、又は、他の方法による一時的な不都
合を補完するためにCD−ROMのサポートが必要である。
ルート設定を、本発明を実現することにより予め行うこ
とができる。
個別の内部変化を検出することができる。ナビゲーショ
ンの保持のような車両の状態の他の内部変化を、中央プ
ロセッサ158で検出することができる。このプロセッサ
を、送受信機144と、ルート設定プロセッサ38と、位置
決定プロセッサ134及び156とに接続する。このような他
の一例では、予め設定された距離がカバーされる。
システム用送受信機とする。素子128又は中央プロセッ
サ158によって検出された状態の内部変化を検出する
と、中央プロセッサは、送受信機144から実際の位置の
伝送を行う。この際、実際の位置は、フォーマット化さ
れ、アンテナ152を介して中央局200に送信される。既に
説明したような車両は、本譲受人によって譲り受けられ
た欧州特許出願公開明細書第959915293.5号(PHN14.84
3)に相当する米国特許出願明細書08/433,669号に詳細
に開示されている。
Claims (11)
- 【請求項1】道路のリンク及びジャンクションの詳細な
表示を特徴づける、比較的低いレベルから複数の階層的
に組織されたレベルの地理的な道路データを格納し、比
較的範囲の広いレベルでこのような詳細な表示から抽出
された表示を得る地理的道路データ格納方法において、 a.このような低いレベルで、基本ジャンクションのセッ
トの間の予め設定された一致に基づいて、前記基本ジャ
ンクションのセットを複合ジャンクションに結合するス
テップと、 b.全ての複合ジャンクションを見つけるまで前記ステッ
プaを繰り返すステップと、 c.基本外部道路リンク上の全ての許容された交通方向を
含む、特定のセットの境界要素及び全ての基本外部リン
クを、これら境界要素とある特定の他のセットの任意の
要素との間で確証し、前記外部道路リンク上の許容され
た交通方向をマップする間単一の複合外部道路リンクに
よって前記基本外部道路リンクを選択的に置換するステ
ップと、 d.このような対のセット間の全ての複合外部道路リンク
を見つけるまで前記ステップcを繰り返すステップと、 e.単一モードの各々によって残りの基本ジャンクション
の各々及び各複合ジャンクションを表し、かつ、オリジ
ナルに関連した又は交通方向をマップした単一の高レベ
ルの道路リンクにより、残りの基本外部道路リンクの各
々及び各複合外部道路リンクを表すステップとを具える
ことを特徴とする地理的道路データ格納方法。 - 【請求項2】前記単一の高レベルの道路リンクの各々を
直線によって表すことを特徴とする請求の範囲1記載の
地理的道路データ格納方法。 - 【請求項3】前記表示を視覚的表示装置上で行うことを
特徴とする請求の範囲1又は2記載の地理的道路データ
格納方法。 - 【請求項4】特定の複合ジャンクションに対する前記確
証は、第1のハイレベル道路リンク上の許容された入力
交通方向を第2のハイレベル道路リンク上の許容された
出力交通方向に接続する許容しうる交通経路に対する基
本ジャンクションの関連のセットの検索を具え、許容さ
れない場合には、関連の複合ジャンクションの関連のハ
イレベル道路リンク対に対する禁止クオリファイヤーを
保持することを特徴とする請求の範囲1,2又は3記載の
地理的道路データ格納方法。 - 【請求項5】ハイレベルの複合道路リンクの長さを、関
連の基本道路リンクの平均長にこれによって接続した一
方又は両方のセットの基本ジャンクションのサイズの値
を加えたものに設定することを特徴とする請求の範囲1
から4のうちのいずれかに記載の地理的道路データ格納
方法。 - 【請求項6】前記結合は、入口ジャンクションから続く
ジャンクション及び出口ジャンクションへの連続的なル
ープした拡張ステップ並びに全ての出口ジャンクション
から先行するジャンクション及び入口ジャンクションへ
の逆行を前記拡張の最終的な末端を検出するまで実行
し、これにより、前記拡張中に見つけた全てのジャンク
ションを、関連のセットに具えることを特徴とする請求
の範囲1から5のうちのいずれかに記載の地理的道路デ
ータ格納方法。 - 【請求項7】道路のリンク及びジャンクションの詳細な
表示を特徴づける、比較的低いレベルから複数の階層的
に組織されたレベルの地理的な道路データを処理し及び
格納し、比較的範囲の広いレベルでこのような詳細な表
示から抽出された表示を得る地理的道路データ処理及び
格納装置であって、この地理的道路データ処理及び格納
装置は、 a.このような低いレベルで、基本ジャンクションのセッ
トの間の予め設定された一致に基づいて、前記基本ジャ
ンクションのセットを複合ジャンクションに結合する結
合手段と、 b.全ての複合ジャンクションを見つけるまで前記項目a
の結合手段を周期的に作動させる第1シーケンス手段
と、 c.基本外部道路リンク上の全ての許容された交通方向を
含む、特定のセットの境界要素及び全ての基本外部リン
クを、これら境界要素とある特定の他のセットの任意の
要素との間で確証し、前記外部道路リンク上の許容され
た交通方向をマップする間単一の複合外部道路リンクに
よって前記基本外部道路リンクを選択的に置換する確証
手段と、 d.このような対のセット間の全ての複合外部道路リンク
を見つけるまで前記項目cの確証手段を周期的に作動さ
せる第2シーケンス手段と、 e.単一モードの各々によって残りの基本ジャンクション
の各々及び各複合ジャンクションを表し、かつ、オリジ
ナルに関連した又は交通方向をマップした単一の高レベ
ルの道路リンクにより、残りの基本外部道路リンクの各
々及び各複合外部道路リンクを表す表示手段とを具える
ことを特徴とする地理的道路データ処理及び格納装置。 - 【請求項8】請求の範囲1から6のうちのいずれかに記
載された地理的道路データ格納方法を実行することによ
り生じた格納データ構造を具える記憶媒体アイテム。 - 【請求項9】請求の範囲8に記載された記憶媒体にイン
タフェースする読出し装置であって、複数の前記複合ジ
ャンクション及び複合外部道路リンクを保持する情報を
抽出するために前記格納データ構造に選択的にアクセス
するアクセス手段を具えることを特徴とする読出し装
置。 - 【請求項10】請求の範囲9に記載された読出し装置で
あって、前記複合ジャンクション及び複合外部道路リン
クを選択的に表示する表示手段を有することを特徴とす
る読出し装置。 - 【請求項11】請求の範囲9又は10に記載された読出し
装置を含むナビゲーションシステムを具える車両。
Applications Claiming Priority (3)
Application Number | Priority Date | Filing Date | Title |
---|---|---|---|
AT95201619.4 | 1995-06-16 | ||
EP95201619 | 1995-06-16 | ||
PCT/IB1996/000502 WO1997000425A2 (en) | 1995-06-16 | 1996-05-28 | System for joining elements to complex junctions and links in road network representation for vehicles |
Publications (2)
Publication Number | Publication Date |
---|---|
JPH10504402A JPH10504402A (ja) | 1998-04-28 |
JP3386816B2 true JP3386816B2 (ja) | 2003-03-17 |
Family
ID=8220388
Family Applications (1)
Application Number | Title | Priority Date | Filing Date |
---|---|---|---|
JP50283897A Expired - Fee Related JP3386816B2 (ja) | 1995-06-16 | 1996-05-28 | 車両用の道路ネットワーク表示の複合ジャンクション及びリンクに要素を結合するシステム。 |
Country Status (5)
Country | Link |
---|---|
US (1) | US5815161A (ja) |
EP (1) | EP0776461B1 (ja) |
JP (1) | JP3386816B2 (ja) |
DE (1) | DE69617172T2 (ja) |
WO (1) | WO1997000425A2 (ja) |
Families Citing this family (20)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
JPH109884A (ja) * | 1996-06-24 | 1998-01-16 | Mitsubishi Electric Corp | 車両用経路案内装置および経路探索方法 |
US5968109A (en) * | 1996-10-25 | 1999-10-19 | Navigation Technologies Corporation | System and method for use and storage of geographic data on physical media |
US6047280A (en) | 1996-10-25 | 2000-04-04 | Navigation Technologies Corporation | Interface layer for navigation system |
US7197500B1 (en) | 1996-10-25 | 2007-03-27 | Navteq North America, Llc | System and method for use and storage of geographic data on physical media |
US5912674A (en) * | 1997-11-03 | 1999-06-15 | Magarshak; Yuri | System and method for visual representation of large collections of data by two-dimensional maps created from planar graphs |
US6369819B1 (en) * | 1998-04-17 | 2002-04-09 | Xerox Corporation | Methods for visualizing transformations among related series of graphs |
US6674434B1 (en) * | 1999-10-25 | 2004-01-06 | Navigation Technologies Corp. | Method and system for automatic generation of shape and curvature data for a geographic database |
EP1241447A1 (en) * | 2001-03-13 | 2002-09-18 | Matsushita Electric Industrial Co., Ltd. | Information terminal and cartographic information providing system |
US7002579B2 (en) * | 2001-05-09 | 2006-02-21 | Cadec Corporation | Split screen GPS and electronic tachograph |
JP4579640B2 (ja) * | 2004-10-18 | 2010-11-10 | クラリオン株式会社 | 要約地図作成装置 |
JP4580209B2 (ja) * | 2004-10-18 | 2010-11-10 | クラリオン株式会社 | 要約地図作成装置 |
US7730429B2 (en) * | 2004-12-03 | 2010-06-01 | Spark-Space Ltd. | Graphical workspace for idea management |
US7508400B2 (en) * | 2005-03-23 | 2009-03-24 | Zenrin Co., Ltd. | Digital map data processing system |
JP4522369B2 (ja) * | 2006-01-18 | 2010-08-11 | 株式会社エムビーエイ | ナビゲーション装置 |
DE602006004215D1 (de) * | 2006-09-22 | 2009-01-22 | Cyclomedia Technology B V | Methode und System zum Erzeugen eines Panoramabildes ausgehend von einem Fahrzeug |
EP2142883B1 (en) | 2007-04-22 | 2017-10-18 | Ilookabout INC. | Method of obtaining geographically related images using a vehicle |
US7447588B1 (en) * | 2007-07-16 | 2008-11-04 | Wenshine Technology Ltd. | Method and system for partitioning a continental roadway network for an intelligent vehicle highway system |
US8670924B2 (en) * | 2008-09-12 | 2014-03-11 | General Motors Llc | Creation of GIS tools and spatial database for limited access highway entrance points in the US and Canada |
DE102011077945A1 (de) * | 2011-06-22 | 2012-12-27 | Robert Bosch Gmbh | Verfahren und Vorrichtung zur Aktualisierung einer in mehreren Generalisierungsebenen strukturierten digitalen Karte |
KR102480000B1 (ko) * | 2015-12-11 | 2022-12-21 | 팅크웨어(주) | 전자 장치, 전자 장치의 경로 안내 방법, 컴퓨터 프로그램 및 컴퓨터 판독 가능한 기록 매체 |
Family Cites Families (6)
Publication number | Priority date | Publication date | Assignee | Title |
---|---|---|---|---|
US4914605A (en) * | 1984-10-22 | 1990-04-03 | Etak, Inc. | Apparatus and method for displaying a map |
CA1277043C (en) * | 1985-07-25 | 1990-11-27 | Marvin S. White, Jr. | Apparatus storing a representation of topological structures and methods of building and searching the representation |
NL8701738A (nl) * | 1987-07-23 | 1989-02-16 | Philips Nv | Werkwijze voor het opslaan van een topologisch netwerk in een geheugen en voor het opzoeken van een 2-cel uit dat netwerk, alsmede inrichting voor het uitvoeren van de werkwijze voor het opzoeken. |
NL8702014A (nl) * | 1987-08-28 | 1989-03-16 | Philips Nv | Routebepalingseenheid. |
EP0479364B1 (en) * | 1990-10-01 | 1999-05-26 | Mannesmann VDO Aktiengesellschaft | Method of storing a topological network, and methods and apparatus for identifying series of 1-cells in a network stored by such a method |
US5515283A (en) * | 1994-06-20 | 1996-05-07 | Zexel Corporation | Method for identifying highway access ramps for route calculation in a vehicle navigation system |
-
1996
- 1996-05-28 DE DE69617172T patent/DE69617172T2/de not_active Expired - Lifetime
- 1996-05-28 JP JP50283897A patent/JP3386816B2/ja not_active Expired - Fee Related
- 1996-05-28 WO PCT/IB1996/000502 patent/WO1997000425A2/en active IP Right Grant
- 1996-05-28 EP EP96913681A patent/EP0776461B1/en not_active Expired - Lifetime
- 1996-06-12 US US08/662,187 patent/US5815161A/en not_active Expired - Lifetime
Also Published As
Publication number | Publication date |
---|---|
US5815161A (en) | 1998-09-29 |
WO1997000425A2 (en) | 1997-01-03 |
EP0776461B1 (en) | 2001-11-21 |
WO1997000425A3 (en) | 1997-02-27 |
EP0776461A2 (en) | 1997-06-04 |
DE69617172D1 (de) | 2002-01-03 |
JPH10504402A (ja) | 1998-04-28 |
DE69617172T2 (de) | 2002-07-25 |
Similar Documents
Publication | Publication Date | Title |
---|---|---|
JP3386816B2 (ja) | 車両用の道路ネットワーク表示の複合ジャンクション及びリンクに要素を結合するシステム。 | |
US6134501A (en) | Vehicle travel-route guidance apparatus with internal intersection discount feature | |
EP0689034B1 (en) | Method for identifying highway access ramps for route calculation in a vehicle navigation system | |
US7734410B2 (en) | Navigation system | |
US6415222B1 (en) | Navigation system and storage medium | |
JP3474380B2 (ja) | ナビゲーション装置および地図データベース装置 | |
EP0838661A2 (en) | Map database apparatus | |
JP3551241B2 (ja) | 道路地図における経路探索条件の決定方法 | |
JPH0553501A (ja) | 経路テーブルを用いた最適経路決定方法 | |
JPH06323861A (ja) | 経路計算機能を有するナビゲーション装置 | |
JP2798615B2 (ja) | 経路探索装置 | |
JPH08105752A (ja) | 車載用ナビゲーション装置 | |
JPH07110238A (ja) | 経路計算装置 | |
JP3502230B2 (ja) | ナビゲーション装置 | |
JP3039226B2 (ja) | 経路計算方法及び装置 | |
JPH09133540A (ja) | 複数経路取得方法及びこの方法を用いた車載ナビゲーション装置 | |
JP3022042B2 (ja) | 経路探索装置 | |
JPH05297800A (ja) | 経路案内装置 | |
JP3841776B2 (ja) | 経路探索装置 | |
JP2601943B2 (ja) | 最適経路計算装置 | |
JP2905491B2 (ja) | ナビゲーション装置 | |
JP3841775B2 (ja) | 経路探索装置 | |
JPH06288783A (ja) | 経路表示機能を有する経路誘導装置 | |
JPH07104175B2 (ja) | 最適経路決定装置 | |
JPH087527B2 (ja) | 最適経路決定装置 |
Legal Events
Date | Code | Title | Description |
---|---|---|---|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
R250 | Receipt of annual fees |
Free format text: JAPANESE INTERMEDIATE CODE: R250 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080110 Year of fee payment: 5 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090110 Year of fee payment: 6 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090110 Year of fee payment: 6 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100110 Year of fee payment: 7 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110110 Year of fee payment: 8 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110110 Year of fee payment: 8 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120110 Year of fee payment: 9 |
|
S111 | Request for change of ownership or part of ownership |
Free format text: JAPANESE INTERMEDIATE CODE: R313111 Free format text: JAPANESE INTERMEDIATE CODE: R313113 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120110 Year of fee payment: 9 |
|
R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120110 Year of fee payment: 9 |
|
FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130110 Year of fee payment: 10 |
|
LAPS | Cancellation because of no payment of annual fees |