(57)【特許請求の範囲】
【請求項１】
近似を用いて三次元形状を表現する地図データを生成可能な地図データ生成装置であって、
前記三次元形状を示す形状点列を取得する取得部と、
前記取得部で取得された前記形状点列のうち、前記形状点列の順序が連続する三点、及び、前記形状点列の順序がＮを自然数としてＮ個置きである三点のいずれか一方である対象三点に基づいて、前記対象三点を通る円弧を生成し、前記円弧に基づいて、前記三次元形状において近似すべきでない近似分割点が前記対象三点に含まれるかを判定する制御部と
を備え、
前記制御部は、
前記形状点列のうちの前記対象三点の真ん中の点と別の点とを結ぶ線分と、前記円弧のうち当該線分に対応する部分円弧との差を示す指標を求め、当該指標が予め定められた閾値よりも大きい場合に、前記近似分割点が前記対象三点に含まれると判定する、地図データ生成装置。
【請求項２】
請求項１に記載の地図データ生成装置であって、
前記制御部は、
前記近似分割点が前記対象三点に含まれると判定された場合、前記取得部で取得された前記形状点列を前記近似分割点によって分割し、分割された前記形状点列に基づいて前記三次元形状を近似する近似線を生成する、地図データ生成装置。
【請求項３】
請求項１に記載の地図データ生成装置であって、
前記制御部は、
前記対象三点の変更を繰り返すことによって、前記形状点列の全ての点について前記円弧の生成及び前記近似分割点の判定を行う、地図データ生成装置。
【請求項４】
請求項１に記載の地図データ生成装置であって、
前記制御部は、
前記形状点列のうち前記地図データ生成装置の外部から指定された三点を前記対象三点として用いる、地図データ生成装置。
【請求項５】
請求項１に記載の地図データ生成装置であって、
前記制御部は、
前記指標として、前記線分上の予め定められた点と前記部分円弧との間の距離を用いる、地図データ生成装置。
【請求項６】
請求項１に記載の地図データ生成装置であって、
前記制御部は、
前記指標として、前記線分と前記部分円弧とによって囲まれる領域の面積を用いる、地図データ生成装置。
【請求項７】
請求項１に記載の地図データ生成装置であって、
前記制御部は、
前記形状点列のうちの第１の三点を前記対象三点として用いることによって第１の前記円弧を生成するともに、前記形状点列のうちの前記第１の三点から１点ずつずらした第２の三点を前記対象三点として用いることによって第２の前記円弧を生成し、前記第１の円弧の曲率と前記第２の円弧の曲率との差が予め定められた閾値よりも大きい場合に、前記近似分割点が、前記第１の三点及び前記第２の三点のうち互いに重複する点に含まれると判定する、地図データ生成装置。
【請求項８】
請求項１に記載の地図データ生成装置であって、
前記制御部は、
前記円弧の曲率が予め定められた閾値よりも大きい場合に、前記近似分割点が前記対象三点に含まれると判定する、地図データ生成装置。
【請求項９】
請求項１に記載の地図データ生成装置であって、
前記制御部は、
前記取得部で取得された前記形状点列の一端点から他端点に向かって順に前記対象三点を変更しながら、前記円弧の生成及び前記近似分割点の判定を含む第１処理と、前記取得部で取得された前記形状点列の前記他端点から前記一端点に向かって順に前記対象三点を変更しながら、前記円弧の生成及び前記近似分割点の判定を含む第２処理とを行い、前記第１処理及び前記第２処理の少なくともいずれか一方で、第１点が前記近似分割点でないと判定された場合には、前記第１処理及び前記第２処理の結果として前記第１点が前記近似分割点でないと判定する、地図データ生成装置。
【請求項１０】
請求項９に記載の地図データ生成装置であって、
前記制御部は、
前記第１処理で前記第１点が前記近似分割点であると判定され、前記第２処理で前記第１点が前記近似分割点でないと判定された場合には、前記一端点側に前記第１点から１点ずらした第２点を前記近似分割点であると判定する、地図データ生成装置。
【請求項１１】
請求項１に記載の地図データ生成装置で生成された前記地図データを用いて前記三次元形状を表現可能な、端末装置。
【請求項１２】
近似を用いて三次元形状を表現する地図データを生成可能な地図データ生成方法であって、
前記三次元形状を示す点列である形状点列を取得し、
取得された前記形状点列のうち、前記形状点列の順序が連続する三点、及び、前記形状点列の順序がＮを自然数としてＮ個置きである三点のいずれか一方である対象三点に基づいて、前記対象三点を通る円弧を生成し、前記円弧に基づいて、前記三次元形状において近似すべきでない近似分割点が前記対象三点に含まれるかを判定し、
前記形状点列のうちの前記対象三点の真ん中の点と別の点とを結ぶ線分と、前記円弧のうち当該線分に対応する部分円弧との差を示す指標を求め、当該指標が予め定められた閾値よりも大きい場合に、前記近似分割点が前記対象三点に含まれると判定する、地図データ生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図データを生成可能な地図データ生成装置及びその方法、並びに、当該地図データに係る端末装置に関する。
【背景技術】
【０００２】
近年、道路面や、道路周辺の建物及び設備などの三次元形状を、三次元点群で表現可能な地図データが提案されている。三次元点群は、例えばＧＮＳＳ（Global Navigation Satellite System）装置、レーザレーダ、カメラなどの測量機能の組み合わせを用いることにより、実物から取得することができる。取得した三次元点群情報のデータ量は、そのままでは非常に大きいため、必要な情報のみが抽出される。例えば、車載機器で用いられる地図では、道路の中心位置や、各車線の中心位置、区画線、標識などの三次元位置及び三次元形状が有用であるため、これらの情報が三次元形状情報として抽出される。【０００３】
しかしながら、三次元形状情報のデータ量が大きくなる傾向があるため、三次元形状情報を適切に抽出する技術だけでなく、三次元形状情報を圧縮する技術も必要となってきている。そのような技術として、近似線を用いて三次元形状を表現することによって、三次元形状情報のデータ量を圧縮する技術が提案されている。【０００４】
例えば特許文献１では、道路走行時に位置センサで取得された三次元走行軌跡のデータに、平面線形を用いて平面走行軌跡のデータを生成する。そして、平面走行軌跡のデータに基づいて、制御点、制御点に関連する円弧、円弧につながる緩和曲線を順に生成し、記憶媒体などに記憶する。これにより、生成された円弧及び緩和曲線などに基づいて、三次元道路の中心線に相当する滑らかな中心線を表現することが可能となる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−２６６３０６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来技術では、近似線を導出する過程において、三次元形状を示す点列のうちの一点と近似線との誤差のみを評価対象としており、当該一点以外の点における誤差は考慮されていない。そのため、従来技術では、三次元形状のうち滑らかにすべきでない角形状を、滑らかな近似線で表現しまうことがあり、地図データで表現される三次元形状と、実物の三次元形状との差が比較的大きくなってしまうという問題がある。例えば、道路縁やフェンス根元のような形状は、道路中心線のような形状よりも、角形状を含む場合が多いので、従来技術では、地図データで表現される道路縁やフェンス根元のような形状が、実物の形状と大きく乖離することがあるという問題があった。【０００７】
そこで、本発明は、上記のような問題点を鑑みてなされたものであり、近似を用いて地図データで表現される三次元形状と、実物の三次元形状との差を低減可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明に係る地図データ生成装置は、近似を用いて三次元形状を表現する地図データを生成可能な地図データ生成装置であって、三次元形状を示す形状点列を取得する取得部と、取得部で取得された形状点列のうち、形状点列の順序が連続する三点、及び、形状点列の順序がＮを自然数としてＮ個置きである三点のいずれか一方である対象三点に基づいて、対象三点を通る円弧を生成し、円弧に基づいて、三次元形状において近似すべきでない近似分割点が対象三点に含まれるかを判定する制御部とを備える。制御部は、形状点列のうちの対象三点の真ん中の点と別の点とを結ぶ線分と、円弧のうち当該線分に対応する部分円弧との差を示す指標を求め、当該指標が予め定められた閾値よりも大きい場合に、近似分割点が対象三点に含まれると判定する。
【発明の効果】
【０００９】
本発明によれば、三次元形状において近似すべきでない近似分割点が、対象三点に含まれるか否かを判定する。これにより、近似を用いて地図データで表現される三次元形状と、実物の三次元形状との差を低減することができる。【００１０】
本発明の目的、特徴、態様及び利点は、以下の詳細な説明と添付図面とによって、より明白となる。
【図面の簡単な説明】
【００１１】
【図１】実施の形態１に係る地図データ生成装置の構成を示すブロック図である。
【図２】実施の形態２に係る地図データ生成装置の構成を示すブロック図である。
【図３】実施の形態２に係る地図データ生成装置の動作を示すフローチャートである。
【図４】実施の形態２に係る近似分割点抽出部の動作を説明するための図である。
【図５】実施の形態２に係る近似分割点抽出部の動作を説明するための図である。
【図６】実施の形態２に係る近似分割点抽出部の動作を示すフローチャートである。
【図７】実施の形態３に係る近似分割点抽出部の動作を示すフローチャートである。
【図８】実施の形態４に係る近似分割点抽出部の動作を示すフローチャートである。
【図９】実施の形態４に係る近似分割点抽出部の動作を説明するための図である。
【図１０】実施の形態５に係る近似分割点抽出部の動作を示すフローチャートである。
【図１１】実施の形態６に係る近似分割点抽出部の動作を示すフローチャートである。
【図１２】実施の形態７に係る近似分割点抽出部の動作を説明するための図である。
【図１３】実施の形態７に係る近似分割点抽出部の動作を説明するための図である。
【図１４】実施の形態７に係る近似分割点抽出部の動作を説明するための図である。
【図１５】実施の形態８に係るカーナビゲーション装置の構成を示すブロック図である。
【図１６】実施の形態８の変形例に係るカーナビゲーション装置の構成を示すブロック図である。
【図１７】その他の変形例に係る地図データ生成装置のハードウェア構成を示すブロック図である。
【図１８】その他の変形例に係る地図データ生成装置のハードウェア構成を示すブロック図である。
【発明を実施するための形態】
【００１２】
＜実施の形態１＞
本発明の実施の形態１に係る地図データ生成装置は、地図データを生成可能な装置であり、当該地図データには、近似を用いて三次元形状を表現する地図データが含まれる。
【００１３】
図１は、本発明の実施の形態１に係る地図データ生成装置１の構成を示すブロック図である。図１の地図データ生成装置１は、取得部１１と、制御部１２とを備える。
【００１４】
取得部１１は、三次元形状を示す点列である形状点列を取得する。例えば、形状点列には、三次元形状の外郭線上に並べられた複数点の列などが用いられる。なお、取得部１１は、地図データ生成装置１の外部または内部の装置から形状点列を取得してもよいし、取得部１１が、他の情報に基づいて形状点列を生成してもよい。
【００１５】
制御部１２は、取得部１１で取得された形状点列から対象三点を決定する。対象三点は、形状点列の順序が連続する三点、及び、形状点列の順序がＮを自然数としてＮ個置きである三点のいずれか一方である。
【００１６】
制御部１２は、対象三点に基づいて当該対象三点を通る円弧を生成する。なお、円には円弧が含まれることから、円弧の代わりに円を生成する構成でも、円弧を生成することになる。
【００１７】
制御部１２は、生成した円弧に基づいて、三次元形状において近似すべきでない近似分割点が、対象三点に含まれるか否かを判定する。なお、近似分割点は近似分割箇所と呼ぶこともできる。
【００１８】
以上のような本実施の形態１に係る地図データ生成装置１によれば、三次元形状において近似すべきでない近似分割点が、対象三点に含まれるか否かを判定する。これにより、三次元形状の角形状を、滑らかな近似線で表現しまうことを抑制することができるので、近似を用いて地図データで表現される三次元形状と、実物の三次元形状との差を低減することができる。
【００１９】
＜実施の形態２＞
図２は、本発明の実施の形態２に係る地図データ生成装置１の構成を示すブロック図である。以下、本実施の形態２で説明する構成要素のうち、実施の形態１と同じまたは類似する構成要素については同じ参照符号を付し、異なる構成要素について主に説明する。
【００２０】
図２の地図データ生成装置１は、三次元点列情報格納部２１と、データ変換部２２と、近似分割点抽出部２３と、近似処理部２４と、近似線パラメータ格納部２５とを備える。なお、データ変換部２２は、実施の形態１で説明した図１の取得部１１に対応する。近似分割点抽出部２３及び近似処理部２４は、実施の形態１で説明した図１の制御部１２に対応する。以下、図２の地図データ生成装置１の各構成要素について詳細に説明する。
【００２１】
＜三次元点列情報格納部２１＞
三次元点列情報格納部２１は、経路及び構造物などを示す三次元形状を示す形状点列のデータを、三次元点列情報として格納している。以下の説明では、データ圧縮の処理対象となる経路及び構造物などを「対象形状」と呼ぶこともある。なお、以下では、対象形状が道路縁である場合を想定して説明するが、これに限ったものではない。例えば、対象形状は、車線中心線、フェンスなどの構造物、道路の中心、仮想線、区画線、立体構造物の位置を示す線、などの形状であってもよい。
【００２２】
＜データ変換部２２＞
データ変換部２２は、三次元点列情報格納部２１から、対象形状の三次元点列情報を取得する。データ変換部２２は、取得した三次元点列情報に基づいて、三次元空間座標を、それから一次元座標の成分を除いた二次元平面座標に変換する。そして、データ変換部２２は、当該二次元平面座標を保持するとともに、除かれた一次元座標の成分に対応する情報を図示しない格納部などに保持する。例えば特願２０１６−０７６３５７号に記載された技術のように、データ変換部２２が、三次元情報を、それから標高成分を除いた二次元情報に変換するように構成された場合には、二次元情報を保持するとともに、当該標高成分に対応する勾配データも図示しない格納部などに保持する。データ変換部２２は、上述の変換によって得られた二次元の形状点列を近似分割点抽出部２３に出力する。
【００２３】
ただし、実施形式によっては、データ変換部２２は、上述の変換を行わずに、三次元点列情報格納部２１から取得した三次元点列情報をそのまま近似分割点抽出部２３に出力するように構成されてもよい。このように構成された場合、データ変換部２２から近似分割点抽出部２３には、三次元の形状点列が出力される。なお、上述のような変換とその逆変換とを適宜行なえば、二次元と三次元とを実質的に同一に扱うことができるので、以下の説明における二次元と三次元とは実質的に同じである。
【００２４】
＜近似分割点抽出部２３＞
近似分割点抽出部２３は、取得部１１で取得された形状点列のうちの対象三点について、円弧の生成及び近似分割点の判定を行う。近似分割点抽出部２３の具体的な動作については、後でフローチャートを用いて詳細に説明する。
【００２５】
＜近似処理部２４＞
近似処理部２４は、近似分割点抽出部２３によって近似分割点が対象三点に含まれないと判定された場合には、データ変換部２２で取得された全ての形状点列に基づいて、三次元形状を近似する近似線を生成する。
【００２６】
一方、近似処理部２４は、近似分割点抽出部２３によって近似分割点が対象三点に含まれると判定された場合には、データ変換部２２で取得された形状点列を近似分割点によって分割し、分割された形状点列に基づいて、地図データにおける三次元形状を近似する近似線を生成する。
【００２７】
例えば、近似分割点抽出部２３によって、形状点列の始点と終点との間に一つの近似分割点があると判定された場合には、近似処理部２４は、始点、近似分割点、及び、それらの間の点に基づいて第１近似線を生成するとともに、終点、近似分割点、及び、それらの間の点に基づいて第２近似線を生成する。
【００２８】
また例えば、近似分割点抽出部２３によって、形状点列の始点と終点との間に二つ以上の近似分割点があると判定された場合には、近似処理部２４は、上述と同様に第１近似線及び第２近似線を生成するとともに、隣り合う二つの近似分割点、及び、それらの間の点に基づいて第３近似線を生成する。
【００２９】
近似線の生成には、例えば、最小二乗法などの一般的な近似が用いられ、近似線を表す近似式には、例えば、単多項式を含む多項式など、一般的な近似に用いられる関数式が用いられる。なお、各近似線は、互いに異なる複数の近似式で表される複数の部分線を繋ぎ合わせた線であってもよい。
【００３０】
＜近似線パラメータ格納部２５＞
近似線パラメータ格納部２５は、近似処理部２４で生成された近似線のパラメータを保存する。近似線のパラメータには、例えば、近似線の端点の座標情報、近似線を表す近似式のパラメータなどが含まれる。
【００３１】
＜動作＞
図３は、本実施の形態２に係る地図データ生成装置１の動作を示すフローチャートである。
【００３２】
ステップＳ１にて、データ変換部２２は、三次元点列情報格納部２１に格納された三次元点列情報を調べ、全ての近似すべき対象形状を近似したかを判定する。全て近似しなかったと判定された場合にはステップＳ２に処理が進み、全て近似したと判定された場合には図３の処理が終了する。
【００３３】
ステップＳ２にて、データ変換部２２は、三次元点列情報格納部２１から、近似されていない対象形状を取得し、当該対象形状に上述した次元の変換を適宜行う。ステップＳ２の最後には、データ変換部２２は形状点列を取得する。
【００３４】
ステップＳ３にて、近似分割点抽出部２３は、ステップＳ２で取得された形状点列に近似分割点があるかを判定する。
【００３５】
ステップＳ４にて、近似処理部２４は、ステップＳ３の判定結果に基づいて対象形状の近似線を生成する。つまり、近似処理部２４は近似線を導出する。
【００３６】
ステップＳ５にて、近似線パラメータ格納部２５は、ステップＳ４で生成された近似線のパラメータを保存する。その後、ステップＳ１に処理が戻る。ステップＳ１〜Ｓ５が１回行われることにより、１つの近似すべき対象形状が近似され、ステップＳ１〜Ｓ５が繰り返されることにより、全ての近似すべき対象形状が近似されることになる。
【００３７】
＜近似分割点抽出部２３の動作＞
図４及び図５は、本実施の形態２に係る近似分割点抽出部２３の動作、つまり図３のステップＳ３の動作を説明するための図である。以下、対象三点が、形状点列の順序が連続する三点である場合について説明する。
【００３８】
図４には、対象形状の形状点列のうちの対象三点として、点Ｐｉ（ｘｉ，ｙｉ）、点Ｐｉ＋１（ｘｉ＋１，ｙｉ＋１）、点Ｐｉ＋２（ｘｉ＋２，ｙｉ＋２）が示されている。この場合、近似分割点抽出部２３は、図４に示すように対象三点を通る円弧３１を生成する。
【００３９】
次に、近似分割点抽出部２３は、対象三点のうち真ん中の点Ｐｉ＋１と別の点Ｐｉとを結ぶ線分Ｌａと、円弧３１のうち線分Ｌａに対応する部分円弧３１ａとの差を示す指標を求める。本実施の形態２では、線分Ｌａに対応する部分円弧３１ａは、円弧３１を真ん中の点Ｐｉ＋１で区分した部分のうちＬａ側の部分である。また本実施の形態２では、近似分割点抽出部２３は、上記指標として、線分Ｌａ上の予め定められた点と部分円弧３１ａとの間の距離Ｄａを求める。
【００４０】
同様に、近似分割点抽出部２３は、対象三点の真ん中の点Ｐｉ＋１と別の点Ｐｉ＋２とを結ぶ線分Ｌｂと、円弧３１のうち線分Ｌｂに対応する部分円弧３１ｂとの差を示す指標として、線分Ｌｂ上の予め定められた点と部分円弧３１ｂとの間の距離Ｄｂを求める。
【００４１】
近似分割点抽出部２３は、距離Ｄａ，Ｄｂのうち大きい方の距離が、予め定められた閾値よりも大きい場合に、近似分割点が対象三点に含まれると判定する。本実施の形態２に係る近似分割点抽出部２３は、近似分割点が対象三点に含まれると判定した場合には、近似分割点は対象三点の真ん中の点Ｐｉ＋１であると判定する。
【００４２】
近似分割点抽出部２３は、以上のような円弧の生成及び近似分割点の判定を、対象三点を変更しながら行う。ここでは図５に示すように、近似分割点抽出部２３は、まず、形状点列のうち始点を含む三点３２ａを対象三点として決定し、三点３２ａについて、上述した円弧の生成及び近似分割点の判定を行う。その後、近似分割点抽出部２３は、形状点列のうち三点３２ａから終点側に一点ずらした三点３２ｂを対象三点として決定し、三点３２ｂについて、上述した円弧の生成及び近似分割点の判定を行う。近似分割点抽出部２３は、以上のような対象三点の変更を繰り返すことによって、形状点列の全ての点について円弧の生成及び近似分割点の判定を行う。ただし、対象三点として最初に用いられる三点及び順序は、上述に限ったものではない。
【００４３】
図６は、本実施の形態２に係る近似分割点抽出部２３の動作を示すフローチャートである。
【００４４】
ステップＳ１１にて、近似分割点抽出部２３は、ｉ＝０として対象三点である点Ｐｉ，Ｐｉ＋１，Ｐｉ＋２の初期化を行う。ただし、添え字ｉの数を０から数え始める０オリジンではなく、１から数え始める１オリジンの場合には、ｉ＝１として対象三点の初期化を行う。以下では、０オリジンであり、ｉ＝０として初期化する場合について説明する。
【００４５】
ステップＳ１２にて、近似分割点抽出部２３は、点Ｐｉ，Ｐｉ＋１，Ｐｉ＋２を通る円弧に対応する円を導出する。ここでは、近似分割点抽出部２３は、円の一般式である次式（１）に、３点の座標を１点ずつ代入してｌ，ｍ，ｎについての三元連立方程式（ｊ＝ｉ，ｉ＋１，ｉ＋２）を取得し、当該三元連立方程式を解くことによって、円を導出する。
【００４６】
【数１】
0006469326.tif 000002
【００４７】
ステップＳ１３にて、近似分割点抽出部２３は、対象三点の真ん中の点Ｐｉ＋１と別の点Ｐｉとを結ぶ線分Ｌａ上の予め定められた点と、部分円弧３１ａとの間の距離Ｄａを求める。以下では、予め定められた点は、線分Ｌａの中点である場合を例にして説明する。この場合、距離Ｄａは、部分円弧３１ａの矢高の長さとなる。
【００４８】
近似分割点抽出部２３は、座標Ｐｉ，Ｐｉ＋１に関する部分円弧３１ａの矢高の長さであるＤａを求める前段階として、次式（２）に点の座標Ｐｉ，Ｐｉ＋１を代入して、線分Ｌａの半分の長さＢａを求めるとともに、次式（３）にステップＳ１２で求めたｌ，ｍ，ｎを代入して、円の半径ｒを求める。
【００４９】
【数２】
0006469326.tif 000003
【００５０】
【数３】
0006469326.tif 000004
【００５１】
そして、近似分割点抽出部２３は、次式（４）に、求めた長さＢａと、求めた円の半径ｒとを代入して、部分円弧３１ａの矢高の長さである距離Ｄａを求める。
【００５２】
【数４】
0006469326.tif 000005
【００５３】
近似分割点抽出部２３は、距離Ｄａと同様に、部分円弧３１ｂの矢高の長さである距離Ｄｂを求める。
【００５４】
ステップＳ１４にて、近似分割点抽出部２３は、ステップＳ１３で求めた距離Ｄａ，Ｄｂのうち大きい方の距離が、予め定められた閾値よりも大きいか否かを判定する。距離が閾値よりも大きいと判定された場合にはステップＳ１５に処理が進み、距離が閾値以下であると判定された場合にはステップＳ１６に処理が進む。なお、近似分割点抽出部２３は、距離Ｄａ，Ｄｂのうち大きい方の距離が閾値よりも大きいか否かを判定する代わりに、距離Ｄａ，Ｄｂの和（＝Ｄａ＋Ｄｂ）が閾値よりも大きいか否かを判定してもよい。
【００５５】
ステップＳ１５にて、近似分割点抽出部２３は、真ん中の点Ｐｉ＋１を近似分割点として例えば図示しないキャッシュメモリなどの記憶装置に記憶する。その後、ステップＳ１６に処理が進む。
【００５６】
ステップＳ１６にて、近似分割点抽出部２３は、対象三点が形状点列の終点を含むか否か、つまりｉ＝Ｍ−２であるか否かを判定する。なお、Ｍは形状点列の点の総数である。ｉ＝Ｍ−２である場合には、形状点列の全ての点について円弧の生成及び近似分割点の判定が行われたと判定されて、図６の処理が終了する。ｉ＝Ｍ−２ではなく、ｉ＜Ｍ−２である場合には、形状点列の全ての点について円弧の生成及び近似分割点の判定が行われていないと判定されて、ステップＳ１７に処理が進む。
【００５７】
ステップＳ１７にて、近似分割点抽出部２３はｉをインクリメントし、ステップＳ１２に処理が戻る。
【００５８】
以上、対象三点に、形状点列の順序が連続する三点を用いた場合について説明した。一方、対象三点に、形状点列の順序がＮ個置きである三点を用いる場合には、上記の説明において、点Ｐｉ＋１（ｘｉ＋１，ｙｉ＋１）、点Ｐｉ＋２（ｘｉ＋２，ｙｉ＋２）の代わりに、点Ｐｉ＋Ｎ＋１（ｘｉ＋Ｎ＋１，ｙｉ＋Ｎ＋１）、点Ｐｉ＋２Ｎ＋２（ｘｉ＋２Ｎ＋２，ｙｉ＋２Ｎ＋２）を用いればよい。
【００５９】
＜実施の形態２のまとめ＞
以上のような本実施の形態２に係る地図データ生成装置１によれば、実施の形態１と同様に、三次元形状において近似すべきでない近似分割点が、対象三点に含まれるか否かを判定するので、実施の形態１と同様の効果を得ることができる。
【００６０】
また本実施の形態２では、線分と部分円弧との間の距離が閾値よりも大きい場合に、近似分割点が対象三点に含まれると判定する。これにより、形状点列から適切な近似分割点を抽出することができる。
【００６１】
また本実施の形態２では、データ変換部２２で取得された形状点列を近似分割点によって分割し、分割された形状点列に基づいて、地図データにおける三次元形状を近似する近似線を生成する。このような構成によれば、近似処理部２４において再帰的な近似処理を行う必要がなくなるので、処理の負荷を低減することができる。
【００６２】
また本実施の形態２では、対象三点の変更を繰り返すことによって、形状点列の全ての点について円弧の生成及び近似分割点の判定を行う。これにより、近似分割点の抽出ミスを抑制することができる。
【００６３】
＜実施の形態３＞
本発明の実施の形態３に係る地図データ生成装置１のブロック構成は、実施の形態２で説明した図２のブロック構成と同じである。以下、本実施の形態３で説明する構成要素のうち、実施の形態２と同じまたは類似する構成要素については同じ参照符号を付し、異なる構成要素について主に説明する。
【００６４】
上述した実施の形態２では、近似分割点抽出部２３は、形状点列の全ての点について円弧の生成及び近似分割点の判定を行った。これに対して本実施の形態３では、近似分割点抽出部２３は、形状点列のうち地図データ生成装置１の外部から指定された三点を対象三点として用いる。なお、地図データ生成装置１の外部としては、ユーザ、または、ユーザの操作結果を送信する通信装置などが想定される。
【００６５】
図７は、本実施の形態３に係る近似分割点抽出部２３の動作を示すフローチャートである。図７の動作は、図６の動作においてステップＳ１１をステップＳ１１ａに変更し、ステップＳ１６及びＳ１７を削除した動作と同様である。ここで、ステップＳ１１ａでは、外部から指定された三点を対象三点として決定する。
【００６６】
＜実施の形態３のまとめ＞
以上のような本実施の形態３に係る地図データ生成装置１によれば、三次元形状において予め評価したい箇所がある場合に、その箇所についてのみ判定を行うことができる。したがって、近似分割点を抽出する時間を短くすることができる。
【００６７】
＜実施の形態４＞
本発明の実施の形態４に係る地図データ生成装置１のブロック構成は、実施の形態２で説明した図２のブロック構成と同じである。以下、本実施の形態４で説明する構成要素のうち、実施の形態２と同じまたは類似する構成要素については同じ参照符号を付し、異なる構成要素について主に説明する。
【００６８】
上述した実施の形態２では、図４のように線分Ｌａと部分円弧３１ａとの差を示す指標として、線分Ｌａ上の予め定められた点と部分円弧３１ａとの間の距離Ｄａが用いられた。これに対して本実施の形態４では、線分Ｌａと部分円弧３１ａとの差を示す指標として、線分Ｌａと部分円弧３１ａとによって囲まれる領域の面積が用いられる。
【００６９】
図８は、本実施の形態４に係る近似分割点抽出部２３の動作を示すフローチャートである。図８の動作は、図６の動作においてステップＳ１３及びＳ１４をステップＳ１３ｂ及びＳ１４ｂに変更した動作と同様である。そこで以下では、ステップＳ１３ｂ及びＳ１４ｂについて主に説明する。
【００７０】
ステップＳ１３ｂにて、近似分割点抽出部２３は、図６のステップＳ１３と同様に、図９の線分Ｌａの半分の長さＢａ、円の半径ｒ、部分円弧３１ａの矢高の長さである距離Ｄａを求める。そして、近似分割点抽出部２３は、それらを次式（５）に代入することによって、線分Ｌａと部分円弧３１ａとによって囲まれる領域、つまり図９でハッチングが付された領域のうち左下側の領域の面積Ｓａを求める。
【００７１】
【数５】
0006469326.tif 000006
【００７２】
近似分割点抽出部２３は、面積Ｓａと同様に、図９の線分Ｌｂと部分円弧３１ｂとによって囲まれる領域、つまり図９でハッチングが付された領域のうち右上側の領域の面積Ｓｂを求める。
【００７３】
ステップＳ１４ｂにて、近似分割点抽出部２３は、ステップＳ１３ｂで求めた面積Ｓａ，Ｓｂの和（＝Ｓａ＋Ｓｂ）が、予め定められた閾値よりも大きいか否かを判定する。面積の和が閾値よりも大きいと判定された場合にはステップＳ１５に処理が進み、面積の和が閾値以下であると判定された場合にはステップＳ１６に処理が進む。なお、近似分割点抽出部２３は、面積Ｓａ，Ｓｂの和（＝Ｓａ＋Ｓｂ）が閾値よりも大きいか否かを判定する代わりに、面積Ｓａ，Ｓｂのうち大きい方の面積が閾値よりも大きいか否かを判定してもよい。
【００７４】
＜実施の形態４のまとめ＞
以上のような本実施の形態４に係る地図データ生成装置１によれば、線分と部分円弧とによって囲まれる領域の面積が閾値よりも大きい場合に、近似分割点が対象三点に含まれると判定する。これにより、形状点列から適切な近似分割点を抽出することができる。
【００７５】
＜実施の形態５＞
本発明の実施の形態５に係る地図データ生成装置１のブロック構成は、実施の形態２で説明した図２のブロック構成と同じである。以下、本実施の形態５で説明する構成要素のうち、実施の形態２と同じまたは類似する構成要素については同じ参照符号を付し、異なる構成要素について主に説明する。
【００７６】
上述した実施の形態２では、近似分割点抽出部２３は、線分と部分円弧との差を示す指標が予め定められた閾値よりも大きい場合に、近似分割点が対象三点に含まれると判定した。これに対して本実施の形態５では、近似分割点抽出部２３は、形状点列のうちの第１の三点を対象三点として用いることによって第１の円弧を生成する。そして、近似分割点抽出部２３は、形状点列のうちの第１の三点から１点ずつずらした第２の三点を対象三点として用いることによって第２の円弧を生成する。それから、近似分割点抽出部２３は、第１の円弧の曲率と第２の円弧の曲率との差が予め定められた閾値よりも大きい場合に、近似分割点が、第１の三点及び第２の三点のうち互いに重複する点に含まれると判定する。
【００７７】
図１０は、本実施の形態５に係る近似分割点抽出部２３の動作を示すフローチャートである。図１０の動作は、図６の動作においてステップＳ１２〜Ｓ１５をステップＳ１２ｃ〜Ｓ１５ｃに変更した動作と同様である。そこで以下では、ステップＳ１２ｃ〜Ｓ１５ｃについて主に説明する。
【００７８】
ステップＳ１２ｃにて、近似分割点抽出部２３は、図６のステップＳ１２と同様に第１の点Ｐｉ，Ｐｉ＋１，Ｐｉ＋２を通る第１の円弧に対応する第１の円を導出する。また、近似分割点抽出部２３は、図６のステップＳ１２と同様に第２の点Ｐｉ＋１，Ｐｉ＋２，Ｐｉ＋３を通る第２の円弧に対応する第２の円を導出する。
【００７９】
ステップＳ１３ｃにて、近似分割点抽出部２３は、図６のステップＳ１３と同様に、第１の円の半径ｒを求めるとともに、第２の円の半径ｒａを求める。そして、近似分割点抽出部２３は、第１の円の半径ｒから第１の円の曲率Ｒ（＝１／ｒ）を求めるとともに、第２の円の半径ｒａから第２の円の曲率Ｒａ（＝１／ｒａ）を求める。
【００８０】
ステップＳ１４ｃにて、近似分割点抽出部２３は、第１の円の曲率Ｒと第２の円の曲率Ｒａとの差（＝｜Ｒ−Ｒａ｜）が、予め定められた閾値よりも大きいか否かを判定する。差が閾値よりも大きいと判定された場合にはステップＳ１５ｃに処理が進み、差が閾値以下であると判定された場合にはステップＳ１６に処理が進む。
【００８１】
ステップＳ１５ｃにて、近似分割点抽出部２３は、第１の点Ｐｉ，Ｐｉ＋１，Ｐｉ＋２と、第２の点Ｐｉ＋１，Ｐｉ＋２，Ｐｉ＋３とのうち重複する点である点Ｐｉ＋２を近似分割点として例えば図示しないキャッシュメモリなどの記憶装置に記憶する。その後、ステップＳ１６に処理が進む。
【００８２】
＜実施の形態５のまとめ＞
以上のような本実施の形態５に係る地図データ生成装置１によれば、第１の円弧の曲率と第２の円弧の曲率との差が予め定められた閾値よりも大きい場合に、近似分割点が、第１の三点及び第２の三点のうち互いに重複する点に含まれると判定する。これにより、形状点列から適切な近似分割点を抽出することができる。
【００８３】
なお、以上の説明では、第２の三点は、第１の三点を添え字が大きくなる方向にずらした点Ｐｉ＋１，Ｐｉ＋２，Ｐｉ＋３であった。しかしこれに限ったものではなく、第２の三点は、第１の三点を添え字が小さくなる方向にずらした三点Ｐｉ−１，Ｐｉ，Ｐｉ＋１であってもよい。そして、近似分割点抽出部２３は、三点Ｐｉ−１，Ｐｉ，Ｐｉ＋１を通る第２の円の半径ｒｂを求め、当該第２の円の曲率Ｒｂ（＝１／ｒｂ）を求め、第１の円の曲率Ｒと第２の円の曲率Ｒｂとの差（＝｜Ｒ−Ｒｂ｜）が、予め定められた閾値よりも大きいか否かを判定してもよい。
【００８４】
または、近似分割点抽出部２３は、三点Ｐｉ，Ｐｉ＋１，Ｐｉ＋２を通る一の第２の円の曲率Ｒａと、三点Ｐｉ−１，Ｐｉ，Ｐｉ＋１を通る別の第２の円の曲率Ｒｂとを求めてもよい。そして近似分割点抽出部２３は、第１の円の曲率Ｒと一の第２の円の曲率Ｒａとの差（＝｜Ｒ−Ｒａ｜）、及び、第１の円の曲率Ｒと別の第２の円の曲率Ｒｂとの差（＝｜Ｒ−Ｒｂ｜）のうち大きい方の差が、予め定められた閾値よりも大きいか否かを判定してもよい。
【００８５】
＜実施の形態６＞
本発明の実施の形態６に係る地図データ生成装置１のブロック構成は、実施の形態２で説明した図２のブロック構成と同じである。以下、本実施の形態６で説明する構成要素のうち、実施の形態２と同じまたは類似する構成要素については同じ参照符号を付し、異なる構成要素について主に説明する。
【００８６】
実施の形態６では、近似分割点抽出部２３は、対象三点を通る円弧の曲率が予め定められた閾値よりも大きい場合に、近似分割点が対象三点に含まれると判定する。
【００８７】
図１１は、本実施の形態６に係る近似分割点抽出部２３の動作を示すフローチャートである。図１１の動作は、図６の動作においてステップＳ１３及びＳ１４をステップＳ１３ｄ及びＳ１４ｄに変更した動作と同様である。そこで以下では、ステップＳ１３ｄ及びＳ１４ｄについて主に説明する。
【００８８】
ステップＳ１３ｄにて、近似分割点抽出部２３は、図６のステップＳ１３と同様に、円の半径ｒを求め、求めた円の半径ｒから円の曲率Ｒ（＝１／ｒ）を求める。
【００８９】
ステップＳ１４ｄにて、近似分割点抽出部２３は、円の曲率Ｒが、予め定められた閾値よりも大きいか否かを判定する。曲率Ｒが閾値よりも大きいと判定された場合にはステップＳ１５に処理が進み、差が閾値以下であると判定された場合にはステップＳ１６に処理が進む。
【００９０】
＜実施の形態６のまとめ＞
以上のような本実施の形態６に係る地図データ生成装置１によれば、対象三点を通る円弧の曲率が予め定められた閾値よりも大きい場合に、近似分割点が対象三点に含まれると判定する。これにより、形状点列から適切な近似分割点を抽出することができる。
【００９１】
＜実施の形態７＞
本発明の実施の形態６に係る地図データ生成装置１のブロック構成は、実施の形態２で説明した図２のブロック構成と同じである。以下、本実施の形態６で説明する構成要素のうち、実施の形態２と同じまたは類似する構成要素については同じ参照符号を付し、異なる構成要素について主に説明する。
【００９２】
上述した実施の形態２では、近似分割点抽出部２３は、データ変換部２２で取得された形状点列の始点から終点に向かって順に対象三点を変更しながら、円弧の生成及び近似分割点の判定を行い、近似分割点の判定結果をそのまま用いた。
【００９３】
これに対して本実施の形態７では、近似分割点抽出部２３は、データ変換部２２で取得された形状点列の一端点である始点から他端点である終点に向かって順に対象三点を変更しながら、円弧の生成及び近似分割点の判定を含む第１処理を行う。また、近似分割点抽出部２３は、データ変換部２２で取得された形状点列の終点から始点に向かって順に対象三点を変更しながら、円弧の生成及び近似分割点の判定を含む第２処理を行う。そして、近似分割点抽出部２３は、第１処理及び第２処理の少なくともいずれか一方で、第１点が近似分割点でないと判定された場合には、第１処理及び第２処理の結果として当該第１点が近似分割点でないと判定する。
【００９４】
例えば図１２に示すように、近似分割点抽出部２３が、形状点列の始点Ｐ１から終点Ｐ５に向かって順に対象三点を変更しながら、円弧の生成及び近似分割点の判定を含む第１処理を行い、点Ｐ４が近似分割点であると判定したとする。この場合、実施の形態２に係る地図データ生成装置１は、点Ｐ１〜Ｐ４に基づいて近似線ＡＬ１を生成し、点Ｐ４と点Ｐ５との間を結ぶ図示しない直線を生成する。
【００９５】
これに対して、本実施の形態７に係る近似分割点抽出部２３は、第１処理だけでなく、図１３に示すように、形状点列の終点Ｐ５から始点Ｐ１に向かって順に対象三点を変更しながら、円弧の生成及び近似分割点の判定を含む第２処理を行う。そして、近似分割点抽出部２３は、第１処理で点Ｐ４が近似分割点であると判定したとしても、第２処理で点Ｐ４が近似分割点でないと判定した場合には、第１処理及び第２処理の結果として点Ｐ４を近似分割点でないと判定する。この場合、実施の形態７に係る地図データ生成装置１は、点Ｐ１〜Ｐ５に基づいて近似線ＡＬ２を生成する。これにより、本実施の形態７に係る地図データ生成装置１は、実施の形態２よりも、近似線の数を低減することができるので、データの圧縮性を高めることができる。
【００９６】
なお、第１処理と第２処理とで判定結果が異なる構成としては、例えば、図４の対象三点の真ん中の点Ｐｉ＋１と別の点Ｐｉとを結ぶ線分Ｌａ上の予め定められた点と、部分円弧３１ａとの間の距離Ｄａを求める構成において、予め定められた点の位置が第１処理と第２処理とで異なる構成などが考えられる。これに以外にも、円弧に基づいて近似分割点が対象三点に含まれるかを判定する判定の設計次第では、第１処理と第２処理との判定結果が異なる場合があることが予測される。
【００９７】
＜実施の形態７のまとめ＞
以上のような本実施の形態７に係る地図データ生成装置１によれば、第１処理及び第２処理の少なくともいずれか一方で、第１点が近似分割点でないと判定された場合には、第１処理及び第２処理の結果として第１点が近似分割点でないと判定する。これにより、近似線の数を低減することができるので、データの圧縮性を高めることができる。
【００９８】
なお、一つの曲線と一つの直線とを組み合わせた近似線を用いる場合よりも、二つの曲線を組み合わせた近似線を用いる場合の方が、ある程度データの圧縮性を高めることができる。そこで、近似分割点抽出部２３は、第１処理で第１点が近似分割点であると判定され、第２処理で第１点が近似分割点でないと判定された場合には、始点側に第１点から１点ずらした第２点を近似分割点であると判定してもよい。
【００９９】
例えば、図１２において、第１処理で点Ｐ４が近似分割点であると判定され、第２処理で点Ｐ４が近似分割点でないと判定された場合には、始点Ｐ１側に点Ｐ４から１点ずらした点Ｐ３を近似分割点であると判定してもよい。この場合、図１４に示すように、地図データ生成装置１は、点Ｐ１〜Ｐ３に基づいて近似線ＡＬ１’を生成し、点Ｐ３〜Ｐ５に基づいて近似線ＡＬ２’を生成する。このような構成によれば、一つの曲線と一つの直線とを組み合わせた近似線よりも、二つの曲線の組み合わせた近似線を用いる可能性が高くなるので、データの圧縮性を高めることができる。
【０１００】
なお、以上の実施の形態７において、終点Ｐ５側の三点近似が可能であるかを判定したが、これに限ったものではなく、終点Ｐ５側において近似の対象となる点の数は三点以上であってもよい。また、以上の実施の形態７において、第１処理と第２処理とを入れ替えてもよい。つまり、第１処理が、形状点列の終点Ｐ５から始点Ｐ１に向かって順に対象三点を変更しながら、円弧の生成及び近似分割点の判定を含む処理であるとするとともに、第２処理が、形状点列の始点Ｐ１から終点Ｐ５に向かって順に対象三点を変更しながら、円弧の生成及び近似分割点の判定を含む処理であるとしてもよい。
【０１０１】
＜実施の形態８＞
実施の形態１〜７に係る地図データ生成装置１としては、例えば、地図データのベンダーなどによって用いられる装置が想定される。この場合、地図データ生成装置１で生成された地図データは、端末装置が備える記憶装置に記憶され、端末装置は、当該地図データを用いて三次元形状を表現することが可能となる。
【０１０２】
なお、端末装置には、例えば、車載端末装置及び携帯端末などが用いられる。車載端末装置には、例えば、ＰＮＤ（Portable Navigation Device）及びカーナビゲーション装置などが用いられる。携帯端末には、例えば、携帯電話、スマートフォン及びタブレットなどの通信端末が用いられる。
【０１０３】
図１５は、端末装置であるカーナビゲーション装置７１の構成を示すブロック図である。図１５のカーナビゲーション装置７１は、出力部７２、地図生成部７３と、記憶部７４と、これらを統括的に制御する制御部７５とを備え、表示装置７６と接続されている。
【０１０４】
記憶部７４は、地図データ生成装置１で生成された、近似線パラメータを含む地図データを格納している。制御部７５は、必要に応じて地図データを記憶部７４から読み出して地図生成部７３に出力し、地図生成部７３は、近似線パラメータを含む地図データに基づいて、三次元形状を表現可能な地図を生成する。制御部７５は、地図生成部７３で生成された地図を、出力部７２を介して表示装置７６に出力し、表示装置７６は当該地図を表示する。このように構成されたカーナビゲーション装置７１では、実物の三次元形状との差が抑制された三次元形状を表示することができる。
【０１０５】
＜実施の形態８の変形例＞
実施の形態８では、地図データ生成装置１は、地図データのベンダーなどによって用いられる装置であるとしたが、これに限ったものではない。例えば、地図データ生成装置１は、カーナビゲーション装置７１などの端末装置に備えられてもよい。
【０１０６】
具体的には図１６に示すようなカーナビゲーション装置７１が考えられる。図１６のカーナビゲーション装置７１は、図１５の構成要素に加えて通信部７７を備えている。
【０１０７】
通信部７７は、カーナビゲーション装置７１の外部と通信を行うことにより、三次元形状を示す形状点列を取得する。制御部７５は、通信部７７で取得された形状点列のうちの対象三点に基づいて、対象三点を通る円弧を生成し、円弧に基づいて近似分割点が対象三点に含まれるかを判定する。そして、制御部７５は、その判定結果に基づいて三次元形状を近似する近似線を生成し、近似線のパラメータを記憶部７４に記憶する。このように構成されたカーナビゲーション装置７１であっても、実物の三次元形状との差が抑制された三次元形状を表示することができる。なお、このことは、カーナビゲーション装置７１に限ったものではなく、カーナビゲーション装置以外の端末装置においても同様である。
【０１０８】
また、以上で説明した地図データ生成装置１は、ナビゲーション装置と、携帯電話、スマートフォン及びタブレットなどの携帯端末を含む通信端末と、これらにインストールされるアプリケーションの機能と、サーバとを適宜に組み合わせてシステムとして構築される地図データ生成システムにも適用することができる。この場合、以上で説明した地図データ生成装置の各機能あるいは各構成要素は、前記システムを構築する各機器に分散して配置されてもよいし、いずれかの機器に集中して配置されてもよい。
【０１０９】
＜その他の変形例＞
上述した地図データ生成装置１における取得部１１及び制御部１２を、以下「取得部１１等」と記す。取得部１１等は、図１７に示す処理回路８１により実現される。すなわち、処理回路８１は、三次元形状を示す形状点列を取得する取得部１１と、取得部１１で取得された形状点列のうちの対象三点に基づいて、対象三点を通る円弧を生成し、円弧に基づいて、三次元形状において近似すべきでない近似分割点が対象三点に含まれるかを判定する制御部１２と、を備える。処理回路８１には、専用のハードウェアが適用されてもよいし、メモリに格納されるプログラムを実行するプロセッサが適用されてもよい。プロセッサには、例えば、中央処理装置、処理装置、演算装置、マイクロプロセッサ、マイクロコンピュータ、ＤＳＰ（Digital Signal Processor）などが該当する。
【０１１０】
処理回路８１が専用のハードウェアである場合、処理回路８１は、例えば、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field Programmable Gate Array）、またはこれらを組み合わせたものが該当する。取得部１１等の各部の機能それぞれは、処理回路を分散させた回路で実現されてもよいし、各部の機能をまとめて一つの処理回路で実現されてもよい。
【０１１１】
処理回路８１がプロセッサである場合、取得部１１等の機能は、ソフトウェア等との組み合わせにより実現される。なお、ソフトウェア等には、例えば、ソフトウェア、ファームウェア、または、ソフトウェア及びファームウェアが該当する。ソフトウェア等はプログラムとして記述され、メモリに格納される。図１８に示すように、処理回路８１に適用されるプロセッサ８２は、メモリ８３に記憶されたプログラムを読み出して実行することにより、各部の機能を実現する。すなわち、地図データ生成装置１は、処理回路８１により実行されるときに、三次元形状を示す形状点列を取得するステップと、取得された形状点列のうちの対象三点に基づいて、対象三点を通る円弧を生成し、円弧に基づいて、三次元形状において近似すべきでない近似分割点が対象三点に含まれるかを判定するステップと、が結果的に実行されることになるプログラムを格納するためのメモリ８３を備える。換言すれば、このプログラムは、取得部１１等の手順や方法をコンピュータに実行させるものであるともいえる。ここで、メモリ８３には、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、フラッシュメモリー、ＥＰＲＯＭ（Erasable Programmable Read Only Memory）、ＥＥＰＲＯＭ（Electrically Erasable Programmable Read Only Memory）などの、不揮発性または揮発性の半導体メモリ、ＨＤＤ（Hard Disk Drive）、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ミニディスク、ＤＶＤ（Digital Versatile Disc）及びそのドライブ装置等、あらゆる記憶媒体が該当する。
【０１１２】
以上、取得部１１等の各機能が、ハードウェア及びソフトウェア等のいずれか一方で実現される構成について説明した。しかしこれに限ったものではなく、取得部１１等の一部を専用のハードウェアで実現し、別の一部をソフトウェア等で実現する構成であってもよい。例えば、取得部１１についてはレシーバなどの専用のハードウェアとしての処理回路でその機能を実現し、それ以外についてはプロセッサ８２としての処理回路８１がメモリ８３に格納されたプログラムを読み出して実行することによってその機能を実現することが可能である。以上のように、処理回路８１は、ハードウェア、ソフトウェア等、またはこれらの組み合わせによって、上述の各機能を実現することができる。
【０１１３】
なお、本発明は、その発明の範囲内において、各実施の形態及び各変形例を自由に組み合わせたり、各実施の形態及び各変形例を適宜、変形、省略したりすることが可能である。
【０１１４】
本発明は詳細に説明されたが、上記した説明は、すべての態様において、例示であって、本発明がそれに限定されるものではない。例示されていない無数の変形例が、本発明の範囲から外れることなく想定され得るものと解される。
【符号の説明】
【０１１５】
１  地図データ生成装置、１１  取得部、１２  制御部、３１  円弧、３１ａ，３１ｂ  部分円弧、７１  カーナビゲーション装置、Ｌａ，Ｌｂ  線分。
【図１】
0006469326.tif 000007
【図２】
0006469326.tif 000008
【図３】
0006469326.tif 000009
【図４】
0006469326.tif 000010
【図５】
0006469326.tif 000011
【図６】
0006469326.tif 000012
【図７】
0006469326.tif 000013
【図８】
0006469326.tif 000014
【図９】
0006469326.tif 000015
【図１０】
0006469326.tif 000016
【図１１】
0006469326.tif 000017
【図１２】
0006469326.tif 000018
【図１３】
0006469326.tif 000019
【図１４】
0006469326.tif 000020
【図１５】
0006469326.tif 000021
【図１６】
0006469326.tif 000022
【図１７】
0006469326.tif 000023
【図１８】
0006469326.tif 000024