JP4875240B2 - ポリゴン道路ネットワークデータ作成装置、道路地図表示装置及び方法 - Google Patents

Description

技 術 分 野
本発明は、道路地図データを扱う地図画像処理技術に関わり、特に道路データの作成装置及び方法に関する。
技 術 背 景
電子的な地図画像データをコンピュータを用いて画面に表示する電子地図技術は、カーナビゲーションを始め様々なアプリケーションで活用されている。さて、地図一般において、道路を表示する場合、広域地図のような小縮尺の地図では、道路はその幅員を無視した単なる線として描いて問題はない。しかし、詳細市街地図のような大縮尺の地図では、道路は正確な幅員をもった領域として表示される必要がある。当然、電子地図においても、道路に幅員を持たせて表現するための道路データの作成方法や表示方法が色々と開発されている。例えば、特開昭６２−８０７７４号公報、特開平４−３０３２７１号公報、特開平４−３０３２７２号及び特開平６−８３９３１号公報に記載のものなどが知られている。
特開昭６２−８０７７４号公報に記載の図形処理装置は、幅員をもつ道路地図を作成する際に、人が道路輪郭を構成する直線を１本ずつ設定し描画するという面倒をなくすために、人が始点と終点と道幅を設定すると、その始点から終点へ道幅相当の間隔をもって走る平行線のペアを描画し、且つ、或る平行線ペアが他の平行線ペアと交差する場合には、その交点部分で平行線を自動的に消去する。従って、交差点を含む幅員をもった道路地図が簡易に作成できる。
特開平４−３０３２７１号公報に記載の装置は、人が道幅を設定してカーソルで基準線を描くと、その基準線に沿って道幅相当の間隔もって走る平行線のペアを描画する。
特開平４−３０３２７２号公報に記載の装置は、平行直線のペアとしてそれぞれ表現された２つの道路同士が角度をもって部分的に重なり合うとき、その重なり部分で平行線を修正して曲がり角を描画する。
特開平６−８３９３１号公報に記載の装置は、平行線ペアでそれぞれ表現された２つの道路同士を連結する場合に、平行直線のペアと弧状線とを用いて道路間の連結部分を描画する。
このように、従来技術によれば道路データは平行線のペアによって表現されている。しかし、実際の道路形状は非常に複雑であり、平行線ペアだけではこれを正確に表現することは到底できない。特に、中央分離帯や歩道や車線等を正確に描いた極めて大縮尺の詳細市街地図では、従来の平行線ペアを用いた道路データの作成技術は全く役に立たない。
さらに電子化された市街地図において、道路を色又はテクスチャで自動的に塗りつぶせるようにしたいという要求がある。紙ベースの市街地図では、道路を他の領域とは異なる色で着色することで見易くしたものが存在し、電子地図でも道路が特定色で塗りつぶされていれば当然に見易い。道路の塗りつぶしを自動的に行うためには、道路が閉ループの多角形データで表現されていなければならない。しかし、従来の道路データは平行線や弧状線などの単なる線分の集まり過ぎないから、道路の塗りつぶしを自動的に行うことはできない。従って、従来の電子的な市街地図では、多角形で表現された建物などは特定色で塗られているが、道路は単にその輪郭線が描かれているだけであって、特別の着色はなされていない。
また、電子地図は、縮尺の変更や、経路探索などの便利な機能を提供することができる。例えば、カーナビゲーション装置で経路探索を行なって地図上に経路を表示した上で、その経路に沿って自動車を走らせつつ、高速道路を走行中は小縮尺の広域地図を表示しておき、市街地に入ると大縮尺の市街地図に表示を切替えるというような使い方ができる。この場合、探索された経路が例えばＡ道路を通っているならば、広域地図上でも市街地図上でも、同じＡ道路に経路が表示されていなければならない。そのためには、広域地図上の各道路と、市街地図上の同じ道路とが論理的に関連付けられている必要がある。一般に、広域地図では、道路は単純な線として表示すればよいから、道路データは交差点をノードとし道路をノード間を結ぶベクトルデータで表現した道路ネットワークデータである。一方、市街地図では、道路データは上述のように道路の輪郭を示す平行線ペアや弧状線などの道路輪郭線分データの集合である。従来は、市街地図上の交差点の中心座標を、広域地図の道路ネットワークデータのノードに対応付けることで、市街地図上の道路と広域地図上の道路とを関連付けている。しかし、その結果、探索された経路は、市街地図上でも交差点の中心点間を結んだ折れ線で単純に表現され、これでは、道路形状を詳細に示した市街地図の利点を十分に生かしているとは言えない。
従って、本発明の目的は、複雑な道路形状に正確に一致する道路データを自動作成することにある。
本発明の別の目的は、幅員をもった道路を塗りつぶせるよう多角形データを用いた道路データを自動作成することにある。
本発明の更に別の目的は、広域地図で用いられる道路ネットワークデータと関連付けて、市街地図用の道路形状を正確に表した道路データを自動作成することにある。
本発明の更にまた別の目的は、上記目的を達成するための実用的な技術を開発する上で発生してくる、後述するような幾つかの具体的な技術的問題を解決することにある。
発 明 の 開 示
本発明に従う道路データ作成装置は、（１）交差点をノードとし道路をノード間を結ぶリンクにモデル化した道路ネットワークデータから、市街地図データ上の幅員をもった道路を内包する簡易道路多角形を生成し、（２）市街地図データから道路の輪郭線を規定する鋏データを作成し、そして、（３）鋏データが規定する輪郭線に沿って簡易道路多角形をトリミングすることにより、市街地図データ上の道路形状に整形された道路多角形データを作成する。結果として、市街地図上の複雑な形状をもった道路が多角形として表現される。
好適な実施形態では、簡易道路多角形を作成する際、一つのリンクについて独立した複数の簡易道路多角形が作成された場合、それら複数の簡易多角形を道路の外形に相当する外形多角形と、道路の中抜き面に相当する中抜き多角形とに識別する。これにより、中抜き面をもった閉ループ様の形状の道路も良好に多角形化できる。
好適な実施形態では、道路ネットワークデータのノードとリンクを市街地図データ上の道路の幅員よりも大きく膨張させることにより、市街地図上の道路を内包する簡易道路多角形を作成する。その際、ノードはリンクよりも大きく膨張させる。また、リンクの屈曲点も大きめに膨張させる。これにより、交差点や道路の曲がり角のような多少面積の広めの場所も確実に内包した簡易道路多角形が作成される。このように道路を完全に内包した簡易道路多角形を作成した上で、これを道路の輪郭線を示す鋏データでトリミングして余分な部分を削除することにより、道路の輪郭形状と良好に一致する道路多角形が得られる。
好適な実施形態では、鋏データを作成する場合、市街地図データ上の道路付近の形状線を選び出し、選び出した形状線のうち端点が互いに一致又は近接している形状線同士を連結し、連結により得られた線分データを鋏データとする。これにより、道路輪郭線を良好に示した鋏データが得られる。
好適な実施形態は、整形された道路多角形データから、複数の車線を表す複数の車線多角形データを作成する車線データ作成部と、上記車多角形データの各々の内部に誘導線を設定する誘導線設定部とを更に備える。
好適な実施形態は、前記道路ネットワークデータがカバーする全体地図領域の中の一部の地域の道路地図を表示する必要が生じたとき、前記一部の地域にのみ含まれる道路について前記整形された道路多角形データを動的に作成する。
本発明に従う道路地図表示装置は、表示しようとする道路の各々を多角形で表現した道路多角形データを含む多角形道路地図データと、上記道路多角形データを用いて前記道路を表示する表示部とを備える。
この道路表示装置の好適な実施形態では、多角形道路地図データは、道路内の各車線を多角形で表現した車線多角形データと、各車線内に設定された誘導線を表す誘導線データと更に含み、上記表示部は、道路を表示するだけでなく、上記車線多角形データを用いて道路内の各車線をも表示し、更に、上記誘導線データを用いて、選択された一つの車線内に位置した誘導マークをも表示する。
この道路表示装置の好適な実施形態は、道路ネットワークデータと、市街地図データと、上記道路ネットワークデータがカバーする全体地図領域の中の一部の地域の道路地図を表示する必要が生じたとき、道路ネットワークデータと市街地図データとに基づいて、表示すべき地域にのみ含まれる道路について道路多角形データを動的に作成する道路多角形データ作成部とを更に備える。
本発明に従う交差点多角形の作成装置は、交差点を表すノードと交差点間の道路を表すノード間のリンクとを持つ道路ネットワークデータと、地図要素の形状を形状要素点のセットで表現した線分データを持つ市街地図データとを受ける。そして、この装置は、道路ネットワークデータを市街地図データに投影し、道路ネットワークデータの注目ノードを内包する所定の検索領域を市街地図データ上で決定し、決定した検索領域内において、所定の位置的条件を満たすように位置する前記形状要素点を検索する。次に、この装置は、検索した形状要素点を用いて、注目ノードについての交差点多角形データを作成する。この装置によれば、道路ネットワークデータと線分ベースの市街地図データとから、交差点多角形データを自動的に作ることができる。作成された交差点多角形データは、道路ネットワークデータにノードへのデータ関連を必然的に有する。
好適な実施形態では、この装置は、上記検索領域を決定した後、注目ノードに接続するリンクを用いてその検索領域を複数のサブ検索領域に分割し、サブ検索領域の各々に対して固有の固有位置的条件を位置的条件として決定する。そして、この装置は、サブ検索領域の各々において、固有位置的条件を持たす前記形状要素点を検索し、それら複数のサブ検索領域で検索した形状要素点を集めて交差点多角形データを作成する。各サブ領域は交差点の各コーナ部の形状要素点を含んでいる。注目ノードと各コーナ部との位置関係は各コーナー部毎に異なるので、各サブ領域毎に各コーナ部に適合した固有の位置的条件を決定することによって、各コーナ部の形状要素点を的確に抽出できる。よって、正確な交差点多角形データが得られる。
好適な実施形態では、この装置は、前記検索領域内の複数のサブ検索領域の各々において、形状要素点の中で注目ノードに最も近い最近点を決定し、そして、注目ノードと最近点までの第１の距離と、第１の距離に所定の許容幅を加えた第２の距離との間の距離範囲だけ注目点から離れているバンド領域を設定する。そして、この装置は、各サブ検索領域において、そのバンド領域内に存在する形状要素点だけを、交差多角形を構成する点としてピックアップする。この方法により、高い精度で正確な交差点多角形が得られる。
好適な実施形態では、この装置は、市街地図データがカバーする市街地図領域をそれぞれ多数の小さいセルに分割し、それらのセルの中から、注目ノードに対応する位置に近接する少なくとも１個のセル（例えば、注目ノードが位置するセルと、それに隣接するセル）を対象セルとして選択し、この対象セル内で上記検索領域を決定する。この方法により、各交差点多角形作成処理で扱うデータの量が削減され、計算機の負担が軽減する。
好適な実施形態では、この装置は、更に、道路多角形データを持つ道路地図データを受け、そして、その道路多角形データと上述した交差点多角形データとが重複する領域をもつ場合には、その交差点多角形データを用いて道路多角形データから前記重複領域を除去して、交差点多角形データと重複しない純粋な道路多角形データを作成する。
好適な実施形態では、この装置は更に、交差点多角形データから、複数の道路に接する複数の接線を決定し、決定した複数の接線の中から２本の接線を抽出する。そして、この装置は、交差点多角形データがカバーする多角形領域内で、抽出した２本の接線同士を滑らかに結ぶ略セクタ状又は略矩形状の誘導用交差点多角形を作成する。
本発明に従う別の道路地図表示装置は、道路多角形データと誘導用交差点多角形データとを持つ道路地図データを受け、この道路地図データから、表示しようとする複数の道路の道路多角形データと、それら複数の道路を繋げるための誘導用交差点多角形データとを選択して、選択した道路多角形データと誘導用交差点多角形データを用いて、上記道路及び交差点表示する。
本発明のまた別の道路地図表示装置は、道路多角形データと交差点多角形データとを持つ道路地図データを受け、また、渋滞列の終端位置を示す渋滞情報を受ける。そして、この装置は、道路地図データから、渋滞列の終端位置が存在する道路又は交差点についての道路多角形データ又は交差点多角形データを選択し、選択した道路多角形データ又は交差点多角形データを前記終端位置で上流側領域部分と下流側領域部分とに分割する。そして、この装置は、分割した道路多角形データ又は交差点多角形データの下流側領域と、この下流側領域よりも渋滞列に沿って下流に存在する道路及び交差点についての道路多角形データ及び交差点多角形データを用いて、渋滞列の存在する道路及び交差点の領域を表示する。これにより、交通渋滞になっている道路の領域を正確に表示できる。
本発明のコンピュータ読取可能なデータ記録媒体は、道路ネットワークを構成するように相互に関連付けられたノードデータとリンクデータとを有し、各ノードデータは各ノードの交差点の形状を多角形で表現した交差点多角形データを含み、各リンクの道路の形状を多角形で表現した道路多角形データを含んでいるポリゴン道路ネットワークデータを格納している。
このポリゴン道路ネットワークデータを用いることで、コンピュータの地図アプリケーションは、市街地図に描かれている道路や交差点と形状及び位置が良好に一致したポリゴン道路地図画像を作成して表示することができるようになる。加えて、地図アプリケーションは、上記ポリゴン道路ネットワークデータを用いて経路探索又はマップマッチングなどの処理を行う場合、従来の道路ネットワークデータを用いた従来の経路探索又はマップマッチングのアルゴリズムの基本部分を利用することができる。
本発明の更に別の地図画像表示装置は、上述したポリゴン道路ネットワークデータと、このポリゴン道路ネットワークデータを受け、交差点を表現した多角形と道路を表現した多角形とからなるポリゴン道路画像を作成し表示する表示部とを備える。
好適な実施形態では、この道路地図表示装置は、更に市街地図データを備え、上記表示部が、その市街地図データを用いて市街地図画像を作成し、その市街地図画像に上記ポリゴン道路画像を重ねて表示する。また、表示部は、上記ポリゴン道路ネットワークデータを用いて経路探索又はマップマッチングなどの処理を行う機能をもつ。
本発明は典型的にはコンピュータを利用して実施することができるが、そのためのコンピュータプログラムは、各種ディスク型ストレージ、半導体メモリ、通信ネットワーク信号などの各種媒体を用いてコンピュータにインストール又はロードすることができる。本発明は、１台のコンピュータで実施することばかりでなく、複数台のコンピュータを用いた分散処理によって実施することができる。
発明を実施するための最良の形態
以下、本発明の一実施形態を図面を参照して具体的に説明する。
図１は、家枠や歩道形状などが詳細かつ正確に描かれた市街地図の一例を示している。図２は、交差点をノードとし道路をノード間を結ぶ方向付きベクトル（リンク）にモデル化して表現した道路ネットワークデータの一例を示している。
本発明の原理に従えば、図２に示したような道路ネットワークデータを図１に示したような市街地図に重ね合わせて以下に詳述するような処理を行うことにより、市街地図の道形形状を良好に再現した道路多角形データを生成することができる。図３は、そのようにして完成した道路多角形データをハッチングで塗りつぶした上で、図１に示した市街地図データに重ねて表示した例を示している。図３から分かるように、市街地図の複雑な道路形状に精度良く一致した道路多角形データが得られている。しかも、図示のように、道路の塗りつぶしが可能であるから、見やすい市街地図が提供できる。また、図２に示した道路ネットワークデータの各道路（交差点間のリンク）を、図３にハッチングで塗りつぶして示した道路多角形データの各道路多角形（交差点から交差点までの道路多角形）に１対１で関連付けることができる。その結果、例えば経路探索を行った場合、探索された経路を、市街地図上で、従来のような交差点中心を結ぶ単純な折れ線ではなく、塗りつぶされた道路それ自体で表現することができる。
図４は、本発明の一実施形態にかかる道路データ作成装置のシステム構成を示す。
この道路データ作成装置は、典型的にはプログラムされた汎用的なコンピュータである。このコンピュータの中央処理装置１は、プログラムに従って簡易道路多角形作成処理３、鋏データ作成処理６、及び道路多角形作成処理８を行う。このコンピュータの記憶装置上には、原料データとして、図２に例示したような交差点と道路をノードとリンクでモデル化した道路ネットワークデータを保存した道路ネットワークデータベース２と、図１に例示したような家枠や歩道形状等が詳細に描かれた市街地図データを保存した市街地図データベース５とが格納されている。
中央処理装置１は、まず簡易道路多角形作成処理３を行なう。この処理３では、道路ネットワークデータベース２に保存されている道路ネットワークデータに含まれている各道路の線分データ（各交差点間のリンクデータ）を市街地図データ５上の各道路幅員よりも大きく幅員方向へ膨張させることにより、市街地図データ５上の各道路の領域をそれより大き目にカバーする各道路毎の簡易道路多角形データを作成する。作成された各道路の簡易道路多角形データは記憶装置上の簡易道路多角形データベース４に集められ保存される。
中央処理装置１は、次に鋏データ作成処理６を行う。この処理６では、市街地図データベース５に保存されている市街地図データに含まれている道路輪郭や家枠などの線分データを基に、各道路の簡易道路多角形データをトリミングして正しい道路形状に生計するための鋏データ（トリミングのカッティングラインを示したデータ）を作成する。作成された各道路の鋏データは記憶装置上の鋏データベース７に集められ保存される。
中央処理装置１は、次に道路多角形作成処理８を行う。この処理８では、簡易道路多角形データベース４に保存されている各道路の簡易道路多角形データを、鋏データベース７からの各鋏データでトリミングして、各道路の正確な道路形状を表した道路多角形データを作成する。作成された道路多角形データは、記憶装置上の道路多角形データベース９に集められ保存される。
以下に、簡易道路多角形作成処理３、鋏データ作成処理６、及び道路多角形作成処理８を詳細に説明する。
図５は、簡易道路多角形作成処理３の手順を示す。
簡易道路多角形作成処理３は、まず、道路ネットワークデータベース２から対象地域の道路ネットワークデータを読み込む。一般的に道路ネットワークデータは交差点と道路をそれぞれノードとリンクにモデル化したものである。図５（ａ）に示すように、一つのリンク（道路）１１は、隣り合う２つのノード（交差点）１３，１５を結ぶ折れ線であり、始端のノード１３と途中の各形状要素点（屈曲点）１７、１７、…と終端のノード１５を順に結ぶ複数の直線分Ｌ１、…、Ｌｎを用いて表現されている。因みに、このような道路ネットワークデータは、例えば２万５千分の１縮尺の全国道路データから作成される。
簡易道路多角形作成処理３は、次に、図５（ａ）に示した各リンクの各線分Ｌ１、…、Ｌｎを、図５（ｂ）に示すように幅員方向（線分と直角の方向）に膨張させて、各線分Ｌｉを内包した要素多角形（例えば長方形）２１ｉを作成する。また、図５（ｃ）に示すように、各線分Ｌｉの始終点（両端の形状要素点）２３ｉ，２３ｉ＋１を全方向へ各線分Ｌｉより大きく膨張させて、各終始点２３ｉ，２３ｉ＋１を内包した要素多角形（例えば、円形に近い多角形）２５ｉ、２５ｉ＋１を作成する。その際、図５（ｄ）に示すように、特にノードに対応する要素多角形２５１、２５ｎ＋１は、他の形状要素点より更に大きく膨張させる。このようにリンクの各要素（ノード、線分、形状要素点）を膨張させて要素多角形を作る処理を、当該リンクの全ての要素について順番に行っていく。その結果、図５（ｄ）に示すように、当該リンクの全体を内包する多数の要素多角形２５１、２１１、…、２１ｎ、２５ｎ＋１のセットが出来上がる。次に、これらの要素多角形２５１、２１１、…、２１ｎ、２５ｎ＋１の領域和を計算することによって、図５（ｅ）に示すような当該リンクを内包した１つの簡易道路多角形２７を作成する。
この簡易道路多角形２７は、幅員をもった一つの道路の形状を大雑把に表現している。後に、この簡易道路多角形２７は、トリミングされることよって（つまり、余計な部分を切り取られることによって）、市街地図データが示す正確な道路の形状に整形されることになる。そのため、この簡易道路多角形２７は、市街地図データが示す正確な道路よりも大きい幅員を有して、正確な道路の領域を完全に内包している必要がある。この理由から、上述した膨張処理では、各線分Ｌｉの要素多角形２１ｉは、市街地図データが示す正確な道路の幅員より若干大きい幅員をもつように膨張される。その膨張量は、例えば図６に示すような方法で決定することができる。すなわち、図６に示すように、道路ネットワークデータの各リンクの線分Ｌｉを市街地図データ３１に重ね合わせ、そして、線分Ｌｉの複数地点から矢印で示すように両側へ垂線を伸ばし、それらの垂線が市街地図上の線分と最初に交わる点までの垂線の長さｄ１、ｄ２、…を測定する。これらの垂線の長さｄ１、ｄ２、…はそれぞれの地点付近の道路区間での当該道路の中心線から各側の縁線までの幅を代表した値であるとみなせる。そこで、道路の各側毎に、それら垂線の長さｄ１、ｄ２、…をそれぞれの地点が代表する道路区間の距離で重み付けて荷重平均を計算し、それを当該道路の中心線から各側の幅とみなす。最も簡単な計算例を示せば、図６の例の場合、図中上側の道路幅Ｗ１は、
Ｗ１＝（ｄ１＊Ｄ１＋ｄ２＊Ｄ２＋ｄ３＊Ｄ３＋ｄ４＊Ｄ４）÷（Ｄ１＋Ｄ２＋Ｄ３＋Ｄ４）
で決定され、下側の道路幅Ｗ２は、
Ｗ２＝（ｄ５＊Ｄ５＋ｄ６＊Ｄ６＋ｄ７＊Ｄ７＋ｄ８＊Ｄ８）÷（Ｄ５＋Ｄ６＋Ｄ７＋Ｄ８）
で決定される。こうして決定した道路幅Ｗ１、Ｗ２よりも適当程度さらに大きい距離Ｗ３、Ｗ４だけ、線分Ｌｉを上下方向に膨張させることにより、市街地図上の当該道路を完全に包含する要素多角形を作成することができる。更に、前述したように、線分Ｌｉの終始点やノードでは線分Ｌｉより大きく膨張させた要素多角形を作成するが、その理由は、その要素多角形内に道路の曲がり角や交差点（これらは、道路のまっすぐな箇所より大きい幅をもつこと多い）を確実に内包させるためである。
また、図５（ｄ）に示した複数の要素多角形２５１、２１１、２５２、２１２、…を図５（ｅ）に示す１リンクの簡易道路多角形２７へ変化させるための領域和の計算は、図７に示すような方法で行うことができる。例えば図７（ａ）に示すように、ある要素多角形Ｇ１が閉ループにされた多角形線分（ｆ１１，ｆ１２，…，ｆ１６）からなり、別の要素多角形Ｇ２が閉ループにされた多角形線分（ｆ２１，ｆ２２，…，ｆ２５）からなり、要素多角形Ｇ１とＧ２が部分的に重なっているとする。まず、図７（ｂ）に示すように、第１の要素多角形Ｇ１の線分で第２の要素多角形Ｇ２を切断する。その結果、第２の要素多角形Ｇ２の線分ｆ２２が切断され、新たに線分ｆ２２’と線分ｆ２２”が発生する。同様に線分ｆ２５も切断されて、新たに線分ｆ２５’と線分ｆ２５”が発生する。これら新たに発生した線分と切断されていない線分とを連結関係でグループ分けすると、複数グループに別れる。図７の例では、２つの線分グループ、つまり、第１グループＦ２１（＝ｆ２５’＋ｆ２１＋ｆ２２’）と第２グループＦ２２（＝ｆ２２”＋ｆ２３＋ｆ２４＋ｆ２５”）に分かれる。次に図７（ｃ）に示すように、第２の要素多角形Ｇ２の線分で第１の要素多角形Ｇ１を切断する。先ほどと同様に連結関係でグループ分けすると、図７の例では、第１の線分グループＦ１１（＝ｆ１１＋ｆ１２＋ｆ１３＋ｆ１４＋ｆ１５）と、第２の線分グループＦ１２（＝ｆ１６）に分かれる。
次に第１の多角形Ｇ１から発生した線分グループＦ１１及びＦ１２の各々について、第２の多角形Ｇ２の領域内に内包されているか否かを調べる内外判定を行う。内外判定の手法自体は公知である。その結果、第１の線分グループＦ１１は、第２の多角形Ｇ２の外領域に存在することが判明し、これは新多角形の外周線分とするために残す。一方、第２の線分グループＦ１２は多角形Ｇ２の内領域に存在することが判明し、これは破棄する。同様に第２の多角形Ｇ２から発生した線分グループＦ２１及びＦ２２についても、多角形Ｇ１に対する内外判定を行う。その結果、第１の線分グループＦ２１は、多角形Ｇ１の内領域に存在するので破棄し、第２の線分グループＦ２２は多角形Ｇ１の外領域に存在するので、新多角形の外周線分として残す。
最後に、図７（ｄ）に示すように、残った外周線分グループＦ１１とＦ２２を連結する。なお、図７では、Ｆ１１の終始点とＦ２２の終始点は離れた場所に描かれているが、実際は同一座標に存在するので、Ｆ１１とＦ２２は互いに連結することができる。このように残った外周線分グループを連結することで、新多角形Ｇが完成する。このような領域和処理を、図５（ｄ）に示した一つのリンクを構成する隣り合う全ての要素多角形間に適用することにより、図５（ｅ）に示した１つの簡易道路多角形２７が得られる。
ところで、例えば高速道路への螺旋状の進入道のように、地図上で閉ループ様の形状を呈する道路は、その簡易道路多角形はその領域内に中抜き面を有するものとなる。このようなケースでは、簡易道路多角形を作成する過程で、その簡易道路多角形の外形状を規定する外形多角形と、中抜き面を規定する中抜き多角形とを正しく識別する必要がある。図８は、このような場合の外形多角形と中抜き多角形の識別方法を示している。例えば、図８（ａ）に示すような形状をもつ道路リンク４１から図５及び図７に示した処理を行っていくと、図７（ｄ）に示した外周線分グループの連結が終わった段階で、図８（ｂ）に示すように、複数の独立した（つまり、互いに連結できない）簡易道路多角形４３、４５が発生することになる。なお、説明の単純化の為に２個の簡易道路多角形が発生した例を図８では示すが、道路形状によっては３個以上の独立した多角形が発生することもある。
さて、この例では、図８（ｃ）に示すように、第１の線分グループＡ（ａ１，…，ａ９）からなる簡易道路多角形４３と、第２の線分グループＢ（ｂ１，…，ｂ３）からなる簡易道路多角形４５が発生する。これらの独立した簡易道路多角形４３、４５のうち、いずれか一つは当該道路の外形多角形であり、他は中抜き多角形である。そこで、これらの簡易道路多角形４３、４５の内のどれが外形多角形であるかを決定するための処理を行う。すなわち、まず、それらの簡易道路多角形４３、４５の各々から線分上の代表点を１点づつ選び出す。次いで、各代表点について、当該代表点と他の全ての多角形との間で内外判定を行う。その結果、当該多角形の代表点が他の全ての多角形の領域外に存在する唯一の多角形を、当該道路の外形多角形と決定し、他の全ての多角形を中抜き多角形と決定する。例えば、図８において、多角形４３の代表点をａ１、多角形４５の代表点をｂ１とすると、多角形４５の代表点ｂ１は他の多角形４３の内部に存在し、多角形４３の代表点ａ１は他の全ての多角形４５の外部に存在する。従って、多角形４３が外形多角形であり、多角形４５が中抜き多角形である。このような外形多角形と中抜き多角形との識別は、図７に示すような方法で隣接する要素多角形のペアの領域和の計算を行う都度に実行する。そして、この要領で、１つの道路の始点ノードから終点ノードまで、隣接し合う要素多角形の領域和計算を繰り返すことによって、最終的に図５（ｅ）に示すような当該道路を内包する簡易道路多角形が完成される。これを道路ネットワークデータの全てのリンクデータについて行い、その結果を簡易道路多角形データベース４に記憶する。
次に、鋏データ作成処理６を説明する。
前述したように、鋏データは、実際の道路形状より大きめに作った簡易道路多角形をトリミングして正確な道路形状に整形するための、カットラインを規定するものである。従って、鋏データつまりカットラインは、道路の正確な外形状に沿って走っていて、道路内の領域には侵入していないことが理想的である。鋏データ作成処理６は、できるだけ理想に近い鋏データを作成するための処理である。
図９は、鋏データ生成処理６の手順を示している。
まず、図９（ａ）に示すように、市街地図データ５１の中から、各道路毎に、当該道路付近に存在する道路枠５３、５７、家枠５９、橋枠５５、水系線６１、６２、…、等さまざまな属性の形状線を抽出する。その際、抽出対象を各道路付近の形状線だけに絞り込むために（つまり、各道路の輪郭形状に関係のない形状線を除外するために）、例えば、市街地図を適当に細かいメッシュで多数のセグメントに区分しておき、道路ネットワークデータの各リンクを市街地図に重ねたときに、各リンクが通過するセグメント内に存在する形状線だけに抽出対象を絞り、更に、各リンクのｘｙ座標の最大値と最初値とで定義される矩形領域に含まれる形状線だけに抽出対象を絞るというような方法を採ることができる。
一般に市街地図データ５１上で道路の外形線を構成しているさまざまな属性の形状線は、互いに連結してない独立した線分データである。換言すれば、道路の輪郭線は、市街地図データ上では一線分ではなく、バラバラの独立した多数の線分の寄せ集めで構成されている。そこで、次に、抽出したさまざまな形状線の中から連結可能な線分５３、５５、５７、５９を選び出し、これらの線分を相互に連結して、図９（ｂ）に示すように１線分６３を作成する。ここで、連結可能な線分とは、ある線分の一端点（終点または始点）と他の線分の一端点の座標が完全に一致している線分同士、及び、図９（ｃ）に示す線分６５、６７のように、ある線分の一端点と他の線分の一端点との距離が所定の許容値γの範囲内にある線分同士（要するに、一線分を構成するとみなせる程度に十分近接している線分同士）を指す。従って、図９（ｄ）に示す例では、線分６７と線分６９の端点６７ａ、６９ａ間の距離は許容値γ以下であるから、線分６７と線分６９は連結される。一方、線分６７と線分７１の端点６７ａ、７１ａ間の距離は許容値γを超えているから、線分６７と線分７１は連結されない。
このようにして各道路付近の形状線を抽出し、それら形状線の中から連結可能な形状線を選んで一線分に連結することにより、その連結された線分データの中に、各道路の輪郭線データがかなり精度良く含まれることになる。この処理を市街地図データ中の各道路について行い、その結果として得られた各道路毎の連結された線分データを、各道路の簡易道路多角形に対する鋏データとして、鋏データベース７に記憶する。
ところで、近接した形状線同士を連結する際、たった２本の線分の端点同士が近接し合っているケースだけでなく、３本以上の線分の端点同士が近接し合っていているケースも多々がある。例えば、図１０（ａ）に示すように、線分７３、７５、７７、７９が同じ道路付近に存在し、２本の線分７３と７５の端点同士が一つの個所Ａで近接し合い、また、３本の線分７５と７７と７９の端点同士が別の個所Ｂで近接し合っているとする。この場合、最初の近接個所Ａでは、すでに説明した通り２本の線分７３と７５が単純に一本の線分に連結される。一方、２番目の近接個所Ｂでは、３本の線分７５と７７と７９を同時に連結して１本の線分にすることはできない。そこで、図１０（ｂ）、（ｃ）、（ｄ）に示すように、この１箇所Ｂに集まった３本以上の線分の端点を一つのノードとして扱い、このノードを介して１本の線分に連結できる２本の線分の組み合わせを全部ピックアップして、各組み合わせ毎に連結する。図１０の例では、３種類の組み合わせＶ１、Ｖ２、Ｖ３が存在するので、３本の連結線分Ｈ１、Ｈ２、Ｈ３が得られる。このようにした得た複数本の連結線分Ｈ１、Ｈ２、Ｈ３の全てを当該道路についての鋏データとして、鋏データベース７に記憶する。
次に、道路多角形作成処理８を説明する。
道路多角形作成処理８は、各道路毎に、その道路の簡易道路多角形をその道路の鋏データを用いてトリミングすることにより、その道路の正確な輪郭形状を表した道路多角形を作成する処理である。すなわち、簡易道路多角形データベース４から各道路の簡易道路多角形データを読み込み、鋏データベース７から各道路の鋏データを読み込み、各道路毎に、その道路の全ての鋏データの各々が、その道路の簡易道路多角形データを貫通しているかを調べる。例えば、図１１（ａ）に示す例では、簡易道路多角形８１を５本の鋏データ９１、９３、９５、９７が貫通している。次に、貫通している鋏データの各々を用いて、簡易道路多角形８１を切断する。
各鋏データ毎に、その鋏データの線分で簡易道路多角形を切断すると、簡易道路多角形は２つの線分グループに分かれる。そのうち、道路ネットワークデータのノードを内包している方（つまり、道路内側）の線分グループを残し、他方（つまり、道路外側）の線分グループは破棄する。同様にその鋏データも簡易道路多角形の線分で切断し、それにより分かれた鋏データの複数の線分グループのうち、簡易道路多角形に内包されている方の線分グループのみを残す。そして、残した簡易道路多角形の線分グループと、残した鋏データの線分グループとを連結することにより、その鋏データに沿って道路外側の部分が切除された新しい簡易道路多角形が得られる。
このような各鋏データによるトリミングを、貫通する全て鋏データについて繰り返すことにより、最終的に道路の輪郭形状にかなりの精度で一致した道路多角形が得られる。例えば、図１１（ａ）に示した大雑把な形状の簡易道路多角形８１を、それを貫通する全ての鋏データ９１、９３、９５、９７でトリミングすると、その結果、図１１（ｂ）に示すように、市街地図上の道路形状に精度良く整形された道路多角形１０１が得られる。このようなトリミングを全ての簡易道路多角形とそれを貫通する全ての鋏データとの間で行い、そうして作成された道路多角形データを道路多角形データベース９に記憶する。
以上の一連の処理により、市街地図上で表現される道路の形状に精度良く一致する道路多角形を自動的に作成できる。このデータはその特性上、道路ネットワークデータとの相性も良く、道路ネットワークデータから作成される広域地図などとのリンク関係も明確になる。また道路ネットワークデータの保持している道路関連情報も、道路多角形に関連付けて保持することが可能になる。
ところで、上述した道路多角形を用いた道路地図データでは、各交差点から隣の交差点までの各道路の領域が１つの多角形で表現される。この道路地図データの構成例を図１２（Ａ）に示し、この道路地図データに基づき画面に表示された道路画像を図１２（Ｂ）に示す。図１２（Ａ）に示すように、この道路地図データは複数の道路多角形２０１、２０３、２０５のデータから構成される。ここで、交差点の領域は、道路多角形２０１、２０３、２０５から区別されてはおらず、道路多角形２０１、２０３、２０５に含まれている。表示された道路画像上では、図１２（Ｂ）に示すように、複数の道路多角形２０１、２０３、２０５同士が重なり合った領域２０７を、人間が視覚的に交差点だと認識する。しかし、道路地図データを利用する計算機上のアプリケーションは、道路地図データ上で交差点の領域と道路の領域とを正確に区別して認識したり指し示したりするができない。
道路地図データを、従来の用途より高度な用途に利用したいという要求がある。例えば、カーナビゲーションにおける目的地までのルート誘導において、従来は、そのルートを交差点間を直線で結ぶ単なる折れ線分で表示している。しかし、それよりも、そのルートを構成する道路及び交差点の領域そのものを強調して表示する方法の方が、ユーザにとってより見易い。後者のルート表示を行う場合、ルートの交差点部分を見栄良く表示するためには、多角形ベースの道路地図データ上で交差点が道路多角形から正確に区別された独立した多角形として表現されている方が望ましい。図１２（Ａ）に示したように交差点が道路多角形に含まれていると、例えば道路多角形２０１から道路多角形２０３へ折れるルートを表示する場合、この２つの道路多角形２０１、２０３が重なる領域２０７が交差点として不自然な形状をもつため、見栄えが悪い。
また、出発地から目的地までルートを決定するルート探索処理は、従来から存在する例えば１／２．５万縮尺の道路ネットワークデータ（交差点はノード（座標点）で表現され、道路はノード間を結ぶ方向付きベクトルで表現されている）に基づいて行われる。そのため、上述した多角形を用いたルート表示を行うためには、道路地図データの交差点多角形及び道路多角形が、道路ネットワークデータの交差点ノード及び道路ベクトルとデータ関連をもっていることも必要である。
さらに、誘導ルートの交差点部分の表示に関し、図１３（Ａ）に示すように交差点２０９の全領域を誘導ルート２１１として表示するよりも、図１３（Ｂ）に示すように、交差点２０９内の走行路線だけを誘導ルート２１３として表示した方が分かり易い。しかし、交差点の領域全体を１つの多角形として定義した交差点多角形データだけでは、このような図１３（Ｂ）に示したような分かり易いルート表示を行うことはできない。
これらの課題を解決するには、道路だけでなく交差点もそれぞれ独立した多角形で表現された道路地図データを作成することが望ましい。
図１４は、道路と交差点をそれぞれ多角形を表現した道路地図データを作成するための本発明の一実施形態にかかる装置のシステム構成を示す。
この道路地図データ作成装置は、典型的にはプログラムされた汎用的なコンピュータである。このコンピュータの中央処理装置３０１は、プログラムに従って前処理３０４、交差点多角形作成処理３０５、道路多角形補正処理３０８、及び誘導用交差点多角形作成処理３１０を行う。このコンピュータの記憶装置上には、原料データとして、交差点と道路をノードとリンクでモデル化した道路ネットワークデータを保存した道路ネットワークデータベース３０２と、家枠や歩道形状等が詳細に描かれた線分ベースの市街地図データを保存した市街地図データベース３０３と、道路ネットワークデータと市街地図データに基づいて例えば図４〜図１１を参照して既に説明した方法で作成された道路多角形データ（図１２に例示したように交差点領域を含む）を保存した道路多角形データベース３０７、が存在する。
中央処理装置３０１は、まず前処理３０４を行なう。この前処理３０４は、道路ネットワークデータと市街地図データをメモリに展開し、道路ネットワークデータと市街地図データの地図空間座標を一致させ、そして、道路ネットワークデータと市街地図データをそれぞれ多数のセル（均等な小サイズの多数の矩形領域）に分割して、セル単位の各地図データを管理できるようにする。
次に、中央処理装置３０１は交差点多角形作成処理３０５を行う。この処理３０５は、前処理３０４の後の道路ネットワークデータと市街地図データに基づいて交差点多角形データを作成して、作成した交差点多角形データを交差点多角形データベース３０６に蓄積する。
次に、中央処理装置３０１は道路多角形補正処理３０８を行う。この処理３０は、道路多角形データベース３０７から読み込んだ道路多角形データ（交差点領域を含む）を、交差点多角形データベース３０６からの交差点多角形データを用いて補正することにより、交差点領域を含まない道路多角形データ（以下、「純粋道路多角形データ」という）を作成して、作成した純粋道路多角形データを純粋道路多角形データベース３０９に蓄積する。
次に、中央処理装置３０１は誘導用交差点多角形作成処理３１０を行う。この処理３１０は、交差点多角形データベース３０６からの交差点多角形データと、純粋道路多角形データベース３０９からの純粋道路多角形データとに基づいて、同じ交差点に接続する２つの道路多角形データ間を図１３（Ｂ）に例示したようにスムーズに連結するような誘導用の交差点多角形データを作成して、作成した誘導用交差点多角形データを誘導用交差点多角形データ３１１に蓄積する。
以下に、前処理３０４、交差点多角形作成処理３０５、道路多角形補正処理３０８、及び誘導用交差点多角形作成処理３１０を詳細に説明する。まず、図１５〜図１７を参照して、前処理３０４を説明する。
前処理３０４では、中央処理装置３０１内のメモリに、データベース３０２からの道路ネットワークデータとデータベース３０３からの市街地図データを展開する。しかし、一般に、図１５に示すように、道路ネットワークデータが表す地図領域３１３と、市街地図データが表す地図領域３１５とは、座標空間（例えば、左下端の座標原点の緯度経度）において不一致である。そこで、この２つの地図領域３１３、３１５の座標空間を次のようにして一致させる。すなわち、両座標空間の位置ずれ（Δｘ、Δｙ）を
Δｘ＝道路ネットワーク地図領域原点経度−市街地図領域原点経度
Δｙ＝道路ネットワーク地図領域原点緯度−市街地図領域原点緯度
で計算する。そして、元の市街地図座標（ｘ１、ｙ１）と道路ネットワーク座標（ｘ１、ｙ２）は、それぞれ以下のように、共通座標空間上の市街地図座標（ｘ′１、ｙ′１）と道路ネットワーク座標（ｘ′１、ｙ′２）に変換される。
（ｘ′１、ｙ′１）＝（Ｆ１ｘ（ｘ１）、Ｆ１ｙ（ｘ１））
（ｘ′１、ｙ′２）＝（Ｆ２ｘ（ｘ１）、Ｆ２ｙ（ｘ１））
ここに、変換関数Ｆｉｘ（），Ｆｉｙ（）は（Δｘ、Δｙ）及び各地図領域３１３、３１５の右上端の最大座標（Ｘｉ，Ｙｉ）を使用したリニア変換関数である。
このような座標変換を道路ネットワークデータと市街地図データに施すことで、両データの座標空間が一致し、それにより、図１６に示すように、道路ネットワークデータ３１７の各ノード３１９を市街地図データ３２１の対応する位置３２３に投影することが可能になる（この投影は、後の交差点多角形作成処理３０５で行われる）。
前処理３０４では、次に、後の交差点多角形作成処理３０５での幾何計算量を減らすために、メモリ上に展開した市街地図データと道路ネットワークデータを、それぞれ、多数のセル（小さい矩形領域）に分割してセル単位で管理する。すなわち、当初、図１７（Ａ）に示すように、各地図データは、それがカバーする全体の地図領域３２５内に存在する全ての地図要素３２７へのポインタが登録された地図要素管理テーブル３２９を有している。前処理３０４では、図１７（Ｂ）に示すように、各地図データの全体地図領域３２５を均等サイズの多数のセル３３１に分割する。そして、地図要素管理テーブル３２９内の地図要素へのポインタの集合を、各セル３３１内に存在する地図要素へのポインタの集合に分類して、各セル毎のポインタ集合３３３に各セルのインデックス３３５を付す。これにより、各セル内に存在する地図要素だけが、各セルから指されるようになる。もし１つの地図要素が複数のセルに跨る場合は、それら複数のセルからその地図要素が指されるようにしておく。このようにして作成された、地図要素をセル別に管理したテーブル３３７を、以下「インデックステーブル」という。インデックステーブル３３７は、道路ネットワークデータ及び市街地図データの各々について作成さえる。セルのサイズは小さくすればするほど、幾何計算の対象データ数が少なく絞り込まれるが、管理しなければならないセル数が増加する。よって、セルのサイズは、ケースバイケースで最適値に決定する。
次に、図１８〜図２５を参照して、交差点多角形作成処理３０５を説明する。
交差点多角形作成処理３０５では、まず、道路ネットワークデータ内の全ノードデータを順番に取り出す。そして、取り出した個々のノードに注目し、図１８（Ａ）に示すように、注目ノード３３９が属するセル３４１を、前処理３０４で作成されたインデックステーブル３３７を利用して決定する。そして、図１８（Ｂ）に示すように、注目ノード３３９が属するセル３４１と同じセル番号を持つ市街地図のセルと、これに隣接する全てのセルを、対象領域３４３として選択する。
このように注目ノードに対する対象領域３４３が絞りこまれたら、次に、図１９に示すように、道路ネットワーク地図内の注目ノード３３９とこの注目ノード３３９に接続するリンクＬ１〜Ｌ４を、市街地図の対象領域３４３内の家枠や道路枠や歩道境界等の地図要素に重ねる。そして、ノード重心を中心とした所定半径Ｒの円形領域（検索範囲）３４５から、市街地図の地図要素の形状要素点３４７を探す。ここで、「ノード重心」とは、注目ノード３３９そのもの、又は注目ノード３３９から所定距離範囲内に存在する全ての形状要素点から計算される重心（これは、注目ノード３３９が実際の交差点の中心からかなりずれているときに、有利である）である。図１９の例では、分かりやすくするために、注目ノード３３９をノード重心としている。また、「形状要素点」とは、線分ベースの市街地図の地図要素（折れ線分）の端点やコーナ点である。
検索範囲３４５から形状要素点３４７を検索する際、まず、注目ノード３３９に接続するリンクＬ１〜Ｌ４間の角度θ１〜θ４を求める（要するに、検索領域３４５を、リンクＬ１〜Ｌ４で複数のセクタＳ１〜Ｓ４に区分する）。ここで、θ１はＬ１とＬ２間の角度、θ２はＬ２とＬ３間の角度、θ３は３とＬ４間の角度、θ４はＬ４とＬ１間の角度である。そして、各角度θｉ（ｉ＝１，２，３，４）の範囲（つまり各セクタＳｉ）ごとに、形状要素点３４７を検索する。
図２０は、最初の角度θ１の範囲（最初のセクタＳ１）での検索結果の例を示している。このセクタＳ１から検索した全ての形状要素点Ｐ１，Ｐ２，Ｐ３…の各々について、ノード重心３３９からの距離ｄ１、ｄ２、ｄ３、…を計算し、その結果を、図２１に示すように、検索結果テーブル３４９に蓄積していく。セクタＳ１内の全ての形状要素点について距離算出が終了したら、図２１の検索結果テーブル３４９を距離の昇順にソートし、セクタＳ１内で最小距離を持つ形状要素点Ｐｊを見つける。例えば、図２０において、形状要素点Ｐ３の距離ｄ３が最小であったとする。次に、図２２に示すように、その最小距離ｄ３からそれに所定の許容幅εだけ加えた距離ｄ３＋εまでの円弧状のベルト範囲Ｂ１を設定し、このベルト範囲Ｂ１内に存在する形状要素点Ｐ１〜Ｐ５を、交差点多角形を構成する形状要素点として抽出する。そして、抽出した形状要素点Ｐ１〜Ｐ５を、図２３に示すように、交差点多角形要素テーブル３５１に登録する。このとき、形状要素点Ｐ１〜Ｐ５の各々の角度（ノード重心３３９を回転中心にして、例えばｘ軸方向を角度０として例えば右回りに角度を測ったときの、各形状要素点の角度）γ１〜γ５も、交差点多角形要素テーブル３５１に登録する。
以上の処理を他のセクタＳ２，Ｓ３，Ｓ４についても同様に繰り返す。すると、図２４に示すように、全てのセクタＳ１〜Ｓ４のバンド範囲Ｂ１〜Ｂ４から抽出された交差点多角形を構成する形状要素点３５３のデータが、図２３に示した交差点多角形要素テーブル３５１に蓄積される。次に、交差点多角形要素テーブル３５１に登録された形状要素点３５３を角度γの昇順にソートする。角度γの順番に形状要素点３５３を並べと、図２５に示すような交差点多角形３５５が定義される。こうして作成された交差点多角形データを、図１４に示した交差点多角形データベース３０６に蓄積する。
以上の交差点多角形データの作成処理を、道路ネットワークデータの全てのノードについて繰り返す。
次に、図２６及び図２７を参照して、道路多角形補正処理３０８を説明する。
道路多角形補正処理３０８では、交差点多角形データベース３０６に蓄積された交差点多角形データを用いて、道路多角形データベース３０７に蓄積されている交差点領域を含む道路多角形データから交差点領域を除去する。図２６に示すように、注目ノード３３９についての交差点多角形データベース３０６からのデータが表す交差点多角形３５５と、注目ノード３３９に接続するリンクＬ１についての道路多角形データベース３０７からのデータが表す道路多角形データ３５７とは、ハッチングで示した領域３５９にて重なり合っている。そこで、道路多角形３５５と交差点多角形３５７との間で領域差分の幾何演算を行うことにより、道路多角形３５５から重なり領域３５９を取り除く。
この交差点多角形３５７による領域差分演算を、注目ノード３３９に接続する全てのリンクの道路多角形に関して繰り返す。その結果、図２７に示すように、交差点多角形３５７と重ならずに接した純粋道路多角形３６１、３６３、３６５、３６７が得られる。この純粋道路多角形３６１、３６３、３６５、３６７のデータを純粋道路多角形データベース３０９に登録する。
次に、図２８〜図３３を参照して、誘導用交差点多角形作成処理３１０を説明する。
誘導用交差点多角形作成処理３１０では、まず、図２８に示すように、注目ノード３３９の交差点多角形３５７と、リンクＬ１の純粋道路多角形３６１との接線Ｃ１を抽出する。接線Ｃ１は、図２９に示すような折れ線であり、
Ｃ１＝（ｐ１、ｐ２、ｐ３、…）
と表現できる。接線Ｃ１の始点ｐ１と終点ｐ５だけを取り出して、始点ｐ１と終点ｐ５を結ぶ直線である仮想接線ｃ１を作る。つまり、
ｃ１＝（ｐ１、ｐ５）
である。
同様にして、交差点多角形３５７に接する他の道路多角形３６１、３６３、３６５、３６７についても、接線Ｃ２，Ｃ３，Ｃ４を抽出し、仮想接線ｃ２、ｃ３、ｃ４を求める。次に、これらの仮想接線ｃ１、ｃ２、ｃ３、ｃ４の中から、任意に２つの仮想接線を取り出す。例えば仮想接線ｃ１とｃ２を取り出したとすると、次に、図３０に示すように、仮想接線ｃ１と仮想接線ｃ２の延長線の交点Ｋ１を求める。この交点Ｋ１にて仮想接線ｃ１とｃ２のなす角度をθとする。この角度θが所定値以上である場合は、交点Ｋ１から仮想接線ｃ１とｃ２の外側端点ｐ１２とｐ２２までの距離ｄ１とｄ２を算出する。そして、長い方の距離ｄ１をもつ仮想接線ｃ１の外側端点ｐ１２から、他方の仮想接線ｃ２へ向けて、交点Ｋ１を中心にした円弧ａ１を伸ばし、この円弧ａ１と仮想接線ｃ２の延長線との交点Ｋ２で円弧ａ１を止める。こうして求まった外側端点ｐ１２から交点Ｋ２までの円弧ａ１を、誘導用交差点多角形の一つの輪郭線とする。同じ誘導用交差点多角形の他の輪郭線として、交差点多角形３５５の輪郭線をそのまま利用する。つまり、交差点多角形３５５を円弧ａ１で２つの領域に切ったときの、交点Ｋ１に近い側の領域を、誘導用交差点多角形とする。結果として、図３１に示すような誘導用交差点多角形３７１が完成する。
図３０に示した処理で、交点Ｋ１での仮想接線ｃ１とｃ２のなす角度θが所定値より小さい（つまり、仮想接線ｃ１とｃ２が平行に近い）場合は、図３２に示すように、仮想接線ｃ１の端点ｐ１１、ｐ１２と仮想接線ｃ２の端点ｐ２１、ｐ２２を矩形ができるように直線ｂ１、ｂ２で接続する。この２本の直線ｂ１、ｂ２と、元の接線Ｃ１，Ｃ２とから構成される多角形を、誘導用交差点多角形３７３とする。
以上の誘導用多角形を作成する処理を、Ｎ差路の交差点の場合、Ｎ個の道路多角形の集合から選ぶことのできる２個の道路多角形の組合せの全部に関して行う。すると、例えば図３３（Ａ）に示すような４差路の交差点の場合、図３３（Ｂ）〜（Ｇ）に示すような６個の誘導用交差点多角形３８１、３８３、３８５、３８７、３８８、３８９が作成される。作成された誘導用交差点多角形のデータを、誘導用交差点多角形データベース３１１へ格納する。全ての交差点について、上記の誘導用交差点多角形作成処理３１０を繰り返す。
以上のようにして作成された交差点多角形データ、純粋道路多角形データ及び誘導用交差点多角形データは、様々な用途に利用することができる。その一つは、カーナビゲーションにおけるルート誘導である。図３４（Ａ）に示すように、従来のルート誘導では、折れ線３９１でルートを示していた。これに対し、純粋道路多角形データと誘導用交差点多角形データとを用いると、図３４（Ｂ）に示すように、純粋道路多角形データと誘導用交差点多角形データとを繋いだ実際のルート形状に近いルート多角形３９３で、ルートを表示することができる。
別の一つの用途は、カーナビゲーションにおける道路渋滞表示である。図３５〜図３７を参照して、道路渋滞表示の方法を説明する。
例えば日本の財団法人道路交通情報通信システムセンターのＶＩＣＳ（Ｖｅｈｉｃｌｅ Ｉｎｆｏｒｍａｔｉｏｎ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）（登録商標）から提供される渋滞情報は、上り車線と下り車線の各々について、渋滞列の始端と終端の位置を、最初と最後の交差点からの距離をそれぞれ用いて指定する。その一例を図３５に示す。図３５では、上り車線（ノードＮ２からノードＮ１へ向かって走行する車線）について、渋滞列の終端がノードＮ１の交差点からＨメートルと指定された場合を示している。この場合、図３６に示すように、その上り車線が通るノードＮ１に接続したリンクＬ１（折れ線である）に沿って距離Ｈだけ、ノードＮ１から離れた渋滞列終端点Ｐｈの座標を計算する。
次に、渋滞列終端点ＰｈからリンクＬ１の両側へ、リンクＬ１に垂直な直線４０９、４１１を伸ばす。そして、それら垂線４０９、４１１と、ノードＮ１の交差点多角形４０３、リンクＬ１の純粋道路多角形４０５及びノードＮ２の交差点多角形４０７との交点を求める。そして、次の処理（１）〜（３）をこの順序で行う。
（１） 起点ノードＮ１の交差点多角形４０３と垂線４０９、４１１との交点が有る場合（つまり、渋滞列終端点Ｐｈが交差点多角形４０３内に存在する場合）、交差点多角形４０３を垂線４０９、４１１で２つの領域に切って、ノードＮ１に近い方の（つまり、車の流れで下流側の）領域だけを渋滞列であると判断する。交差点多角形４０３と垂線４０９、４１１との交点が無い場合（つまり、渋滞列終端点Ｐｈが交差点多角形４０３より上流側に存在する場合）、交差点多角形４０３の全域を渋滞列であると判断し、次の（２）のステップへ進む。
（２） リンクＬ１の道路多角形４０５と垂線４０９、４１１との交点（例えば４１０、４１２）が有る場合（つまり、渋滞列終端点Ｐｈが道路多角形４０５内に存在する場合）、道路多角形４０５を垂線４０９、４１１で２つの領域に切って、ノードＮ１に近い方の（つまり、下流側の）領域だけを渋滞列であると判断する。道路多角形４０５と垂線４０９、４１１との交点が無い場合（つまり、渋滞列終端点Ｐｈが道路多角形４０５より上流側に存在する場合）、道路多角形４０５の全域を渋滞列であると判断し、次の（３）のステップへ進む。
（３） 終点ノードＮ２の交差点多角形４０７と垂線４０９、４１１との交点が有る場合（つまり、渋滞列終端点Ｐｈが交差点多角形４０７内に存在する場合）、交差点多角形４０７を垂線４０９、４１１で２つの領域に切って、ノードＮ１に近い方の（つまり、下流側の）領域だけを渋滞列であると判断する。交差点多角形４０７と垂線４０９、４１１との交点が無い場合（つまり、渋滞列終端点Ｐｈが交差点多角形４０７より上流側に存在する場合）、交差点多角形４０７の全域を渋滞列であると判断する。
次に、図３７に示すように、渋滞列と判断された多角形領域、つまり、渋滞列終端点Ｐｈでの垂線４０９、４１１より下流側の道路及び交差点多角形の領域４０５Ａ、４０３、４０１を、ハッチングで示すように、渋滞列を示す色又はテクスチャで塗りつぶして表示する。渋滞列の始端についても、上記と同様の処理で、始端より上流側の多角形領域だけを渋滞列を示す色又はテクスチャで塗りつぶして表示する。つまり、上記の処理を渋滞列の終端と始端について行うことで、渋滞列の始端から終端までの正確な道路領域が強調表示される。
なお、図３８に示すように、個々の車線を１つの道路と捉えて車線で区別された道路及び交差点の多角形データ４１１〜４３３を作成することもでき、その場合には、渋滞表示やルート表示を車線別に行なうことができる。例えば、図３８では、片方の車線の渋滞部分がハッチングで示されている。
個々の車線を表した多角形データを作成することは、上述したように地図上の渋滞している車線を識別して示したり、カーナビゲーションでドライバーを正しい車線に誘導したりするために、とても有用である。図３９〜図４５は、個々の車線を表した多角形データを作成するための一方法例を示している。
図３９に示すように、道路ネットワークデータのノード５１１、５１３及びリンク５１５の位置は、市街地図から作成した交差点ポリゴン５０１、５０５及び純粋道路ポリゴン５０９と、必ずしも位置的に整合しているとは限らない。そこで、まず、交差点ポリゴンの幾何重心５０３、５０７をそれぞれ求め、その各幾何重心５０３、５０７を各交差点ポリゴン５０１、５０５の新しいノードと定義する。
次に、図４０に示すように、交差点ポリゴン５０１、５０５と純粋道路ポリゴン５０９との間の接線５２１、５２３、並びに純粋道路ポリゴン５０９を貫くリンク５１５に注目する。そして、その接線５２１、５２３とそのリンク５１５との交点５３１、５３３を抽出する。
次に、図４１に示すように、リンク５１５上の一方の交点５３１から他方の交点５３３までの間の適当間隔の複数位置から、リンク５１５に垂直な線５４１〜５４４をリンク５１５の両側へ延ばす。そして、それらの垂線５４１〜５４４と、純粋道路ポリゴン５０９の上記接線５２１、５２３以外の輪郭線５５１、５５３との交点５６１〜５６８を求める。
次に、図４２に示すように、上のように求めた交点５６１〜５６８を、垂線５４１〜５４４の端点とする。そして、それらの垂線５４１〜５４４と上記接線５２１、５２３の各々を、この道路のもつ車線の本数Ｎで等分する。ここで、この道路のもつ車線の本数Ｎは、道路ネットワークデータに含まれるリンク５１５の属性データから得ることができ、１以上の整数である（Ｎ＝１の場合は、当然ながら、その純粋道路ポリゴン自体が既にその単一の車線を表している）。図４２の例では、車線本数Ｎは２であり、そのため、各垂線５４１〜５４４と各接線５２１、５２３は、各々の中点５７２〜５７５、５７１、５７６で２等分される。そして、これらの中点を順番に通る線分５８１を求め、この線分５８１で、この純粋道路ポリゴン５０９を２つのサブ道路ポリゴン５９１、５９３に分割する。得られた２つのサブ道路ポリゴン５９１、５９３を、この道路のもつ２本の車線を表した車線ポリゴンとして、道路地図データに登録する。
更に、図４２に示すように、各車線ポリゴン５９１、５９３の中に、カーナビゲーションのための車両誘導線を設定する（Ｎ＞１の場合だけでなく、Ｎ＝１の場合も行う）。車両誘導線は、上述した車線ポリゴン５９１、５９３を区分する線分５８１を求めたときの方法と同様の方法で求めることができる（Ｎ＝１の場合、線分５８１が車両誘導線となる）。すなわち、車線ポリゴン５９１、５９３の各々の内側で、上記垂線５４１〜５４４と上記接線５２１、５２３の各々の中点（図４２では白抜き丸印で示す）を求め、それらの中点を順番に通る線分（図４２では破線で示す）を求め、この線分を各車線ポリゴン５９１、５９３の車両誘導線として、道路地図データに登録する。
さらに、２本以上の車線を持つ道路に接する各交差点ポリゴンの中にも、複数の車線ポリゴンと誘導線を設定する。
図４３は、交差点ポリゴン６０１内に、図中の上の道路の２本の車線ポリゴン６１１、６１３と、下の道路の２本の車両ポリゴン６１５、６１７とを結ぶ、直進用の２本の交差店内車線ポリゴン６２１、６２３を設定した例を示している。図示してないが、同様に、左の道路の複数本の車線６３１〜６３４と右の道路の複数の車線６４１〜６４４とを結ぶ直進用の複数本の交差店内車線ポリゴンも設定される。図中の破線は、各車線ポリゴン内に設定された車両誘導線を示している。
図４４は、交差点ポリゴン６０１内に、左側通行の場合の左折（右側通行の場合の右折）用の車線ポリゴン６５１〜６５４を作成した例を示す。この例では、図中で左右に走る道路の最外側の車線ポリゴン６３１、６４１、６３４、６４４と、上下に走る道路の最外側の車線ポリゴン６１１、６１３、６１５、６１７とが、交差点内車線ポリゴン６５１〜６５４によってそれぞれ結ばれている。交差点内車線ポリゴン６５１〜６５４のカーブした輪郭線は、クロソイド曲線、円弧、楕円弧、放物線、双曲線または折れ線などで表現することができる。図中の破線は、各車線ポリゴン内に設定された車両誘導線を示している。
図４５は、交差点ポリゴン６０１内に、左側通行の場合の右折（右側通行の場合の左折）用の車線ポリゴン６６１、６６３を作成した例を示す。この例では、図中で左右に走る道路の内側の車線ポリゴン６３３、６４２と、上下に走る道路の内側の車線ポリゴン６１３、６１７とが、交差点内車線ポリゴン６６１、６６３によってそれぞれ結ばれている。交差点内車線ポリゴン６６１、６６３のカーブした輪郭線は、クロソイド曲線、円弧、楕円弧、放物線、双曲線または折れ線などで表現することができる。図中の破線は、各車線ポリゴン内に設定された車両誘導線を示している。
このように各交差点ポリゴン内に直進や右左折に必要な車線ポリゴンを予め用意しておき、各車線ポリゴン内に誘導線を設定しておくことにより、交差点での車両の誘導を正確に行うことができる。図４３〜図４５に示した交差点内の車線ポリゴンは、説明のための例示に過ぎない。交差する道路の車線本数、各車線の走行方向（固定的に定まっている場合もあるし、時間帯によって切換わる場合もある）、適用される交通法規などに応じて、用意するべき交差点内車線ポリゴンの種類は異なる。
さて、以上説明した交差点ポリゴン、純粋道路ポリゴン及び車線ポリゴンの作成は、静的な方法と動的な方法のいずれ方法でも行うことができる。静的な方法とは、地図の全域にわたり全ての交差点ポリゴン、純粋道路ポリゴン及び車線ポリゴンを先に作成して地図データベースに格納しておく方法である。道路地図を表示する際には、データベースから表示すべき地域のポリゴンを読み出して表示することができる。一方、動的な方法とは、前もって全てのポリゴンを作成しておくことはせずに、道路地図を表示する都度に、必要な区域の必要なポリゴンだけを、市街地図データと道路ネットワークデータから作成する方法である。静的な方法は、ふんだんに大きい記憶容量をもつ道路地図表示装置に適している。一方、動的な方法は、カーナビゲーション装置のような、十分大きい記憶容量が確保し難い地図表示装置に適している。
カーナビゲーション装置などで動的にポリゴン地図データを作成する場合、ポリゴンデータの作成に使える時間が短く限られているため、ポリゴンデータ化する道路の取捨選択が重要になる。図４６は、カーナビゲーション装置で動的にポリゴン地図データを作成する際のポリゴン作成の対象の地域的範囲をどこに限定するかという点についての、一つの原理を示している。
図４６に示すように、ポリゴン作成の対象の地域は、自動車が停止しているか超低速で走行しているときは、その自動車の位置７０１（図示の三角マークは図中上方へ向いて走行していることを示す）をほぼ中心とした、所定半径のほぼ円形の地域７１１とする。自動車が中速で走行しているときは、その自動車の位置７０１を後端部に含む、その自動車の進行方向へより長く延びたほぼ楕円形または卵形の地域７１３を、その対象地域とする。自動車の速度がより上がると、その自動車の位置７０１を後端部に含む、その自動車の進行方向へより一層細長く延びたほぼ楕円形または卵形の地域７１５を、その対象地域とする。
図４７〜図４９は、上記の原理の下での具体的なポリゴン作成対象地域の選定方法を示す。
カーナビゲーション用の地図は、一般に、多数の小面積の矩形の区域（メッシュ）に分割されて管理されている。そのため、道路や交差点のポリゴンを動的に生成する対象の地域は、複数のメッシュの集合となる。
図４７に示すように、停止時または超低速走行時には、自動車の現在位置７０１（三角マークは図中上方へ走行していることを示す）を含むメッシュＭ０と、このメッシュＭ０を包囲する例えば隣接の８個のメッシュＭ１〜Ｍ８を、ポリゴン作成の対象とする。そして、自動車の進行方向（停止時は、指向している方向）に応じて、その自動車が次の時点で存在する可能性（つまり、ドライバーが必要とする可能性）のより高いメッシュほどを先順位にするという順序で、これらのメッシュＭ０〜Ｍ８を処理していく。すなわち、最初に、現在位置７０１を含むメッシュＭ０を処理して道路や交差点のポリゴンを作成する。次に、現在位置のメッシュＭ０の前方にあるメッシュＭ２を処理する。その次が、進行方向の左右斜め前方のメッシュＭ１とＭ３（順不同）であり、その次が、現在位置のメッシュＭ０の左右のメッシュＭ４とＭ５（順不同）であり、その次が、現在位置のメッシュＭ０の左右斜め後方のメッシュＭ６とＭ７（順不同）であり、最後が、現在位置のメッシュＭ０の後方のメッシュＭ７である。
図４８に示すように、中速走行時には、現在位置７０１の後方は無視し、進行方向に存在するより多くのメッシュを、ポリゴン作成の対象とする。例えば、現在位置のメッシュＭ０と、その前方及び左右の８個のメッシュＭ１〜Ｍ８を対象とする。そして、やはり、進行方向に応じて、その自動車が次の時点で存在する可能性（つまり、ドライバーが必要とする可能性）のより高いメッシュほどを先順位にするという順序で、これらのメッシュＭ０〜Ｍ８を処理していく。すなわち、最初が、現在位置のメッシュＭ０であり、次が、現在位置のメッシュＭ０の前方にあるメッシュＭ５、その次が、更に前方及び左右斜め前方にあるメッシュＭ２とＭ４とＭ６（順不同）、その次が、左右斜め更に前方にあるメッシュＭ１とＭ３（順不同）、最後が、左右隣のメッシュＭ７とＭ８（順不同）である。
図４９に示すように、高速走行時には、自動車の現在位置７０１から進行方向前方に存在するより一層多くの数のメッシュ（走行速度によって増減するであろうが、例えば１８個のメッシュＭ０〜Ｍ１７）を処理対象とする必要がある。この場合、中速以下のときのように、対象のメッシュ内の全ての道路及び交差点をポリゴン化するのは、装置の性能及びドライバー安全性の観点から、得策ではない。そこで、ドライバーにとって必要性が或る程度以上高い道路及び交差点を選択して、その選択した道路及び交差点のみをポリゴン化する。例えば、その自動車が現在走行している道路の種別と同じ種別の道路及び交差点のみを選択するとか、或いは、その同じ種別の道路及び交差に加えて、予め決めておいた優先順位が高い種別の道路及び交差点を選択するというようにである。ここで、道路の種別とは、例えば「国道１０号線」とか「靖国通り」といった道路固有名称、及び「国道」、「県道」、「市道」、「自動車専用道路」、「高速道路」などといった道路分類名称のことであり、道路ネットワークデータに含まれるリンクの属性データから得られる。
ポリゴン化する道路及び交差点の数又は種別は、自動車の走行速度ｖに応じて、増減することができる。例えば次の原理に従った増減方法を採用することができる。すなわち、現在の走行速度ｖでポリゴン化処理を行う必要のあるメッシュの個数をＮとし、１メッシュのサイズ（一辺の長さ）をＸとし、１メッシュ内で作成すべきポリゴンの平均的個数をｍとしたとき、１メッシュの処理に要する平均的時間Ｓ（ｍ）が次式を充たすように、１メッシュ当たりの作成ポリゴン数ｍを決定する。
Ｓ（ｍ）・Ｎ＝Ｘ／ｖ
つまり、自動車が１メッシュ分の距離を通過するのに要する時間Ｘ／ｖ内に、処理対象のＮ個のメッシュの全てのポリゴン化処理を終えるように、１メッシュ当たりの作成すべき平均的ポリゴン数ｍを決定する。そして、１メッシュ当たりの実際に作成する平均的ポリゴン数が、上記のｍを超えないように、ポリゴン化対象の道路種別を選定する。
以上のような方法で動的に道路及び交差点ポリゴンを作成することにより、自動車の走行速度に応じた適切なドライバ誘導を行うことができる。
図５０は、本発明の一実施形態にかかる道路地図表示装置を示す。
この道路地図表示装置８００は、市街地図データ８０１と、ポリゴン道路ネットワークデータ８０３と、表示部８０５とを有する。ポリゴン道路ネットワークデータ８０３は、従来のノードとリンクから構成される道路ネットワークデータにおけるノードの形状データを点データから本発明の方法で作成した交差点ポリゴンデータに置き換え、リンクの形状データを線分データから本発明の方法で作成された純粋道路ポリゴンデータに置き換えたものである。更に、このポリゴン道路ネットワークデータ８０３には、上述したような純粋道路ポリゴンを分割したレーンポリゴンデータや交差点ポリゴン内に設定した交差点内レーンポリゴンデータを含むこともできる。表示部８０５は、市街地図データ８０１から市街地図画像を描画し、ポリゴン道路ネットワークデータ８０３から市街地図上の道路と交差点の形状に合致した形状をもつ道路ポリゴンと交差点ポリゴンの画像を描画し（必要あれば、それらポリゴンを特定の色で塗りつぶし）、そして、市街地図画像上に道路ポリゴンと交差点ポリゴンの画像を重ねて表示する。これにより、市街地図上の道路と交差点の形状に良好に合致した領域が道路及び交差点として表示される。また、例えばこの装置８００がカーナビゲーションに用いられる場合、表示部８０５は、ポリゴン道路ネットワークデータ８０３を用いて出発地から目的地までの道路経路を探索する経路探索機能や、ポリゴン道路ネットワークデータ８０３を用いて自動車の現在位置を或る道路ポリゴン又は或る交差点ポリゴン内に入るように修正したりする。
図５１は、ポリゴン道路ネットワークデータ８０３の構造を示す。
ポリゴン道路ネットワークデータ８０３には、個々のノード（交差点）を表すノードデータ９０１と、個々のリンク（道路）を表すリンクデータ９０３と、ノードとリンクの関連性を表す関連データ９０５とが含まれている。関連データ９０５は、例えば、特定の一つのノードのノードデータ９０１に、特定のｎ本のリンクのリンクデータ９０３が接続しているというような、ノードとリンクの接続関係を示している。
各ノードデータ９０１は、そのノードの属性を示す属性データ９１３と、そのノードの形状を示す形状データ９１５とを含む。各リンクデータ９０３は、そのノードの属性を示す属性データ９１７と、そのノードの形状を示す形状データ９１９とを含む。ここで、関連データ９０５及び属性データ９１３、９１７としては、道路ポリゴンデータや交差点ポロゴンデータを作成する最に用いた従来の道路ネットワークデータのそれを流用することができる。一方、ノードの形状データ９１５は、そのノードの交差点ポリゴンデータであり、リンクの形状データ９１９は、そのリンクの純粋道路ポリゴンデータである。
要するに、このポリゴン道路ネットワークデータ８０３は、先述したように、従来の道路ネットワークデータにおいて、各ノードの形状データとして従来の点データを交差点ポリゴンデータに置き換え、かつ、各リンクの形状データとして従来の線分データを純粋ポリゴンデータに置き換えたものである。そのため、例えばカーナビゲーションシステムなどで、このポリゴン道路ネットワークデータ８０３を用いて経路探索やマップマッチングなどの処理を行う場合、従来の道路ネットワークデータを用いた従来の経路探索アルゴリズムや従来のマップマッチングの基本部分を流用することができる。また、このポリゴン道路ネットワークデータ８０３を用いて作成した道路地図画像は、道路及び交差点の形状と位置において、市街地図画像と良好にマッチするので、ユーザにとって見やすいものとなる。
上述した実施形態は本発明の説明のための例示に過ぎず、本発明をこの実施形態のみに限定する趣旨ではない。本発明は、上述の実施形態以外の様々な形態で実施することができる。
【図面の簡単な説明】
図１は、家枠や歩道形状等々の詳細に描かれた市街地図データの例を示す図。
図２は、交差点をノードとし道路をノード間を結ぶ方向付きベクトルにモデル化して持つ道路ネットワークデータの例を示す図。
図３は、本発明の原理に従って完成した道路多角形データを、市街地図データに重ねて表示した例を示す図。
図４は、本発明の一実施形態にかかる道路多角形作成装置のシステム構成を示すブロック図。
図５は、簡易道路多角形作成処理の手順を示す説明図。
図６は、道路幅員を測る方法を示す説明図。
図７は、要素多角形の領域和を計算する手順を示す説明図。
図８は、外形多角形と中抜き多角形を示す説明図。
図９は、鋏データ作成処理の手順を示す説明図。
図１０は、３本以上の線分が近接する場合の鋏データの作成方法を示す説明図。
図１１は、道路多角形作成処理の手順を示す説明図。
図１２は、道路多角形による交差点の表現を示す図。
図１３は、道路多角形と交差点多角形を用いたルート誘導の例を示す図。
図１４は、本発明の別の実施形態にかかる道路多角形作成装置の概略構成を示すブロック図。
図１５は、市街地図と道路ネットワーク地図の座標空間における不一致を説明する図。
図１６は、道路ネットワークデータを市街地図データへ投影した図。
図１７は、セル分割を説明する図。
図１８は、対象セルを説明する図。
図１９は、道路ネットワーク地図と市街地図を重ねた状態での形状要素点の検索を説明した図。
図２０は、θ１のセクタＳ１での検索を説明した図。
図２１は、セクタＳ１内の最小距離を持つ要素点を見つける為のテーブルを示す図。
図２２は、交差点多角形を構成する要素点を説明する図。
図２３は、交差点多角形を構成する要素点を蓄積したテーブルを示す図。
図２４は、全てのセクタから交差点多角形を構成する要素点を検索した結果を示す図。
図２５は、交差点多角形が完成を示す図である
図２６は、道路多角形と交差点多角形の重なりを示す図。
図２７は、交差点多角形と重ならない純粋な道路多角形を示す図。
図２８は、道路多角形と交差点多角形との接線を示す図。
図２９は、実際の接線と仮想の接線の関係を説明した図。
図３０は、２つの仮想接線から、誘導用交差点多角形の一つの輪郭線となる円弧を作る方法を説明した図。
図３１は、図３０に示した円弧を用いて作った誘導用交差点多角形を示す図。
図３２は、ほぼ平行な２本の仮想接線から誘導用交差点多角形を作る方法を説明した図。
図３３は、四差路交差点の場合に作成される６種類の誘導用交差点多角形を示す図。
図３４は、従来のルート誘導の表示例と、誘導用交差点多角形を利用したルート誘導の表示例とを示した図。
図３５は、渋滞を通知する情報の内容を説明した図。
図３６は、渋滞列の終端の位置を決める方法を説明した図。
図３７は、渋滞列を表示した例を示す図。
図３８は、車線別に渋滞列を表示した例を示す図。
図３９は、純粋道路内に車線ポリゴンを作成する第１のステップを示す図。
図４０は、純粋道路内に車線ポリゴンを作成する第２のステップを示す図。
図４１は、純粋道路内に車線ポリゴンを作成する第３のステップを示す図。
図４２は、純粋道路内に車線ポリゴンを作成する第４のステップを示す図。
図４３は、交差点内の直進用車線ポリゴンの例を示す図。
図４４は、交差点内の左側通行の左折用の車線ポリゴンの例を示す図。
図４５は、交差点内の左側通行の右折用の車線ポリゴンの例を示す図。
図４６は、カーナビゲーション装置で動的にポリゴン地図データを作成する際のポリゴン化対象の地域的範囲をどこに限定するかという点の原理を示した図。
図４７は、停止時または超低速走行時のポリゴン作成対象地域の選定方法を示す図。
図４８は、中速走行時のポリゴン作成対象地域の選定方法を示す図。
図４９は、高速走行時のポリゴン作成対象地域の選定方法を示す図。
図５０は、本発明の一実施形態にかかる道路地図表示装置を示すブロック図。
図５１は、交差点及び道路の形状をポリゴンで表現したポリゴン道路ネットワークデータの構造を示す図。

Claims (7)

1. 交差点を多角形として表現した交差点多角形データと、道路を多角形として表現した道路多角形データと、前記交差点を点として表現したノードデータと、前記道路をノード間を結ぶベクトルとして表現したリンクデータとを含み、前記交差点多角形データ及び前記道路多角形データが、前記ノードデータ及び前記リンクデータに対し、それぞれ一対一で関係付けられているポリゴン道路ネットワークデータを記録したコンピュータ読取可能な記録媒体。
2. 前記ポリゴン道路ネットワークデータに更に、前記道路内の車線を、前記道路の多角形が分割された多角形として表現した車線多角形データが含まれている請求項１記載のコンピュータ読取可能な記録媒体。
3. 交差点を多角形として表現した交差点多角形データと、道路を多角形として表現した道路多角形データと、前記交差点を点として表現したノードデータと、前記道路をノード間を結ぶベクトルとして表現したリンクデータとを含み、前記交差点多角形データ及び前記道路多角形データが、前記ノードデータ及び前記リンクデータに対し、それぞれ一対一で関係付けられているポリゴン道路ネットワークデータを受けるデータ入力部と、
   前記データ入力部が受けたポリゴン道路ネットワークデータを用いて、前記交差点の多角形画像と前記道路の多角形画像を含むポリゴン道路画像を作成し表示する表示部と
   を備えた道路地図表示装置。
4. 前記ポリゴン道路ネットワークデータには、更に、前記道路内の車線を、前記道路の多角形が分割された多角形として表現した車線多角形データが含まれており、
   前記ポリゴン道路画像には、更に、前記車線の多角形画像も含まれる請求項３記載の道路地図表示装置。
5. 前記データ入力部が受けたポリゴン道路ネットワークデータ内の前記ノードデータ及びリンクデータを用いて、経路探索を行う経路探索部を更に備えた請求項３記載の道路地図表示装置。
6. 交差点を多角形として表現した交差点多角形データと、道路を多角形として表現した道路多角形データと、前記交差点を点として表現したノードデータと、前記道路をノード間を結ぶベクトルとして表現したリンクデータとを含み、前記交差点多角形データ及び前記道路多角形データが、前記ノードデータ及び前記リンクデータに対し、それぞれ一対一で関係付けられているポリゴン道路ネットワークデータを受けるステップと、
   前記ポリゴン道路ネットワークデータを用いて、前記交差点の多角形画像と前記道路の多角形画像を含むポリゴン道路画像を作成し表示するステップと
   を道路地図表示装置が行う道路地図表示方法。
7. 交差点を多角形として表現した交差点多角形データと、道路を多角形として表現した道路多角形データと、前記交差点を点として表現したノードデータと、前記道路をノード間を結ぶベクトルとして表現したリンクデータとを含み、前記交差点多角形データ及び前記道路多角形データが、前記ノードデータ及び前記リンクデータに対し、それぞれ一対一で関係付けられているポリゴン道路ネットワークデータを受けるステップと、
   前記ポリゴン道路ネットワークデータを用いて、前記交差点の多角形画像と前記道路の多角形画像を含むポリゴン道路画像を作成し表示するステップとをコンピュータに実行させるコンピュータプログラムを格納したコンピュータ読み取り可能な記録媒体。

Images