(57)【要約】【課題】  地図データに用いられる道路ポリゴンの自動生成時の労力の増大を回避しつつ、地図の見栄えを向上する。【解決手段】  地図データ生成装置は、道路をノード・リンクで表現したネットワークデータ４０を読み込み、これを加工して道路ポリゴンを含むポリゴンデータ５０を生成する。道路ポリゴンの生成は、リンクに対して幅を持たせて矩形状のポリゴンを生成する工程、ポリゴンに縁線を施す工程、不要な縁線を消去する工程などを含む。地図データ生成装置は、矩形状のポリゴンを生成した後、各ポリゴンと他のポリゴンとの接続状態や両者の形状、属性に基づいて末端形状決定方法を使い分けて、ポリゴンの末端形状を決定する。こうすることにより、ポリゴン同士の接続部分における見栄えを向上させることができる。【選択図】  図１
2006301601.tif 000002
【特許請求の範囲】
【請求項１】
地図を描画するための地図データを生成する地図データ生成装置であって、
前記地図データに含まれる道路の描画に用いられる複数のポリゴンの形状を決定するために用いられる幾何データおよび属性を入力する基礎データ入力部と、
処理の対象となる対象道路および該対象道路に接続すべき接続道路双方の属性、並びに前記幾何データに基づいて定まる形状、および向きの少なくとも一部に基づき、前記道路ポリゴンの末端形状を決定するために予め用意された複数種類の決定方法のうちいずれを適用すべきかを選択し、
該選択された決定方法に従って、前記幾何データに応じて前記各ポリゴンの末端形状を求め、道路のポリゴンを描画するためのポリゴンデータを生成するポリゴンデータ生成部とを有する地図データ生成装置。
【請求項２】
請求項１記載の地図データ生成装置であって、
前記幾何データは、道路の接続状態をノード・リンクで表したネットワークデータであり、
前記ポリゴンデータ生成部は、前記リンクから所定距離の位置にある点群からなる側線、および前記末端形状により、前記ポリゴンの形状を決定する地図データ生成装置。
【請求項３】
請求項１または２記載の地図データ生成装置であって、
前記ポリゴンデータ生成部は、前記対象道路および接続道路の道路種別の異同に基づいて前記選択を行う地図データ生成装置。
【請求項４】
請求項３記載の地図データ生成装置であって、
前記ポリゴンデータ生成部は、前記対象道路に対して前記接続道路が複数存在する場合に、該対象道路および複数の接続道路の全ての道路種別が同一である場合と、その他の場合とで前記選択のための条件を切り換える地図データ生成装置。
【請求項５】
請求項３または４記載の地図データ生成装置であって、
前記ポリゴンデータ生成部は、前記対象道路に対して前記接続道路が複数存在する場合に、前記対象道路と種別が同一となる接続道路が存在するか否かで前記選択のための条件を切り換える地図データ生成装置。
【請求項６】
請求項１〜５いずれか記載の地図データ生成装置であって、
前記ポリゴンデータ生成部は、前記対象道路および接続道路の幅の異同、および両者間の接続角度の少なくとも一方に基づき前記選択を行う地図データ生成装置。
【請求項７】
請求項１〜６いずれか記載の地図データ生成装置であって、
前記末端形状の決定方法は、前記対象道路および接続道路の側線同士の交点を結ぶ線分で該末端形状を規定する方法を含む地図データ生成装置。
【請求項８】
請求項１〜７いずれか記載の地図データ生成装置であって、
前記末端形状の決定方法は、前記対象道路が凸ポリゴンとなるよう、該対象道路の側線間を結ぶ折れ線によって該末端形状を規定する方法を含む地図データ生成装置。
【請求項９】
地図を描画するための地図データを生成するためのコンピュータプログラムであって、
前記地図データに含まれる道路の描画に用いられる複数のポリゴンの形状を決定するために用いられる幾何データおよび属性を入力するサブプログラムと、
処理の対象となる対象道路および該対象道路に接続すべき接続道路双方の属性、並びに前記幾何データに基づいて定まる形状、および向きの少なくとも一部に基づき、前記道路ポリゴンの末端形状を決定するために予め用意された複数種類の決定方法のうちいずれを適用すべきかを選択するためのサブプログラムと、
該選択された決定方法に従って、前記幾何データに応じて前記各ポリゴンの末端形状を求め、道路のポリゴンを描画するためのポリゴンデータを生成するサブプログラムとを有するコンピュータプログラム。
【請求項１０】
地図を描画するための地図データを生成する地図データ生成装置であって、
前記地図データに含まれる道路の描画に用いられる複数のポリゴンの形状を決定するために用いられる幾何データおよび属性を入力する基礎データ入力部と、
前記複数のポリゴンの少なくとも一部を所定の規則に基づいてグループ化するグループ化部と、
前記グループに基づき、前記幾何データを用いて前記ポリゴンを描画するためのポリゴンデータを生成するポリゴンデータ生成部とを有する地図データ生成装置。
【請求項１１】
請求項１０記載の地図データ生成装置であって、
前記幾何データは、道路の接続状態をノード・リンクで表したネットワークデータであり、
前記ポリゴンデータ生成部は、前記リンクから所定距離の位置にある点群からなる側線、および前記末端形状により、前記ポリゴンの形状を決定する地図データ生成装置。
【請求項１２】
請求項１０または１１記載の地図データ生成装置であって、
前記グループ化部は、前記ポリゴンが表す道路の名称、および該道路に付された通行規制の少なくとも一方を用いて前記グループ化を行う地図データ生成装置。
【請求項１３】
請求項１０〜１２いずれか記載の地図データ生成装置であって、
前記属性には、前記ポリゴンが表す道路の道路種別が含まれており、
前記グループ化部は、前記道路種別が同一のポリゴン間で前記グループ化を行う地図データ生成装置。
【請求項１４】
請求項１０〜１３いずれか記載の地図データ生成装置であって、
前記グループ化部は、前記複数のポリゴン間の接続角度に基づき前記グループ化を行う地図データ生成装置。
【請求項１５】
請求項１０〜１４いずれか記載の地図データ生成装置であって、
前記ポリゴンデータ生成部は、前記道路の縁線を表すための縁線データを前記各ポリゴンに付す縁線処理部を有し、
前記縁線処理部は、前記グループ化されたポリゴンの縁線が連続となるよう前記縁線データを生成する地図データ生成装置。
【請求項１６】
地図を描画するための地図データを生成するためのコンピュータプログラムであって、
前記地図データに含まれる道路の描画に用いられる複数のポリゴンの形状を決定するために用いられる幾何データおよび属性を入力するサブプログラムと、
前記複数のポリゴンの少なくとも一部を所定の規則に基づいてグループ化するグループ化サブプログラムと、
前記グループに基づき、前記幾何データに基づいて前記ポリゴンを描画するためのポリゴンデータを生成するするポリゴンデータ生成サブプログラムとを有するコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図を描画するための地図データを生成する技術に関する。
【背景技術】
【０００２】
電子地図データは、コンピュータ、ナビゲーション装置などの画面上への地図の表示に利用される。この電子地図データは、建造物その他の地物、道路、鉄道などを表す種々のポリゴンデータで構成されている。従来、地図データの生成にかかる人手を軽減するため、これらのポリゴンデータ、特に道路を描画するためのポリゴンデータを自動的に生成する技術が種々提案されている。
【０００３】
例えば、特許文献１は、経路探索用のデータ、即ちノード・リンクから構成されたネットワークデータを利用し、それぞれのリンクデータに幅を持たせることによってポリゴンデータを自動生成する技術を開示している。また、生成されたポリゴン同士が折れ線状につながる部分を円弧で滑らかに整形したり、幅の異なるポリゴン同士の接続部分をテーパ状に整形する技術も開示されている。特許文献２は、ネットワークデータに幅を持たせてポリゴンデータを生成した後、高架道路か否かなど、道路の上下関係を判断して、道路の縁線データを生成する技術を開示している。
【０００４】
【特許文献１】特開平６−８３９３７号公報
【特許文献２】特開２００２−３３３８２９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
電子地図データに対しては、地図の見栄えの更なる向上、生成に要する労力の更なる軽減が要請されていた。例えば、道路は、国道、県道などの種別によって色分け表示されることがある。このような色分け表示を行う場合、国道と県道とが接続される交差点での各ポリゴンの形状次第では、不自然な色分けがなされることがあり地図の見栄えを損なうおそれがある。かかる箇所の見栄えを向上するため、オペレータが、こうした箇所の形状を手作業で決定していては、地図データ生成に多大な労力が要求されることとなる。
【０００６】
別の例として、例えば、２本の道路が比較的近接して併走している場合を考える。例えば、上下線を別々のリンクで形成している場合や、高架道路の下側を他の道路が併走している場合などが該当する。このようなリンクに幅を持たせることでポリゴンを自動生成した場合には、これらの２本の道路を構成するポリゴン同士が重なる可能性がある。地図の描画上の違和感を回避するため、このように重なったポリゴンについては、一方を優先し、他方の縁線を消去する必要が生じる。この場合、道路の縁線が不連続とならないようにするためには、併走する２本の道路のうちいずれか一方を統一的に優先し、他方の縁線を統一的に消去することが望まれる。従来、こうした処理は、オペレータが逐一、手作業で決定する必要があり、多大な労力が要求されていた。本発明は、これらの課題に鑑み、地図の描画上の違和感を生じにくい道路ポリゴンを自動生成する技術を提供することを目的とする。
【課題を解決するための手段】
【０００７】
本発明は、地図を描画するための地図データを生成する地図データ生成装置として構成することができる。この地図データ生成装置は、地図データに含まれる道路の描画に用いられる複数のポリゴンの形状を決定するために用いられる幾何データおよび属性を入力する。そして、処理の対象となる対象道路および対象道路に接続すべき道路（以下、「接続道路」と呼ぶ）双方の属性、並びに前記幾何データに基づいて定まる形状、および向きの少なくとも一部に基づき、道路ポリゴンの末端形状を決定するために予め用意された複数種類の決定方法のうちいずれを適用すべきかを選択する。そして、地図データ生成装置は、選択された決定方法に従って、幾何データに応じて各ポリゴンの末端形状を求め、道路のポリゴンを描画するためのポリゴンデータを生成する。この処理過程では、いずれの決定方法も適用しないという選択肢を含めても良い。この場合には、幾何データから得られる最も原始的な形状をそのままポリゴンデータとして適用すればよい。
【０００８】
本発明は、接続道路の属性等を考慮することにより、接続道路との接続上、最も適した方法で対象道路の末端形状を決定することができる。例えば、表示上の違和感が少なくなるよう、末端形状の決定方法を使い分けることができる。こうすることで、表示上の違和感が少ないポリゴンを比較的軽い負荷で生成することができる。
【０００９】
幾何データとしては、予め用意された原形状のポリゴンデータ自体を用いても良いし、地図データ生成装置がポリゴンデータを生成するために使用するデータを用いてもよい。後者の例として、例えば、道路の接続状態をノード・リンクで表したネットワークデータを幾何データとし、地図データ生成装置は、この幾何データを利用してポリゴンデータを生成するようにしてもよい。リンクとは、道路を線分または折れ線で表したものであり、ノードとはリンクの端点である。
【００１０】
ポリゴンの形状は、リンクから所定距離の位置にある点群からなる側線、および末端形状に基づいて決定することができる。距離とは、リンクに直角方向の長さである。側線および末端形状を表す折れ線または線分データを求め、これらを結合してポリゴンデータを生成してもよい。また、各リンクが対称軸となる一定幅の矩形の仮ポリゴンデータを一旦求め、この末端形状を修正して最終的なポリゴンデータを生成するようにしてもよい。リンクからの所定距離または矩形のポリゴンの幅は、例えば、リンクに対応づけられた属性、例えば、国道や県道などの道路種別、車線数、道路幅などの情報に基づいて決定することができる。
【００１１】
地図データ生成装置は、先に説明した通り、種々の決定方法を使い分けて末端形状を求める。本明細書における「選択」には、広義には末端形状の整形有無も含んでおり、例えば、種々の条件によって末端形状の整形処理を行う場合／行わない場合を切り換える態様も本発明の概念には含まれることになる。
【００１２】
上述の使い分けは、種々の条件で行うことが可能である。例えば、対象道路および接続道路の道路種別の異同に基づいて選択するようにしてもよい。この態様には、道路種別の異同のみを条件として選択する場合のみならず、道路種別の異同以外の条件も併せて考慮した上で選択する場合も含まれる。
【００１３】
交差点などのように、対象道路に接続される接続道路が複数存在する場合がある。かかる場合には、対象道路および複数の接続道路の全ての道路種別が同一である場合と、その他の場合とで選択のための条件を切り換えるようにしてもよい。例えば、道路を描画する際の色やパターンを道路種別に応じて選択する場合を考える。接続されている全ポリゴンの道路種別が同一であれば、これらの全ポリゴンには、統一的なパターンまたは色が付されることになるため、各ポリゴンの末端形状は地図の見栄えにほとんど影響を与えない。これに対して、異種のポリゴンが含まれている場合には、このポリゴンの末端形状は地図の見栄えに大きな影響を与えることになる。上述の態様によれば、全ポリゴンの道路種別が同一か否かで使い分け条件を選択することにより、見栄えの確保、処理負荷の軽減などの要素を考慮しながら適した方法で末端形状の決定を行うことが可能となる。
【００１４】
また、接続道路に対象道路と同一種別の道路が存在するか否かによって、処理を選択するようにしてもよい。また、上述のように複数の接続道路が存在する場合、対象道路と接続道路との道路種別の異同のみならず、接続道路同士の道路種別の異同を考慮するようにしてもよい。例えば、接続道路中に道路種別が同一となる接続道路が２以上存在する場合と、その他の場合とで選択のための条件を切り換えるようにしてもよい。
【００１５】
また、別の態様として、対象道路および接続道路の幅の異同、および両者間の接続角度の少なくとも一方に基づき選択するようにしてもよい。接続角度とは、ポリゴンの対称軸のなす角度、またはポリゴンが表す道路の進行方向のなす角度を言う。これらの形状的な要素を考慮して末端形状を選択することにより、地図の見栄えを向上することが可能となる。幅の異同については、例えば、対象道路と接続道路の幅が同じである場合と異なる場合に分ける態様としてもよいし、後者を更に細分化し、対象道路の幅が接続道路の幅よりも広い場合、狭い場合に分ける態様としてもよい。
【００１６】
末端形状は、種々の方法で決定することができる。第１の方法として、対象道路および接続道路の側線同士の交点を求め、この交点を結ぶ線分で末端形状を規定する方法が挙げられる。交点の位置によって、決定前の矩形状の末端の一部を削除する形、矩形状の末端を延長する形、一部を削除しつつ一部を延長する形のいずれの場合もある。このような処理の過程で鋭角状の角が形成される場合には、円弧で角を削除するフィレット処理を施してもよい。
【００１７】
更に、対象道路と接続道路の接続角度が比較的浅く、側線同士の交点を用いると、ポリゴン形状がいびつになる場合には、このような交点に代えて、接続道路の測線上において対象道路側の端点から所定距離にある点を用いて、対象道路の末端形状を決定するようにしてもよい。
【００１８】
第２の方法として、対象道路が凸ポリゴンとなるよう、対象道路の側線間を折れ線で結んで末端形状を規定するようにしてもよい。凸ポリゴンとは、いずれの対角線もポリゴンからはみ出さない形状など末端形状を凸形状にしたポリゴンを言う。かかる形状を用いることにより、交差点部分など他のポリゴンとの接続部分において、道路種別、幅、接続角度などの相違に起因して、対象道路の末端形状が不自然な見栄えとなることを回避することができる。上述の折れ線の形状も種々の方法で設定可能である。更に、折れ線に代えて、側線間を半円形の曲線その他の外に凸の曲線で結ぶことで末端形状を規定してもよい。
【００１９】
上述した末端形状の決定方法および使い分けの条件は、種々の設定が可能である。複数の道路を、道路名称、種別、通行規制、接続角度、上り線下り線情報などに基づいて予めグループ化しておき、グループ化されている道路の有無によって末端形状の決定方法を使い分けるようにしてもよい。本発明の地図データ生成装置は、道路ポリゴンデータを生成する機能の他、地形形状、建造物その他の地物等を表すためのポリゴンデータを生成・管理する機能を設けることもできる。
【００２０】
グループ化は、種々の条件で行うことができる。例えば、道路の名称、および道路に付された通行規制の少なくとも一方を用いることができる。同一の名称が付されている道路や、一方通行などの通行規制が整合的に付されている道路は、社会通念上、連続した道路と認識されることが多いため、これらの道路をグループ化することにより、こうした通念に沿った地図表示を実現することが可能となる。また、Ｙ字状の分岐では、対象道路に対して接続角度が浅いものが、いわゆる「道なり」として認識されるため、これらをグループ化しておく。「道なり」とは、このように幾何学的な形状から、通常、一本の連続した道路と認識される一連の道路を表している。以下、本発明では、「道なり」という用語は、広義には、幾何学的な形状の他、通行規制、道路名称、種別などに基づき、一連の道路と認識される道路を表すものとする。本発明では、このように広義の「道なり」にある道路をグループ化することにより、このグループに対して、ポリゴン化処理や縁線処理において統一的な処理を施すことが可能となり、地図の見栄えが向上する。本明細書では、「道なり」に類似の概念として、「接続性有り」という表現を用いることもある。接続性有りとは、道路の幾何学的な形状の評価である。接続角度が３０度などの所定角度以下となっている道路同士を「接続性有り」と表現するものとする。
【００２１】
属性に道路種別が含まれている場合には、道路種別が同一の道路間でグループ化を行うようにしてもよい。同一種別の道路全てをグループ化してもよいし、更に条件を付加し、同一種別の道路の一部をグループ化するようにしてもよい。通念上、連続の道路として認識されているのは同一種別であることが多い。また、塗りつぶしの色やパターンなどの表現も種別ごとに規定されることが多い。同一種別内でグループ化を行えば、これらの実状に沿って、ポリゴンデータの生成方法の統一化を図ることができる。
【００２２】
グループ化を行う際には、複数のポリゴン間の接続角度を考慮してもよい。接続角度とは、ポリゴンの対称軸のなす角度、またはポリゴンが表す道路の進行方向のなす角度を言う。一般に接続角度が小さい程、連続した道路と認識される可能性が高いため、接続角度を考慮することにより、こうした通念に沿ったグループ化を行うことができる。
【００２３】
グループ化は、ポリゴンを色やパターンで塗りつぶす処理や、ポリゴンの末端形状の決定など、ポリゴンデータを生成する種々の処理に活かすことが可能である。特に、これらの処理の中で、道路の縁線を表すための縁線データを各ポリゴンに付す縁線処理において有用性が高い。この縁線処理において、例えば、グループ化されたポリゴンの縁線が連続となるよう縁線データを生成することにより、地図の見栄えを確保することが可能となる。
【００２４】
地図の見栄えを確保するため、ポリゴン同士が接続する末端部分の形状決定が望まれる場合がある。この形状決定時は、決定の対象となる対象道路および対象道路に接続すべき接続道路双方の属性、形状、および向きの少なくとも一部に基づき、決定の要否を含め複数種類の決定方法を使い分けることが望ましい。この際、対象道路と接続道路がグループ化されているか否か、接続道路の中に相互にグループ化されたポリゴンがあるか否かなどによって使い分けを行うようにしてもよい。こうすることで、連続した道路と認識されるべきポリゴン間について、形状の連続性を確保させることができる。
【００２５】
本発明は、上述の特徴を必ずしも全て備えている必要はなく、一部を省略したり、適宜組み合わせたりして構成することが可能である。本発明は、地図データ生成装置としての態様の他、コンピュータを利用して地図データを生成する地図データ生成方法の態様で実現することもできる。また、地図データを生成するための機能をコンピュータに実現させるためのコンピュータプログラムとして実現することもできるし、かかるコンピュータプログラムを記録した記録媒体の形で提供することもできる。この場合、記録媒体としては、フレキシブルディスクやＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【発明を実施するための最良の形態】
【００２６】
本発明の実施例について以下の順序で説明する。
Ａ．装置構成：
Ｂ．道路ポリゴン生成処理：
Ｃ．ポリゴン化処理：
Ｄ．ポリゴンのグループ化処理：
Ｅ．ポリゴンの末端処理：
Ｅ１．処理方法：
Ｅ２．対象道路と接続道路が全て同一種別の場合：
Ｅ３．対象道路と接続道路に同種／異種が混在している場合：
Ｅ４．接続道路が対象道路と異種の場合：
Ｅ５．末端処理の使い分け条件一覧およびフローチャート：
Ｅ６．末端処理の使い分け（変形例）：
Ｆ．縁線処理：
Ｇ．効果および変形例：
【００２７】
Ａ．装置構成：
図１は実施例としての地図データ生成装置の構成を示す説明図である。地図データ生成装置１０は、地図データの生成に要求される各機能を実現するためのコンピュータプログラムを汎用のコンピュータにインストールすることによって構成される。図中に地図データ生成装置１０の機能ブロックを示した。本実施例では、これらの機能ブロックは、上述の通りソフトウェア的に構築されるが、ＡＳＩＣその他のハードウェアによって構築することも可能である。
【００２８】
地図データ生成装置１０は、ネットワークデータ４０に基づいて、ポリゴンデータ５０を生成する。本実施例では、ネットワークデータ４０およびポリゴンデータ５０は、それぞれ地図データ生成装置１０とネットワークで接続されたサーバによって提供・管理される。ネットワークとしては、ＬＡＮなどの限定的なネットワーク、およびインターネットなどの広域的なネットワークのいずれを用いても良い。ネットワークデータ４０およびポリゴンデータ５０は、地図データ生成装置１０内に格納・管理するようにしてもよい。
【００２９】
ネットワークデータ４０とは、経路探索に用いられるデータであり、ノード、リンクによって道路の接続状態を表したデータである。ネットワークデータには、各リンクおよびノードに対して、属性情報も付されている。属性情報としては、国道・県道・一般道などの道路種別、道路の車線数、道路名称、および高さレベルなどが含まれる。
【００３０】
高さレベルとは、道路の高さを量子化された数値で表したデータである。本実施例では、高さレベルデータは「−１，０，１，２」という整数値を採るものとした。「−１」は、地下または半地下状態の道路を意味し、「０」は地上を走る道路を意味する。「１」および「２」は高架道路を意味する。高架道路に対して複数のレベルが割り当てられているのは、多層的な高架道路に対応可能とするためである。数値が高いほど、上層の高架道路であることを意味する。このように高さレベルデータを用いることにより、道路の高さデータを直接数値データとして格納する場合に比較して、小さなデータ容量で道路同士の立体的な上下関係を表すことができる利点がある。
【００３１】
ポリゴンデータ５０とは、地図を描画するためのポリゴンを格納・管理したデータベースである。「ポリゴンデータ」という用語は、以下、各々のポリゴンを描画するためのデータを表すために用いることもある。ポリゴンデータ５０は、ポリゴンを描画するためのデータを、地形を表すレイヤ、道路や鉄道を表すレイヤ、建造物などの地物を表すレイヤに分けて格納している。本実施例の地図データ生成装置１０が、ネットワークデータ４０に基づいて作成するのは、ポリゴンデータ５０のうち道路を描画するための道路ポリゴンのみである。地形、鉄道、建造物などのポリゴンについては、別途オペレータの操作等によって生成するものとした。
【００３２】
図中には、道路ポリゴンを自動生成するための機能ブロックを示した。これらの機能ブロックは、主制御部１２の制御下で連携動作し、地図データ生成機能、特に道路ポリゴンの自動生成機能を実現する。
【００３３】
通信部１１は、ネットワークを介してネットワークデータ４０、ポリゴンデータ５０の読み書きを制御する。中間データ格納部１３は、道路ポリゴン生成過程で生じる種々のデータを一時的に格納・管理する。ポリゴンデータ生成部１４は、ネットワークデータ４０のリンクデータに基づき、道路形状を表す矩形状のポリゴンを生成する。ポリゴンを生成するための仕様は、仕様テーブル１８によって与えられる。実施例では、この段階で、一旦、矩形状のポリゴンを生成した上で、このポリゴンに対して後述する末端形状の決定を施すものとした。これに対し、この段階では、リンクデータに含まれる各リンクから一定距離にある点群で構成される折れ線または線分データを求めるのに留め、ポリゴンデータとしての形式は末端形状の決定などの処理が完了した後で行うようにしてもよい。
【００３４】
仕様テーブル１８は、図示する通り、道路種別に応じて、ポリゴンの幅、塗りつぶしの色、優先度などのデフォルト値を与える。優先度とは描画時の順序を規定する制御情報であり、優先度が高いポリゴンは他のポリゴンに上書きするように描かれることで、地図上では他のポリゴンに隠されたり分断されたりすることなく優先的に表示されることになる。仕様テーブル１８はデフォルト値を与えるテーブルに過ぎず、ネットワークデータ４０の属性で幅等が与えられている場合には、ポリゴンデータ生成部１４は、属性で与えられる値を優先的に用いる。ポリゴンデータ生成部１４によって生成されたポリゴンは、中間的なものであるため、中間データ格納部１３に格納される。
【００３５】
グループ化部１５は、中間データ格納部１３に格納された複数のポリゴンデータを予め設定された規則に従ってグループ化する。本実施例では、通念上、連続した道路と認識されるべき一連のポリゴンをグループ化するものとした。グループ化されるべきポリゴンとしては、例えば、「国道＊号線」のように道路名称が付されている道路を表すポリゴン、同一方向の一方通行規制が付された道路、接続角度が浅くほぼ同じ方向を向いた道路などが挙げられる。グループ化の方法については、後で詳述する。
【００３６】
ポリゴンデータ生成部１４は、さらに、中間データ格納部１３に格納された道路ポリゴンの末端を整形する。ネットワークデータ４０のリンクデータに基づき生成される当初のポリゴンは矩形状であるため、ポリゴン同士の接続部分では、道路がいびつな外形となる可能性がある。ポリゴンデータ生成部１４は、接続するポリゴン同士の属性や接続角度などを参照して、描画時の違和感を抑制するよう末端形状を決定するのである。末端形状の決定方法については後述する。
【００３７】
縁線処理部１７は、末端形状が決定された道路ポリゴンに縁線を生成する。この際、高架か否か、地上で交差点となっているか否かなどを考慮して、不要な縁線は消去する。また、グループ化されたポリゴンを統一的に取り扱うことによって、これらのポリゴンで表される道路については連続した縁線が描かれるようにしている。縁線処理の具体的内容については後述する。
【００３８】
地図データ生成装置１０は、以上の各機能ブロックによる処理によって、道路ポリゴンを自動生成することができる。こうして生成された道路ポリゴンは、ポリゴンデータ５０に格納される。以下では、道路ポリゴンを生成するための全体処理、およびそれぞれの加工処理について具体的な内容を説明する。
【００３９】
Ｂ．道路ポリゴン生成処理：
図２は道路ポリゴン生成処理のフローチャートである。図１に示した機能ブロックの連携によって実現される処理であり、ハードウェア的には、地図データ生成装置１０を構成するパーソナルコンピュータのＣＰＵがコンピュータプログラムに従って実行する処理である。
【００４０】
道路ポリゴン生成処理を開始すると、ＣＰＵはネットワークデータ４０の読み込みを行う（ステップＳ１０）。図中にネットワークデータ４０の概略構成を例示した。ネットワークデータ４０はノードおよびリンクで構成される。リンクとは道路を線分で表したものであり、ノードとはリンクの交点または端点である。図中には、リンクＬ１〜Ｌ８およびノードＮ１，Ｎ２を例示した。リンクＬ４とリンクＬ５は二次元的には交わっているが、交点にはノードが設定されていない。これは、リンクＬ４、Ｌ５が高架であり、交差点がないことを意味している。
【００４１】
ＣＰＵは上述のネットワークデータ４０に含まれる各リンクのポリゴン化を行う（ステップＳ２０）。図中に、リンクＬ１、Ｌ４、Ｌ８に基づいて生成されるポリゴンＰ１、Ｐ４、Ｐ８を例示した。処理の詳細は後述するため、ここでは概要のみを説明する。ポリゴン化処理では、ＣＰＵはそれぞれのリンクが対称軸となるよう、矩形状のポリゴンを生成する。ポリゴンの幅は、道路種別などによって決まる。本実施例では、国道、県道、一般道の幅の比を３：２：１に設定した。「高速道路」を別の種別として加える場合には、例えば、高速道路、国道、県道、一般道路の幅の比を５：４：３：２に設定する方法を採ることができる。各ポリゴンは、例えば、ポリゴンＰ１，Ｐ４（図中にハッチングを付して示した）がノードＮ１で接続されているように、それぞれノードで接続されることとなる。ノードＮ１、Ｎ２のように３本以上のリンクが接続されたノードでは、複数のポリゴンが重なって生成される。道路幅は、種別と無関係に、道路ごとに個別に設定してもよい。
【００４２】
ＣＰＵは、こうして生成されたポリゴンを一定の規則に従って、グループ化する（ステップＳ３０）。ネットワークデータでは、リンクは交差点などに設置されたノードごとに分断されているため、これに基づいて生成されるポリゴンもノード間で分断されている。この結果、例えば、国道＊号線のように、一つの連続した道路は複数のポリゴンの集合で表されることとなる。グループ化は、こうした実状を考慮し、連続した道路を構成すると認識されるべき複数のポリゴンをまとめる処理である。具体的な処理内容については後述する。
【００４３】
次に、ＣＰＵはポリゴンの末端処理を実行する（ステップＳ４０）。ステップＳ２０で生成されたポリゴンは矩形状であるため、ポリゴン同士の接続状態によっては、接続部分で隙間や余分なはみ出し部分が生じる可能性がある。末端処理とは、ポリゴン同士の接続状態に応じて、この末端形状を整形する処理を言う。ポリゴンは閉じた図形であるため厳密には「末端」は存在しない。本明細書ではポリゴンの末端とは、リンクまたは道路の進行方向の末端を含む辺を意味している。
【００４４】
図中に末端処理の代表的な処理例を示した。２つのポリゴンＰｏ１、Ｐｏ２が図示するように浅い接続角度で交差している場合を考える。各ポリゴンＰｏ１、Ｐｏ２の形状は、末端処理を施す前には、ハッチングを付して示したように矩形である。末端処理では、ポリゴンＰｏ１の側線Ｌ１１、Ｌ１２と、Ｐｏ２の側線Ｌ２１、Ｌ２２の交点Ｍ１、Ｍ２を求め、両者を結ぶ線分が末端となるようポリゴンＰｏ１の末端形状を整形する。末端処理では、道路の種別その他を考慮して、ここに例示した方法を含む複数の処理方法を使い分ける。末端処理の具体的内容については後述する。
【００４５】
こうして末端処理が完了すると、ＣＰＵは縁線生成処理を行う（ステップＳ５０）。図中に処理例を示した。図の左側に示す通り、処理前の状態では、ポリゴンＰＯＬは縁線が付されていない。縁線生成処理を施すことによってポリゴンＰＯＬの全周を取り囲むように縁線ＥＬが生成される。
【００４６】
上述のように縁線を生成すると、道路同士の接続部分に無用な縁線が発生し、道路同士があたかも分断されているかのような見栄えを生じることになる。そこで、ＣＰＵは生成された縁線のうち不要な縁線を消去する（ステップＳ６０）。処理の具体的内容については後述する。
【００４７】
ＣＰＵはこうして生成された道路ポリゴンをポリゴンデータ５０に出力し（ステップＳ７０）、道路ポリゴン生成処理を完了する。本実施例では、全ての処理を自動的に行うものとして説明するが、適宜、オペレータによる指示を介在させるようにしてもよい。例えば、図２中の各処理が完了したところで、処理結果を表示させて、適切な処理がなされているか否かをオペレータが確認したり、不適切な処理がなされている部分については、オペレータが決定を施すようにしたりしてもよい。また、本実施例では、ポリゴン化処理（ステップＳ２０）、グループ化（ステップＳ３０）、末端処理（ステップＳ４０）、縁線生成処理（ステップＳ５０）、不要な縁線消去（ステップＳ６０）を、それぞれ処理ごとに全リンクについて実行する。これに対し、別の処理方法として、各リンクごとに上述した一連の処理（ステップＳ２０〜Ｓ６０）を実行するようにしてもよい。この場合は、処理対象となるリンクを変更しつつ、一連の処理を繰り返し実行することで、全リンクに対応するポリゴンデータを生成することができる。以下、上述の説明では概要のみを示した種々の処理について具体的な内容を順次説明する。
【００４８】
Ｃ．ポリゴン化処理：
図３はポリゴン化処理のフローチャートである。この処理は、リンクに幅を持たせることによって矩形状のポリゴンを生成する処理であり、道路ポリゴン生成処理（図２）のステップＳ２０に相当する処理である。
【００４９】
処理を開始すると、予め決められた順序に基づいて、ＣＰＵはまず処理対象となるリンクを選択し（ステップＳ３１）、その属性を入力する（ステップＳ３２）。属性としては、道路種別、車線数、道路幅などが含まれる。ただし、これらの属性は、必ずしも全て設定されている必要はない。
【００５０】
ＣＰＵは次に生成すべきポリゴンの幅を決定する（ステップＳ３３）。ステップＳ３２において道路幅に関連する属性が読み込まれている場合には、その値を用いる。例えば、道路幅自体が属性で与えられている場合には、その値に基づいてポリゴンの幅を決定することができる。車線数が与えられている場合には、一車線当たりの幅として予め設定された標準値を用いてポリゴンの幅を決定することができる。これらの属性が得られていない場合には、仕様テーブル（図１参照）で与えられるデフォルト値を用いる。
【００５１】
次に、ＣＰＵは仕様テーブルに基づきポリゴンの色を設定する（ステップＳ３４）。本実施例では、道路種別に応じて色を塗り分けるものとした。属性入力時（ステップＳ３２）に、道路種別が得られていない場合には、ＣＰＵは一般道として扱い、色を決定する。道路の色は、道路種別だけでなく、車線数その他の条件を考慮して更に細分化してもよい。逆に、道路種別に依らずに、車線数その他の条件のみで決定するようにしてもよい。
【００５２】
ＣＰＵは、各リンクを対称軸として、リンク上の各点に対し幅Ｗとなる点の集合を求めることによって矩形状のポリゴンを生成する（ステップＳ３５）。図中にリンクＬ４に対するポリゴンＰ４の例を示した。ポリゴンはリンクＬ４と同じ長さＬｅｎおよび設定された幅Ｗの矩形となる。ここでは、リンクＬ４が直線状の場合を例示したが、リンクが折れ線状に定義されている場合も同様の処理がなされる。つまり、リンク上の各点に対し幅Ｗとなる点の集合を求めることによって、側線が折れ線状態となり、末端形状は矩形状のポリゴンを生成する。
【００５３】
以上の処理をＣＰＵは全リンクについて完了するまで、繰り返し実行し（ステップＳ３６）、ポリゴン化処理を完了する。生成されたポリゴンは、中間データ格納部（図１参照）に格納され、以後の処理に供される。本実施例では、以上の処理で、矩形状の仮のポリゴンデータを生成した。これに対し、ポリゴン化の処理では、ポリゴンとしてのデータ形式を整えることは行わず、ポリゴンの外形を規定する折れ線または線分群を求めるだけに留めても良い。この場合、ポリゴンとしてのデータ形式は、例えば、後述する末端処理の完了以降に整えるようにすればよい。
【００５４】
Ｄ．ポリゴンのグループ化処理：
図４はグループ化処理の例を示す説明図である。Ｒ１〜Ｒ６までの６本の道路が一つの交差点で交差している例を示した。道路に部分的に付したハッチングは道路種別を表している。図の例では、ポリゴンＲ１、Ｒ３、Ｒ６が国道であり、ポリゴンＲ４は県道、Ｒ２、Ｒ５が一般道である。また、ポリゴンＲ５には、交差点に向かう方向に一方通行の規制が付されており、ポリゴンＲ２には交差点から離れる方向に一方通行の規制が付されている。
【００５５】
グループ化とは、通念上、連続した道路を構成すると認識される複数のポリゴンを関連づける処理である。本実施例では、まず、連続する一方通行規制が付された道路同士をグループ化する。図の例では、ポリゴンＲ２、Ｒ５に連続する一方通行規制が付されている。従って、これら２本の道路をグループ化する。図中では、このグループにラベルＧｒ２を付して表した。通行規制の他、国道＊号線のように道路に名称が付されている場合には、同一の名称を属性として有するポリゴン同士をグループ化するようにしてもよい。
【００５６】
次に、ポリゴンＲ１についてグループ化処理する場合を考える。ポリゴンＲ１には通行規制は施されていない。本実施例では、かかる場合には、道路種別が同一の道路を選択し、グループ化を行うものとした。図の例では、ポリゴンＲ１、Ｒ３、Ｒ６が同一種別であるため、ポリゴンＲ１のグループ化の対象としては、ポリゴンＲ３、Ｒ６の２本が存在することになる。これら２本の道路を含めてグループ化することも可能ではあるが、本実施例では、道路の分岐が生じないようにグループ化を行うものとした。分岐を含めると、後述する縁線処理などが複雑となるからである。分岐を含まないようにするため、本実施例では、ポリゴンＲ３、Ｒ６のうち、ポリゴンＲ１との接続角度が小さい側をグループ化の対象として選択するものとした。接続角度は、各道路の対称軸のなす角度、またはポリゴンＲ１の進行方向とのなす角度をいう。図の例では、ポリゴンＲ１とポリゴンＲ３の接続角度Ａｎｇ３の方が、ポリゴンＲ６との接続角度よりも小さい。従って、ポリゴンＲ１とポリゴンＲ３をグループ化する。図中では、このグループにラベルＧｒ１を付して表した。
【００５７】
上述の処理によれば、ポリゴンＲ４、Ｒ６は、この交差点ではグループ化の対象となる道路が存在しないことになる。従って、ポリゴンＲ４、Ｒ６はこの時点では単独でグループを形成する。図中では、このグループにラベルＧｒ３、Ｇｒ４を付して表した。
【００５８】
図５はグループ化処理のフローチャートである。図４で説明した処理を実現するためのフローチャートであり、道路ポリゴン生成処理（図２）のステップＳ３０に相当する処理である。ＣＰＵは、まず処理対象の道路（以下、対象道路と称する）を選択し（ステップＳ３１）、このポリゴンに接続する道路（以下、接続道路と称する）を抽出する（ステップＳ３２）。図４の例では、ポリゴンＲ１を対象道路として選択した場合には、ポリゴンＲ２〜Ｒ６を接続道路として選択することになる。
【００５９】
ＣＰＵは対象道路および接続道路の属性を読み込み（ステップＳ３３）、対象道路と同一名称の道路を探す（ステップＳ３４）。同一名称の道路が存在する場合には（ステップＳ３４）、対象道路とこの道路とをグループ化する（ステップＳ３９）。グループ化は、例えば、図４に示したように、グループを形成する各道路の属性として、共通のラベルを付す方法を採ることができる。
【００６０】
同一名称の道路がない場合（ステップＳ３４）、ＣＰＵは対象道路と連続した一方通行が付された接続道路を探す（ステップＳ３５）。かかる条件を満たす道路が存在する場合には、その道路と対象道路とをグループ化する（ステップＳ３９）。
【００６１】
上述した条件を満たす道路が存在しない場合、または対象道路に一方通行規制が付されていない場合には（ステップＳ３５）、次にＣＰＵは対象道路と同一種別の道路をグループ化の候補として接続道路から選択する（ステップＳ３６）。そして、この選択された道路のうち、接続角度が所定値Ａｎｇ以下となるものに候補を絞り込む（ステップＳ３７）。所定値Ａｎｇは任意に設定可能であるが、本実施例では９０°に設定した。この処理によって、鋭角的に折れ曲がるように接続された道路はグループ化の候補から外れることになる。
【００６２】
ＣＰＵは、絞り込まれた道路の中から、接続角度が最小のものを選択し（ステップＳ３８）、この道路と対象道路とをグループ化する（ステップＳ３９）。ステップＳ３７までの絞り込みによって候補となる道路が残っていない場合には、対象道路のみでグループを形成することになる。ＣＰＵは以上の処理を全道路について完了するまで繰り返し実行する。
【００６３】
グループ化するための条件およびその優先度は、上述の例に限定されるものではなく、種々の設定が可能である。例えば、通行規制の条件については、一方通行のみならず、右左折禁止などの規制を考慮してもよい。接続角度に関する条件（ステップＳ３７）を省略することも可能である。種別に関する条件（ステップＳ３６）と接続角度に関する条件（ステップＳ３７）を並列し、いずれか一方を満たす道路をグループ化の候補にするようにしてもよい。
【００６４】
図６は変形例としてのグループ化処理のフローチャートである。実施例のグループ化処理（図５）とは、グループ化を行う条件の優先度が異なっている。ＣＰＵは、まず処理対象の道路（以下、対象道路と称する）を選択し（ステップＳ３１）、この道路に接続する道路（以下、接続道路と称する）を抽出する（ステップＳ３２）。
【００６５】
ＣＰＵは対象道路および接続道路の属性を読み込み（ステップＳ３３）、対象道路と同一種別の道路を抽出する（ステップＳ３４Ａ）。更に、この中から、ＣＰＵは、接続角度がＡｎｇ以下となっている道路、即ち浅い角度で接続された道路を抽出する（ステップＳ３５Ａ）。
【００６６】
次に、ＣＰＵは対象道路と連続した一方通行が付された接続道路を探す（ステップＳ３６Ａ）。かかる条件を満たす道路が存在する場合には、その道路と対象道路とをグループ化する（ステップＳ３９）。上述した条件を満たす道路が存在しない場合、または対象道路に一方通行規制が付されていない場合（ステップＳ３５）、ＣＰＵは対象道路と同一名称の道路を検索する（ステップＳ３７Ａ）。
【００６７】
かかる道路が存在する場合には、その道路と対象道路とをグループ化し（ステップＳ３９）、存在しない場合には、以上の処理で選択された道路のうち、接続角度が最小のものを選択し（ステップＳ３８Ａ）、この道路と対象道路とをグループ化する（ステップＳ３９）。所定値Ａｎｇは任意に設定可能であるが、本実施例では９０°に設定した。この処理によって、鋭角的に折れ曲がるように接続された道路はグループ化の候補から外れることになる。ＣＰＵは以上の処理を全道路について完了するまで繰り返し実行する。
【００６８】
変形例の処理は、同一名称の道路が、複数の道路に分岐する可能性がある場合など、道路名称だけでは分岐を含まない状態でグループを特定することができない時に有用である。グループ化は、変形例の他、更に種々の条件および優先度で行うことが可能である。
【００６９】
Ｅ．ポリゴンの末端処理：
ポリゴンの末端処理は、地図の見栄えを向上するため、ポリゴン同士の接続状態に応じて、ポリゴンの末端形状を整形する処理である。本実施例では、複数の処理方法を条件によって使い分けて末端処理を行う。以下では、まず図７〜１０において複数の処理方法を示し、次に、図１１〜図１５に基づいて、道路の接続状況に応じた具体的な処理方法を説明した後、図１６でフローチャートを示す。
【００７０】
Ｅ１．処理方法：
本実施例では、リンクを拡幅して単純な矩形形状のポリゴンを生成する処理の他、ポリゴンの末端形状の整形処理として、接続処理、フィレット処理、凸ポリゴン化処理、Ｍ字処理の４種類を用いる。以下、これら４種類の処理について、処理内容を順次説明する。
【００７１】
（１）接続処理：
図７は接続処理のフローチャートである。接続処理では、まず処理対象となるリンクが交差しているノードを中心として、放射状に各リンクの方向を定義する（ステップＳ１００）。リンクデータは、その経由点からなる点列データで構成されている。ステップＳ１００の処理は、ノードを始点としてこの点列データを配列する処理である。この処理は、後述する通り、リンク間の位置関係を定義するための前処理である。従って、リンク間の位置関係を他の方法で定義する場合には、ステップＳ１００の処理を省略してもよい。
【００７２】
次に、ＣＰＵはノードで交差する複数のリンクから、１本のリンクを、処理対象となる対象リンク［１］として選択する（ステップＳ１０１）。そして、この対象リンク［１］から反時計回り方向に隣接するリンクを探索し、このリンクを対象リンク［２］として選択する（ステップＳ１０２）。探索する方向は、必ずしも反時計回りである必要はなく、時計回り方向であってもよい。
【００７３】
図の右側に処理例を示した。上側の図は２本の道路がノードＮで交差している場合を示しており、下側の図は３本の例を示している。上側の図において、ノードＮで２本のリンクＬ［１］、Ｌ［２］が交差しているものとし、この中でリンクＬ［１］を対象リンク［１］として選択したとする。ここから反時計回り（図中の矢印方向）に探索すると、対象リンク［２］としてリンクＬ［２］が選択されることになる。
【００７４】
こうして対象リンク［１］、［２］が選択されると、ＣＰＵは矩形ポリゴン［１］の左側線と、矩形ポリゴン［２］の右側線との交点を算出する（ステップＳ１０３）。左側、右側は、ステップＳ１００で定義されたリンク方向を基準として定義する。矩形ポリゴン［１］、［２］はそれぞれ対象リンク［１］［２］を拡幅して形成された矩形形状のポリゴンを意味する。この段階では、ポリゴンデータとしての形式を整えていなくても構わない。矩形形状のポリゴンにおいて、リンク［１］［２］と平行な辺を構成する左右の側線が定義されていれば足りる。
【００７５】
右側の処理例においては、リンクＬ［１］に対応する左側線はＲＬ［１］であり、右側線はＲＲ［１］である。リンクＬ［２］に対応する左側線はＲＬ［２］であり、右側線はＲＲ［２］である。ステップＳ１０３の処理では、左側線ＲＬ［１］と右側線ＲＲ［２］との交点Ｃ［１］が求められることになる。
【００７６】
ＣＰＵは、対象リンク［２］を対象リンク［１］に置き換えながら、以上の処理を全リンクについて終了するまで繰り返す（ステップＳ１０４、Ｓ１０５）。右側の処理例では、リンクＬ［１］を対象リンク［１］とする処理が完了すると、次に、リンクＬ［２］を対象リンク［１］として同様の処理を実行することになる。この時は、リンクＬ［１］が対象リンク［２］として選択され、左側線ＲＬ［２］と右側線ＲＲ［１］の交点Ｃ［２］が求められることになる。
【００７７】
全リンクについて処理が終了すると、ＣＰＵはこれらの処理で求められた交点およびノードを頂点とするポリゴンを生成する（ステップＳ１０６）。右側の処理例では、リンクＬ［１］に対応するポリゴンの末端形状は、図中に太線で示すように、交点Ｃ［１］、ノードＮ、交点Ｃ［２］を結ぶ線で定義される。
【００７８】
３本以上のリンクが交差する場合も同様である。３本のリンクＬ［１］〜Ｌ［３］が交差する場合の処理を、処理例の下側に示す例に従って説明する。対象リンク［１］としてリンクＬ［１］を選択した時には、対象リンク［２］としてリンクＬ［２］が選択され、交点Ｃ［１］が求められる。以下、順にリンクＬ［２］、［３］を対象リンク［１］とすることにより、交点Ｃ［２］、［３］が求められる。この結果、リンクＬ［１］〜［３］に対応するポリゴンの末端形状は、それぞれ図中に太線で示すように定義される。
【００７９】
（２）フィレット処理：
図８はフィレット処理のフローチャートである。この処理は、接続処理（ステップＳ１１０）に続く後処理として実行する。ＣＰＵは、処理対象となるリンクについて接続角度ＡＣを算出する（ステップＳ１１１）。本実施例では、接続角度ＡＣは、処理対象となるリンクの一方から進入し、他方に抜け出る場合における進路変更の角度に相当する角度である。図中に、２つのリンクに対して接続処理を施した状態を示した。接続処理により２つのポリゴンＰＯＬ［１］、［２］が生成される。接続角度ＡＣが大きくなる程、ポリゴンＰＯＬ［１］、［２］の接続部分には鋭角のコーナーＣＯが現れる。
【００８０】
フィレット処理は、接続角度ＡＣが所定値Ｔｈよりも大きい場合にのみ施される（ステップＳ１１２）。本実施例では、所定値Ｔｈを９０°としたが、この値は任意に設定可能である。接続角度ＡＣが所定値Ｔｈよりも大きい場合には、ＣＰＵは鋭角のコーナーＣＯを、円弧ＦＬＴで曲線状に削除する（ステップＳ１１３）。円弧ＦＬＴの半径は、予め定められた固定値としてもよいし、ポリゴンの幅に所定の係数を乗じるなどの方法で設定してもよい。
【００８１】
（３）凸ポリゴン化処理：
図９は凸ポリゴン化処理のフローチャートである。ＣＰＵは次に示す手順で処理対象となる矩形状のポリゴンの末端形状を凸ポリゴン化する（ステップＳ１２０）。凸ポリゴン化とは、ポリゴンの側線間を凸形状となるように折れ線で結ぶ整形方法を言う。つまり、折れ線は凸ポリゴン、つまりいかなる対角線もポリゴンからはみ出さない形状を形成するものに限られる。本実施例では、末端形状を等脚台形状に整形するものとした。
【００８２】
図中に凸ポリゴン化の処理内容を例示した。ノードＮを端点とするリンクＬに対し、矩形状のポリゴンの側線ＲＲ、ＲＬが定義されているとする。ＣＰＵはノードＮを、リンクに沿ってＷｈ移動させるとともに、リンクと平行方向にＷｈ移動させた点Ａｐ２を求める。ノードＮを頂点としリンクに平行な辺を有する一辺Ｗｈの正方形を求め、ノードＮの対角にある頂点をＡｐ２とする処理と説明してもよい。同様にして、点Ａｐ２とリンクＬに対して線対称な位置にある点Ａｐ３を求める。そして、側線ＲＲ、ＲＬの端点Ａｐ１、Ａｐ４とこれらの点Ａｐ２、Ａｐ３を結ぶ折れ線でポリゴンの末端形状を定義する。
【００８３】
上述の処理で用いられるＷｈは任意に設定可能であるが、本実施例では処理対象となる道路種別よりも２段階以上下位の道路種別の道路半幅を用いる。本実施例では、高速道路、国道、県道、一般道の順序で道路種別がランク分けされているため、例えば、対象道路ＰＰが国道である場合には、Ｗｈの長さは、県道の道路半幅となる。Ｗｈの値は対象道路の半幅Ｗ１に一定の比率を乗じて求めるようにしてもよい。次のステップＳ１２０Ａの処理は、変形例で用いるものであり、実施例では省略される処理であるため、内容は後述する。
【００８４】
次に、ＣＰＵは対象道路の幅Ｗ１、優先度Ｐ１、およびこの対象道路と交差する道路（接続道路）の幅Ｗ２、優先度Ｐ２を算出する（ステップＳ１２１）。そして、幅Ｗ１がＷ２よりも大きい時、または優先度Ｐ１がＰ２よりも高い時には（ステップＳ１２２）、凸ポリゴン化した部分のうち、余分な部分を削除する処理を実行する（ステップＳ１２３）。優先度の優劣は、仕様テーブル（図１参照）に設定されている通りである。本実施例では、例えば、「国道」は「県道」よりも優先度が高くなる。従って、対象道路が「国道」であり、接続道路が「県道」である場合には、幅の広狭に関わらず、ステップＳ１２３の処理が実行されることになる。また、対象道路の優先度が低い場合、例えば、対象道路が「県道」であり、接続道路が「国道」である場合には、対象道路の道路幅Ｗ１が、接続道路の道路幅Ｗ２よりも広ければステップＳ１２３の処理が実行されることになる。
【００８５】
図中にステップＳ１２３での処理例を示した。ここでは、幅Ｗ１のポリゴンＰＯＬ［１］に凸ポリゴン化処理が施されているものとする。このポリゴンＰＯＬ［１］は、交差するポリゴンＰＯＬ［２］の幅Ｗ２よりも広い。かかる状況では、図示するように、ポリゴンＰＯＬ［２］からポリゴンＰＯＬ［１］がはみ出す可能性がある。従って、ポリゴンＰＯＬ［１］に関し、図中でハッチングを付した領域Ａを削除するのである。
【００８６】
削除時に伴う演算の丸め誤差によって、図中の破線楕円に示すように、削除後のポリゴンＰＯＬ［１］とポリゴンＰＯＬ［２］との間に隙間ができる場合がある。かかる隙間は非常に微細なものであるため、本実施例ではそのまま放置するものとしたが、ポリゴンＰＯＬ［２］の側線上に、ポリゴンＰＯＬ［１］の頂点に一致する点を追加することで、隙間をなくすようにしてもよい。
【００８７】
本実施例では、ポリゴンＰＯＬ［１］の幅Ｗ１が接続道路のポリゴンＰＯＬ［２］の幅Ｗ２以下の場合には（ステップＳ１２２）、余分な部分を削除する処理をスキップするものとした。このような場合には、ポリゴンＰＯＬ［１］がポリゴンＰＯＬ［２］からはみ出す可能性が低いからである。また、余分な部分を削除する処理を施して上述した隙間が生じることを嫌うからである。このスキップは必須ではなく、ポリゴンＰＯＬ［１］、［２］の幅に関わらず、余分な部分を削除する処理（ステップＳ１２３）を施すようにすることもできる。
【００８８】
凸ポリゴン化処理では、等脚台形状の末端形状に代えて、円弧状の末端形状を採っても良い。例えば、対象道路ＰＰの両端を直径とする半円で末端形状を整形するようにしてもよい。
【００８９】
（４）Ｍ字処理：
図１０はＭ字処理の方法を示す説明図である。Ｍ字処理は、対象道路ＰＰの末端形状を、点ＣＰ１、ＣＰ２、Ｎ、ＣＰ３、ＣＰ４からなるＭ字形状に整形する処理である。点ＣＰ１、ＣＰ４は、対象道路ＰＰを矩形状に形成した場合の頂点である。点Ｎは対象道路ＰＰと接続道路ＰＣとが接続するノードである。交点ＣＰ２、ＣＰ３は、接続道路ＰＣの末端の辺ＬＣｅを距離Ｗｈだけ平行移動した線分と、測線ＬＣｉ、ＬＣｏとの交点である。距離Ｗｈは、接続道路ＰＣの半幅である。Ｍ字処理の点ＣＰ２、ＣＰ３の決め方は、図示した場合に限定されず種々の設定が可能である。
【００９０】
Ｅ２．対象道路と接続道路が全て同一種別の場合：
次に、交差する複数の道路からいずれか２本の道路を選択し、この２本の道路間で末端形状の整形を施す場合を例にとって、上述の各処理の使い分け方法を説明する。図１１は末端処理方法（１）を示す説明図である。この処理は、対象道路と接続道路が全て同一種別という条件下で適用される。図中には、ｉ）対象道路と接続道路の幅が同一の場合、ｉｉ）接続道路の幅が対象道路よりも狭く、３０°＜接続角度≦９０°の場合、ｉｉｉ）接続道路の幅が対象道路よりも狭く、接続角度≦３０°の場合、ｉｖ）接続角度＞９０°の場合に分けて４通りの処理例を示した。図１１に該当する条件下では、接続処理、Ｍ字処理、フィレット処理が適用される。
【００９１】
最上段に示したケース、つまり道路幅が同一で接続角度が９０°以下の場合の処理例について説明する。この例では、対象道路ＰＰと接続道路ＰＣが９０°以下の接続角度ＡＣで接続されている。接続処理を施さない場合に形成されるポリゴンは、左側の図に示すようにポリゴンＰＰ、ＰＣの末端形状は矩形状である。
【００９２】
この状態で、接続処理（図７参照）を施す。即ち、対象道路ＰＰの側線ＬＰｉ、ＬＰｏと、接続道路ＰＣの側線ＬＣｉ、ＬＣｏの交点ＣＰｉ、ＣＰｏを求める。そして、両者を結ぶ線分ＣＰｉ−ノード−ＣＰｏが辺となるよう、対象道路ＰＰの末端形状を整形する。ここでは、説明の便宜上、矩形状のポリゴンとして対象道路ＰＰを一旦形成した後、接続処理で末端形状を修正するように示した。これに対し、リンクに基づいて側線ＬＰｉ、ＬＰｏ、および交点ＣＰｉ、ＣＰｏを求め、矩形状のポリゴンを経ることなく対象道路ＰＰの形状を決定してもよい。これは、以下で説明する各処理においても同様である。
【００９３】
上から２段目には、対象道路と接続道路の幅が相違し、３０°＜接続角度≦９０°のケースについて処理例を示した。図の例では、対象道路ＰＰに対して接続道路ＰＣの幅が狭くなっている。この状態では、接続処理を施すと、それぞれの側線の交点ＣＰｉ、ＣＰｏは右側の図に示すように側線ＬＰｉを延長し、側線ＬＰｏを短縮した位置に求められる。
【００９４】
上述の接続処理では、接続角度が浅くなるにつれて、交点ＣＰｉの位置が、処理前の対象道路ＰＰの末端から遠く離れていく。従って、接続角度が浅い場合には、対象道路ＰＰがいびつな形状となることがある。本実施例では、かかる弊害を回避するため、接続角度≦３０°の場合には、接続処理を変形したＭ字処理を施すものとした。上から３段目には、Ｍ字処理を施す例として、接続道路の幅が対象道路よりも狭く、接続角度≦３０°の場合を示した。Ｍ字処理を適用する接続角度の範囲は、図示した場合に限定されず種々の設定が可能である。
【００９５】
４段目には対象道路と接続道路の幅が相違し接続角度が９０°より大きい場合をそれぞれ示した。これらのケースについても、接続処理を施し、対象道路および接続道路の側線を延長または短縮し、交点を求めることによって、図示するように末端形状を整形することができる。ただし、接続角度が９０°より大きい場合には、側線の交点は図中の鋭角状のコーナーＣＯを形成する。本実施例では、角の見栄えを向上するため、このような場合にはフィレット処理を施すものとした。本実施例では、角ＣＯの角度が９０°より小さい場合に円弧ＦＬＴによる整形を適用するものとしたが、整形を適用するか否かの判断基準となる角度は９０°に限らず任意に設定可能である。円弧ＦＬＴによる整形を適用しないようにしてもよい。
【００９６】
本実施例では、上述の通り、対象道路よりも接続道路の幅が狭く、かつ接続角度≦３０°の場合に、Ｍ字処理を適用するものとした。この時、接続道路（図１１の３段目におけるＰＣ）については、上から１段目の処理が行われることになる。３段目における接続道路ＰＣの処理時には、接続角度≦３０°となってはいるものの、相手となる道路（この場合は３段目における対象道路ＰＰ）の幅の方が広いからである。この状態では、３段目のケースにおいて、接続道路ＰＣと対象道路ＰＰの末端形状は不整合となる。しかし、実際には、３段目においてＭ字処理が施された対象道路ＰＰが、接続道路ＰＣよりも後から描画されることにより、接続道路ＰＣの末端は対象道路ＰＰによって覆い隠されるため、表示上の不自然さは生じない。
【００９７】
もっとも、本実施例の変形例として上述のケースで末端形状が整合するよう整形処理を使い分けるようにしてもよい。まず、図１１の１段目のケースを対象道路と接続道路の幅が「同一」の場合に限定する。そして、２段目は、対象道路よりも接続道路の方が広い場合も含めて、対象道路と接続道路の幅が「相違」し、３０°＜接続角度≦９０°の場合に適用する。更に、対象道路よりも接続道路の幅が「広く」、かつ接続角度≦３０°の場合には、末端を３段目の接続道路ＰＣの形状に整形する処理（「えんぴつ処理」と称する）を適用する。えんぴつ処理の形状を規定する交点ＣＰ２、ＣＰ３の設定方法は、Ｍ字処理と同じであるため説明を省略する。こうすることにより、対象道路と接続道路の描画順序に関わらず、接続部分の不自然さを回避することが可能となる。
【００９８】
Ｅ３．対象道路と接続道路に同種／異種が混在している場合：
図１２は末端処理方法（２）を示す説明図である。この処理は、接続道路に対象道路と同一および異種の道路が混在するという条件下で適用される。対象道路に２本以上の道路が接続されている場合を対象とする処理例である。
【００９９】
図中には図１１と同様、４通りの処理例を示した。最上段には、対象道路と接続道路の幅が同一で接続角度が９０°以下の例を示した。上から２段目には、対象道路より接続道路の幅が狭く、３０°＜接続角度≦９０°の例を示した。上から３段目には、対象道路より接続道路の幅が狭く、接続角度≦３０°の例を示した。これらの３通りのケースについては、図１１で説明したのと同様、接続処理またはＭ字処理がそれぞれ施される。
【０１００】
上から４段目には、対象道路と接続道路の接続角度が９０°よりも大きい場合を示した。本実施例では、このケースについては、凸ポリゴン化処理によって末端形状を整形する。
上から４段目の具体例に示すように、凸ポリゴン化処理では、対象道路ＰＰのリンクと、接続道路ＰＣのリンクとの交点（ノード）を頂点とし、対象道路の末端の辺ＬＰｅ上に一辺を配置して、リンクを延長する方向に正方形ＳＱ（図中のハッチングを付した部分）を配置し、ノードと対角上にある頂点ＣＰ２を求める。  
【０１０１】
図１３は凸ポリゴン化処理の効果を示す説明図である。対象道路ＰＯＬ１〜ＰＯＬ３に対し、３通りの方法で末端形状を決定した結果を示した。この例では、更に、対象道路よりも幅が狭い種別の道路ＰＯＬ４が交差している。
【０１０２】
対象道路ＰＯＬ１は、矩形状のポリゴンを表している。この状態では、対象道路ＰＯＬ１は、道路ＰＯＬ４からはみ出すことはないものの、図中の領域ＩＳ１に示すように、対象道路ＰＯＬ１との接続処理で使用された接続道路も含めると、交差点中の塗り分け状態は不自然となる。
【０１０３】
対象道路ＰＯＬ２は、接続処理にフィレットを施した場合（図１１の上から４段目）の結果を表している。フィレットを施した場合には、図中の領域ＩＳ２に示すように、対象道路ＰＯＬ２の末端が、道路ＰＯＬ４からはみ出す可能性がある。かかる形状は、不自然であるとともに、非現実的でもある。
【０１０４】
対象道路ＰＯＬ３は、凸ポリゴン化処理を施した場合の例である。図示する通り、対象道路ＰＯＬ３の末端形状も自然な状態になるとともに、道路ＰＯＬ４からはみ出すこともない。先に説明した通り、凸ポリゴン化処理で対象道路ＰＯＬ３が延長される長さ（図１２中の正方形ＳＱの一辺の長さ）は、対象道路よりも下位の道路種別の半幅で抑えているからである。このように、本実施例の凸ポリゴン化処理には、対象道路に交差する道路からはみ出すことなく、対象道路の末端形状を整形することができるという効果を有する。
【０１０５】
Ｅ４．接続道路が対象道路と異種の場合：
図１４は末端処理方法（３）を示す説明図である。この処理は、接続道路のいずれもが対象道路と異種の道路である場合に適用される。かかる場合には、接続道路間では同一種別の道路が存在するケース、接続道路間にも同一種別の道路が存在せず全て異種の道路というケースが含まれる。
【０１０６】
図中には４通りの処理例を示した。最上段には、対象道路ＰＰの幅Ｗｐｐよりも接続道路ＰＣの幅Ｗｐｃが広い場合の例を示した。本実施例では、かかるケースについては、末端形状の整形を行わず、矩形状のまま放置するものとした。理由については後述する。
【０１０７】
上から２段目には、対象道路と接続道路の幅が同一で接続角度が９０°以下の例を示した。このケースについては、図１１で説明したのと同様、接続処理、即ちポリゴンの側線同士の交点を結ぶ線分でカットすることで、末端形状の整形が行われる。
【０１０８】
上から３段目には、対象道路よりも接続道路の幅が狭く、接続角度が９０°以下の場合を示した。このケースでは、凸ポリゴン化処理を行う。具体的な処理方法は、先に図１０で説明した通りである。凸ポリゴン化処理における正方形ＳＱの一辺の長さは、接続道路ＰＣの半幅Ｗｈで決めるようにしてもよい。
【０１０９】
上から４段目には、接続道路の幅が、対象道路の幅以下であり、接続角度が９０°よりも大きい場合を示した。このケースでも、図１０で説明した凸ポリゴン化処理によって、対象道路ＰＰの末端形状を整形する。
【０１１０】
上述の通り、本実施例では、接続道路の幅が対象道路の幅よりも広い場合には、末端形状の整形を行わない。ただし、接続道路については、上から３段目または４段目の条件に適合するため、末端形状の整形処理として凸ポリゴン化処理が適用される。このように処理された接続道路を対象道路よりも後から描画するようにすれば、対象道路の末端は接続道路によって覆い隠されることになり、表示上の不自然さは生じない。本実施例では、かかる理由から、接続道路の幅が対象道路の幅よりも広い場合には、対象道路の末端形状の整形を行わないものとしている。もっとも、かかる場合でも末端形状の整形を行うようにしても構わない。この場合には、例えば、凸ポリゴン化処理が施された後の接続道路の末端形状に適合するように整形する処理を施すことができる。こうすることにより、接続道路と対象道路の描画順序に依らず、表示上の不自然さを回避できる利点がある。
【０１１１】
Ｅ５．末端処理の使い分け条件一覧およびフローチャート：
図１５は末端処理の方法の一覧を示す説明図である。図１１〜図１４で示した各処理の適用条件等を一覧表の形式で示した。種別欄は、対象道路および接続道路の種別と各ケースとの関係を示している。次の欄は、処理対象となる接続道路である。本実施例では、接続道路が複数存在する場合、その中の一つを選択し、対象道路と接続道路との二者の関係に基づいて、対象道路の形状の決定処理を行うものとした。処理対象となる接続道路とは、上述の選択を行う際の規則を表している。次の欄の「接続状態」は対象道路の末端形状の処理方法を使い分けるための条件を、対象道路と接続道路との幅の広狭および接続角度を用いて示している。
【０１１２】
ケース１〜３は図１１、即ち対象道路および接続道路の全てが同一種別である場合に該当する。このケースについては、接続道路の中から対象道路と同一グループに属するものを選択し、対象道路の末端形状の整形に使用する。末端形状の整形は、図中に示す条件に応じて、「接続処理」「Ｍ字処理」「接続処理＆フィレット」のいずれか（図１１参照）によって行われる。
【０１１３】
ケース４〜６は接続道路中に対象道路と同一種別および異種の道路が存在する場合である（図１２参照）。これらのケースでは、対象道路と同一種別の道路のうち接続角度が最小となるものを接続道路として末端処理を適用する。対象道路と同一グループの道路が存在する場合には、その道路を接続道路とすることもできる。ケース４〜６では、末端形状の整形は、図中に示す条件に応じて、「接続処理」「Ｍ字処理」「凸ポリゴン化処理」のいずれかによって行われる。
【０１１４】
ケース７〜１０は接続道路には対象道路と同一種別の道路が存在しない場合の処理である（図１４参照）。接続道路間では同一種別の道路が存在するケース、および全て異種のケースの双方が含まれる。この処理では、接続道路内で同一種別の道路が存在しないもののうち、接続角度が最小となるものを接続道路として末端処理を行う。ケース７〜１０では、図中に示す条件に応じて、「修正無し」「接続処理」「凸ポリゴン化処理」のいずれかが行われる。修正無しとは、対象道路の形状を矩形とすることを意味する。
【０１１５】
図１６はポリゴンの末端処理のフローチャートである。図１５に示した使い分けを行ってポリゴンの末端形状を整形する処理であり、道路ポリゴン生成処理（図２）のステップＳ４０に相当する処理である。
【０１１６】
処理を開始すると、ＣＰＵは処理対象となる道路ポリゴンを対象道路として選択し（ステップＳ４１）、対象道路に対する接続道路を選択する。接続道路が存在しない場合には（ステップＳ４２）、ステップＳ４１から処理を再開し、他の道路ポリゴンを対象道路として選択する（ステップＳ４６）。
【０１１７】
接続道路が存在する場合には（ステップＳ４２）、対象道路および接続道路の属性を入力する（ステップＳ４３）。入力すべき属性には、末端処理の使い分けに要求される情報であり、道路種別、道路幅または車線数が含まれる。ＣＰＵは、こうして得られた属性を用いて、図１５で示した条件に照らして、末端形状の決定方法を決定し、末端形状を決定する（ステップＳ４４、Ｓ４５）。決定方法の決定に必要となる情報のうち、接続角度は、リンク同士のなす角度によって演算することができる。ＣＰＵは以上の処理を、全道路の処理が完了するまで繰り返し実行する。
【０１１８】
Ｅ６．末端処理の使い分け（変形例）：
末端処理は、図１１〜図１６に限らず、種々の方法で使い分けが可能である。図１７には、変形例としての使い分けを例示した。実施例では、対象道路の他、交差点に存在する複数の道路のうちいずれか１本を選択して末端形状の整形を行う例を示したが、変形例では３本以上を対象として処理を行うことを許容する例を示す。  
【０１１９】
変形例では、図示する９通りのケースに分けて処理を実行する。ケース１は、接続道路が存在しない場合である。この場合には、末端形状は矩形の状態とする。
【０１２０】
ケース２は、交差点に存在する道路が全て同一種別の場合である。この場合には、全道路を対象として接続処理を施す。例えば、交差点に３本の道路が存在する場合には、図７の処理例（右下図）に示す状態となる。
【０１２１】
ケース３は、交差点に対象道路と同一種別／異種の道路の双方が混在し、かつ道路に接続性がある場合である。この場合には、対象道路と同一種別の全道路を対象として接続処理を施す。
【０１２２】
図の下側に接続性の有無の判断方法を例示した。変形例では、接続性は、リンク間の角度に基づいて決定する。例えば、図示するようにノードでリンクＬ１〜Ｌ３が交差している場合を考える。それぞれのリンク間の角度はＡ１２、Ａ２３、Ａ３１と求められる。変形例では、これらの中で最大の角度が所定値３０°よりも大きい場合には「接続性有り」、３０°以下の場合には「接続性無し」と定義した。接続性有無の判断基準となる所定値は３０°に限らず任意に設定可能である。
【０１２３】
３本のリンクが交差している場合において、接続性有りとなる状態を右側に例示した。図示するように、リンクＬ４〜Ｌ６が交差している場合、リンクＬ４とＬ６のなす角度Ａ４６が最大の角度となる。この角度Ａ４６が３０°以下の場合には、「接続性無し」と判断される。
【０１２４】
ケース４は、交差点に対象道路と同一種別／異種の道路の双方が混在し、かつ道路に接続性がない場合である。この場合には、各道路について個別に凸ポリゴン化処理を施す。
【０１２５】
変形例では、３本以上を対象として処理を行う点で実施例と異なるため、凸ポリゴン化処理（図９）も、実施例と相違する部分がある。ここで、図９に戻り、変形例における凸ポリゴン化処理について説明する。先に説明した通り、凸ポリゴン化処理では、対象道路の末端形状の凸ポリゴン化が行われる（ステップＳ１２０）。変形例では、その後に、接続道路同士の接続性の有無を判定する（ステップＳ１２０Ａ）。ケース４（図１７）では対象道路と接続道路との接続性を判断しているのに対し、ステップＳ１２０Ａでは、接続道路同士の接続性を判断している点が異なる。ただし、接続性の判断方法には差違はなく、道路間の接続角度が３０°よりも大きい場合には「接続性有り」となる。
【０１２６】
変形例では、接続道路同士の接続性がない場合には、凸ポリゴン化処理を終了する。この場合には、対象道路と接続道路の幅、優先度に依らず、余分な部分の削除（ステップＳ１２３）は行われないことになり、対象道路の末端形状は凸ポリゴン化された状態（ステップＳ１２０の処理が完了した状態）となる。接続道路同士の接続性がある場合には、実施例と同様の処理（ステップＳ１２１〜Ｓ１２３）を実行する。接続道路同士の接続性の有無によって、このように処理を切り換えるのは、接続性無しの場合には、余分な部分の削除（ステップＳ１２３）を実行すると、かえって見栄えを損ねるからである。
【０１２７】
ケース５は、対象道路と同一種別の道路が交差点内に存在しない場合である。ただし、接続道路、即ち交差点内の他の道路内には同一種別の道路が存在するものとする。かかる場合には、対象道路について凸ポリゴン化処理を施す。
【０１２８】
ケース６、７は、交差点に存在する道路が全て異種であるが、対象道路と同じ幅の道路が接続道路内に存在する場合である。ケース６は、これらの道路について接続性が有る場合であり、かかる場合には、同じ幅の全道路を対象として接続処理を施す。ケース７は、接続性がない場合であり、かかる場合には、対象道路について凸ポリゴン化処理を施す。
【０１２９】
ケース８、９は、交差点に存在する道路が全て異種であり、対象道路と同じ幅の道路が接続道路内に存在しない場合である。ケース８は対象道路よりも大きい幅の道路が一本でも存在する場合であり、かかる場合には、末端形状は矩形とする。ケース９は、接続道路が全て対象道路よりも小さい幅の場合であり、かかる場合には、対象道路について凸ポリゴン化処理を施す。
【０１３０】
図１８は変形例における末端処理のフローチャートである。図１７に示したケース１〜９の順序で、それぞれの条件に合致するか否かを判断する場合の処理例を示した。図１７の各ケースに該当するか否かは、ケース９〜１の順序など任意の判定順序で判断可能である。末端処理のフローチャートは、この判定順序に応じて異なる。従って、図１８は図１７のケースの使い分けを実現する処理の一例に過ぎない。
【０１３１】
この処理では、ＣＰＵは処理対象となる道路（対象道路）を選択する（ステップＳ６１）。次にＣＰＵはケース１の条件、即ち接続道路の有無を判定する（ステップＳ６２）。接続道路がない場合には、ケース１に該当するから、ＣＰＵは末端形状は矩形とする（ステップＳ６３）。
【０１３２】
接続道路が有る場合（ステップＳ６２）、ＣＰＵは対象道路と接続道路の種別の関係を判断する（ステップＳ６４）。対象道路と接続道路が全て同一の場合には、ケース２に該当するから、ＣＰＵは接続処理を実行する（ステップＳ６５）。
【０１３３】
対象道路と接続道路に同一／異種が混在する場合において（ステップＳ６４）、接続性が有る場合（ステップＳ６６）はケース３に該当するから、ＣＰＵは接続処理を実行する（ステップＳ６５）。接続性がない場合にはケース４に該当するから、ＣＰＵは凸ポリゴン化処理を行う（ステップＳ６７）。
【０１３４】
接続道路には対象道路と同一種別の道路が無い場合において（ステップＳ６４）、接続道路間に同一種別が有る場合には（ステップＳ６８）、ケース５に該当するため、ＣＰＵは凸ポリゴン化処理を行う（ステップＳ６７）。
【０１３５】
接続道路間に同一種別が無い場合には（ステップＳ６８）、接続道路間に同一幅の道路が有るか否かを判断する（ステップＳ６９）。同一幅の道路がある場合において、接続性が有る場合には（ステップＳ７０）、ケース６に該当するため、ＣＰＵは接続処理を行う（ステップＳ７１）。接続性が無い場合には（ステップＳ７０）、ケース７に該当するため、ＣＰＵは凸ポリゴン化処理を行う（ステップＳ７３）。
【０１３６】
接続道路間に同一幅の道路が無い場合において（ステップＳ６９）、対象道路よりも幅広の接続道路が有る場合には（ステップＳ７２）、ケース８に該当するため、ＣＰＵは、末端形状を矩形とする（ステップＳ７４）。幅広の接続道路が無い場合には（ステップＳ７２）、ケース９に相当するため、ＣＰＵは凸ポリゴン化処理を施す（ステップＳ７３）。  
【０１３７】
図１９は変形例における末端処理の例を示す説明図である。図中の道路Ｒ１１〜Ｒ１７は国道、道路Ｒ２１〜Ｒ２４は県道、道路Ｒ３１〜Ｒ３３は一般道であるものとする。
【０１３８】
交差点ＩＣ３は、国道Ｒ１２、Ｒ１３、および県道Ｒ２２、Ｒ２３が混在しており、接続性が有るため、図１７中のケース３に相当する。従って、国道Ｒ１２、Ｒ１３間で接続処理が施され、県道Ｒ２２、Ｒ２３間で接続処理が施される。図中では、国道Ｒ１３に接続処理を施した結果を太線およびハッチングを付して示した。
【０１３９】
交差点ＩＣ４は、国道Ｒ１４、Ｒ１５および県道Ｒ２１が混在しており、国道同士は接続性がないため、図１７中のケース４に相当する。従って、国道Ｒ１４、Ｒ１５に対して、それぞれ凸ポリゴン化処理が施される。図中には、国道Ｒ１４に対する処理結果を太線およびハッチングを付して示した。
【０１４０】
交差点ＩＣ５には、国道Ｒ１１と、県道Ｒ２１、Ｒ２２が混在している。国道Ｒ１１を対象道路とする場合、接続道路Ｒ２１、Ｒ２２同士は同一種別であるが、対象道路とは異なる種別である。従って、交差点ＩＣ５は、図１７中のケース５に相当し、国道Ｒ１１には凸ポリゴン化処理が施される。この例では、対象道路Ｒ１１は、接続道路Ｒ１２、Ｒ２２よりも優先度が高いため、余分な部分の削除が行われている。図中には、国道Ｒ１１に対する処理結果を太線およびハッチングで示した。なお、対象道路Ｒ１１が接続道路Ｒ１２、Ｒ２２よりも優先度の低い一般道であり、かつ、対象道路Ｒ１１の幅の方が接続道路の幅よりも狭い場合には、対象道路Ｒ１１の末端は、図中に破線で示したように凸ポリゴン化されることになる。
【０１４１】
なお、交差点ＩＣ５は、県道Ｒ２１、Ｒ２２にとっては、ケース３に相当する。従って、県道Ｒ２１、Ｒ２２には接続処理が施される。ただし、図の煩雑化を回避するため、処理結果の図示は省略した。
【０１４２】
交差点ＩＣ６は、国道Ｒ１６、県道Ｒ２１、一般道Ｒ３１が混在している。ただし、国道Ｒ１６と県道Ｒ２１は同じ幅であるとし、両者間は接続性有りとする。この場合、交差点ＩＣ６は、図１７のケース６に相当し、国道Ｒ１６と県道Ｒ２１に対して接続処理が施される。図中には、国道Ｒ１６に対する処理結果を太線およびハッチングで示した。
【０１４３】
交差点ＩＣ７は、国道Ｒ１７、県道Ｒ２４、一般道Ｒ３３が混在している。国道Ｒ１７と県道Ｒ２４は同じ幅であるが、両者間は接続性無しとする。この場合、交差点ＩＣ７は、図１７のケース７に相当し、国道Ｒ１７および県道Ｒ２４に対して、それぞれ凸ポリゴン化処理が施される。図中には、国道Ｒ１７，県道Ｒ２４に対する処理結果を太線およびハッチングで示した。
【０１４４】
交差点ＩＣ９は、国道Ｒ１３、県道Ｒ２４、一般道Ｒ３２が混在している。国道Ｒ１３を対象道路とする時、接続道路は全て対象道路よりも狭い幅の道路となる。国道Ｒ１３にとって交差点ＩＣ９は図１７のケース９に相当するため、国道Ｒ１３には凸ポリゴン化処理が施される。図中には、国道Ｒ１３に対する処理結果を太線およびハッチングで示した。
【０１４５】
交差点ＩＣ９は、県道Ｒ２４および一般道Ｒ３２を対象道路とする時には、接続道路の中に対象道路よりも幅が広い国道Ｒ１３が存在する。従って、交差点ＩＣ９はケース８に相当するため、県道Ｒ２４、一般道Ｒ３２の末端形状は矩形のままとされる。変形例で示した使い分けも一例に過ぎず、末端処理の使い分けは、更に種々の条件で使い分けることが可能である。
【０１４６】
Ｆ．縁線処理：
図２０は縁線処理の具体例を示す説明図である。縁線処理は、対象道路について、他のポリゴンとの接続状態または重なり状態に応じて、縁線の不要な部分を消去する処理である。図２０には、Ｇ１１〜Ｇ１３、Ｇ２０、Ｇ３０、Ｇ４１〜Ｇ４２、Ｇ５０、Ｇ６１〜Ｇ６２、Ｇ７１〜Ｇ７２の各ポリゴンが存在する場合について処理例を示した。Ｇ１１〜Ｇ１３、Ｇ４１〜Ｇ４２、Ｇ６１〜Ｇ６２、Ｇ７１〜Ｇ７２はそれぞれグループ化されている。図中では、縁線処理を施す前のポリゴン形状を実線または破線で示した。図中の太線は縁線処理を施した後の縁線の状態を表している。
【０１４７】
ポリゴンＧ３０について処理する場合について説明する。処理前の時点では、図中の破線で示した部分も含めてポリゴンＧ３０の全周に縁線が生成されている。この例では、ポリゴンＧ３０は、ポリゴンＧ１３、Ｇ１２と接続されている。両者が接続しているか否かは、ポリゴンＧ３０、Ｇ１２、Ｇ１３の交点にノードがあるか否かによって判別可能である。ポリゴンＧ３０、Ｇ１２、Ｇ１３が接続している場合には、それぞれのポリゴンの側線の交点で縁線を切断し、不要な部分を消去する。
【０１４８】
ポリゴンＧ７１について処理する場合について説明する。ポリゴンＧ７１は高さレベル０の一般道であるとする。一方、ポリゴンＧ７１に交差するポリゴンＧ１３は高さレベル２の国道であるとする。つまり、高さレベル２のポリゴンＧ１３は、高さレベル０のポリゴンＧ７１の上を通過する高架道路である。かかる場合には、上に位置するポリゴンＧ１３の縁線を優先し、下に位置するポリゴンＧ７１の縁線のうち、ポリゴンＧ１３の内部に存在する部分を消去することで高架道路を表現することができる。
【０１４９】
但し、本実施例では、高架道路についてはポリゴンの描画順序を制御することで、実際に縁線の消去を行うことなく表現する手法を採用した。つまり、地図を表現する際に、下位に位置するポリゴンＧ７１を描いた後、上位に位置するポリゴンＧ１３を上書きするのである。こうすることによって、下位に位置するポリゴンＧ７１を描いた時点ではその縁線が残っていたとしても、上位に位置するポリゴンＧ１３を上書きすることで図示する状態を実現することができる。
【０１５０】
次に、ポリゴンＧ１１、Ｇ１２およびポリゴンＧ４１、Ｇ４２の処理について説明する。ポリゴンＧ１１、Ｇ１２はグループ化され（以下、「グループ１」と呼ぶ）、一つの連続した道路を表している。ポリゴンＧ４１、Ｇ４２も同様にグループ化され（以下、「グループ４」と呼ぶ）、一つの連続した道路を表している。これら２本の道路は比較的近くを併走している。
【０１５１】
かかる状態では、グループ１、４のポリゴンは一部が重なる場合がある。図中では、ポリゴンの重なり状態が認識しやすいよう、ポリゴンＧ４１、Ｇ４２に部分的にハッチングを付した。現実にこれらの道路同士が高架などで重なっている場合もあれば、リンクから道路ポリゴンを生成する際の幅の設定値（図３参照）によっては現実に重なっていない道路同士が重なって表現される可能性もある。
【０１５２】
本実施例では、２つのグループを比較した場合、各グループに含まれるポリゴンの優劣関係が常に一定となるよう縁線処理を実行する。例えば、図の例では、グループ１をグループ４よりも優先するよう縁線処理を実行する。この結果、グループ１、４のポリゴンが重なっている部分では、常にグループ４のポリゴンの縁線が消去されることになる。この処理も、グループ４に対してグループ１を上書きするよう、描画順序を制御することで実現することができる。
【０１５３】
図の右上にポリゴンの優劣がグループ間で不統一となる場合の処理例を示した。この例では、ポリゴンＧ１２はポリゴンＧ４２よりも優位にあるが、ポリゴンＧ１１はポリゴンＧ４１よりも劣位となっている。この結果、縁線Ｅ２は図示するようにポリゴンＧ４１、Ｇ４２の境界で不連続的に折れ曲がっており、表示時に違和感を生じてしまう。
【０１５４】
これに対し、本実施例の処理によれば、グループ１についての縁線Ｅ１を連続的に描画することができ、表示上の違和感を回避することができる。本実施例の処理は、対象道路の縁線処理に対して、その対象道路とグループ化されたポリゴンについて設定された優劣関係を反映させることにより実現することができる。図の例では、ポリゴンＧ１１を処理する際に、グループ化されたポリゴンＧ１２、Ｇ１３を参照する。ポリゴンＧ１３がポリゴンＧ４２よりも優位となるよう描画順序が設定されている場合には、ポリゴンＧ１１にもこの描画順序を反映すればよい。
【０１５５】
本実施例の縁線処理は、以上で説明した各処理の組み合わせで実現される。図中の例で、ポリゴンＧ２０、Ｇ４０、Ｇ６１〜Ｇ６２の処理については説明を省略したが、既に説明した処理のいずれかを他のポリゴンとの接続状況に応じて適用すればよい。
【０１５６】
図２１は縁線処理のフローチャートである。図２０で説明した縁線処理内容を表したものであり、道路ポリゴン生成処理（図２）のステップＳ５０に相当する処理である。
【０１５７】
処理を開始するとＣＰＵは処理対象道路を選択し（ステップＳ５１）、これにオーバラップするポリゴン（以下、「ＯＬポリゴン」と呼ぶ）、即ち対象道路に一部が重なるポリゴンの有無を判定する（ステップＳ５２）。ＯＬポリゴンが存在しない場合には、他のポリゴンとの重なり具合を考慮する必要がないため、単に道路種別に従って描画順序を設定する（ステップＳ５８）。
【０１５８】
描画順序は値が小さいほど優先度が高く、他のポリゴンの後で上書き描写されることを表している。ＯＬポリゴンが存在しない場合には、各道路種別の中で最低の描画順序に設定するものとした。例えば、国道であれば、描画順序「２０〜２９」までのうち、「２９」に設定するものとした。
【０１５９】
ＯＬポリゴンが存在する場合には（ステップＳ５２）、そのポリゴンが高架か否かを判断する（ステップＳ５３）。この判断は、対象道路とＯＬポリゴンとの高さレベルの比較によって行うことができる。
【０１６０】
高架である場合には、高さレベルに従って、描画順序を決定する（ステップＳ５４）。先に図２０のポリゴンＧ７１の処理で説明した通り、高さレベルが低い値にあるポリゴンよりも高い値にあるポリゴンが優先するように描画順序を設定することになる。
【０１６１】
高架道路ではない場合には（ステップＳ５３）、対象道路およびＯＬポリゴンについて、それぞれグループ化されたポリゴンを抽出する（ステップＳ５５）。先に図４で示した例において、対象道路がＧ１１であるとすると、ポリゴンＧ１１とグループ化されたポリゴンＧ１２、Ｇ１３、およびポリゴンＧ１１にオーバラップするポリゴンＧ４１，Ｇ４２が抽出されることになる。
【０１６２】
ＣＰＵはこうして抽出されたグループ間のいずれかのポリゴンで描画順序の設定がなされているか否かを判定する（ステップＳ５６）。描画順序が設定されている場合には、その既設定値を対象道路の描画順序にも適用し（ステップＳ５７）、設定されていない場合には対象道路の道路種別に従って描画順序を設定する（ステップＳ５８）。これによって、図２０で説明したように、各グループごとに他グループに属するポリゴンとの優劣関係を統一することができ、見栄えを確保することができる。ＣＰＵは以上の処理を全ポリゴンについて完了するまで繰り返し実行する（ステップＳ５９）。フローチャートでは図示を省略したが、ＣＰＵは、以上の処理過程において、不要な縁線の消去を行う。例えば、図２０のポリゴンＧ３０について説明した処理である。
【０１６３】
Ｇ．効果および変形例：
以上で説明した本実施例の地図データ生成装置によれば、ポリゴンのグループ化を行い、縁線処理などの加工に反映させられる。また、対象道路と接続道路の道路種別等を考慮して末端形状の決定方法を使い分けることができる。このような特徴に基づき、地図データ生成装置は、比較的軽い負荷で、見栄えを損なわない道路ポリゴンデータを生成可能である。
【０１６４】
本発明は上述の実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。例えば、実施例で説明した種々の処理は、必ずしも全てを備えている必要はなく、適宜、一部を省略してもよい。また、末端形状の決定処理や縁線処理などについて、実施例で示した処理方法と異なる処理方法を適用可能としてもよい。この場合、他の処理方法は、実施例の処理に追加するようにしてもよいし、実施例で説明した処理と使い分けるようにしてもよい。この他、実施例において、ソフトウェア的に実現されている処理についてはハードウェアで実現することも可能である。
【図面の簡単な説明】
【０１６５】
【図１】実施例としての地図データ生成装置の構成を示す説明図である。
【図２】道路ポリゴン生成処理のフローチャートである。
【図３】ポリゴン化処理のフローチャートである。
【図４】グループ化処理の例を示す説明図である。
【図５】グループ化処理のフローチャートである。
【図６】変形例としてのグループ化処理のフローチャートである。
【図７】接続処理のフローチャートである。
【図８】フィレット処理のフローチャートである。
【図９】凸ポリゴン化処理のフローチャートである。
【図１０】Ｍ字処理の方法を示す説明図である。
【図１１】末端処理方法（１）を示す説明図である。
【図１２】末端処理方法（２）を示す説明図である。
【図１３】凸ポリゴン化処理の効果を示す説明図である。
【図１４】末端処理方法（３）を示す説明図である。
【図１５】末端処理の方法の一覧を示す説明図である。
【図１６】ポリゴンの末端処理のフローチャートである。
【図１７】変形例における末端処理の方法の一覧を示す説明図である。
【図１８】変形例における末端処理のフローチャートである。
【図１９】変形例における末端処理の例を示す説明図である。
【図２０】縁線処理の具体例を示す説明図である。
【図２１】縁線処理のフローチャートである。
【符号の説明】
【０１６６】
１０…地図データ生成装置
１１…通信部
１２…主制御部
１３…中間データ格納部
１４…ポリゴンデータ生成部
１５…グループ化部
１７…縁線処理部
１８…仕様テーブル
４０…ネットワークデータ
５０…ポリゴンデータ
【図１】
2006301601.tif 000003
【図２】
2006301601.tif 000004
【図３】
2006301601.tif 000005
【図４】
2006301601.tif 000006
【図５】
2006301601.tif 000007
【図６】
2006301601.tif 000008
【図７】
2006301601.tif 000009
【図８】
2006301601.tif 000010
【図９】
2006301601.tif 000011
【図１０】
2006301601.tif 000012
【図１１】
2006301601.tif 000013
【図１２】
2006301601.tif 000014
【図１３】
2006301601.tif 000015
【図１４】
2006301601.tif 000016
【図１５】
2006301601.tif 000017
【図１６】
2006301601.tif 000018
【図１７】
2006301601.tif 000019
【図１８】
2006301601.tif 000020
【図１９】
2006301601.tif 000021
【図２０】
2006301601.tif 000022
【図２１】
2006301601.tif 000023