(57)【要約】【課題】道路に沿って実測された道路軌跡データの間引きを効果的に行い、構成点を抽出するとともに、得られた構成点の標高情報に基づき、二次元地図データの各リンクの三次元化を行う道路網データの作成技術を提供する。【解決手段】道路軌跡の３次元座標点列の道路軌跡データが記憶された道路軌跡記憶手段２と、鉛直曲折点を、道路軌跡データの座標点から選択し、構成点データに追加する鉛直曲折点選択手段３を備える。鉛直曲折点選択手段３は、リンクに沿って連続する３つの鉛直曲折点の組み合わせのすべてにおいて、両端の鉛直曲折点を結ぶ直線と中間の鉛直曲折点との間の距離が所定の閾値以下であるように最少の鉛直曲折点を選択する。【選択図】        図１
2007072011.tif 000002
【特許請求の範囲】
【請求項１】
地図上の道路を表すリンクに関わる情報を示すリンクデータ、及び各リンクの位置及び形状を表す構成点に関わる情報を示す構成点データを含んだ道路網データを作成する作成装置であって、
道路に沿って実測された道路軌跡を表す複数の３次元の座標点列からなる道路軌跡データが記憶された道路軌跡記憶手段と、
鉛直方向にリンクが曲折する位置を表す構成点（以下「鉛直曲折点」という。）を、前記道路軌跡データの座標点から選択し、前記構成点データに追加する鉛直曲折点選択手段と、
を備え、
前記鉛直曲折点選択手段は、リンクに沿って連続する３つの前記鉛直曲折点の組み合わせのすべてにおいて、両端の鉛直曲折点を結ぶ直線と中間の鉛直曲折点との間の距離が所定の閾値以下であるように最少の前記鉛直曲折点を選択すること
を特徴とする道路網データの作成装置。
【請求項２】
前記鉛直曲折点選択手段は、
鉛直曲折点を選択する対象となる前記道路軌跡データの区間（以下「処理区間」という。）の初期設定を行う初期設定手段と、
前記処理区間内の座標点のうち、前記処理区間の両端の点（以下「区間端点」という。）を結ぶ直線に対して最遠の座標点を選択しその座標点と直線との間の距離（以下「最遠点距離」という。）を算出する距離算出手段と、
前記最遠点距離が所定の閾値以上の場合、前記最遠の座標点を鉛直曲折点として選択し前記構成点データに追加するとともに、選択した鉛直曲折点と前記各区間端点との間の２つの区間をそれぞれ新たな処理区間に設定する区間再設定手段と、
を備えていることを特徴とする請求項１記載の道路網データの作成装置。
【請求項３】
前記鉛直曲折点選択手段は、
前記初期設定手段が前記処理区間を設定した場合、隣接する２つの座標点間の距離が所定の距離となるように前記道路軌跡データの座標点の一部を選択し、その他の座標点を削除することにより前記道路軌跡データの間引き処理を行う間引き手段
を備えていることを特徴とする請求項１又は２記載の道路網データの作成装置。
【請求項４】
前記構成点データとして、リンクの端点の位置を表す構成点であるノード、及び経緯平面上でリンクが曲折する位置を表す構成点である経緯曲折点が記憶された構成点記憶手段と、
前記鉛直曲折点選択手段により追加された前記各鉛直曲折点について、前記ノード及び前記経緯曲折点により特定されるリンクを経緯平面に射影した射影リンク上における点のうち、当該鉛直曲折点との距離が最短の点の経緯座標を算出する経緯座標算出手段と、
前記各鉛直曲折点の経緯座標を、当該鉛直曲折点に対し前記経緯座標算出手段が算出する経緯座標に補正する経緯座標補正手段と、
を備えていることを特徴とする請求項１乃至３の何れか一記載の道路網データの作成装置。
【請求項５】
前記各リンクについて、前記経緯座標補正手段により補正された前記各鉛直曲折点及び前記各ノードの三次元座標を固定するとともに前記経緯曲折点の経緯座標を固定した状態で、前記経緯曲折点の鉛直座標を、前記各鉛直曲折点及び前記各ノードを補間することにより算出し補正する鉛直座標補正手段
を備えていることを特徴とする請求項４記載の道路網データの作成装置。
【請求項６】
地図上の道路を表すリンクに関わる情報を示すリンクデータ、及び各リンクの位置及び形状を表す構成点に関わる情報を示す構成点データを含んだ道路網データを作成する作成方法であって、
道路に沿って実測された道路軌跡を表す複数の３次元の座標点列からなる道路軌跡データの座標点から、鉛直方向にリンクが曲折する位置を表す構成点（以下「鉛直曲折点」という。）を選択し、前記構成点データに追加する鉛直曲折点選択ステップを有し、
前記鉛直曲折点選択ステップにおいては、リンクに沿って連続する３つの前記鉛直曲折点の組み合わせのすべてにおいて、両端の鉛直曲折点を結ぶ直線と中間の鉛直曲折点との間の距離が所定の閾値以下であるように最少の前記鉛直曲折点を選択すること
を特徴とする道路網データの作成方法。
【請求項７】
前記鉛直曲折点選択ステップは、
（１）鉛直曲折点を選択する対象となる前記道路軌跡データの区間（以下「処理区間」という。）の初期設定を行う初期設定ステップと、
（２）ａ．前記処理区間内の座標点のうち、前記処理区間の両端の点（以下「区間端点」という。）を結ぶ直線に対して最遠の座標点を選択しその座標点と直線との間の距離（以下「最遠点距離」という。）を算出する距離算出処理、
及び、ｂ．前記最遠点距離が所定の閾値以上の場合、前記最遠の座標点を鉛直曲折点として選択し前記構成点データに追加するとともに、選択した鉛直曲折点と前記各区間端点との間の２つの区間をそれぞれ新たな処理区間に設定する区間再設定処理
を行う鉛直曲折点追加ステップと、
を有し、
前記区間再設定処理において新たな２つの処理区間が設定された場合、それぞれの処理区間に対して前記鉛直曲折点追加ステップを再帰的に実行することを特徴とする請求項６記載の道路網データの作成方法。
【請求項８】
前記鉛直曲折点選択ステップは、
前記初期設定ステップにおいて前記処理区間が設定された場合、隣接する２つの座標点間の距離が所定の距離となるように前記道路軌跡データの座標点の一部を選択し、その他の座標点を削除することにより前記道路軌跡データの間引き処理を行う間引きステップを有し、
前記間引き処理が行われた前記道路軌跡データの前記処理区間に対して前記鉛直曲折点追加ステップを再帰的に行うことを特徴とする請求項６又は７記載の道路網データの作成方法。
【請求項９】
初期の前記構成点データとして、リンクの端点の位置を表す構成点であるノード、及び経緯平面上でリンクが曲折する位置を表す構成点である経緯曲折点が予め与えられており、前記鉛直曲折点選択ステップにおいて前記構成点データに前記鉛直曲折点が追加された場合において、
前記鉛直曲折点選択ステップにおいて追加された前記各鉛直曲折点について、前記ノード及び前記経緯曲折点により特定されるリンクを経緯平面に射影した射影リンク上における点のうち、当該鉛直曲折点との距離が最短の点の経緯座標を算出する経緯座標算出ステップと、
前記各鉛直曲折点の経緯座標を、当該鉛直曲折点に対し前記経緯座標算出ステップにおいて算出された経緯座標に補正する経緯座標補正ステップと、
を有することを特徴とする請求項６乃至８の何れか一記載の道路網データの作成方法。
【請求項１０】
前記各リンクについて、前記経緯座標補正ステップにおいて補正された前記各鉛直曲折点及び前記各ノードの三次元座標を固定するとともに前記経緯曲折点の経緯座標を固定した状態で、前記経緯曲折点の鉛直座標を、前記各鉛直曲折点及び前記各ノードを補間することにより算出し補正する鉛直座標補正ステップ
を備えていることを特徴とする請求項９記載の道路網データの作成方法。
【請求項１１】
コンピュータに読み込んで実行することにより、コンピュータを請求項１乃至５の何れか一に記載の道路網データの作成装置として機能させることを特徴とするプログラム。
【請求項１２】
地図上の道路を表すリンクに関わる情報を示すリンクデータ、及び各リンクの位置及び形状を表す構成点に関わる情報を示す構成点データ、を備え、
前記構成点は、リンクの端点の位置を表す構成点であるノード、経緯平面上でリンクが曲折する位置を表す構成点である経緯曲折点、及び鉛直方向にリンクが曲折する位置を表す構成点である鉛直曲折点を含んでいる道路網データのデータ構造であって、
すべての前記鉛直曲折点は、リンクに沿って連続する３つの鉛直曲折点の組み合わせのすべてにおいて、両端の鉛直曲折点を結ぶ直線と中間の鉛直曲折点との間の距離が所定の閾値以下で、且つ当該鉛直曲折点におけるリンクの鉛直方向の曲率が０より大きいことを特徴とする道路網データのデータ構造。
【請求項１３】
地図上の道路を表すリンクに関わる情報を示すリンクデータ、及び各リンクの位置及び形状を表す構成点に関わる情報を示す構成点データ、を備え、
前記構成点は、リンクの端点の位置を表す構成点であるノード、経緯平面上でリンクが曲折する位置を表す構成点である経緯曲折点、及び鉛直方向にリンクが曲折する位置を表す構成点である鉛直曲折点を含んでいる道路網データのデータ構造であって、
すべての前記鉛直曲折点は、当該鉛直曲折点におけるリンクの鉛直方向の曲率が、所定の閾値以上であることを特徴とする道路網データのデータ構造。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は電子地図の道路網データを作成する技術に関し、特に、道路を表す既存のリンクに対して、道路に沿って実測された道路軌跡を表す複数の３次元の道路軌跡データに基づき標高についての形状の補正を行う技術に関する。
【背景技術】
【０００２】
従来、二次元電子地図は広く利用されてきており、二次元電子地図のデータ資源は極めて豊富である。一方、近年は、カーナビゲーションの表示を立体的に行う場合や、自動車の走行状態の総合制御に道路地図の三次元情報を使用する場合など、三次元電子地図の需要が高まりつつある。
【０００３】
そこで、既存の二次元地図データを元に、それに標高データを追加することにより三次元地図データを作成する技術の開発が行われている。かかる地図データの作成技術としては、特許文献１，２に記載のものが公知である。
【０００４】
特許文献１に記載の地図情報作成装置は、道路網がリンク及びノードで表された二次元地図データに対し、各リンク及びノードに標高値情報を発生させて三次元化する。まず、二次元地図データに含まれている道路の構造種別や交差関係の情報から、各リンクの高さを幾つかのレイヤに階層分けする。各レイヤの高さ（標高）は予め固定値として与えられている。そして、階層分けされたリンク間に不自然な高さが生じた場合には、リンク内に新たなノードを発生させる等の処理を行い、高さを補正する。このようにして、各リンク及びノードにレイヤに応じた標高値を与え、三次元地図データを生成する。
【０００５】
しかしながら、この方法によって与えられる各リンク及びノードの標高値は、あくまでも二次元地図データに含まれる各種情報から推定されたものであって、一般に実際の道路の標高値には一致しない。従って、この方法は、カーナビゲーション装置における地図表示のために二次元地図情報を一時的に三次元化して表示する場合には適用可能であるかもしれないが、一般的な三次元電子地図を作成する場合や、自動車の走行状態の総合制御に利用可能な三次元電子地図を作成する場合に適用可能な程度の精度はない。
【０００６】
また、特許文献２には、二次元地図データ、特定の一次基準点における既知の標高データ、及び全地球測位システム（以下「ＧＰＳ」という。）やジャイロを用いて測定車により測定された連続的な測定点列からなる道路軌跡データから、三次元地図データを作成する方法が記載されている。ここで、一次基準点における既知の標高データは、地形図判読、写真測量、レーザー航測等によって得られる。
【０００７】
特許文献２に記載された方法では、まず、道路軌跡データに対して、一次基準点の標高データを用いてキャリブレーションを行う。そして、道路軌跡データにおける鉛直方向又は水平方向の変曲点、及び道路の交差点を二次基準点とし、二次基準点の標高値を道路軌跡データから求める。そして、一次基準点及び二次基準点の標高値を二次元地図データに追加することにより、三次元地図データを作成する。
【０００８】
この方法の欠点は、膨大な測定点数を有する道路軌跡データから適度な数の二次基準点を抽出できない点である。一般に、道路軌跡データは測定誤差や揺らぎによって多くの変曲点が現れる。このような変曲点をすべて二次基準点に取り込むと、データ量が膨大となる。一方、道路軌跡データをスムージングして変曲点を求めることも考えられる。しかし、その場合、二次基準点として取り込まれる測定点の数は削減されるが、今度は道路軌跡データにより表された道路の三次元形状を精度よく再現することができなくなるという問題が生じる。
【０００９】
すなわち、道路軌跡データを用いて二次元地図データを三次元地図データに変換する場合、道路の三次元形状を精度よく再現し且つデータ量ができるだけ少なくなるように、道路軌跡データの測定点を適度に間引くことが最大の重要な点となる。しかしながら、特許文献２においては、このような間引き方法に関しては言及されていない。
【００１０】
一方、一般的な形状点列の間引き方法としては、特許文献３に記載の方法が公知である。
【００１１】
特許文献３には、三次元形状の点列に対し、各点ごとに、その点の前の数点及び後ろの数点から求めた２つの曲線の接線が成す交差角を参照し、間引きの可否を判定する方法が記載されている。この間引き方法は、例えば次のようにして行われる。
【００１２】
例えば、三次元形状の点列（Ｄ１，Ｄ２，…，Ｄ１８）が与えられたとする。このうち、例えば、点Ｄ５の間引きの可否を判定する場合を考える。まず、点Ｄ５の前の３点（Ｄ２，Ｄ３，Ｄ４）及び点Ｄ５を透る仮想曲線を２次近似式により求め、当該仮想曲線の点Ｄ５における接線単位ベクトルＰを求める。同様に、点Ｄ５の後ろ３点（Ｄ６，Ｄ７，Ｄ８）及び点Ｄ５を透る仮想曲線を２次近似式により求め、当該仮想曲線の点Ｄ５における接線単位ベクトルＱを求める。そして、単位ベクトルＰ，Ｑの成す角度がある閾値以上の場合は点Ｄ５を間引き、閾値未満の場合は点Ｄ５を残す。このようにして、三次元形状の点列の間引きを行う。
【特許文献１】特許３６０６８０５号明細書
【特許文献２】特開２００４−３２５７７７号公報
【特許文献３】特許３０７５０２３号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１３】
上記特許文献３に記載の間引き方法を、測定車により走行しながら得られる三次元の道路軌跡データの間引きに適用すれば、道路軌跡の形状の再現性を保持しつつデータ点数を大幅に削減することが可能となり有効である。しかしながら、この方法により間引きを行って、尚、道路軌跡データのデータ量は多い。特に、三次元地図データは、二次元地図データに比べると、非常にデータ量が増えるため、各リンクを構成する構成点数は可能な限り減らすことが好ましい。従って、特許文献３に記載の間引き方法よりも更に効果的に道路軌跡データの間引きを行う方法が求められる。
【００１４】
そこで、本発明の目的は、道路に沿って実測された道路軌跡データの間引きを効果的に行い、構成点を抽出するとともに、得られた構成点の標高情報に基づき、二次元地図データの各リンクの三次元化を行う道路網データの作成技術を提供することにある。
【００１５】
また、本発明の目的は、道路軌跡の形状の再現性を保持しつつ構成点の数を効果的に削減することが可能な道路網データのデータ構造を提供することにある。
【課題を解決するための手段】
【００１６】
本発明に係る道路網データの作成装置の第１の構成は、地図上の道路を表すリンクに関わる情報を示すリンクデータ、及び各リンクの位置及び形状を表す構成点に関わる情報を示す構成点データを含んだ道路網データを作成する作成装置であって、
道路に沿って実測された道路軌跡を表す複数の３次元の座標点列からなる道路軌跡データが記憶された道路軌跡記憶手段と、
鉛直方向にリンクが曲折する位置を表す構成点（以下「鉛直曲折点」という。）を、前記道路軌跡データの座標点から選択し、前記構成点データに追加する鉛直曲折点選択手段と、
を備え、
前記鉛直曲折点選択手段は、リンクに沿って連続する３つの前記鉛直曲折点の組み合わせのすべてにおいて、両端の鉛直曲折点を結ぶ直線と中間の鉛直曲折点との間の距離が所定の閾値以下であるように最少の前記鉛直曲折点を選択することを特徴とする。
【００１７】
この構成によれば、鉛直曲折点選択手段により選択される座標点は、道路軌跡の形状が変化するピークである。鉛直曲折点選択手段に選択されない座標点は、道路軌跡の形状に変化がない部分である。これは、道路軌跡の形状を再現するために重要な座標点のみを選別しているといえる。従って、鉛直曲折点選択手段は道路軌跡データの再現性を保持しつつ、鉛直曲折点の数を最小化とすることができる。
【００１８】
ここで、「道路軌跡データ」としては、ＰＯＳ／ＬＶ（Position and Orientation System for Land Vehicles：商標名）等により得られる走行軌跡データ等を使用することができる。
【００１９】
本発明に係る道路網データの作成装置の第２の構成は、前記第１の構成において、前記鉛直曲折点選択手段は、
鉛直曲折点を選択する対象となる前記道路軌跡データの区間（以下「処理区間」という。）の初期設定を行う初期設定手段と、
前記処理区間内の座標点のうち、前記処理区間の両端の点（以下「区間端点」という。）を結ぶ直線に対して最遠の座標点を選択しその座標点と直線との間の距離（以下「最遠点距離」という。）を算出する距離算出手段と、
前記最遠点距離が所定の閾値以上の場合、前記最遠の座標点を鉛直曲折点として選択し前記構成点データに追加するとともに、選択した鉛直曲折点と前記各区間端点との間の２つの区間をそれぞれ新たな処理区間に設定する区間再設定手段と、
を備えていることを特徴とする。
【００２０】
この構成によれば、まず、（１）初期設定手段は処理区間の初期設定を行う。次に、（２）距離算出手段は、処理区間内の座標点のうち、２つの区間端点を結ぶ直線から最遠の座標点を選択し最遠点距離を算出する。（３）最遠点距離が所定の閾値以上の場合、区間再設定手段は、最遠の座標点を鉛直曲折点として選択し構成点データに追加する。また、選択した鉛直曲折点と各区間端点との間の２つの区間をそれぞれ新たな処理区間に設定する。そして、新たな処理区間に対して、距離算出手段及び区間再設定手段は、再帰的に（２）（３）と同様な処理を行う。
【００２１】
これにより、リンクに沿って連続する３つの鉛直曲折点の組み合わせのすべてにおいて、両端の鉛直曲折点を結ぶ直線と中間の鉛直曲折点との間の距離を所定の閾値以下とすることができる。また、鉛直曲折点の数も最小に抑えることができる。
【００２２】
ここで、初期の処理区間の決め方は特に限定しない。例えば、道路軌跡データを、それに対応するリンクの長さに区切り、それぞれの区間を初期の処理区間とすることができる。
【００２３】
本発明に係る道路網データの作成装置の第３の構成は、前記第１又は２の構成において、前記鉛直曲折点選択手段は、
前記初期設定手段が前記処理区間を設定した場合、隣接する２つの座標点間の距離が所定の距離となるように前記道路軌跡データの座標点の一部を選択し、その他の座標点を削除することにより前記道路軌跡データの間引き処理を行う間引き手段を備えていることを特徴とする。
【００２４】
実際の道路軌跡データは、必ずしも等間隔の座標点列ではない。例えば、ＰＯＳ／ＬＶ（商標名）においては、一定の時間間隔で測定車の位置座標（経緯座標及び標高値）を取得する。この場合、測定車が一定の速度で走行すれば座標点列は等間隔のデータとなるが、通常は一般道において測定車が一定速度で走行するのは困難である。
【００２５】
また、測定車が信号等で停止した場合、同一の位置で多数の座標点が出力される。更に、測定車の停止中には常に同一の座標値が出力されるとは限らず、ＧＰＳやジャイロの測定誤差や大気の揺らぎ等に起因して座標値が微小に揺らいで出力される。
【００２６】
そこで、間引き手段は、隣接する２つの座標点間の距離が所定の距離となるように道路軌跡データの座標点の間引きを行う。これにより、道路軌跡データは一定間隔の座標点列のデータとなる。また、測定車の停止中における座標値の揺らぎの影響も除去することができる。
【００２７】
本発明に係る道路網データの作成装置の第４の構成は、前記第１乃至３の何れか一の構成において、前記構成点データとして、リンクの端点の位置を表す構成点であるノード、及び経緯平面上でリンクが曲折する位置を表す構成点である経緯曲折点が記憶された構成点記憶手段と、
前記鉛直曲折点選択手段により追加された前記各鉛直曲折点について、前記ノード及び前記経緯曲折点により特定されるリンクを経緯平面に射影した射影リンク上における点のうち、当該鉛直曲折点との距離が最短の点の経緯座標を算出する経緯座標算出手段と、
前記各鉛直曲折点の経緯座標を、当該鉛直曲折点に対し前記経緯座標算出手段が算出する経緯座標に補正する経緯座標補正手段と、
を備えていることを特徴とする。
【００２８】
この構成によれば、経緯座標算出手段及び経緯座標補正手段は、道路軌跡データの間引きにより抽出された鉛直曲折点を、経緯平面上で当該鉛直曲折点に最も近いリンク上の点に移動させ、リンク上に新たな構成点を発生させるとともにその構成点に標高値を与える。これにより、各リンクに実測に基づく標高情報を与えることができる。
【００２９】
本発明に係る道路網データの作成装置の第５の構成は、前記第４の構成において、前記各リンクについて、前記経緯座標補正手段により補正された前記各鉛直曲折点及び前記各ノードの三次元座標を固定するとともに前記経緯曲折点の経緯座標を固定した状態で、前記経緯曲折点の鉛直座標を、前記各鉛直曲折点及び前記各ノードを補間することにより算出し補正する鉛直座標補正手段を備えていることを特徴とする。
【００３０】
この構成によれば、鉛直座標補正手段により、鉛直曲折点以外の構成点にも標高値を与え、各リンクの各構成点を完全に三次元化することができる。
【００３１】
本発明に係る道路網データの作成方法の第１の構成は、地図上の道路を表すリンクに関わる情報を示すリンクデータ、及び各リンクの位置及び形状を表す構成点に関わる情報を示す構成点データを含んだ道路網データを作成する作成方法であって、
道路に沿って実測された道路軌跡を表す複数の３次元の座標点列からなる道路軌跡データの座標点から、鉛直方向にリンクが曲折する位置を表す構成点（以下「鉛直曲折点」という。）を選択し、前記構成点データに追加する鉛直曲折点選択ステップを有し、
前記鉛直曲折点選択ステップにおいては、リンクに沿って連続する３つの前記鉛直曲折点の組み合わせのすべてにおいて、両端の鉛直曲折点を結ぶ直線と中間の鉛直曲折点との間の距離が所定の閾値以下であるように最少の前記鉛直曲折点を選択すること
を特徴とする。
【００３２】
本発明に係る道路網データの作成方法の第２の構成は、前記第１の構成において、前記鉛直曲折点選択ステップは、
（１）鉛直曲折点を選択する対象となる前記道路軌跡データの区間（以下「処理区間」という。）の初期設定を行う初期設定ステップと、
（２）ａ．前記処理区間内の座標点のうち、前記処理区間の両端の点（以下「区間端点」という。）を結ぶ直線に対して最遠の座標点を選択しその座標点と直線との間の距離（以下「最遠点距離」という。）を算出する距離算出処理、
及び、ｂ．前記最遠点距離が所定の閾値以上の場合、前記最遠の座標点を鉛直曲折点として選択し前記構成点データに追加するとともに、選択した鉛直曲折点と前記各区間端点との間の２つの区間をそれぞれ新たな処理区間に設定する区間再設定処理
を行う鉛直曲折点追加ステップと、
を有し、
前記区間再設定処理において新たな２つの処理区間が設定された場合、それぞれの処理区間に対して前記鉛直曲折点追加ステップを再帰的に実行することを特徴とする。
【００３３】
本発明に係る道路網データの作成方法の第３の構成は、前記第１又は２の構成において、前記鉛直曲折点選択ステップは、
前記初期設定ステップにおいて前記処理区間が設定された場合、隣接する２つの座標点間の距離が所定の距離となるように前記道路軌跡データの座標点の一部を選択し、その他の座標点を削除することにより前記道路軌跡データの間引き処理を行う間引きステップを有し、
前記間引き処理が行われた前記道路軌跡データの前記処理区間に対して前記鉛直曲折点追加ステップを再帰的に行うことを特徴とする。
【００３４】
本発明に係る道路網データの作成方法の第４の構成は、前記第１乃至３の何れか一の構成において、初期の前記構成点データとして、リンクの端点の位置を表す構成点であるノード、及び経緯平面上でリンクが曲折する位置を表す構成点である経緯曲折点が予め与えられており、前記鉛直曲折点選択ステップにおいて前記構成点データに前記鉛直曲折点が追加された場合において、
前記鉛直曲折点選択ステップにおいて追加された前記各鉛直曲折点について、前記ノード及び前記経緯曲折点により特定されるリンクを経緯平面に射影した射影リンク上における点のうち、当該鉛直曲折点との距離が最短の点の経緯座標を算出する経緯座標算出ステップと、
前記各鉛直曲折点の経緯座標を、当該鉛直曲折点に対し前記経緯座標算出ステップにおいて算出された経緯座標に補正する経緯座標補正ステップと、
を有することを特徴とする。
【００３５】
本発明に係る道路網データの作成方法の第５の構成は、前記第４の構成において、前記各リンクについて、前記経緯座標補正ステップにおいて補正された前記各鉛直曲折点及び前記各ノードの座標を固定するとともに前記経緯曲折点の経緯座標を固定した状態で、前記経緯曲折点の鉛直座標を、前記各鉛直曲折点及び前記各ノードを補間することにより算出し補正する鉛直座標補正ステップを備えていることを特徴とする。
【００３６】
本発明に係るプログラムは、コンピュータに読み込んで実行することにより、コンピュータを前記第１乃至５の何れか一の構成の道路網データの作成装置として機能させることを特徴とする。
【００３７】
本発明に係る道路網データのデータ構造の第１の構成は、地図上の道路を表すリンクに関わる情報を示すリンクデータ、及び各リンクの位置及び形状を表す構成点に関わる情報を示す構成点データ、を備え、
前記構成点は、リンクの端点の位置を表す構成点であるノード、経緯平面上でリンクが曲折する位置を表す構成点である経緯曲折点、及び鉛直方向にリンクが曲折する位置を表す構成点である鉛直曲折点を含んでいる道路網データのデータ構造であって、
すべての前記鉛直曲折点は、リンクに沿って連続する３つの鉛直曲折点の組み合わせのすべてにおいて、両端の鉛直曲折点を結ぶ直線と中間の鉛直曲折点との間の距離が所定の閾値以下で、且つ当該鉛直曲折点におけるリンクの鉛直方向の曲率が０より大きいことを特徴とする。
【００３８】
この構成によれば、道路軌跡の形状の再現性を保持しつつ構成点の数を効果的に削減することが可能な道路網データのデータ構造を提供することができる。
【００３９】
本発明に係る道路網データのデータ構造の第２の構成は、地図上の道路を表すリンクに関わる情報を示すリンクデータ、及び各リンクの位置及び形状を表す構成点に関わる情報を示す構成点データ、を備え、
前記構成点は、リンクの端点の位置を表す構成点であるノード、経緯平面上でリンクが曲折する位置を表す構成点である経緯曲折点、及び鉛直方向にリンクが曲折する位置を表す構成点である鉛直曲折点を含んでいる道路網データのデータ構造であって、
すべての前記鉛直曲折点は、当該鉛直曲折点におけるリンクの鉛直方向の曲率が、所定の閾値以上であることを特徴とする。
【００４０】
この構成によれば、道路軌跡の形状の再現性を保持しつつ構成点の数を効果的に削減することが可能な道路網データのデータ構造を提供することができる。
【発明の効果】
【００４１】
以上のように、本発明に係る道路網データの作成装置及び作成方法によれば、道路に沿って実測された道路軌跡データの間引きを効果的に行い、構成点を抽出するとともに、得られた構成点の標高情報に基づき、二次元地図データの各リンクの三次元化を行うことが可能となる。
【００４２】
また、に係る道路網データのデータ構造によれば、道路軌跡の形状の再現性を保持しつつ構成点の数を効果的に削減することが可能なとなる。
【発明を実施するための最良の形態】
【００４３】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００４４】
図１は、本発明の実施例１に係る道路網データ作成装置１の構成を表すブロック図である。本実施例１に係る道路網データ作成装置１は、道路軌跡記憶手段２、鉛直曲折点選択手段３、鉛直曲折点記憶手段４、構成点記憶手段５、経緯座標算出手段６、経緯座標補正手段７、鉛直座標補正手段８、及び標高点記憶手段９を備えている。
【００４５】
道路軌跡記憶手段２は、道路に沿って実測された道路軌跡を表す複数の３次元の座標点列からなる道路軌跡データが記憶されている。道路軌跡データは、具体的には、ＰＯＳ／ＬＶのような移動体用高精度位置標定システムにより道路に沿って測定される。
【００４６】
図２に、道路軌跡データのデータ構造を示す。道路軌跡データは、ｎ１（ｎ１≧１）の道路軌跡レコードにより構成される。各道路軌跡レコードは、移動体用高精度位置標定システムによる１回の測定で得られた道路軌跡データを表している。各道路軌跡レコードは、複数の計測点位置情報の集合からなる。ここで、計測点位置情報は、移動体用高精度位置標定システムにより計測された道路上の点の緯度，経度，標高からなる。
【００４７】
構成点記憶手段５は、道路網データを記憶する。ここで、道路網データの構造について説明しておく。
【００４８】
図３は、道路網データの一例を表す図である。道路網データは、地図上の各道路に一対一対応する“リンク”及び“ノード”により構成される。「ノード」とは、道路の交差点、又は橋やトンネルの起終点をいう。「リンク」とは、ノードを結ぶ線分をいう。尚、本明細書においては、「交差点」とは、２本以上の道路が接続する地点をいう。ｎ本（ｎ≧２）の道路が接続する地点を、特に「ｎ差路」と呼ぶ。ｎ＝２の場合、一般的には交差点とは呼ばないが、電子地図を取り扱う上では、これも便宜上、交差点の一種とみなし、このような交差点を「二差路」と呼ぶ。
【００４９】
図３においては、Ｌ１〜Ｌ１４がリンクを表し、Ｎ１〜Ｎ７がノードを表す。地図上の道路網は、リンクの集合とノードの集合からなる無向グラフとして表現される。各リンクは、直線又は１以上の折点を有する折線により表現される。リンクの端点及び折点を、当該リンクの「構成点」と呼ぶ。１つのリンクは２以上の構成点を有する。図３においては、構成点は「○」及び「△」で表されている。
【００５０】
二次元地図においては、構成点は経緯座標（二次元座標）により特定される。図４は、電子地図における道路網データのデータ構造を表す。図４（ａ）は二次元地図の場合であり、図４（ｂ）は三次元地図の場合である。
【００５１】
二次元地図の道路網データ（図４（ａ））は、各リンクに対応して設けられた、複数の２Ｄ空間レコードを有する。各２Ｄ空間レコードは、“オブジェクトＩＤ”，“地物種別”，“構成点数”，及び複数の“構成点情報”を有する。
【００５２】
「オブジェクトＩＤ」は、当該２Ｄ空間レコードに対応するオブジェクトを特定するための識別番号である。「地物種別」とは、当該２Ｄ空間レコードに対応するオブジェクトの種類を表す情報である。地物種別はさらに｛地物分類コード，道路種別コード，リンク種別コード｝の組により構成されている。
【００５３】
「地物分類コード」は、オブジェクトの種類を表し、‘リンク’，‘ノード’がある。
【００５４】
道路種別コード及びリンク種別コードは、地物分類が‘リンク’の場合に有効となる。「道路種別コード」は、道路種別を表し、例えば、‘未定義’，‘高速道路’，‘都市高速’，‘一般国道’，‘主要地方道’，…のように定められる。「リンク種別コード」は、道路の形状や種別による分類を表し、例えば、‘上下線分離道路’，‘本線’，‘本線渡り線’，‘ランプ（取り付け道路）’，…のように定められる。
【００５５】
「構成点数」は、地物分類コードが‘リンク’の場合に有効な情報であり、当該オブジェクトに対応するリンク内の構成点の数を表す。「構成点情報」は、各構成点の位置座標（経緯座標）を表す情報であり、“緯度”と“経度”からなる。
【００５６】
一方、三次元地図の道路網データ（図４（ｂ））は、各リンクに対応して設けられた、複数の３Ｄ空間レコードを有する。３Ｄ空間レコードのデータ構造は、基本的には２Ｄ空間レコードと同様である。但し、３Ｄ空間レコードの場合、“構成点情報”が各構成点の３次元位置座標である点で異なる。すなわち、３Ｄ空間レコードの構成点情報は、各構成点の“緯度”，“経度”，及び“標高”からなる。
【００５７】
本実施例の道路網データ作成装置１は、二次元地図の道路網データを三次元地図の道路網データに変換する。従って、初期状態においては、構成点記憶手段５には、図４（ａ）に示した二次元地図の道路網データが記憶されている。
【００５８】
二次元地図においては、構成点は、（１）リンクの端点、（２）経緯平面上でリンクが曲折する点、（３）立体交差点、及び（４）道路の構造種別が変化する点、に設定されている。
【００５９】
ここで、道路の「構造種別」とは、道路構造の種類をいう。構造種別は、例えば、‘種別なし’，‘橋’，‘高架’，‘トンネル’，‘切取’，‘盛土’，…のような値を採る。構造種別は、各リンクの道路属性を指定する道路属性情報によって指定される。道路属性情報は、構成点記憶手段５に記憶されている。道路属性情報については、本発明に直接関係がないため、詳細な説明は省略するが、本実施例の理解を助けるため、そのデータ構造について簡単に説明しておく。
【００６０】
図５は、道路属性情報のデータ構造を表す。道路属性情報は、各リンクに一対一に対応して設けられた複数の“道路属性レコード”からなる。各道路属性レコードは、｛“オブジェクトＩＤ”，“始点オブジェクトＩＤ”，“終点オブジェクトＩＤ”，“相対高さ情報数（ｑｉ）”，ｑｉ個の“構造種別情報数（ｒｉ）”，ｑｉ個の“相対高さ情報”，ｒｉ個の“構造種別情報”｝の組から構成されている。
【００６１】
「オブジェクトＩＤ」は、当該道路属性レコードに対応するリンク（以下「レコード対応リンク」という。）のオブジェクトＩＤである。「始点オブジェクトＩＤ」及び「終点オブジェクトＩＤ」は、それぞれ、レコード対応リンクの始点及び終点のノードのオブジェクトＩＤである。「相対高さ情報数」は、当該道路属性レコードに格納される“相対高さ情報”の数である。「構造種別情報数」は、当該道路属性レコードに格納される“構造種別情報”の数である。
【００６２】
「相対高さ情報」とは、レコード対応リンクとそれに交差する他のリンク（以下「交差リンク」という。）との交差の状態に関する情報である。相対高さ情報は、“位置”，“相対高さ”，“立体交差フラグ”，“構造種別”から構成される。「位置」は、レコード対応リンクと交差リンクとが立体交差する点（以下「リンク交差点」という。）の位置を表し、レコード対応リンクの長さを１として、レコード対応リンクの始点からリンク交差点までの長さで表される。「相対高さ」は、交差リンクに対するレコード対応リンクの相対位置を表し、レコード対応リンクが上側の場合は‘オーバーパス’，下側の場合は‘アンダーパス’に設定される。「立体交差フラグ」は、リンク交差点が立体交差点か否かを表すフラグであり、立体交差点の場合は１，立体交差点でない場合は０が設定される。「構造種別」は、交差リンクのリンク交差点における構造種別を表すコードである。
【００６３】
「構造種別情報」とは、レコード対応リンクの所定区間における構造種別の情報である。構造種別情報は、｛“構造種別コード”，“対象サイド”，“区間開始位置”，“区間終了位置”｝の組から構成される。「区間開始位置」及び「区間終了位置」は、当該構造種別情報によって構造種別が指定されるレコード対応リンクの区間の開始位置及び終了位置を表す。開始位置及び終了位置は、レコード対応リンクの長さを１として、レコード対応リンクの始点から開始位置又は終了位置までの長さで表される。「対象サイド」とは、当該構造種別情報によって構造種別が指定されるレコード対応リンクのサイド（始点から終点に向かって見たときのサイド）を表し、‘両側’，‘左側’，‘右側’のいずれかの値を採る。「構造種別」とは、対象区間，対象サイドにおけるレコード対応リンクの構造種別を表すコードである。
【００６４】
次に、図１の標高点記憶手段９について説明する。標高点記憶手段９は、二次元地図上の特定の点（標高点）で測定された標高値に関する情報（以下「標高点情報」という。）を記憶する。図６に、標高点情報のデータ構造を表す。
【００６５】
「標高点」とは、都市計画図，三角点，水準点等によって標高値が与えられている、標高が既知の地点をいう。ここでは、各標高点もそれぞれが一つのオブジェクトとして取り扱われる。
【００６６】
標高点ファイルは、“標高点数（ｎ４）”，及びｎ４個の“標高点レコード”から構成されている。「標高点数」は、標高点ファイル内に含まれる標高点の数を表す。「標高点レコード」は、各標高点に対して一対一に設けられており、その標高点に関する情報を格納するレコードである。
【００６７】
各標高点レコードは、｛“オブジェクトＩＤ”，“標高点座標”，“標高点種別”，“標高点値”，“地物区別”｝の組からなる。「オブジェクトＩＤ」は、当該標高点レコードに対応する標高点（以下「レコード対応標高点」という。）のオブジェクトＩＤである。「標高点座標」は、レコード対応標高点の位置座標（経緯座標）を表す情報であり、“緯度”と“経度”からなる。「標高点種別」は、レコード対応標高点の種類を表し、例えば、‘三角点’，‘水準点’，‘多角点及び標石のある図根点’，‘その他の標高点’のような値を採る。「標高点値」は、レコード対応標高点の標高値である。「地物区別」は、レコード対応標高点が置かれている地物を表し、‘地表’又は‘高架’の値を採る。すなわち、標高点は必ずしも地表に置かれているとは限られず、高架上に置かれている場合もある。従って、“地物区別”によって、標高点が地表に置かれているか高架上に置かれているかを区別する。
【００６８】
また、図１において、鉛直曲折点選択手段３は、鉛直方向にリンクが曲折する位置を表す構成点（鉛直曲折点）を、道路軌跡データ中の座標点から選択し、構成点データに追加する。鉛直曲折点記憶手段４は、鉛直曲折点選択手段３が選択した鉛直曲折点を一時的に記憶する。
【００６９】
ここで、鉛直曲折点選択手段３は、初期設定手段１１、区間記憶手段１２、間引き手段１３、距離算出手段１４、及び区間再設定手段１５を有する。
【００７０】
初期設定手段１１は、鉛直曲折点を選択する対象となる道路軌跡データの区間（処理区間）の初期設定を行う。区間記憶手段１２は、処理設定区間を記憶する。間引き手段１３は、初期設定手段１１が処理区間を設定した場合、隣接する２つの座標点間の距離が所定の距離となるように道路軌跡データの座標点の一部を選択し、その他の座標点を削除することにより道路軌跡データの間引き処理を行う。距離算出手段１４は、処理区間内の座標点のうち、処理区間の両端の点（区間端点）を結ぶ直線に対して最遠の座標点を選択しその座標点と直線との間の距離（最遠点距離）を算出する。区間再設定手段１５は、最遠点距離が所定の閾値以上の場合、最遠の座標点を鉛直曲折点として選択し構成点データに追加するとともに、選択した鉛直曲折点と各区間端点との間の２つの区間をそれぞれ新たな処理区間に設定する。
【００７１】
経緯座標算出手段６は、鉛直曲折点選択手段３により選択された各鉛直曲折点について、その鉛直曲折点に最も近いリンク上の点の経緯座標を算出する。すなわち、ノード及び経緯曲折点により特定される二次元地図のリンクにおいて、当該鉛直曲折点との距離が最短の点の経緯座標を算出する。経緯座標補正手段７は、各鉛直曲折点の経緯座標の補正を行う。すなわち、当該鉛直曲折点の経緯座標を、当該鉛直曲折点に対し経緯座標算出手段６が算出した経緯座標に補正する。
【００７２】
鉛直座標補正手段８は、各リンクについて、経緯座標補正手段７により補正された各鉛直曲折点及び各ノードの三次元座標を固定し経緯曲折点の経緯座標を固定した状態で、経緯曲折点の鉛直座標を、各鉛直曲折点及び各ノードを補間することにより算出し補正する。
【００７３】
尚、本実施例の道路網データ作成装置１は、図１に示した各機能ブロックをハードウェア的に構成してもよい。また、各機能ブロックをプログラムによって構成し、当該プログラムをコンピュータで実行することによって道路網データ作成装置１の機能を実現する構成としてもよい。
【００７４】
以上のように構成された本実施例に係る道路網データ作成装置１について、以下その動作を説明する。
【００７５】
図７は、実施例１に係る道路網データ作成装置１の動作の全体の流れを表すフローチャートである。道路網データ作成装置１は、上記二次元の道路網データ、標高点データ、及び道路軌跡データに基づいて、上記三次元の道路網データの生成を行う。処理の流れとしては、初期設定（Ｓ１）、等間隔間引き処理（Ｓ２）、鉛直曲折点選択処理（Ｓ３）、鉛直曲折点取り込み処理（Ｓ４）、経緯曲折点補正処理（Ｓ５）の順序で実行される。以下、それぞれのステップでの処理について、順を追って説明する。
【００７６】
〔１〕初期設定（Ｓ１）
初期設定においては、初期設定手段１１が処理区間を設定し、処理区間の道路軌跡データを道路軌跡記憶手段２から読み出して区間記憶手段１２に一時保存する。
【００７７】
〔２〕等間隔間引き処理（Ｓ２）
等間隔間引き処理においては、区間記憶手段１２に記憶されている初期の道路軌跡データに対して、一定の間隔で間引きを行う。この等間隔間引き処理の目的は、道路軌跡データを一定間隔の座標点列のデータとし、また、測定車の停止中における座標値の揺らぎの影響を除去することにある。
【００７８】
具体的に説明すると、測定車で走行しながら移動体用高精度位置標定システムによって測定された道路軌跡データは、図９（ａ）に示すように、測定車の停止中における座標値の揺らぎを含む場合がある。
【００７９】
本来は、測定車の停止中には計測位置情報は同じ座標値であるはずである。しかしながら、移動体用高精度位置標定システムの精度上、測定車の停止中の計測位置情報が同じ座標値を示さず揺らぐことがある。このような揺らぎを含むデータに対して、後述の曲折点選択処理（Ｓ３）によって曲折点の選択を行うと、本来、図９（ｂ）に示すように、滑らかにカーブするように曲折点の選択を行うべきところであっても、図９（ａ）のように測定点の誤差の影響が直接反映されて曲折点の選択がされてしまうおそれがある。
【００８０】
そこで、曲折点選択処理（Ｓ３）を実行する前に、等間隔間引き処理（Ｓ２）において測定車の停止中における座標値の揺らぎの除去を行う。
【００８１】
図８は、ステップＳ２における等間隔間引き処理の流れを表すフローチャートである。この処理では、間引き手段１３は、時間的等間隔の間引きを行う。
【００８２】
ステップＳ１１において、間引き手段１３は、内部変数として有するインデックスｎ，ｍ、及びパラメータｔをそれぞれ１，０，０に初期化する。インデックスｎは間引きを行う前の道路軌跡データの測定点のインデックス、インデックスｍは間引き後の道路軌跡データの測定点のインデックス、インデックスｔは間引き間隔を測るためのパラメータである。
【００８３】
ステップＳ１２において、間引き手段１３は、区間記憶手段１２から、間引きを行う前の道路軌跡データの測定点ｐ（ｎ）を読み出す。
【００８４】
ステップＳ１３において、間引き手段１３は、パラメータｔが所定の間引き間隔Ｔに達したか否かを判定する。ｔ＜Ｔの場合、ステップＳ１４に移行し、ｔ＝Ｔの場合、ステップＳ１５に移行する。
【００８５】
ステップＳ１４においては、間引き手段１３は、パラメータｔを１だけインクリメントし、ステップＳ１８へ移行する。
【００８６】
一方、ステップＳ１５においては、間引き手段１３は、インデックスｍを１だけ増加させる。そして、ステップＳ１６において、間引き後の道路軌跡データｐ１（ｍ）に道路軌跡データｐ（ｎ）の値を代入し、ステップＳ１７において、パラメータｔを０に設定した後、ステップＳ１８へ移行する。
【００８７】
ステップＳ１８において、間引きを行う前の道路軌跡データのすべての測定点の読み出しが終了したか否かを判定する。すべての測定点の読み出しが終了した場合には、等間隔間引き処理を終了する。まだ終了していない場合には、ステップＳ１９において、インデックスｎを１だけ増加させた後、ステップＳ１２に戻る。
【００８８】
以上のような処理により、道路軌跡データは、時間的に等間隔で間引きがされる。尚、ここで間引き間隔Ｔの大きさは、道路軌跡データの測定間隔に応じて適宜決定されるが、間引き後の道路軌跡データは道路形状を十分な精度で再現できる程度の間隔とされる。
【００８９】
図１０は、図８の等間隔間引き処理による道路軌跡データのデータ削減の様子を図示したものである。この処理により、元の道路軌跡データ（図１０（ａ））は、一定の点数ごとにサンプリングされ、図１０（ｂ）のようにデータ数が削減される。
【００９０】
尚、図８では、時間的に等間隔の間引きを行うようにしたが、等間隔間引き処理の他の例として、距離的等間隔の間引きを行うようにすることもできる。
【００９１】
図１１は、ステップＳ２における等間隔間引き処理の他の例の流れを表すフローチャートである。この処理では、間引き手段１３は、距離的等間隔の間引きを行う。
【００９２】
ステップＳ２１において、間引き手段１３は、内部変数として有するインデックスｎ，ｍを１に初期化する。インデックスｎは間引きを行う前の道路軌跡データの測定点のインデックス、インデックスｍは間引き後の道路軌跡データの測定点のインデックスである。
【００９３】
ステップＳ２２において、間引き手段１３は、間引き後の測定点ｐ１（ｍ）（＝ｐ１（１））に間引き前の測定点ｐ（ｎ）（＝ｐ（１））を設定する。
【００９４】
ステップＳ２３において、間引き手段１３は、インデックスｎの値を１だけ増加させる。そして、ステップＳ２４において、間引き手段１３は、間引き前の測定点ｐ（ｎ）を読み出す。
【００９５】
次に、ステップＳ２５において、間引き手段１３は、ｐ（ｎ）とｐ１（ｍ）との間の三次元的な距離｜ｐ（ｎ）−ｐ１（ｍ）｜を計算する。そして、距離｜ｐ（ｎ）−ｐ１（ｍ）｜が所定の間引き間隔Ｌ以上か否かを判定する。間引き間隔Ｌ以上の場合はステップＳ２６に移行し、そうでない場合はステップＳ２８に移行する。
【００９６】
ステップＳ２６においては、間引き手段１３は、インデックスｍを１だけ増加させる。そして、ステップＳ１６において、間引き後の道路軌跡データｐ１（ｍ）に道路軌跡データｐ（ｎ）の値を代入した後、ステップＳ２８へ移行する。
【００９７】
ステップＳ２８において、間引きを行う前の道路軌跡データのすべての測定点の読み出しが終了したか否かを判定する。すべての測定点の読み出しが終了した場合には、等間隔間引き処理を終了する。まだ終了していない場合にはステップＳ２３に戻る。
【００９８】
この図１１の等間隔間引き処理における間引き間隔Ｌは、道路軌跡データの測定間隔に応じて適宜決定されるが、間引き後の道路軌跡データは道路形状を十分な精度で再現できる程度の間隔とされる。図１２に、図１１の等間隔間引き処理による道路軌跡データの間引きを行った例を示す。図１２（ａ）は間引き間隔Ｌが１０ｍ、図１２（ａ）は間引き間隔Ｌが５ｍ、図１２（ａ）は間引き間隔Ｌが２ｍ、図１２（ａ）は間引き間隔Ｌが１ｍである。この場合、間引き間隔Ｌは、１〜２ｍ程度が適当であることがわかる。
【００９９】
〔３〕鉛直曲折点選択処理（Ｓ３）
鉛直曲折点選択処理（Ｓ３）は、リンクに沿って連続する３つの鉛直曲折点の組み合わせのすべてにおいて、両端の鉛直曲折点を結ぶ直線と中間の鉛直曲折点との間の距離が所定の閾値以下であるように最少の鉛直曲折点を選択する処理である。
【０１００】
図１３は、ステップＳ３における鉛直曲折点選択処理の流れを表すフローチャートである。
【０１０１】
最初に、ステップＳ３１において、処理区間の初期設定がされる。この場合の処理区間は、等間隔間引き処理（Ｓ２）で得られた間引き後の道路軌跡データ｛ｐ１（ｉ）｜ｉ＝１，２，…，Ｍ｝の全区間［ｐ１（１），ｐ１（Ｍ）］とされる。
【０１０２】
そして、ステップＳ３２において、鉛直曲折点追加処理を再帰的に実行し、鉛直曲折点選択処理を終了する。
【０１０３】
図１４は、ステップＳ３２における鉛直曲折点追加処理の流れを表すフローチャートである。図１４において、最初に設定されている処理区間は［ｐ１（ｉ），ｐ１（ｊ）］とする。
【０１０４】
まず、ステップＳ５１において、距離算出手段１４は、処理区間［ｐ１（ｉ），ｐ１（ｊ）］のそれぞれの内点ｐ１（ｋ）（ｉ＜ｋ＜ｊ）について、端点ｐ１（ｉ），ｐ１（ｊ）を結ぶ直線Ｌｉｊとの間の距離ｄ（ｐ１（ｋ），Ｌｉｊ）を計算する。そして、距離ｄ（ｐ１（ｋ），Ｌｉｊ）が最大である内点（最遠点）ｐ１（ｋ）を求める。この最遠点における距離ｄ（ｐ１（ｋ），Ｌｉｊ）を最遠点距離といい、ｄと記す。
【０１０５】
次に、区間再設定手段１５は、最遠点距離ｄが閾値ｄｔｈ以上か否かを判定する。ｄ＜ｄｔｈの場合には、鉛直曲折点追加処理を終了する。一方、ｄ≧ｄｔｈの場合は、ステップＳ５３に移行する。
【０１０６】
ステップＳ５３において、区間再設定手段１５は、最遠点ｐ１（ｋ）を鉛直曲折点に追加し、鉛直曲折点記憶手段４に保存する。
【０１０７】
次に、ステップＳ５４において、区間再設定手段１５は、処理区間を［ｐ１（ｉ），ｐ１（ｋ）］に設定し、ステップＳ５５において、処理区間［ｐ１（ｉ），ｐ１（ｋ）］に対して鉛直曲折点追加処理を再帰的に実行する。
【０１０８】
次に、ステップＳ５６において、区間再設定手段１５は、処理区間を［ｐ１（ｋ），ｐ１（ｊ）］に設定し、ステップＳ５７において、処理区間［ｐ１（ｋ），ｐ１（ｊ）］に対して鉛直曲折点追加処理を再帰的に実行する。そして、鉛直曲折点追加処理を終了する。
【０１０９】
図１５は、鉛直曲折点追加処理による鉛直曲折点の追加の例を表した図である。図１５（ａ）において、まず、処理区間［ｐ１（ｉ），ｐ１（Ｍ）］に対して最遠点ｐ１（ｋ１）が鉛直曲折点に選択される。次に、図１５（ｂ）において、まず、処理区間［ｐ１（ｉ），ｐ１（ｋ１）］に対して最遠点ｐ１（ｋ２）が鉛直曲折点に選択され、処理区間［ｐ１（ｋ１），ｐ１（ｊ）］に対して最遠点ｐ１（ｋ３）が鉛直曲折点に選択される。以下同様にして、処理区間における最遠点の最遠点距離が閾値ｄｔｈ未満になるまで繰り返し鉛直曲折点が選択される（図１５（ｃ）参照）。これらの選択された鉛直曲折点を直線補間することにより、リンクの形状が近似される。図１５（ｄ）に示すように、閾値ｄｔｈを適宜決めることによって、近似されたリンク形状はもとのリンク形状をよく再現することができる。また、後に説明するように、この鉛直曲折点追加処理により鉛直曲折点を選択することにより、他の方法で間引きを行った場合に比べて、リンク形状の再現性が同程度の場合に構成点（鉛直曲折点）数を最も少なくすることが可能となる。
【０１１０】
尚、閾値ｄｔｈは、要求される道路形状の再現性に応じて適宜決められる。図１６は、閾値ｄｔｈを変化させたときの再現性の変化を示した図である。図１６（ａ）はｄｔｈ＝０．５０ｍ，図１６（ｂ）はｄｔｈ＝０．２０ｍ，図１６（ｃ）はｄｔｈ＝０．１０ｍ，図１６（ｄ）はｄｔｈ＝０．０５ｍである。この例では、ｄｔｈ＝０．１〜０．２ｍ程度であれば十分な再現性が得られることがわかる。
【０１１１】
〔４〕鉛直曲折点取り込み処理（Ｓ４）及び経緯曲折点補正処理（Ｓ５）
図１７は、ステップＳ４，Ｓ５における鉛直曲折点取り込み処理及び経緯曲折点補正処理を説明する図である。
【０１１２】
実際の道路軌跡データは、二次元地図における道路網データの各リンクに対して、経緯平面上において多少のずれがある。二次元地図における道路網データにおいては、道路を１本の線としてリンクにより表現するのであるが、実際の道路は幅を持っている。そのため、道路軌跡データを測定する際に、測定車が道路の何れの車線を走行したかにより、道路網データのリンクとは経緯平面上で多少のずれが生じるのである。
【０１１３】
従って、鉛直曲折点選択手段３により選択された鉛直曲折点も、二次元地図上の道路網データの各リンクに対して経緯座標でずれが発生している。鉛直曲折点取り込み処理（Ｓ４）においては、この経緯座標のずれを補正する。
【０１１４】
この場合、まず、経緯座標算出手段６が、鉛直曲折点選択手段３により追加された各鉛直曲折点について、ノード及び経緯曲折点により特定されるリンクを経緯平面に射影した射影リンク上における点のうち、当該鉛直曲折点との距離が最短の点の経緯座標を算出する。具体的には、図１７（ａ）のように、経緯座標算出手段６は、道路軌跡データ２２に最も近いリンク２１を二次元地図データの中から選択する。そして、道路軌跡データ２２の各鉛直曲折点に最も近いリンク２１上の点（最近接点）を算出する。
【０１１５】
そして、経緯座標補正手段７は、各鉛直曲折点の経緯座標を、当該鉛直曲折点に対し経緯座標算出手段６が算出する経緯座標に補正する。補正された各鉛直曲折点は、リンク２１の構成点として追加され、構成点記憶手段５に保存される。
【０１１６】
この段階で、道路網データの各リンクのデータ構造は、図４（ｂ）に示すような３次元の構成点情報を有するデータとされる。但し、一部の構成点（鉛直曲折点以外の構成点）に関しては、標高値がまだ未決定のままである。そこで、経緯曲折点補正処理（Ｓ５）において、すべての構成点の標高値を決定する。
【０１１７】
その場合、鉛直座標補正手段８は、各リンクについて、経緯座標補正手段７により補正された各鉛直曲折点及び各ノードの三次元座標を固定し経緯曲折点の経緯座標を固定した状態で、経緯曲折点の鉛直座標を、各鉛直曲折点及び各ノードを補間することにより算出し補正する。具体的には、図１７（ｂ）に示すように、リンク上に新たに設定された構成点（鉛直曲折点）を直線補間する。そして、各経緯曲折点（図１７（ａ）の「△」の点）の標高値を、この補間直線上の高さ（図１７（ｂ）の「▲」の点）に変更する。これにより、すべての構成点の標高値が決定される。
【０１１８】
〔他の方法との比較〕
最後に、本発明に係る道路網データの作成方法の有効性を示すため、幾つかの方法との比較を行ったので、その結果について説明する。
【０１１９】
比較例として、以下の方法を行った。
【０１２０】
〔比較例１〕等間隔間引き処理のみの場合：
これは、図１１において説明した空間的な等間隔間引き処理を用いた。
【０１２１】
〔比較例２〕連続する構成点で角度の変化が閾値より大きい構成点を抽出する間引き処理。これは、処理区間内の道路軌跡データ｛ｐ（ｉ）｜ｉ＝１，２，…，Ｍ｝のそれぞれの内点ｐ（ｋ）（１＜ｋ＜Ｍ）について、直線ｐ（ｋ−１）ｐ（ｋ）と直線ｐ（ｋ）ｐ（ｋ＋１）とのなす角度θを計算する。そして、この角度θが所定の閾値以上の場合、その内点を構成点とし、それ以外の内点を間引く処理である（図１８参照）。
【０１２２】
〔比較例３〕始点を基準点とし、基準点とその次点で基準線を設定し、基準線と基準点とある構成点で作る線分のなす角度で閾値を越えたとき、その一つ前の構成点を抽出し、また次回の基準点とする。閾値を越えないとき、構成点をその次点とし繰り返す。これを終点まで繰り返す（図１９参照）。
【０１２３】
図２０に、実施例１の方法に間引きを行った場合と、比較例１〜３の方法により間引きを行った場合との比較結果を示す。図２０からわかるように、実施例１の方法によれば、他の方法に比べ、同じ再現性で最も構成点数を減らすことができる。
【図面の簡単な説明】
【０１２４】
【図１】本発明の実施例１に係る道路網データの作成装置の構成を表すブロック図である。
【図２】道路軌跡データのデータ構造である。
【図３】道路網データの一例を表す図である。
【図４】電子地図における道路網データのデータ構造である。
【図５】道路属性情報のデータ構造である。
【図６】標高点情報のデータ構造である。
【図７】実施例１に係る道路網データ作成装置１の動作の全体の流れを表すフローチャートである。
【図８】ステップＳ２における等間隔間引き処理の流れを表すフローチャートである。
【図９】等間隔間引き処理による測定車の停止中における座標値の揺らぎの影響の除去を説明する図である。
【図１０】図８の等間隔間引き処理による道路軌跡データのデータ削減の様子を図示したものである。
【図１１】ステップＳ２における等間隔間引き処理の他の例の流れを表すフローチャートである。
【図１２】図１１の等間隔間引き処理による道路軌跡データの間引きを行った例である。
【図１３】ステップＳ３における鉛直曲折点選択処理の流れを表すフローチャートである。
【図１４】ステップＳ３２における鉛直曲折点追加処理の流れを表すフローチャートである。
【図１５】鉛直曲折点追加処理による鉛直曲折点の追加の例を表した図である。
【図１６】閾値ｄｔｈを変化させたときの再現性の変化を示した図である。
【図１７】ステップＳ４，Ｓ５における鉛直曲折点取り込み処理及び経緯曲折点補正処理を説明する図である。
【図１８】比較例２の間引き処理を説明する図である。
【図１９】比較例３の間引き処理を説明する図である。
【図２０】実施例１の方法に間引きを行った場合と、比較例１〜３の方法により間引きを行った場合との比較結果である。
【符号の説明】
【０１２５】
１  道路網データ作成装置
２  道路軌跡記憶手段
３  鉛直曲折点選択手段
４  鉛直曲折点記憶手段
５  構成点記憶手段
６  経緯座標算出手段
７  経緯座標補正手段
８  鉛直座標補正手段
９  標高点記憶手段
１１  初期設定手段
１３  間引き手段
１２  区間記憶手段
１４  距離算出手段
１５  区間再設定手段
２１  もとの地図データにおけるリンク
２２  道路軌跡データ
２３  修正されたリンク
【図１】
2007072011.tif 000003
【図２】
2007072011.tif 000004
【図３】
2007072011.tif 000005
【図４】
2007072011.tif 000006
【図５】
2007072011.tif 000007
【図６】
2007072011.tif 000008
【図７】
2007072011.tif 000009
【図８】
2007072011.tif 000010
【図９】
2007072011.tif 000011
【図１０】
2007072011.tif 000012
【図１１】
2007072011.tif 000013
【図１２】
2007072011.tif 000014
【図１３】
2007072011.tif 000015
【図１４】
2007072011.tif 000016
【図１５】
2007072011.tif 000017
【図１６】
2007072011.tif 000018
【図１７】
2007072011.tif 000019
【図１８】
2007072011.tif 000020
【図１９】
2007072011.tif 000021
【図２０】
2007072011.tif 000022