JPS6311987A

JPS6311987A - 地図デ−タのサ−チ方法

Info

Publication number: JPS6311987A
Application number: JP61156886A
Authority: JP
Inventors: 雅幸細井; 福島　敦彦; 隆柏崎; 斉安藤
Original assignee: Pioneer Electronic Corp
Current assignee: Pioneer Corp
Priority date: 1986-07-02
Filing date: 1986-07-02
Publication date: 1988-01-19

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】炎血且１本発明は、地図データのサーチ方法に関し、特に車載ナ
ビゲーション装置において地図の道路上の各位置及び交
差点位置が数値化されて記憶された地図データのサーチ
方法に関するものである。

１且且」近年、地図情報をメモリに記憶しておき、その地図情報
をメモリから読み出して車両の現在地とともに表示装置
に表示させることにより、車両を所定の目的地に誘導す
る車載ナビゲーション装置が研究、開発されている。

かかるナビゲーション装置では、車両に搭載された走行
距離センサや方位センサ等の出力データに基づいて車両
の走行距離や方位を検出し、これに基づいて時々刻々と
変化する車両の現在地を推測することにより、ディスプ
レイに表示されている地図上への現在地の表示が行なわ
れる。

この場合、現在地は常に地図の道路上に表示されるのが
好ましく、そのために車両の現在地に最も近い道路や交
差点への引込みが行なわれる。この引込みを行なうため
には、現在地に最も近い道路や交差点を地図データ中か
らサーチする作業が必要となるが、サーチエリアが広い
とサーチに時間がかかってしまい、車両の走行に伴い時
々刻々と変化する現在地をスムーズに表示できないこと
になる。

１匪五且Ｉ本発明は、上述した点に鑑みなされたもので、サーチの
高速化を図り、車両の現在地のスムーズな表示を可能と
した地図データのサーチ方法を提供することを目的とす
る。

本発明による地図データのナーブ方法は、地図の道路上
の各位置及び交差点位置を数値化して地図データとして
記憶する際、地図を細分化してエリア単位で記憶してお
き、車両の現在地から道路上の最近傍位置又は最近情交
差点をサーチするときは、現在地が属するエリア単位で
行なうことを特徴としている。

実−一思一一出以下、本発明の実施例を図に基づいて説明する。

第１図は、本発明に係る車載ナビゲーション装置の構成
を示すブロック図である。同図においで、１は地磁気に
基づいて車両の方位データを出力するための地磁気セン
サ、２は車両の角速度を検出するための角速度センサ、
３は車両の移動距離を検出するための走行距離センサ、
４は緯度及び経度情報等から車両の現在地を検出するた
めのＧＰ３　（Ｇｌｏｂａｌ　Ｐｏ５ｉｔｉｏｎｉｎｏ
　Ｓｙｓｔｅｍ）Ｉｉ置であり、これら各センサ（装置
）の出力はシステムコントローラ５に供給される。

システムコントローラ５は、各センサ（装置）１〜４の
出力を入力としＡ１０　（アナログ／ディジタル）変換
等を行なうインターフェース６と、種々の画像データ処
理を行なうとともにインターフェース６から順次送られ
てくる各センサ（装置）１〜４の出力データに基づいて
車両の移動量等を演算するｃｐｕ　＜中央処理回路）７
と、このＣＰＵ７の各種の処理プログラムやその仙必要
な情報が予め古き込まれたＲＯＭ（リード・オンリ、メ
モリ）８と、プログラムを実行する上で必要な情報の書
込み及び読出しが行なわれるＲＡＭ（ランダム・アクセ
ス・メモリ）９と、いわゆるＣＤ−ＲＯＭ、ＩＣカード
等からなり、ディジタル化（数値化）された地図情報が
記録された記録媒体１０と、Ｖ　−ＲＡ　Ｍ　（Ｖｉｄ
ｅｏ　ＲＡＭ）等からなるグラフィックメモリ１１と、
ＣＰＵ７から送られてくる地図等のグラフィックデータ
をグラフィックメモリ１１に描画しかつ画像としてＣＲ
Ｔ等のディスプレイ１２に表示すべく制御するグラフィ
ックコントローラ１３とから構成されている。入力装置
１４はキーボード等からなり、使用者によるキー人力に
より各種の指令等をシステムコント０−ラ５に対して発
する。

記録媒体１０には地図情報が記録されるのであるが、そ
のデータ構造について以下に説明する。

先ず、第２図（Ａ）に示すように、日本全図を例えば１
６３８４　（＝２’　）［ｍ］四方（７）メツシュに分
割し、このときの１つのメツシュをテリトリ−と呼ぶ。

テリトリ−はテリ１へり−Ｎｏ、（ＴＸ。

Ｔｙ）で識別され、各テリトリ−には例えば図の左下の
テリトリ−を基準にテリトリ−Ｎｏ、が付与される。テ
リトリ−Ｎｏ、は現在地（Ｃｒｎｔｘ。

Ｃｒｎｔｙ）より求まる。テリトリ−は本データ構造の
中で最も大きな管理単位となる。地図データファイル全
体の構成が第２図（Ｂ）に示されており、テリトリ−Ｉ
Ｄファイルには、第２図（Ｃ）に示すように、テリトリ
−Ｎｏ、（Ｔｘ、Ｔｙ）のファイルにおける先頭アドレ
ス、テリトリ−の左下の緯度（実数）、テリトリ−の左
下の経度（実数）、地磁気の偏角（実数）等のデータが
各テリトリ−毎に書き込まれている。

テリトリ−ファイルは本データ構造において最も重要な
ファイルであり、各種の地図データや地図描画に必要な
データが書き込まれている。第３図（Ａ）において、ナ
ビＩＤ及びセクションテーブルがナビゲーションにおけ
る道路及び交差点検索用ファイル、ピクチャーＩＤが表
示管理用ファイル、道路セクションデータから交差点デ
ータまでが実際の地図データである。地図データは、第
３図（Ｂ）に示すように、互層構造となっており、最下
層が川、海、湖等のポリゴンデータ、その上が道路、鉄
道等のラインデータ、その上が各種マーク等のキャラク
タデータ、その上が地名等の文字データ、そして最上層
が交差点データとなっている。最上層の交差点データは
後述する交差点引込みのために用いられるデータであり
、ディスプレイ上には表示されない。

次に、第４図（Ａ＞に示すように、１つのテリトリ−の
中を例えば２５６分割し、これにより得られる１　０２
４　（２”　）［ｍ］四方のメツシュをユニットと呼ぶ
。このユニットも同様にユニットＮｏ、（Ｎｘ、Ｎｙ）
で管理され、そのＮｏ。

（’Ｎｘ、Ｎｙ）は現在地（Ｃｒｎｔｘ　、　Ｃｒｎｔ
ｙ　）より求まる。ユニットは中間的な管理単位で、地
図情報はこの単位で記録され、ユニットが２５６個集ま
ってテリトリ−ファイルを構成する。地図描写の際はこ
の単位を基に行なわれるので、描画の基本単位と言うこ
とができる。ナビＩＤファイルには、第４図（Ｂ）に示
すように、ユニットＮ００（Ｎｘ、Ｎｙ＞のファイルに
おけるライン先頭アドレス、交差点先頭アドレス、道路
セクション先頭アドレス、交差点先頭アドレス等のデー
タが各ユニット毎に書き込まれている。

更に、第５図（△）に示すように、１つのユニット内を
例えば１６分割し、これにより得られる２５６　（２８
）［ｍ］四方のメツシュをセクションと呼ぶ。このセク
ションも同様にセクションＮｏ、（Ｓｘ、Ｓｙ）で管理
され、そのＮｏ、（Ｓｘ、Ｓｙ）は現在地（Ｃｒｎｔｘ
　、　Ｃｒｎｔｙ　）より求まる。セクションは最も小
さい管理単位であり、この範囲内の線分（ｌ！！分の繋
りで道路等が表わされる）や交差点の情報が第５図（Ｂ
）、（Ｃ）に示す如くセクションテーブルとして、更に
第６図＜Ａ＞、（Ｂ）及び第７図（△＞、（Ｂ）に示す
如くセクションデータとしてテリトリ−ファイルに登録
されている。

また、第３図（Ａ）に示すように、テリトリ−ファイル
内には表示管理用のピクチャーＩＤというファイルがあ
る。本丈施例では、地図データの縮尺が例えば２．５万
分の１，５万分の１，１０万分の１の３種類に設定され
ており、実際の地図データとしては、最も縮尺の大きい
２．５万分の１のものだけを持っている。各縮尺の地図
は、第８図〜第１０図の各図（Ａ＞に示すように、エリ
アに分割され、このエリアはエリアＮ　ｏ　、　　（Ａ
　ｎｘ。

Ａｎｙ）で管理される。エリアＮｏ、　　＜Ａｎｘ、　
Ａｎｙ）は現在地（Ｃｒｎｔｘ　、　Ｃｒｎｔｙ　）よ
り求まる。縮尺が２．５万分の１の場合、エリアＮｏ、
とユニットＮｏ、は同じであり、５万分の１の場合は１
つのエリアがユニットファイル４個分となり、１０万分
の１の場合は１つのエリアがユニット１６個分となる。

また、各縮尺のピクチャーＩＤには、第８図〜第１０図
の各図（Ｂ）にそれぞれ示すように、その縮尺の地図を
表示するのに必要なポリゴン、ライン、キャラクタ、文
字データの先頭アドレスとデータサイズが記録されてい
る。

続いて、ポリゴンデータとラインデータについて説明す
る。ポリゴンデータとラインデータは、第１１図（Ａ＞
及び第１２図（Ａ＞に示すように、始点と終点で表わさ
れる繋りのあるベクトル（線分）で表わされる。ここで
、最も縮尺の大きい２゜５万分の１の地図データで５万
分の１や１０万分の１の地図を表現すると、始点・終点
間が縮まるのでディスプレイ上で見た限りでは、全ての
点を表示しなくても差し支えないことがある。このこと
を考慮に入れて、ディスプレイ上に表示した場合に、見
た目上省略しても差し支えない点の情報を、第１１図（
Ｂ）及び第１２図（Ｂ）に示すように、予めポリゴン及
びラインデータの各間引きビットに入れておく。そして
、各縮尺の表示時に間引きビットをチェックして必要に
応じて間引きビットに情報が入っている点を除く、いわ
ゆる間引きを行なうことにより、表示する線分（ベクト
ル）数を減らすことができる。

また、第１３図（Ａ＞に示すように、１ユニツト内に存
在する交差点の全てに通し番号（ｘ　ｎ、　ｙｎ）が付
されている。ところで、交差点には、直交型、Ｙ字路、
５支路等種々あるが、特に方位の似た道路が複数入って
いる交差点では、この交差点を通過したときに、センサ
の精度、計０誤差、地図精度等により道路の選択を誤り
、ディスプレイ上に現在地が表示されている道路と実際
に走行している道路とが一致しない状態が生ずる可能性
がある。そこで、このような交差点に対しては、第１３
図（Ｂ）に示すように、交差点のｙｌｉ易度を示す難易
度データを交差点データ中の難易度ビットにいれておく
。そして、交差点を通過するときには、この難易度デー
タに基づいた処理を行なえば、誤った道路の選択を防止
できるのである。その処理に関しては後で説明する。

次に、地図データの表示に関して、グラフィックメモリ
１１として例えばＶ−ＲＡＭを用いた場合について説明
する。表示の構成としては、第１４図（Ａ）に示すよう
に、５１２（ドツト）Ｘ５１２（ドツト）のＶ−ＲＡＭ
上で画面を１６分割し、それぞれのエリアに独立した１
枚の地図を表示するようにする。１エリアは１２８くド
ツト）Ｘ１２８（ドツト）の１ユニツトであり、更に１
６分割することにより１エリアは３２（ドツト）×３２
（ドツト）の１セクシヨンとなる（第１４図（Ｂ）、（
Ｃ）を参照）。実際の車載ディスプレイには、第１４図
（Ａ）の中央の４両面に相当する２５６（ドツト）Ｘ２
５６（ドツト）のエリア（太線で囲ったエリア）が表示
され、このエリアがＶ−ＲＡＭ上を移動することによっ
て車両の現在地の動きを表現する。

次に、ＣＰＵ７によって実行される基本的な手順を第１
５図のフローチャートに従って説明する。

ＣＰＵ７は、先ず最初にプログラムを実行させるための
イニシャライズを行ないくステップＳ１）、しかる後車
両の現在地がセットされているか否かを判断する（ステ
ップ３２）。現在地がセットされていない場合は、現在
地セットルーチンの実行くステップＳ３）、例えば入力
装＠１４でのキー人力による現在地のセットが行なわれ
る。次に、走行距離を零にしくステップＳ４）、続いて
入力装置１４からのキー人力が有るが否かの判断を行な
う（ステップ３５）。

キー人力が無い場合は、ディスプレイ１２上に現在地周
辺の地図表示を行なうとともに車両の現在位置及びその
方位を例えば車両マークにてこの地図上に表示し、車両
が移動したらその移動に伴い地図をスクロールさせ、更
に現在グラフィックメモリ１１上にある地図データの範
囲を車両位置が越えそうなときには、記録媒体１０から
必要な地図データを読み出してディスプレイ１２上に表
示する（ステップＳ６）。

キー人力が有ると、その入力データに応じて現在地の再
セット（ステップＳ７）、センサ補正（ステップＳ８）
、目的地セット（ステップ８９）及び地図の拡大・縮小
（ステップ５１０）の各ルーチンを実行する。

また、ＣＰＵ７はタイマーによる割込みにより、第１６
図に示すように、一定時間間隔で地磁気センサ１及び角
速度センサ２の各出力データに基づいて車両の方位を常
に計篩する処理を行なう（ステップＳ１１．５１２）。

ｃｐｕ７は更に、走行距離センサ３よりデータが入力さ
れた場合は、走行距離センサによる割込み処理を行なう
。この割込み処理では、第１７図に示すように、走行距
離と方位からの現在地の算出（ステップ５１３）、右折
、左折の判定（ステップ５１４）、道路への引込み（ス
テップ５１５）、交差点引込み（スナップ８１６）、走
行距離による引込み（ステップ５１７）が実行される。

なお、このステップ３１３〜ステツプ８１７における各
処理に□関しては、後で詳細に説明する。

また、ＧＰＳ装置４より得られる緯度、経度データは、
第１８図に示すように、ＧＰＳデータ受信割込みにより
処理され、現在地データとして座標変換される（ステッ
プ８１８）。

車両の走行距離は走行距離センサ３の出力から求められ
る。この走行距離センサ３としては、例えば、車のいわ
ゆるスピードメータケーブルの回転数（ＪＩＳ規格では
、６３７回転／Ｋｍ）より１回転の距離を積分すること
により走行距離を求める構成のものが用いられるが、セ
ンサ３の精度により得られる走行距離に誤差が生ずるこ
とは避けられない。また、センサ３の精度だ（プではな
く、地図の精度、タイヤの空気圧の変化、或はスリップ
等も走行距離の誤差の要因となる。従って、走行距離の
補正を度々行なわないと、正確に距離を求めることがで
きなくなってしまうことになる。

このため、走行距離センサ３の出力より得た実測の距離
と地図データより得た距離とから距離補正係数ｒｓを求
め、この補正係数ｒｓを用いて距離補正を行なうことに
より、走行距離を常に正確に検出できるのである。

また、車両の方位は地磁気センサ１の出力から求められ
る。この方位検出方法に関しては、本出願人等による特
願昭６０−２８２３４１号明細書等に記載されている。

この地磁気センサ１の示す北は磁北であり、地図北では
ない。このため、磁北が地図北に対してずれていた場合
、第１９図に示すように、基準位置から一定距離だけ走
行したときに地磁気センサ１の出力から得られる推測現
在地Ｐ１は実際の現在地Ｐ２に対してずれを生じること
になる。そのため、地磁気センサ１より求めた方位を地
図方位に変換する作業が必要となる。

この変換作業は、第２０図に示すように、２次元幾何の
座標変換で求まる回転角、即ち方位補正係数θＳによっ
て行なわれる。この方位補正係数θＳは地域により変化
し、更に地磁気センサ１を車体に取り付けたときに生じ
る取付は誤差によっても変わる。この方位補正係数θＳ
は、第２１図に示すように、当該係数を零として位置の
わかっている２点間を走行し、慣性航法により求められ
た現在地と到着点との誤差により求めることができる。

この方位補正係数θＳを用いて方位補正を行なうことに
より、車両の方位を常に正確に検出できるのである。

なお、距離補正係数ｒｓ及び方位補正係数θＳの算出方
法は、本出願人等による特願昭６０−２８２３４４号明
細書等に記載されている。

次に、ＣＰＵ　７によって実行される走行距離センサ３
による割込み処理の手順を、第２２図のフローチャート
に従って説明する。走行距離センサ３の出力データによ
り、現在地の推測地点が随時計口されており、現在地Ｈ
Ｈルーチンとして、本ルーチンが所定のタイミングで呼
び出される。

ＣＰＵ７は先ず、単位距離１０を走ったか否かを判断す
る（ステップＳ２０＞。ここに、単位距離とは、車両が
実際に走行した一定の道程を言い、例えば２０　［ｍ］
に設定されている。そして、一定走行距離毎に本ルーチ
ンが実行され、先ず地図データとの関係即ち、第２３図
に示す如く最近傍線分りまでの距１１１ｊｊ１ｍ、その
線分りの地図北となす角度θｎ等を求め、更にほぼ等距
離に２本以上の線分があるときは、その旨をフラグで示
す（ステップ５２１）。その伯、近傍交差点の有無など
をここで求めるようにしても良い。続いて、距離ρｍが
予め設定した閾値ｆＪｔｈを超えたか否かを判断する（
ステップ５２２）。超えていなければ、はぼその線分近
傍に現在地があるとして、誤差分ＩＪｍの修正を行なう
くステップ５２３）。この誤差分子Ｊｍは、走行距離セ
ン１す３の検出誤差、地図データのデジタイズ誤差等に
起因するものである。

この修正を行なうのは、次の現在地の認識のためには、
それらの誤差をキャンセルしておく必要があるためであ
る。この後、後述層るパターン引込みルーチンに進む。

一方、距離ｊ１ｍが閾値ｒ　ｔｈを超えている場合は、
次に車両がカーブ（右折又は左折）したか否かを判断す
る（ステップ５２４）。カーブの検出方法については、
後で別に述べる。カーブしなかった場合、地磁気センサ
１の出力データから得られた車両の進行方位θと線分り
の角度θｎの差を設定基準値θｔｈと比較する（ステッ
プ５２５）。１θ−θｎｌ＞θｔｈならば、何もせずに
パターン引込みルーチンに進む。このケースとしては、
例えば、１字路をつき当り方向に進んだり、或は地図デ
ータとして記憶されていない道を走っているような場合
が考えられる。続いて、近傍にＹ字路等、より小さい角
度をもった難易度の高い交差点があるか否かを判断する
（ステップ８２６）。近傍に例えばＹ字路がある場合に
は、現在走っている道路とは別の道路に引き込んでしま
う可能性があるので、何もせずにパターン引込みルーチ
ンに進む。

交差点の難易度を示すデータは、地図を数値化する際に
予め第１３図（Ｂ）に示す如く交差点データの難易度ビ
ットに挿入されているので、ＣＰＵ７はステップＳ２６
でこのビットをチェックすれば良いのである。

以上の２つの条件が当てはまらないときは、センサ等の
誤差が生じて道路データから外れつつあると判断し、こ
の場合は、現在地の修正、即ち道路データへの引込みを
行なう（ステップ５２７）。

新しい現在地の堆測点Ｐ　ｃｐｄは、第２４図に示すよ
うに、センサ出力から求めた前回推測地点Ｐｐρｄから
の相対関係より演算された現在推定地点Ｐｃｐより、最
近傍線分Ｌ１．：おろした垂線と交わる点とし、表示等
を変更する。距離ｊｍ及び現在推定地点ＰＣｐの座標（
Ｘ　ｍ、　Ｙ　ｍ）はその地点における修正値として、
後で述べるパターン引込みルーチンで使用するため記憶
される。

ステップ８２４で力、−ブしたと判断した場合、交差点
引込みルーチンに入る。先ず、前回交差点としてＨ７Ｂ
した地点からの走行距離ρＣを求め、この走行距離ρＣ
に対して一定［ｉ　ａ　ｃを乗じたものを、交差点検出
閾値ｕ　Ｃｔｈとする（ステップ３２８）。一定値ａＣ
は走行距離センサ３の精度に関連した値で、倒λば０．
０Ｂ程度の値とする。

地図データとして入っている交差点データに対し、現在
地Ｐｃｐから各交差点までの距５Ｊｃを求め　　・（ス
テップＳ２９＞　、Ｊ　ｃ　＜ｆＪ　ｃｔｈなる交差点
が存在するか否かを判断する（ステップ５３０）。

ステップＳ３０では、一定距離範囲（例えば、数百１ｍ
］程度）以内か否かの判断も行なう。ここで、交差点が
存在しなかった場合には、パターン引込みルーチンに進
む。また、近傍交差点が複数あり、かつ交差点までの距
離ＩＪｃが同程度で近傍交差点を特定できないと判断（
ステップ５３１）した場合も、パターン引込みルーチン
に進む。

近傍交差点が特定された場合、その交差点を新しい現在
地推測地点Ｐ　ｃｐｄとして引込みを行なう（ステップ
５３２）。この際、交差点までの距離ｆＪｃ及び現在地
Ｐｃｐの座標（Ｘ　ｃ、　Ｙ　ｃ）は引込み母として記
憶される。また、現在地推測地点Ｐ　ｃｐｄを新しい認
識交差点として記憶（更新）する。これにより、車両の
現在地がディスプレイ１２上に表示されている地図の道
路上から外れた場合に、強制的に地図上の交差点上に車
両の現在地をのせろ、いわゆる交差点引込みが行なわれ
るのである。

続いて、前回認識した交差点の座標、そこからの修正値
の和及び現在地の座標に基づいて距離及び方位の補正係
数ｒｓ、θＳを更新する（ステップ５３３）。このよう
に、交差点を認識する毎又は交差点間の距離が長い場合
には一定路１！ｔｌｌｐだけ走行する毎に、距離及び方
位の補正係数ｒｓ、θＳの更新を行なえば、より精度の
高い現在地推測が可能となる。

次に、パターン引込みについて説明する。このルーチン
は一定路１！ｔＮｐｏだけ走った時点で実行される。距
離ｆＪ　ｐｏは、例えば１０００　［ｍ］という値であ
る。なお、ステップ８３１で交差点認識が行なわれた場
合には、走行距離はリセットされる。

一定路！１１ρｐｏだけ走行する間に、最近傍線分まで
の距離ｆＪｍが、ｎ＝ｊｌ　ｐｏ／ｉｆ　ｏ　　［回］
測定されることになり、ｎ個の誤差修正量ｅｉがデータ
として記憶されている。更に、１回の測定に対し、前回
測定時の誤差修正量ｅ　ｉ−１と今回の誤差修正量ｅｉ
　との差を、変化１ｉｃｉ　　（ｅｉ　−ｅｉ−１）と
して計算しておくものとする。

一定路ｊ５ｊｐｏだけ走ったと判断したら（ステップ５
３４）、変化量Ｃ１の値のばらつきについて計算しくス
テップ５３５）、続いてその偏差α。

６）。そして、この値αを予め定めた閾値αｔｈｈと比
較する（ステップ５３７）。この値αは、各センサの検
出誤差、走行距離等を考慮して求めたものである。α〉
αｔｈｈの場合、引込み不可能と判断し、パターン引込
みは行なわない。一方、αくαｔｈｈの場合、更に現在
引込みが行なわれているか否かを判断しくステップ８３
８）、引込みが行なわれていない場合、即ち道路データ
から外れた位置に現在地がある場合、現在地の最近傍線
分への引込みを行なう（ステップ＄３９）。更に、閾値
αｔｈｈと同様に定められた閾値αｔＭと比較しくステ
ップ５４０）　、α〈α１１＋９のときには、距離及び
方位の補正係数ｒｓ、Ｏ３を更新する（ステップ５４１
）。

以上の方法で、一度道路から外れたところを走行した後
、他の道路に再引込みを行なうことが可能となる。すな
わち、デジタイズされていない道路を走行し、再びデジ
タイズされた通路を走行すると、一定距離を走った時点
でその道路が認識され、精度の良い現在地推測が可能と
なる。また、一定距離Ｊ　ｐｏに対し、より良い距離Ｕ
ｔについて偏差計算を行ない、距１！１ｆＪｐｏを短く
とって精度を上げ、応答時間を類くすることも可能であ
る。第２５図（Ａ）、（Ｂ）に、その様子を示す。

以上のようにして、最近情交差点への引込みや最近傍線
分への引込みが行なわれるのであるが、この引込みを行
なうためには、現在地に最も近い道路（最近傍線分）や
交差点く最近情交差点）を探し出す作業が必要となる。

この最近情交差点や最近傍線分をサーチする作業は、線
分や交差点データの吊が多い、即ちサーチエリアが広い
と、時間がかかってしまい、萌々刻々と変化する現在地
をスムーズに表示できないことになる。ところが、本実
施例においては、第２図〜第５図に示したデータ構造か
ら明らかなように、現在地からのサーチエリアをできる
だけ小さくし、かつそのエリアに入る線分や交差点のデ
ータを管理するデータ（セクションデータ、セクション
テーブル）を持たせていることにより、最小単位のセク
ションをサーチエリアとしてその中から線分や交差点を
サーチすることができるので、サーチに要する時間を短
縮できるのである。以下、ＣＰＵ７によって実行される
現在地から最近傍線分と最近情交差点をサーチする手順
を、第２６図のフローチャートに従って説明する。

ＣＰＬｊ７は先ず、現在地（ｃｒｎｔｘ　、　ｃｒｉｌ
ｔｙ　）からテリトリ−Ｎｏ、（Ｔｘ、Ｔｙ）、ｌニッ
トＮｏ、（Ｎｘ、Ｎｙ）、セクションＮｏ、（Ｓｘ。

Ｓｙ）をそれぞれ求める〈ステップ８５０〜５５２）。

これは、各エリアが２　単位で分割されているので、簡
単な演算（割算）で求めることができる。次に、セクシ
ョンを勺−チェリアとして、この中に存在する線分と交
差点データをセクションテーブルとセクションデータを
参照することによりロードする（ステップ３５３〜５５
５）。ロードしたデータを基に、現在地がらサーチエリ
ア内の全ての線分までの距離（線分に対する垂線の長さ
）、全ての交差点までの距離を計算し、それらを比較す
ることによって最近傍線分と最近情交差点を得ることが
できる（ステップ８５６）。サーチを行なう際のスピー
ドは、線分の本数や交差点の個数に比例するが、前述し
たデータ構造に基づくサーチ方式によれば、サーチエリ
ア（セクション）が小さく、計算の対象となる線分の本
数や交差点の個数が少ないので、高速サーチが可能とな
るのである。

ところで、ナビゲーションシステムにおいては、種々の
縮尺の地図データを表示する際、全ての縮尺の地図デー
タを持っていると、表示は簡単にしかも高速に行なえる
が、その半面データサイズが大きくなるというデメリッ
１−がある。逆に配も縮尺の大きい地図データだけを持
っていてその他の縮尺を単純な縮小によって表わす場合
、データサイズは小さくなるが表示が遅くなるという欠
点を持つ。

これに対し、本実施例においては、第８図〜第１０図に
示したデータ構造から明らかなように、データサイズを
小さくするために最も縮尺の大きい地図データだけを持
ち、更に他の縮尺のデータを表示する際は表示用の管理
ファイル及び間引きデータを用いることによって表示の
高速化を図っている。以下、第２７図のフローチャート
に従って、ＣＰＵ７によって実行される地図の拡大・縮
小の手順を説明する。

ＣＰＵ　７は先ず、表示すべき縮尺が入力装置９からキ
ー人力されたことを判別すると（ステップ５６０）　、
現在地（Ｃｒｎｔｘ　、　Ｃｒｎｔｙ　）から縮尺に対
応したエリアＮ　ｏ　、　　（Ａｎｘ、△ｎｙ＞を求め
〈ステップ８６１〜５６３）、続いてその縮尺のピクチ
ャーＩＤを参照しくステップ３６４〜８６６）、先頭ア
ドレスとデータサイズによって地図データをロードして
Ｖ−ＲＡＭ上の１６個のエリアにそれぞれ描画する（ス
テップ５６７）。このように、表示管理用のピクチャー
ＩＤによって、表示すべき識別された地図データの参照
が（縮尺が小さくなるに従って表示する道路、地名等を
重要なものに絞る）ができるので、表示の高速化が実現
できるのである。

また、ポリゴンとラインデータに対しては、第１１図及
び第１２図で説明したように、表示を省略しても差し支
えない点の間引きビットにはその旨の情報が入れである
ので、５万分の１や１０万分の１の地図の描画の際に、
この間引きビットをチェックしくステップ５６８）、間
引きの対象となっている点を除いて描画する（ステップ
５６９）。このように、地図の縮小の際、ディスプレイ
に表示した場合に、見た目上省略しても差し支えない点
を間引いて表示を行なうことにより、表示する線分の数
を減すことができるので、表示のより高速化が図れるの
である。

なお、上記実施例では、ポリゴンとラインデータに間引
きビットを設け、表示を省略しても差し支えない点の間
引きビットにはその旨の情報が入れるようにしたが、ポ
リゴンとラインのデータを等間隔でプロットしておき、
表示の際に所定の規則（例えば、縮尺５万分の１の場合
１つ飛び、１０万分の１の場合４つ飛び等）に従って間
引くようにしても良く、同様の効果が得られる。

次に、第２２図のフローチャートにおけるステップ８２
４のカーブ（右折・左折）の判断方法について説明する
。

基本的には、方位センサである例えば地磁気センサ１の
出力データに基づいて右折・左折を判別し、曲がったこ
とを検出した場合に、ステップ８２８以降の処理によっ
て交差点引込みを行なうのである。しかしながら、地磁
気センサ１は外乱に弱く、踏切通過時、鉄橋通過時、自
車の側を大きな車（例えば、トラック、バス）が通過し
た際、その出力データに大きな誤差が含まれることにな
る。このデータをそのまま右折・左折判断に利用すると
、直進しているところで曲がったと誤認して、交差点で
もないのに交差点引込みを行なってしまい、現在地が正
しい位置からずれてしまうことになる。

そこで、本実施例においては、曲がったことを判断する
のに、曲率半径と車速を判断基準に入れることにより、
正確な右折・左折の判断を可能としている。以下、ＣＰ
Ｕ７によって実行される右折・左折の判断方法の手順に
ついて、第２８図のフローチャートに従って説明する。

ＣＰＵ７は先ず、ある一定距離（例えば、１５　［ｍ］
　）を走行した際に一定角（例えば、４０度）以上向が
ったときをカーブ（右折又は左折）したと判断する（ス
テップ３７０）。しかし、カーブしたときにそのときの
曲率半径Ｒが判断基準最小回転半径である一定値Ｒｍｉ
ｎ　　（例えば、３．５　［ｍ］　）以下のときは、そ
のデータは間違っていると判断し、カーブしたとは判定
しない（ステップ５７１）。

これは、自動車の最小回転半径以下では曲がれないから
である。更に、車速Ｓがある判断基準最高速度である一
定速度３ｍａｘ（（例えば、４０［Ｋｍ／ｈ］）以上の
場合は、交差点を曲がることは通常は考えられないので
、この速度以上では、カーブしたとは判定しない（ステ
ップ５７２）。また、右折・左折の判定は、例えば、東
を方位０度、北を方位９０度、西を方位１８０度、南を
方位２７０度とすると、その方位の増減によって行なう
ことができる（ステップ５７３）。すなわち、方位が増
える方向が左折（ステップ５７４）、方位が減る方向が
右折（ステップ５７５）となるので、これにより右折・
左折を判断できるのである。

なお、曲率半径Ｒは、第２９図に示すように、ある点ａ
における車両の方位とその点ａから一定距離１だけ走行
した点すにおける車両の方位とのなす角度をθ［ラジア
ン］とすると、ｊ＝Ｒ・θであるから、この式を変形し
て得られる次式Ｒ＝ｆＪ／θ から求めることができる。

また、第２２図のフローに沿った処理によって行なわれ
る交差点引込み等により、現在地がディスプレィ上に表
示されている地図の道路上に常に位置するように制御さ
れるが、例えば交差点間の距離が長い場合には、その間
現在地の微小修正が行なわれるのであるが、センサの精
度、計算１Ｌ地図精度等による距離誤差により、前回引
込んだ交差点からの実際の現在地と地図上の現在地とに
距離差が生じ、その誤差は交差点間の距離が長い程大き
くなる。このような場合、次に引込みを行なうべき交差
点の近傍に複数の交差点が近接して複数あると、間違っ
た交差点に引込みを行なう可能性がある。そこで、本実
施例では、交差点間において一定距離だけ走行したら、
いわゆる走行距離による引込みを行なうようにしている
。以下、その手順を第３０図のフローチャートに従って
説明する。

先ず初期値を設定する（ステップ８８０）。この初期値
としては、ある確定した現在地が必要となるが、これは
使用者が最初に設定するか、交差点など確定した点へ引
き込んだ場合の現在地を利用できるし、またすでに確定
した現在地ならば不Ｎ発性メモリにそのデータを登録し
ておけば、一度だけセットすれば良いことになる。この
確定した現在地で走行距離をゼロリセットしくステップ
５８１）、交差点を曲がったか（ステップ５８２）、一
定距離を走ったかくステップ５８３）を常に監視しなが
ら、一定距離走ったときに、地図データに基づいてゼロ
リセッ１〜した地図上の点く前回検出位置）からこの一
定距離の点を求めてその点に現在地を変更し引込みを行
なう（ステップ５８４）。一定距離を走る間は、見掛は
上一番近い線分に垂線をおろし、その交点に引込みを行
なうことにより（ステップ５８５）、ディスプレイ上に
表示された地図の道路上に車両の現在地をのせることが
できる。車両が曲がったことを検出した場合には、交差
点引込みを行なう（ステップ８８６）。この交差点引込
みは先述した通りである。

なお、交差点で曲がったという判断にも、この走行距離
による引込みが有効に使える。すなわち、交差点間の距
離と走行距離により曲がった交差点を地図データより判
断できるのである。

及」１と１里以上説明したように、本発明によれば、地図の道路上の
各位置及び交差点位置を数値化して地図データとして記
憶する際、地図を細分化してエリア単位で記憶しておき
、車両の現在地から道路上の最近傍位置又は最近例文着
点をサーブするときは、現在地が属するエリア単位で行
なうことにより、最近傍位置又は最近傍交差点のサーチ
に要する演算時間等を大幅に短縮できるので、サーチの
高速化が可能となり、車両の走行に伴い現在地をスムー
ズに表示できることになる。

【図面の簡単な説明】

第１図は本発明に係る車載ナビゲーション装置の構成を
示すブロック図、第２図（Ａ）〜（Ｃ）乃至第１３図（
Ａ）、（Ｂ）は第１図における記録媒体に記憶される地
図情報のデータ構造を示す図、第１４図く、Ａ）〜（Ｃ
）はＶ−ＲＡＭ上の画面構成を示す図、第１５図乃至第
１８図は第１図におけるＣＰＬＩによって実行される基
本的な手順を示すフローチャート、第１９図乃至第２１
図は方位補正係数θＳの求め方を示す図、第２２図はＣ
ＰＵによって実行される交差点引込みルーチン及びパタ
ーン引込みルーチンの手順を示すフローチャート、第２
３図及び第２４図は地図上の現在地と最近傍線分との位
置関係を示す図、第２５図は道路への引込みを行なう伯
の方法を示す図、第２６図は最近傍線分及び交差点をサ
ーチする手順を示すフローチャート、第２７図は地図の
拡大・縮小の手順を示すフローチャート、第２８図は右
折・左折の判定方法の手順を示すフローチャート、第２
９図は曲率半径の求め方を示す図、第３０図は走行距離
（こよる引込み方法の手順を示すフローチャートである
。主要部分の符号の説明

Claims

【特許請求の範囲】

地図の道路上の各位置及び交差点位置を数値化して地図
データとして記憶する際、前記地図を細分化してエリア
単位で記憶しておき、車両の現在地から前記道路上の最
近傍位置又は最近傍交差点をサーチするときは、前記現
在地が属するエリア単位で行なうことを特徴とする地図
データのサーチ方法。