(57)【要約】  地図データに含まれている線分を構成しているノードの中から、特定の縮尺より広域である生成対象の縮尺に応じて分岐点以外のノードの間引き処理を実施するノード間引き部１２を設け、階層的グラフ構成部１３がノード間引き部１２による間引き処理前後の各ノードを縮尺に応じて階層的に分類し、データ変換部１４が各階層に属するノードが接続されるノードを示す接続先情報を生成する。
2009118781.tif 000002
【特許請求の範囲】
【請求項１】
特定の縮尺の地図データを取得する地図データ取得手段と、上記地図データ取得手段により取得された地図データに含まれている線分を構成しているノードの中から、特定の縮尺より広域である生成対象の縮尺に応じて分岐点以外のノードの間引き処理を実施するノード間引き手段と、上記ノード間引き手段による間引き処理前後の各ノードを縮尺に応じて階層的に分類し、各階層に属するノードが接続されるノードを示す接続先情報を生成する接続先情報生成手段とを備えた地図データ作成装置。
【請求項２】
接続先情報生成手段は、各階層に属するノードが接続されるノードが、上位の階層に属するノード、同一の階層に属するノード、あるいは、下位の階層に属するノードであることを特徴とする請求項１記載の地図データ作成装置。
【請求項３】
接続先情報生成手段は、各階層に属するノードが接続されるノードを示す接続先情報を生成する際、各階層に属するノードが接続されるノードの階層方向を示す情報を接続先情報に含めることを特徴とする請求項２記載の地図データ作成装置。
【請求項４】
接続先情報生成手段は、各階層に属するノード間の接続関係をグラフで表現し、上記グラフのデータを所定の書式に変換して接続先情報を生成することを特徴とする請求項１記載の地図データ作成装置。
【請求項５】
接続先情報生成手段は、各階層に属するノード間の接続関係をグラフで表現する際、ある階層に属しているノードが２階層以上離れている上位の階層又は下位の階層に属しているノードと接続される場合、中間の階層にダミーノードを配置して、ある階層に属しているノードが上記ダミーノードを介して上記上位の階層又は上記下位の階層に属しているノードと接続されているように表現することを特徴とする請求項４記載の地図データ作成装置。
【請求項６】
接続先情報生成手段は、ある階層に属しているノードがダミーノードを介して上位の階層に属しているノードと接続される場合、ある階層に属しているノードが上記上位の階層に属しているノードと接続される旨を示す接続先情報を生成することを特徴とする請求項５記載の地図データ作成装置。
【請求項７】
ノード間引き手段は、複数のノードから構成されている複数の閉領域が隣接している場合、複数の閉領域を統合することを特徴とする請求項１記載の地図データ作成装置。
【請求項８】
ノード間引き手段は、複数のノードから構成されている閉領域の全てのノードを間引く場合、上記閉領域を示す代理ノードをグラフ上に配置することを特徴とする請求項４記載の地図データ作成装置。
【請求項９】
ノード間引き手段は、生成対象の縮尺と隣接するノード間の距離に応じて間引き対象のノードを決定することを特徴とする請求項１記載の地図データ作成装置。
【請求項１０】
特定の縮尺の地図データを取得する地図データ取得手段と、上記地図データ取得手段により取得された地図データに含まれている線分を構成しているノードの中から、特定の縮尺より広域である生成対象の縮尺に応じて分岐点以外のノードの間引き処理を実施するノード間引き手段と、上記ノード間引き手段による間引き処理前後の各ノードを縮尺に応じて階層的に分類し、各階層に属するノードが接続されるノードを示す接続先情報を生成する接続先情報生成手段と、上記接続先情報生成手段により生成された接続先情報のうち、所望の縮尺に対応する階層に属するノードに係る接続先情報を参照して、地図を描画する地図描画手段とを備えた地図描画装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、複数の縮尺に対応する地図データを作成する地図データ作成装置と、地図データ作成装置により作成された地図データにしたがって所望の縮尺の地図を描画する地図描画装置とに関するものである。
【背景技術】
【０００２】
従来の地図データ作成装置では、複数の縮尺の地図データを用意するために、事前に設定された規則にしたがって特定の縮尺の地図データに含まれているノードの間引き処理を実施するようにしている（例えば、特許文献１を参照）。【０００３】
例えば、カーナビゲーション装置に搭載されている従来の地図描画装置では、ユーザが指定する縮尺の地図を描画することができるようにするために、従来の地図データ作成装置により作成された複数の縮尺の地図データをメモリに格納し、ユーザが指定する縮尺の地図データを選択することができるようにしている（例えば、特許文献２を参照）。
このように、予め複数の縮尺の地図データを用意すれば、複数の縮尺の地図を描画することができるが、縮尺毎に地図データを用意する必要があるため、地図データのデータ量が膨大になる。【０００４】
そこで、縮尺毎に地図データを用意することなく、一つの地図データで複数の縮尺の地図を描画することができるようにするために、特定の縮尺の地図データに含まれているノードと、間引かれたノードとの関係を木構造で表現している地図データ作成装置が開発されている（例えば、特許文献３を参照）。【０００５】
【特許文献１】特開平７−３７０６７号公報（第２頁〜第４頁、図４、図６、図７）
【特許文献２】特開２００１−１１７４８８号公報（第３頁〜第４頁、図７）
【特許文献３】特開２０００−２９３８３号公報（第７頁〜第９頁、図２〜図７）
【０００６】
従来の地図データ作成装置は以上のように構成されているので、縮尺毎に地図データを用意することなく、一つの地図データで複数の縮尺の地図を描画することができる。しかし、特定の縮尺の地図データに含まれているノードと、間引かれたノードとの関係を木構造で表現するだけでは、例えば、分岐点がある道路など、複雑な形状の道路や地形を表現することができないなどの課題があった。【０００７】
この発明は上記のような課題を解決するためになされたもので、複数の縮尺に対応可能であり、かつ、複雑な形状の道路や地形を表現することが可能な地図データを作成することができる地図データ作成装置を得ることを目的とする。
また、この発明は、複雑な形状の道路や地形を所望の縮尺で描画することができる地図描画装置を得ることを目的とする。
【発明の開示】
【０００８】
この発明に係る地図データ作成装置は、地図データに含まれている線分を構成しているノードの中から、特定の縮尺より広域である生成対象の縮尺に応じて分岐点以外のノードの間引き処理を実施するノード間引き手段を設け、接続先情報生成手段がノード間引き手段による間引き処理前後の各ノードを縮尺に応じて階層的に分類し、各階層に属するノードが接続されるノードを示す接続先情報を生成するようにしたものである。
【０００９】
このことによって、複数の縮尺に対応可能であり、かつ、複雑な形状の道路や地形を表現することが可能な地図データを作成することができるなどの効果がある。
【図面の簡単な説明】
【００１０】
【図１】この発明の実施の形態１による地図描画装置を示す構成図である。
【図２】この発明の実施の形態１による地図データ作成装置１の処理内容を示すフローチャートである。
【図３】（ａ）（ｂ）はノード間引き部１２による間引き処理後のノードを示し、（ｃ）はノード間引き部１２による間引き処理前のノードを示す説明図である。
【図４】階層的グラフ構成部１３により表現されるグラフ（各階層に属するノード間の接続関係）を示す説明図である。
【図５】データ変換部１４により生成される接続先情報を示す説明図である。
【図６】（ａ）（ｂ）はノード間引き部１２による間引き処理後のノードを示し、（ｃ）はノード間引き部１２による間引き処理前のノードを示す説明図である。
【図７】階層的グラフ構成部１３により表現されるグラフ（各階層に属するノード間の接続関係）を示す説明図である。
【図８】データ変換部１４により生成される接続先情報を示す説明図である。
【発明を実施するための最良の形態】
【００１１】
以下、この発明をより詳細に説明するために、この発明を実施するための最良の形態について、添付の図面に従って説明する。
実施の形態１．
図１はこの発明の実施の形態１による地図描画装置を示す構成図であり、図において、地図データ作成装置１は複数の縮尺に対応可能であり、かつ、複雑な形状の道路や地形を表現することが可能な地図データを作成する装置である。【００１２】
地図データ記録装置２は基準となる特定の縮尺の地図データを記録しており、また、地図データ作成装置１により作成された地図データを格納するメモリである。
地図データ読み込み部１１は地図データ記録装置２から特定の縮尺の地図データを読み込む入力インタフェースである。なお、地図データ読み込み部１１は地図データ取得手段を構成している。【００１３】
ノード間引き部１２は最広域の縮尺設定を受け付けるインタフェースを備え、地図データ読み込み部１１により読み込まれた地図データに含まれている線分を構成しているノードの中から、特定の縮尺より広域である生成対象の縮尺に応じて分岐点以外のノードの間引き処理を実施する。なお、ノード間引き部１２はノード間引き手段を構成している。【００１４】
階層的グラフ構成部１３はノード間引き部１２による間引き処理前後の各ノードを縮尺に応じて階層的に分類し、各階層に属するノード間の接続関係をグラフで表現する処理を実施する。
データ変換部１４は階層的グラフ構成部１３によるグラフのデータを所定の書式に変換して、各階層に属するノードが接続されるノードを示す接続先情報を生成する処理を実施する。
なお、階層的グラフ構成部１３及びデータ変換部１４から接続先情報生成手段が構成されている。【００１５】
接続先情報書き込み部１５はデータ変換部１４により生成された接続先情報を地図データとして地図データ記録装置２に書き込む出力インタフェースである。
地図描画部１６は所望の縮尺の指定を受け付けるインタフェースを備え、地図データ記録装置２に記録されている接続先情報のうち、所望の縮尺に対応する階層に属するノードに係る接続先情報を参照して、地図を例えばカーナビゲーション装置のディスプレイ１７に描画する処理を実施する。なお、地図描画部１６は地図描画手段を構成している。【００１６】
図２はこの発明の実施の形態１による地図データ作成装置１の処理内容を示すフローチャートである。
図３はノード間引き部１２による間引き処理前後のノードを示す説明図である。
図４は階層的グラフ構成部１３により表現されるグラフ（各階層に属するノード間の接続関係）を示す説明図である。
図５はデータ変換部１４により生成される接続先情報を示す説明図である。【００１７】
次に動作について説明する。
地図データ作成装置１の地図データ読み込み部１１は、地図データ記録装置２から基準となる特定の縮尺の地図データを読み込み（図２のステップＳＴ１）、その地図データをノード間引き部１２に出力する。
なお、地図データは線分を構成しているノードの情報を含んでおり、このノードの情報には、当該ノードの位置を示す座標データ等が含まれている。【００１８】
ノード間引き部１２は、地図データ読み込み部１１から地図データを受けると、その地図データの縮尺を最も詳細なレベルの縮尺に設定する（ステップＳＴ２）。
また、ノード間引き部１２は、最広域の縮尺設定を受け付け、生成対象の縮尺を最も詳細なレベルの縮尺より一段階広域のレベル（最広域の縮尺より詳細な縮尺、あるいは、最広域の縮尺と等しい縮尺）に設定する（ステップＳＴ３）。
なお、図３の例では、（ｃ）の縮尺が最も詳細なレベルの縮尺に設定され、（ａ）の縮尺が最広域の縮尺に設定され、（ｂ）の縮尺が最初の生成対象の縮尺に設定される。【００１９】
ノード間引き部１２は、生成対象の縮尺を設定すると、地図データ読み込み部１１から出力された地図データに含まれている線分を構成しているノードの中から、生成対象の縮尺に応じて分岐点以外のノードの間引き処理を実施する（ステップＳＴ４）。
間引き対象のノードの決定方法は特に問わないが、例えば、生成対象の縮尺と隣接するノード間の距離に応じて間引き対象のノードを決定すればよい。
即ち、生成対象の縮尺に対応する基準距離（生成対象の縮尺が広域である程、大きな距離値）と、隣接するノード間の距離とを比較し、隣接するノード間の距離が基準距離より小さければ、隣接するノードのいずれか一方を間引き対象のノードに決定するようにする。【００２０】
この段階では、図３（ｂ）の縮尺が生成対象の縮尺に設定されているので、図３（ｃ）のノードに対して間引き処理が行われる。
図３（ｃ）の例では、ノードＣ１〜Ｃ１０が間引き処理の対象に決定され、■で表されている７つのノードが間引き処理の対象にならずに残っている。【００２１】
階層的グラフ構成部１３は、ノード間引き部１２がノードの間引き処理を実施すると、ノード間引き部１２による間引き処理前後の各ノードを縮尺に応じて階層的に分類し、各階層に属するノード間の接続関係をグラフで表現する処理を実施する（ステップＳＴ５）。
この段階では、図３（ｂ）の縮尺が最初の生成対象の縮尺に設定されており、ノードＣ１〜Ｃ１０が間引かれているので、図４（ｃ）に示すように、ノードＣ１〜Ｃ１０が最下位層に属するノードに分類され、ノードＣ１〜Ｃ１０が最下位層に配置される。
図３（ｃ）における■で表されている７つのノード（ノードＡ１〜Ａ４、Ｂ１〜Ｂ３）は、この段階では間引かれないノードであるため、最下位層に属するノードには分類されない。【００２２】
階層的グラフ構成部１３は、ノードＣ１〜Ｃ１０を最下位層に配置すると、ノードＣ１〜Ｃ１０の接続関係をグラフで表現する。
例えば、ノードＣ２は同位層のノードＣ１と接続関係があるので、ノードＣ１とノードＣ２を線で結合する。また、ノードＣ２は上位層のノードＢ１と接続関係があるので、ノードＣ２とノードＢ１を線で結合する。
例えば、ノードＣ８は同位層のノードＣ９と接続関係があるので、ノードＣ８とノードＣ９を線で結合する。また、ノードＣ８は最上位層（２層上）のノードＡ２と接続関係があるが、ノードＡ２は一つ上の層に分類されないので、ノードＣ８を一つ上の層に配置されるダミーノードＤ２（ダミーノードについては後述する）と線で結合する。
以下、同様にして、最下位層に配置している全てのノードの接続関係をグラフで表現する。【００２３】
ノード間引き部１２は、階層的グラフ構成部１３がノードＣ１〜Ｃ１０を最下位層に配置して、ノードＣ１〜Ｃ１０の接続関係をグラフで表現すると、生成対象の縮尺が最広域の縮尺であるか否かを判定する（ステップＳＴ６）。
この段階では、生成対象の縮尺が図３（ｂ）の縮尺であり、最広域の縮尺ではないと判定される。【００２４】
ノード間引き部１２は、生成対象の縮尺が最広域の縮尺でないと判定すると、生成対象の縮尺を前回より一段階広域のレベルに設定する（ステップＳＴ３）。
図３の例では、生成対象の縮尺を図３（ａ）の縮尺（最広域の縮尺）に設定する。【００２５】
ノード間引き部１２は、生成対象の縮尺を図３（ａ）の縮尺に設定すると、図３（ｂ）が示すノードの中から、生成対象の縮尺に応じて分岐点以外のノードの間引き処理を実施する（ステップＳＴ４）。
この段階では、図３（ａ）が生成対象の縮尺に設定されているので、図３（ｂ）のノードに対して間引き処理が行われる。
図３（ｂ）の例では、ノードＢ１〜Ｂ３が間引き処理の対象に決定され、■で表されている４つのノードが間引き処理の対象にならずに残っている。【００２６】
階層的グラフ構成部１３は、ノード間引き部１２がノードの間引き処理を実施すると、ノード間引き部１２による間引き処理前後の各ノードを縮尺に応じて階層的に分類し、各階層に属するノード間の接続関係をグラフで表現する処理を実施する（ステップＳＴ５）。
この段階では、図３（ａ）の縮尺が生成対象の縮尺に設定されており、ノードＢ１〜Ｂ３が間引かれているので、図４（ｂ）に示すように、ノードＢ１〜Ｂ３が中位層に属するノードに分類され、ノードＢ１〜Ｂ３が中位層に配置される。【００２７】
図３の例では、縮尺の段階が３段階であるため、図３（ｂ）における■で表されている４つのノード（ノードＡ１〜Ａ４）は、自動的に最上位層に属するノードに分類され、最上位層に配置される。
なお、図３（ｂ）における■で表されている４つのノード（ノードＡ１〜Ａ４）が最上位層に属するノードに分類されることにより、ノードＡ１〜Ａ４と接続関係がある下位のノードＣ１，Ｃ３，Ｃ４，Ｃ７，Ｃ８，Ｃ１０が２階層離れてしまうので、この４つのノードの代わりとして、ダミーノードＤ１，Ｄ２，Ｄ３，Ｄ４を中位層に配置している。【００２８】
階層的グラフ構成部１３は、ノードＢ１〜Ｂ３，ダミーノードＤ１〜Ｄ４を中位層に配置し、ノードＡ１〜Ａ４を最上位層に配置すると、ノードＢ１〜Ｂ３，ダミーノードＤ１〜Ｄ４及びノードＡ１〜Ａ４の接続関係をグラフで表現する。
例えば、ノードＢ１は上位層のノードＡ１，Ａ２と接続関係があるので、ノードＢ１とノードＡ１，Ａ２を線で結合する。また、ノードＢ１は下位層のノードＣ２，Ｃ３と接続関係があるので、ノードＢ１とノードＣ２，Ｃ３を線で結合する。
例えば、ダミーノードＤ２は上位層のノードＡ２と接続関係があるので、ダミーノードＤ２とノードＡ２を線で結合する。また、ダミーノードＤ２は下位層のノードＣ３，Ｃ４，Ｃ８と接続関係があるので、ダミーノードＤ２とノードＣ３，Ｃ４，Ｃ８を線で結合する。【００２９】
例えば、ノードＡ２は同位層のノードＡ１，Ａ３，Ａ４と接続関係があるので、ノードＡ２とノードＡ１，Ａ３，Ａ４を線で結合する。また、ノードＡ２は下位層のノードＢ１，Ｂ２，Ｂ３，ダミーノードＤ２と接続関係があるので、ノードＡ２とノードＢ１，Ｂ２，Ｂ３，ダミーノードＤ２を線で結合する。さらに、ノードＡ２は最上位層のノードであるので、ノードＡ２と（根）ノードを線で結合する。
以下、同様にして、中位層及び最上位層に配置している全てのノードの接続関係をグラフで表現する。【００３０】
ノード間引き部１２は、階層的グラフ構成部１３がノードＢ１〜Ｂ３，ダミーノードＤ１〜Ｄ４を中位層、ノードＡ１〜Ａ４を最上位層に配置して、ノードＢ１〜Ｂ３，ダミーノードＤ１〜Ｄ４及びノードＡ１〜Ａ４の接続関係をグラフで表現すると、生成対象の縮尺が最広域の縮尺であるか否かを判定する（ステップＳＴ６）。
この段階では、生成対象の縮尺が図３（ａ）の縮尺であるため、最広域の縮尺であると判定され、ステップＳＴ７の処理に移行する。【００３１】
データ変換部１４は、階層的グラフ構成部１３が全てのノードの接続関係をグラフで表現すると、そのグラフのデータ（各ノードの配置や、ノード間の接続関係を示すデータ）を所定の書式に変換し、図５に示すような接続先情報を生成する（ステップＳＴ７）。
接続先情報は、図５に示すように、各階層に属するノードが接続されるノードを示す情報であり、各階層に属するノードが接続されるノードの階層方向（上位、同位、下位）を示す情報を含んでいる。【００３２】
例えば、最下位層に属するノードＣ１に係る接続先情報は、同位層のノードＣ２と接続され、かつ、最上位層のノードＡ１と接続される旨を示している。
図４のグラフ表現では、ノード間の接続関係及び階層関係を明確にするために、ノードＣ１はダミーノードＤ１と接続されるように表現されているが、図５の接続先情報では、ノードＣ１が実際に接続されるノードを特定するため、ダミーノードＤ１の本体であるノードＡ１と接続される旨を示している。【００３３】
接続先情報書き込み部１５は、データ変換部１４が接続先情報を生成すると、その接続先情報を地図データとして地図データ記録装置２に格納する。
地図描画部１６は、所望の縮尺の指定を受け付けるインタフェースを備えており、地図データ記録装置２に記録されている接続先情報のうち、所望の縮尺に対応する階層に属するノードに係る接続先情報を参照して、地図をディスプレイ１７に描画する。
例えば、図３（ｃ）の縮尺が指定された場合、最下位層に属するノードＣ１〜Ｃ１０に係る接続先情報を参照する。具体的には、ノードＣ１〜Ｃ１０と接続される同位層のノードと、上位層のノードを確認して、図３（ｃ）の縮尺の地図を描画する。【００３４】
また、図３（ｂ）の縮尺が指定された場合、中位層に属するノードＢ１〜Ｂ３に係る接続先情報を参照する。具体的には、ノードＢ１〜Ｂ３と接続される同位層のノードと、上位層のノードを確認して、図３（ｂ）の縮尺の地図を描画する。
また、図３（ａ）の縮尺が指定された場合、最上位層に属するノードＡ１〜Ａ４に係る接続先情報を参照する。具体的には、ノードＡ１〜Ａ４と接続される同位層のノードを確認して、図３（ａ）の縮尺の地図を描画する。【００３５】
以上で明らかなように、この実施の形態１によれば、地図データに含まれている線分を構成しているノードの中から、生成対象の縮尺に応じて分岐点以外のノードの間引き処理を実施するノード間引き部１２を設け、階層的グラフ構成部１３がノード間引き部１２による間引き処理前後の各ノードを縮尺に応じて階層的に分類し、データ変換部１４が各階層に属するノードが接続されるノードを示す接続先情報を生成するように構成したので、複数の縮尺に対応可能であり、かつ、複雑な形状の道路や地形を表現することが可能な地図データを作成することができるなどの効果を奏する。【００３６】
また、この実施の形態１によれば、地図データ記録装置２に記録されている接続先情報のうち、所望の縮尺に対応する階層に属するノードに係る接続先情報を参照して、地図をディスプレイ１７に描画するように構成したので、例えば、分岐点がある道路のように、複雑な形状の道路や地形を所望の縮尺で描画することができる効果を奏する。【００３７】
実施の形態２．
上記実施の形態１では、地図データに含まれている線分が分岐しているものについて示したが、他の線分と独立している閉領域が地図データに含まれている場合にも、図１の地図データ作成装置１及び地図描画装置を適用することができる。【００３８】
図６はノード間引き部１２による間引き処理前後のノードを示す説明図である。
図７は階層的グラフ構成部１３により表現されるグラフ（各階層に属するノード間の接続関係）を示す説明図である。
図８はデータ変換部１４により生成される接続先情報を示す説明図である。【００３９】
以下、図１の地図データ作成装置１及び地図描画装置の処理内容を説明するが、地図データ記録装置２には、基準となる特定の縮尺の地図データとして、図６（ｃ）に示すように、１本の線分の他に、２つの閉領域（例えば、街区などが該当する）が地図データに含まれている例を説明する。
地図データ作成装置１の地図データ読み込み部１１は、地図データ記録装置２から基準となる特定の縮尺の地図データを読み込み（図２のステップＳＴ１）、その地図データをノード間引き部１２に出力する。
なお、地図データは線分を構成しているノードの情報を含んでおり、このノードの情報には、当該ノードの位置を示す座標データ等が含まれている。【００４０】
ノード間引き部１２は、地図データ読み込み部１１から地図データを受けると、上記実施の形態１と同様に、その地図データの縮尺を最も詳細なレベルの縮尺に設定する（ステップＳＴ２）。
また、ノード間引き部１２は、最広域の縮尺設定を受け付け、生成対象の縮尺を最も詳細なレベルの縮尺より一段階広域のレベル（最広域の縮尺より詳細な縮尺、あるいは、最広域の縮尺と等しい縮尺）に設定する（ステップＳＴ３）。
なお、図６の例では、（ｃ）の縮尺が最も詳細なレベルの縮尺に設定され、（ａ）の縮尺が最広域の縮尺に設定され、（ｂ）の縮尺が最初の生成対象の縮尺に設定される。【００４１】
ノード間引き部１２は、生成対象の縮尺を設定すると、地図データ読み込み部１１から出力された地図データに含まれている線分を構成しているノードの中から、生成対象の縮尺に応じて分岐点以外のノードの間引き処理を実施する（ステップＳＴ４）。
間引き対象のノードの決定方法は特に問わないが、例えば、生成対象の縮尺と隣接するノード間の距離に応じて間引き対象のノードを決定すればよい。
即ち、生成対象の縮尺に対応する基準距離（生成対象の縮尺が広域である程、大きな距離値）と、隣接するノード間の距離とを比較し、隣接するノード間の距離が基準距離より小さければ、隣接するノードのいずれか一方を間引き対象のノードに決定するようにする。【００４２】
この段階では、図６（ｂ）が生成対象の縮尺に設定されているので、図６（ｃ）のノードに対して間引き処理が行われる。
図６（ｃ）の例では、ノードＣ９，Ｃ１０，Ｃ１１等から構成されている線分については、ノードＣ９，Ｃ１０，Ｃ１１が間引き処理の対象に決定され、■で表されている３つのノードが間引き処理の対象にならずに残っている。【００４３】
また、隣接している２つの閉領域については、広域描画（生成対象の縮尺で描画）を行う場合、２つの閉領域間の境界部分（ノードＣ４とノードＣ５の間、ノードＣ３とノードＣ６の間）が非常に狭くなり、その境界部分の明確な描画が困難であるため、２つの閉領域を統合するようにしている。
図６（ｃ）の例では、ノードＣ１〜Ｃ８が間引き処理の対象に決定され、■で表されている４つのノードが間引き処理の対象にならずに残っている。
この結果、図６（ｂ）に示すように、■で表されている４つのノード（ノードＢ１〜Ｂ４）から１つの閉領域が構成されている。
なお、２つの閉領域間の境界部分が非常に狭いか否かの判断としては、例えば、生成対象の縮尺に対応する基準距離（生成対象の縮尺が広域である程、大きな距離値）と、境界部分の距離とを比較し、境界部分の距離が基準距離より小さければ、境界部分が非常に狭いと判断するようにすればよい。【００４４】
階層的グラフ構成部１３は、ノード間引き部１２がノードの間引き処理を実施すると、上記実施の形態１と同様に、ノード間引き部１２による間引き処理前後の各ノードを縮尺に応じて階層的に分類し、各ノードが属する階層とノード間の接続関係をグラフで表現する処理を実施する（ステップＳＴ５）。
この段階では、図６（ｂ）の縮尺が最初の生成対象の縮尺に設定されており、ノードＣ１〜Ｃ１１が間引かれているので、図７（ｃ）に示すように、ノードＣ１〜Ｃ１１が最下位層に属するノードに分類され、ノードＣ１〜Ｃ１１が最下位層に配置される。
図６（ｃ）における■で表されている７つのノード（ノードＡ１〜Ａ２、Ｂ１〜Ｂ４）は、この段階では間引かれないノードであるため、最下位層に属するノードには分類されない。【００４５】
階層的グラフ構成部１３は、ノードＣ１〜Ｃ１１を最下位層に配置すると、ノードＣ１〜Ｃ１１の接続関係をグラフで表現する。
例えば、ノードＣ２は同位層のノードＣ３と接続関係があるので、ノードＣ２とノードＣ３を線で結合する。また、ノードＣ２は上位層のノードＢ２と接続関係があるので、ノードＣ２とノードＢ２を線で結合する。
例えば、ノードＣ９は同位層のノードＣ１０と接続関係があるので、ノードＣ９とノードＣ１０を線で結合する。また、ノードＣ９は最上位層（２層上）のノードＡ１と接続関係があるが、ノードＡ１は一つ上の層に分類されないので、ノードＣ９を一つ上の層に配置されるダミーノードＤ１と線で結合する。
以下、同様にして、最下位層に配置している全てのノードの接続関係をグラフで表現する。【００４６】
ノード間引き部１２は、階層的グラフ構成部１３がノードＣ１〜Ｃ１１を最下位層に配置して、ノードＣ１〜Ｃ１１の接続関係をグラフで表現すると、上記実施の形態１と同様に、生成対象の縮尺が最広域の縮尺であるか否かを判定する（ステップＳＴ６）。
この段階では、生成対象の縮尺が図６（ｂ）の縮尺であり、最広域の縮尺ではないと判定される。【００４７】
ノード間引き部１２は、生成対象の縮尺が最広域の縮尺でないと判定すると、生成対象の縮尺を前回より一段階広域のレベルに設定する（ステップＳＴ３）。
図６の例では、生成対象の縮尺を図６（ａ）の縮尺（最広域の縮尺）に設定する。【００４８】
ノード間引き部１２は、生成対象の縮尺を図６（ａ）の縮尺に設定すると、図６（ｂ）が示すノードの中から、生成対象の縮尺に応じて分岐点以外のノードの間引き処理を実施する（ステップＳＴ４）。
この段階では、図６（ａ）が生成対象の縮尺に設定されているので、図６（ｂ）のノードに対して間引き処理が行われる。
図６（ｂ）の例では、ノードＢ５等から構成されている線分については、ノードＢ５が間引き処理の対象に決定され、■で表されている２つのノードが間引き処理の対象にならずに残っている。【００４９】
また、ノードＢ１〜Ｂ４から構成されている閉領域については、広域描画（生成対象の縮尺で描画）を行う場合、閉領域の表示面積が非常に狭くなり、その閉領域の明確な描画が困難であるため、その閉領域を除去するようにしている。
この結果、ノードＢ１〜Ｂ４が間引き処理の対象に決定されている。
なお、閉領域の表示面積が非常に狭いか否かの判断としては、例えば、生成対象の縮尺に対応する基準面積（生成対象の縮尺が広域である程、大きな面積値）と、閉領域の表示面積とを比較し、閉領域の表示面積が基準面積より小さければ、閉領域の表示面積が非常に狭いと判断するようにすればよい。【００５０】
階層的グラフ構成部１３は、ノード間引き部１２がノードの間引き処理を実施すると、上記実施の形態１と同様に、ノード間引き部１２による間引き処理前後の各ノードを縮尺に応じて階層的に分類し、各ノードが属する階層とノード間の接続関係をグラフで表現する処理を実施する（ステップＳＴ５）。
この段階では、図６（ａ）の縮尺が生成対象の縮尺に設定されており、ノードＢ１〜Ｂ５が間引かれているので、図７（ｂ）に示すように、ノードＢ１〜Ｂ５が中位層に属するノードに分類され、ノードＢ１〜Ｂ５が中位層に配置される。【００５１】
図６の例では、縮尺の段階が３段階であるため、図６（ｂ）における■で表されている２つのノード（ノードＡ１〜Ａ２）は、自動的に最上位層に属するノードに分類され、最上位層に配置される。
なお、図６（ｂ）における■で表されている２つのノード（ノードＡ１〜Ａ２）が最上位層に属するノードに分類されることにより、ノードＡ１〜Ａ２と接続関係がある下位のノードＣ９，Ｃ１１が２階層離れてしまうので、この２つのノードＡ１〜Ａ２の代わりとして、ダミーノードＤ１，Ｄ２を中位層に配置している。
また、ノードＢ１〜Ｂ４から構成されている閉領域が除去されており、ノードＢ１〜Ｂ４が（根）ノードと２階層離れてしまうので、代理ノードＰＤ１を最上位層に配置している。【００５２】
階層的グラフ構成部１３は、ノードＢ１〜Ｂ５，ダミーノードＤ１〜Ｄ２を中位層に配置し、ノードＡ１〜Ａ２，代理ノードＰＤ１を最上位層に配置すると、ノードＢ１〜Ｂ５，ダミーノードＤ１〜Ｄ２，ノードＡ１〜Ａ２及び代理ノードＰＤ１の接続関係をグラフで表現する。
例えば、ノードＢ１は上位層の代理ノードＰＤ１と接続関係があるので、ノードＢ１と代理ノードＰＤ１を線で結合する。また、ノードＢ１は同位層のノードＢ２，Ｂ４と接続関係があるので、ノードＢ１とノードＢ２，Ｂ４を線で結合する。さらに、ノードＢ１は下位層のノードＣ１，Ｃ４と接続関係があるので、ノードＢ１とノードＣ１，Ｃ４を線で結合する。
例えば、ダミーノードＤ１は上位層のノードＡ１と接続関係があるので、ダミーノードＤ１とノードＡ１を線で結合する。また、ダミーノードＤ１は下位層のノードＣ９と接続関係があるので、ダミーノードＤ１とノードＣ９を線で結合する。【００５３】
例えば、ノードＡ１は同位層のノードＡ２と接続関係があるので、ノードＡ１とノードＡ２を線で結合する。また、ノードＡ１は下位層のノードＢ５，ダミーノードＤ１と接続関係があるので、ノードＡ１とノードＢ５，ダミーノードＤ１を線で結合する。さらに、ノードＡ１は最上位層のノードであるので、ノードＡ１と（根）ノードを線で結合する。
例えば、代理ノードＰＤ１は下位層のノードＢ１，Ｂ２，Ｂ３，Ｂ４と接続関係があるので、代理ノードＰＤ１とノードＢ１，Ｂ２，Ｂ３，Ｂ４を線で結合する。さらに、代理ノードＰＤ１は最上位層のノードであるので、代理ノードＰＤ１と（根）ノードを線で結合する。
以下、同様にして、中位層及び最上位層に配置している全てのノードの接続関係をグラフで表現する。【００５４】
ノード間引き部１２は、階層的グラフ構成部１３がノードＢ１〜Ｂ５，ダミーノードＤ１〜Ｄ２を中位層、ノードＡ１〜Ａ２，代理ノードＰＤ１を最上位層に配置して、ノードＢ１〜Ｂ５，ダミーノードＤ１〜Ｄ２，ノードＡ１〜Ａ４及び代理ノードＰＤ１の接続関係をグラフで表現すると、生成対象の縮尺が最広域の縮尺であるか否かを判定する（ステップＳＴ６）。
この段階では、生成対象の縮尺が図６（ａ）の縮尺であるため、最広域の縮尺であると判定され、ステップＳＴ７の処理に移行する。【００５５】
データ変換部１４は、階層的グラフ構成部１３が全てのノードの接続関係をグラフで表現すると、上記実施の形態１と同様に、そのグラフのデータ（各ノードの配置や、ノード間の接続関係を示すデータ）を所定の書式に変換し、図８に示すような接続先情報を生成する（ステップＳＴ７）。
接続先情報は、図８に示すように、各階層に属するノードが接続されるノードを示す情報であり、各階層に属するノードが接続されるノードの階層方向（上位、同位、下位）を示す情報を含んでいる。【００５６】
例えば、最下位層に属するノードＣ２に係る接続先情報は、同位層のノードＣ３と接続され、かつ、中位層のノードＢ２と接続される旨を示している。
例えば、中位層に属するノードＢ１に係る接続先情報は、同位層のノードＢ２，Ｂ４と接続され、かつ、最下位層のノードＣ１，Ｃ４と接続され、かつ、最上位層の代理ノードＰＤ１と接続される旨を示している。【００５７】
接続先情報書き込み部１５は、データ変換部１４が接続先情報を生成すると、上記実施の形態１と同様に、その接続先情報を地図データとして地図データ記録装置２に格納する。
地図描画部１６は、所望の縮尺の指定を受け付けるインタフェースを備えており、地図データ記録装置２に記録されている接続先情報のうち、所望の縮尺に対応する階層に属するノードに係る接続先情報を参照して、地図をディスプレイ１７に描画する。
例えば、図６（ｃ）の縮尺が指定された場合、最下位層に属するノードＣ１〜Ｃ１１に係る接続先情報を参照する。具体的には、ノードＣ１〜Ｃ１１と接続される同位層のノードと、上位層のノードを確認して、図６（ｃ）の縮尺の地図を描画する。【００５８】
また、図６（ｂ）の縮尺が指定された場合、中位層に属するノードＢ１〜Ｂ５に係る接続先情報を参照する。具体的には、ノードＢ１〜Ｂ５と接続される同位層のノードと、上位層のノードを確認して、図６（ｂ）の縮尺の地図を描画する。
また、図６（ａ）の縮尺が指定された場合、最上位層に属するノードＡ１〜Ａ２に係る接続先情報を参照する。具体的には、ノードＡ１〜Ａ２と接続される同位層のノードを確認して、図６（ａ）の縮尺の地図を描画する。【００５９】
以上で明らかなように、他の線分と独立している閉領域が地図データに含まれている場合でも、上記実施の形態１と同様に、複数の縮尺に対応可能であり、かつ、複雑な形状の道路や地形を表現することが可能な地図データを作成することができる効果を奏する。【００６０】
なお、上記実施の形態１，２では、縮尺の段階が３段階であるものについて示したが、これは一例に過ぎず、縮尺の段階が４段階以上であってもよい。
【産業上の利用可能性】
【００６１】
以上のように、この発明に係る地図データ作成装置は、縮尺毎に地図データを用意することなく、一つの地図データで複数の縮尺の地図を描画する必要があるカーナビゲーション装置などに用いるのに適している。
【図１】
2009118781.tif 000003
【図２】
2009118781.tif 000004
【図３】
2009118781.tif 000005
【図４】
2009118781.tif 000006
【図５】
2009118781.tif 000007
【図６】
2009118781.tif 000008
【図７】
2009118781.tif 000009
【図８】
2009118781.tif 000010
【国際調査報告】
2009118781.tif 000011
2009118781.tif 000012
2009118781.tif 000013
2009118781.tif 000014