(57)【特許請求の範囲】
【請求項１】
地図表示領域の一部に表示されるデフォルメ対象の地図を重要性に応じて複数の領域に分割し、重要性が高い領域が広くなり、重要性が低い領域が狭くなるように、各分割領域の輪郭形状を上記地図表示領域内で変形するレイアウト決定手段と、
上記レイアウト決定手段により変形された上記各分割領域内の地図を示す地図データを、上記地図データを構成する複数のノードの座標を変更して各ノードが上記変形された各分割領域内に入るようにするとともに、各ノードを接続するエッジの方向を量子化することによりデフォルメ処理するデフォルメ手段と、
上記デフォルメ手段によるデフォルメ処理後の各分割領域の地図を表示する表示手段と
を備えたデフォルメ地図生成装置。
【請求項２】
レイアウト決定手段は、デフォルメ対象の地図を、特に注目する部分と注目しない部分を区別可能な重要性を示すパラメータに基づき複数の領域に分割する領域分割部と、デフォルメ対象の地図と地図表示領域とから上記各分割領域の輪郭形状を伸張することが可能な伸張領域として、地図表示領域においてデフォルメ対象の地図が表示されていない伸張可能領域を検出する伸張領域検出部と、上記領域分割部により分割された各分割領域を上記伸張可能領域まで伸ばして、分割領域の輪郭形状を変形する配置位置決定部とを備えていることを特徴とする請求項１記載のデフォルメ地図生成装置。
【請求項３】
デフォルメ手段は、相互に隣接している分割領域間を跨いでいる複数のノードで構成された地図データがある場合、上記分割領域間の境界と交差する上記地図データ上の地点を接続地点としてノードを設定する接続地点設定部と、各分割領域内の地図を示す地図データを構成するノードの間引きを行うデータ削減部と、上記接続地点設定部により設定された接続地点のノード及び上記データ削減部により間引かれずに残っているノードのうち、少なくとも１つ以上のノードを移動して、複数の分割領域内の地図の形状を変形する形状変形部とを備えていることを特徴とする請求項１または請求項２記載のデフォルメ地図生成装置。
【請求項４】
形状変形部は、レイアウト決定手段により配置位置が決定された分割領域のうち、地図表示領域の淵に配置位置が決定された分割領域内の地図の形状を変形する際の条件として、ノードの移動方向、または、ノードの移動後の座標値の制限、の少なくとも一方の条件を算出する変形条件算出部と、上記変形条件算出部により算出された条件の下で、接続地点設定部により設定された接続地点のノード及びデータ削減部により間引かれずに残っているノードのうち、少なくとも１つ以上のノードを移動する初期配置部と、上記初期配置部により移動処理が実施されたのち、エッジ長やエッジ方向、ノードの個数に基づき、複数のエッジをグループ分けして、複数のグループを生成するグループ生成部と、上記グループ生成部により生成されたグループ毎に、当該グループに属するエッジ列の形状の簡略化度合が変わるように変形するエッジ列形状変形部とを備えていることを特徴とする請求項３記載のデフォルメ地図生成装置。
【請求項５】
初期配置部は、形状のデフォルメにおいて最重要視する基準であるエッジ長、エッジ方向が設定されている場合、上記基準にしたがってノードを移動することを特徴とする請求項４記載のデフォルメ地図生成装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、地図をデフォルメして、デフォルメ地図を生成するデフォルメ地図生成装置に関するものである。
【背景技術】
【０００２】
例えば、カーナビゲーション装置や歩行者ナビゲーション装置では、地図の表示内容の視認性を高める目的で、デフォルメ地図を生成するデフォルメ地図生成装置が搭載されていることがある。
例えば、以下の特許文献１には、地図を複数の領域に分割して、各分割領域内の地図を異なる簡略化度合で簡略化することによって、必要な部分は詳細に表示し、不要な部分は簡易化したデフォルメ地図を表示しているデフォルメ地図生成装置が開示されている。
【０００３】
また、以下の特許文献２には、道路の方向を量子化して道路の形状を変形することにより、デフォルメ地図を生成しているデフォルメ地図生成装置が開示されている。
即ち、エッジと基準線（水平あるいは鉛直方向）とのなす角度が、予め設定された単位角度の整数倍となるように、逐次、エッジを回転させながらエッジ方向を量子化するようにしている。
【０００４】
【特許文献１】特開２００６−２２７７６７号公報（段落番号［０００６］、図１）
【特許文献２】特開２００６−１１３４５７号公報（段落番号［０００５］、図１）
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来のデフォルメ地図生成装置は以上のように構成されているので、地図の表示内容の視認性を高める目的で、デフォルメ地図を生成することができる。しかし、地図を表示するディスプレイ等の画面領域が考慮されることなくデフォルメ地図が生成されるため、デフォルメ地図のレイアウト（配置位置）が適正な位置にならず、ユーザが意図する内容に近いデフォルメ地図が得られないことがある課題があった。
具体的には、以下に示す課題があった。
【０００６】
（１）デフォルメ対象領域の形状によっては、ディスプレイ等の画面領域を有効に活用することができないことがある。例えば、デフォルメ対象領域の形状が縦長である場合、デフォルメ後の領域の形状も縦長になる可能性が大きいが、画面領域が横長のディスプレイに表示する場合には、画面領域の左右に無駄な領域が発生する。
（２）ユーザが重要視する部分がディスプレイの画面領域のいずれに表示されるか分らず、画面領域内で見やすい位置に表示される保障がない。
（３）デフォルメ対象領域に対して、大局的な形状のデフォルメが困難であり、ディスプレイ等の画面領域を有効に活用することができない。例えば、図２６に示すようなデフォルメ対象領域について、図２７に示すように、デフォルメ対象領域の一部分を大胆にデフォルメすることができない。
（４）ある領域の地図の簡略化を行う場合、当該領域内に、複雑な形状の道路と簡素な形状の道路が混在していても、双方の道路が同じ簡略化度合で簡略化されてしまう。このため、簡略化度合を大きくすると、複雑な形状の道路が分り難くなってしまうことがある。逆に、簡略化度合を小さくすると、簡素な形状の道路のデフォルメを十分に行えなくなることがある。
【０００７】
この発明は上記のような課題を解決するためになされたもので、ユーザが意図する内容に近いデフォルメ地図を表示することができるデフォルメ地図生成装置を得ることを目的とする。
【課題を解決するための手段】
【０００８】
この発明に係るデフォルメ地図生成装置は、地図表示領域の一部に表示されるデフォルメ対象の地図を重要性に応じて複数の領域に分割し、重要性が高い領域が広くなり、重要性が低い領域が狭くなるように、各分割領域の輪郭形状を上記地図表示領域内で変形するレイアウト決定手段と、レイアウト決定手段により変形された各分割領域内の地図を示す地図データを、地図データを構成する複数のノードの座標を変更して各ノードが変形された各分割領域内に入るようにするとともに、各ノードを接続するエッジの方向を量子化することによりデフォルメ処理するようにしたものである。
【発明の効果】
【０００９】
この発明によれば、デフォルメ対象の地図を複数の領域に分割して、各分割領域を地図表示領域に応じて変形し、各分割領域の配置位置を決定するレイアウト決定手段を設け、デフォルメ手段がレイアウト決定手段により配置位置が決定された各分割領域内の地図を示す地図データを変更して、地図の形状を変形するように構成したので、ユーザが意図する内容に近いデフォルメ地図を表示することができる効果がある。
【発明を実施するための最良の形態】
【００１０】
実施の形態１．
図１はこの発明の実施の形態１によるデフォルメ地図生成装置を示す構成図であり、図において、地図記憶部１はデフォルメ対象の地図を示す地図データ（例えば、道路を構成する点（以下、「補間点」又は「ノード」と表記する）の座標や、ノードとリンクからなる道路の接続関係を示す道路ネットワークデータ）を記憶しているほか、デフォルメ処理の途中結果や、デフォルメに関するパラメータなどを格納するメモリである。
表示部２は例えば液晶ディスプレイなどの表示装置であり、表示処理部５の指示の下、デフォルメ地図などを表示する。
【００１１】
大局的レイアウト決定部３はデフォルメ対象の地図を複数の領域に分割して、各分割領域を表示部２の画面領域（地図表示領域）に応じて大局的に変形し、各分割領域の配置位置を大まかに決定する処理を実施する。なお、大局的レイアウト決定部３はレイアウト決定手段を構成している。
ここでは、大局的レイアウト決定部３が各分割領域を表示部２の画面領域に応じて大局的に変形するものについて示したが、地図表示領域が表示部２の画面領域に限るものではなく、例えば、地図を紙に印刷するような場合には、地図表示領域が紙の印刷領域でもよい。
領域内デフォルメ部４は大局的レイアウト決定部３により配置位置が決定された各分割領域内の地図を示す地図データを変更して、各分割領域内の地図の形状を変形するデフォルメ処理を実施する。なお、領域内デフォルメ部４はデフォルメ手段を構成している。
表示処理部５は領域内デフォルメ部４によるデフォルメ処理後の各分割領域を大局的レイアウト決定部３により決定された配置位置に表示する表示指令を表示部２に出力する。
なお、表示処理部５及び表示部２から表示手段が構成されている。
【００１２】
大局的レイアウト決定部３の領域分割部１１はデフォルメ対象の地図を領域の重要性に応じて分割する処理を実施する。
大局的レイアウト決定部３の伸張領域検出部１２はデフォルメ対象の地図と表示部２の画面領域とを比較して、デフォルメ対象の地図を伸張することが可能な伸張領域（デフォルメ対象の地図と表示部２の画面領域が重なっていない空白の領域）を検出する処理を実施する。
大局的レイアウト決定部３の配置位置決定部１３は領域分割部１１により分割された各分割領域を伸張領域検出部１２により検出された伸張領域まで伸ばして、各分割領域を変形することにより、各分割領域の配置位置を決定する処理を実施する。
【００１３】
領域内デフォルメ部４の接続地点設定部２１は領域分割部１１により分割された各分割領域において、相互に隣接している分割領域間を跨いでいる道路の地図データがある場合、その分割領域間の境界と交差する道路上の地点を接続地点として、その地図データ上に接続地点のノードを設定する処理を実施する。
領域内デフォルメ部４のデータ削減部２２は補間点削減部２３と隣接エッジ統合部２４から構成されている。
【００１４】
データ削減部２２の補間点削減部２３は各分割領域内の地図を示す地図データから、道路を構成する補間点の間引き処理を実施する。
データ削減部２２の隣接エッジ統合部２４は補間点削減部２３により間引き処理が実施された地図データを参照して、隣接エッジ（エッジは隣り合う２つノードを結ぶ線分であり、隣接エッジは隣り合う２つエッジを表すものとする）のなす角度を算出し、そのなす角度が閾値以下であれば、その隣接エッジを統合して形状の簡略化を図る。
【００１５】
領域内デフォルメ部４の形状変形部３１は変形条件算出部３２、初期配置部３３、グループ生成部３４、エッジ列形状変形部３５及び削除点挿入部３６から構成されており、接続地点設定部２１により設定された接続地点のノード及びデータ削減部２２により間引かれずに残っているノードのうち、少なくとも１つ以上のノードを移動して、複数の分割領域内の地図の形状を変形する処理を実施する。
形状変形部３１の変形条件算出部３２は大局的レイアウト決定部３の配置位置決定部１３により配置位置が決定された分割領域のうち、表示部２の画面領域の淵に配置位置が決定された分割領域内の地図の形状を変形する際の条件を算出する処理を実施する。
【００１６】
形状変形部３１の初期配置部３３は変形条件算出部３２により算出された条件の下で、接続地点設定部２１により設定された接続地点のノード及びデータ削減部２２により間引かれずに残っているノードのうち、少なくとも１つ以上のノードを移動する処理を実施する。
形状変形部３１のグループ生成部３４は初期配置部３３により移動処理が実施されたのち、複数のノードから構成されるエッジをグループ分けして、複数のグループを生成する処理を実施する。
【００１７】
形状変形部３１のエッジ列形状変形部３５はグループ生成部３４により生成されたグループ毎に、当該グループに属するエッジ列の形状を変形する処理を実施する。
形状変形部３１の削除点挿入部３６はデータ削減部２２により間引かれたノードのうち、最終的なデフォルメ地図に必要なノードがあれば、エッジ列形状変形部３５の変形処理結果であるデフォルメ結果に対して、そのノードを挿入する処理を実施する。
【００１８】
次に動作について説明する。
地図記憶部１は、デフォルメ対象の地図を示す地図データ（例えば、道路を構成する補間点の座標や、ノードとリンクからなる道路の接続関係を示す道路ネットワークデータ）などを記憶している。
ここで、図２は地図データを構成しているノード等を示す説明図である。
図２では、道路を構成する補間点（ノード）や、２つのノードを両端とする線分（エッジ）を表している。
特に、交差点ノードは道路が交差している地点のノードであり、終端ノードはデフォルメ対象の地図内の道路の終端に該当するノードである。
交差点ノードから別の交差点ノード（または、終端ノード）に至るまでの一連のエッジ列をリンクと称している。
【００１９】
また、地図記憶部１に記憶されている道路ネットワークデータは、リンクを構成するノードの情報（座標、ＩＤ等）、リンクを構成するエッジの接続関係、交差点ノードの情報（座標、ＩＤ等）、及び交差点ノードに接続するリンクの情報（ＩＤ等）などを有している。
また、地図記憶部１には、デフォルメ対象領域である外接矩形の左下及び右上の座標が記憶されており、また、形状のデフォルメにおいて最重要視する基準（例えば、エッジ長、エッジ方向等）などがデフォルメに関するパラメータとして記憶されている。
ここで、デフォルメ対象領域とは、デフォルメ対象を内包する領域であり、例えば、県内全域の道路をデフォルメする場合、デフォルメ対象領域は県全体である。また、特定の道路をデフォルメの対象とする場合には、その道路が含まれる領域をデフォルメ対象領域とする。
【００２０】
まず、大局的レイアウト決定部３は、地図記憶部１から地図データを取得すると、デフォルメ対象の地図を複数の領域に分割して、各分割領域を表示部２の画面領域に応じて大局的に変形し、各分割領域の配置位置を大まかに決定する。
以下、大局的レイアウト決定部３の処理内容を具体的に説明する。
【００２１】
大局的レイアウト決定部３の領域分割部１１は、地図記憶部１から地図データとして、デフォルメ対象領域である外接矩形の左下座標及び右上座標を取得すると、デフォルメ対象領域を領域の重要性に応じて分割する。
領域分割方法としては、例えば、デフォルメ対象領域の全体をメッシュ状に分割して、各メッシュ内のデータ密度を算出し、同程度のデータ密度となる付近のメッシュを統合していく方法を用いることができる。
あるいは、地図記憶部１から各領域の重要性を示すパラメータ（特に注目する領域（重要な領域：特定の市町村・特定の道路・特定の領域・特定の地点）と注目しない領域とを区別することが可能な領域分割基準を示すパラメータ）を取得し、そのパラメータを参照して、デフォルメ対象領域を分割する方法を用いることもできる。
なお、領域分割部１１は、各分割領域であるメッシュのＩＤや左下・右上座標を算出し、各分割領域に領域の重要性を対応付けておくようにする。
【００２２】
大局的レイアウト決定部３の伸張領域検出部１２は、地図記憶部１から地図データとして、デフォルメ対象領域である外接矩形の左下座標及び右上座標を取得すると、デフォルメ対象領域と表示部２の画面領域とを比較して、デフォルメ対象領域を伸張することが可能な伸張領域（デフォルメ対象領域と表示部２の画面領域が重なっていない空白の領域）を検出する。
ここで、図３はデフォルメ対象領域を伸張することが可能な伸張領域を示す説明図である。
図３では、表示部２の画面領域がＰＱＲＳであり、デフォルメ対象領域がノードＡＢＣＤを含むＬ字の領域である。
デフォルメ対象領域を伸張することが可能な伸張領域は、図中、斜線の領域である。
【００２３】
大局的レイアウト決定部３の配置位置決定部１３は、領域分割部１１がデフォルメ対象領域を分割し、伸張領域検出部１２が伸張領域を検出すると、領域分割部１１により分割された各分割領域を伸張領域まで伸ばして、各分割領域を変形することにより、各分割領域の配置位置を大まかに決定する。
ここで、図４及び図５は配置位置決定部１３により決定された各分割領域の配置位置の一例を示す説明図である。
図４はデフォルメ対象領域のノードＣからノードＤに至る領域の重要性が極めて低くない場合のレイアウト例であり、図５はノードＣからノードＤに至る領域の重要性が極めて低い場合のレイアウト例である。
【００２４】
図４及び図５では、重要性が高い領域が広くなり、重要性が低い領域が狭くなるように、各分割領域を伸張領域まで伸ばして、各分割領域を変形するようにしている。
このとき、配置位置決定部１３は、図６に示すように、重要性が高い領域と低い領域の接続点を算出し、重要性が高い領域の変形に伴って、その接続点が分断されないように、重要性が低い領域も変形させている。
この変形は、各領域の輪郭を構成する点を伸張領域に向かって移動させていく方法等が用いられる。
なお、伸張領域の終端に達した時点で、その方向への変形を停止する。配置位置決定部１３で変形配置するのは、領域の輪郭のみであり、領域内の道路を構成するノードやエッジの形状を変形させる処理は、後述する領域内デフォルメ部４の処理である。
表示処理部５は、配置位置決定部１３により変形される前の各分割領域の配置位置と、配置位置決定部１３により変形された後の各分割領域の配置位置とを表示部２の画面領域に表示する。
【００２５】
領域内デフォルメ部４は、上記のようにして、大局的レイアウト決定部３が各分割領域の配置位置を決定すると、各分割領域内の道路の形状を変形するデフォルメ処理を実施する。
以下、領域内デフォルメ部４の処理内容を具体的に説明する。なお、領域内デフォルメ部４は、重要性の高い分割領域から順番に、当該分割領域内の道路の形状を変形するデフォルメ処理を実施する。
【００２６】
領域内デフォルメ部４の接続地点設定部２１は、領域分割部１１により分割された各分割領域において、相互に隣接している分割領域間を跨いでいる道路の地図データがある場合、その分割領域間の境界と交差する道路上の地点を接続地点として、その地図データ上に接続地点のノードを設定する。
ここで、図９は領域分割部１１によりデフォルメ対象領域が３つの分割領域Ａ，Ｂ，Ｃに分割され、接続地点設定部２１により接続地点のノードｐ１〜ｐ５が設定されている例を示す説明図である。
また、図１０は配置位置決定部１３により決定された分割領域Ａ，Ｂ，Ｃの配置位置を示す説明図である。
【００２７】
領域内デフォルメ部４のデータ削減部２２は、接続地点設定部２１が接続地点のノードｐ１〜ｐ５を設定すると、ノードの削減やエッジの統合を行うことによって、後述する形状変形部３１における変形対象のノードの個数を削減するようにしている。
即ち、データ削減部２２の補間点削減部２３は、道路の形状の特徴を失わない範囲で道路を構成するノードの間引き処理を実施し、ノードの間引き結果（ノード・リンクの情報）を隣接エッジ統合部２４及び削除点挿入部２６に出力する。なお、削除点挿入部２６には間引いたノードの情報（ＩＤ、座標））も出力する。
ノードの間引き方法としては、一般的に知られている再帰的にエッジ列を近似する方法を用いることができる。
【００２８】
データ削減部２２の隣接エッジ統合部２４は、補間点削減部２３からノードの間引き結果を受けると、隣接エッジのなす角度θを算出し、そのなす角度θが所定の閾値（例えば、４５度）以下であれば、その隣接エッジを統合して、形状の簡略化を図るようにする。
ここで、図７は補間点削減部２３によりノードの間引き処理が実施された道路を構成するエッジを示す説明図である。
図７では、道路がノードＡ〜Ｆから構成されており、ノードＡ〜Ｆがエッジ（１）〜（５）を構成している。
【００２９】
例えば、隣接エッジであるエッジ（１）とエッジ（２）に着目すると、エッジ（１）とエッジ（２）のなす角度θを算出する。
図７の例では、エッジ（１）とエッジ（２）のなす角度θが閾値（例えば、４５度）以下であるため、エッジ（１）とエッジ（２）を統合するようにしている。即ち、エッジ（１）とエッジ（２）の途中にあるノードＥを削除して、エッジ（１）とエッジ（２）を一つのエッジとするようにする。
同様にして、他の隣接エッジにも着目して、ノードＢ、ノードＣ、ノードＤを削除することにより、エッジ（１）（２）（３）（４）（５）を統合すると、図８に示すように、道路がノードＡとノードＦからなるリンクになる。
なお、隣接エッジ統合部２４がエッジを統合する際、閾値を適宜変更することにより、エッジの簡略化度合を変えることができる。したがって、複雑な形状の道路は詳細形状を維持し、簡素な形状の道路は簡素化したエッジとすることが可能になる。
【００３０】
領域内デフォルメ部４の形状変形部３１は、接続地点設定部２１により設定された接続地点のノード及びデータ削減部２２により間引かれずに残っているノードのうち、少なくとも１つ以上のノードを移動して、複数の分割領域内の道路の形状を変形する。
即ち、形状変形部３１の変形条件算出部３２は、大局的レイアウト決定部３の配置位置決定部１３により配置位置が決定された分割領域のうち、表示部２の画面領域の淵に配置位置が決定された分割領域内の道路の形状を変形する際の条件を算出する。
ここで、道路の形状を変形する際の条件とは、分割領域内の道路を構成するノードやエッジの移動後の座標算出において、座標値の制限や、移動方向等を定める条件である。
【００３１】
以下、変形条件算出部３２の処理内容を具体的に説明する。
例えば、配置位置決定部１３により図９の分割領域Ａ，Ｂ，Ｃが、図１０に示すような位置に配置された場合、変形条件算出部３２では、表示部２の画面領域の淵に配置位置された分割領域が、分割領域Ａ，Ｃであると特定する。
変形条件算出部３２は、分割領域Ａ，Ｃのそれぞれについて、配置位置決定部１３により配置位置が決定される前の状態（図９の状態）と、配置位置決定部１３により配置位置が決定された後の状態（図１０の状態）とを比較して、配置位置決定部１３によるレイアウト内容を調査する。
【００３２】
ここで、レイアウト内容の調査は、拡大縮小のみによるレイアウトであるのか、あるいは、表示部２の画面領域の淵に沿って輪郭形状が変形されて配置されたことによるレイアウトであるのかを調査する。
分割領域Ａの場合、レイアウトの前後で、４頂点からなる矩形であることに変わりがないため、拡大縮小によるレイアウトであるとみなされる。
一方、分割領域Ｃの場合、レイアウト前が六角形であるのに対して、レイアウト後では八角形となっているため、画面領域の淵に沿った輪郭形状の変形を伴うレイアウトであるとみなされる。
【００３３】
変形条件算出部３２は、配置位置決定部１３によるレイアウト内容を調査すると、そのレイアウト内容に基づいて、分割領域Ａ，Ｃ内の道路の形状を変形する際の条件を以下のように定める。
（１）分割領域Ａ
分割領域Ａ内の道路を構成するノード及びエッジの移動範囲を図１１の矩形ａ１ａ２ａ３ａ４内に制限する（矩形ａ１ａ２ａ３ａ４以外の領域には、分割領域Ａ内の道路を構成するノードやエッジを移動させない条件を定める）。
（２）分割領域Ｃ
分割領域Ｃ内の道路を構成するノード及びエッジの移動範囲を図１２の多角形ｃ１ｃ２ｃ３ｓ１ｃ４ｃ５ｓ２ｃ６内に制限するとともに、表示部２の画面領域の淵に沿って輪郭形状を変形させる部分についての変形方向の条件を定める。
輪郭形状を変形させる部分についての変形方向の条件は、図９の線分１−２よりも下側の領域を図１２の斜線部分に変形配置するために、図９に示す道路ｒ１、道路ｒ２を画面領域の下部ＱＲに沿って水平方向に変形させる条件である。
条件の具体例としては、道路ｒ１や道路ｒ２を構成するノードの移動方向をＸ軸方向に限定する条件などが該当である。
【００３４】
初期配置部３３は、変形条件算出部３２により算出された条件の下で、接続地点設定部２１により設定された接続地点のノード及びデータ削減部２２により間引かれずに残っているノードのうち、少なくとも１つ以上のノードを移動する処理を実施する。
以下、初期配置部３３の処理内容を具体的に説明する。ただし、処理内容の具体例は後述する。
【００３５】
初期配置部３３は、ノードの移動処理を実施するに際して、現在の処理対象の分割領域に隣接している分割領域に対して、領域内デフォルメ部４が、既にノードやエッジの変形配置を実行している場合には、移動後の接続地点におけるノードの座標を取得し、そのノードの座標を現在の処理対象の分割領域の接続地点におけるノードの初期座標とする。
一方、隣接している分割領域に対して、領域内デフォルメ部４が、未だノードやエッジの変形配置を実行していない場合には、接続地点におけるノードの初期座標を地図データ記憶部１に記憶されている地図データから得られる座標値とする。
【００３６】
接続地点以外のノードの初期座標については、例えば、データ削減部２２により間引かれずに残っているノードの中からノードを一つ選択し、最重要視する基準（例えば、エッジ長、エッジ方向）と大局的なレイアウトから定まる条件に基づいて移動後のノード座標を算出する。
ノードの選択方法は任意でよく、例えば、接続地点のノードを除いて、データ削減部２２により間引かれずに残っているノードの中からランダムに選ぶ方法を用いてもよい。また、理想的なエッジ長やエッジ方向とするために、移動量が小さいノードから順番に選ぶ方法でもよい。また、複数のノードを同時に選んで移動させるようにしてもよい。
【００３７】
移動後のノードの座標を算出すると、元の道路の接続関係が維持されているか否かを判定し、元の道路の接続関係が維持されている場合には、そのノードに対して座標値を更新する。道路の接続関係が維持されているか否かを判定する判断基準としては、例えば、以下の判断基準を使用する。
［判断基準］
（１）簡略化前の地図データ（市販の道路地図のデータ）に存在する交差点が消失しないこと
（２）簡略化前の地図データに存在しない道路の交差を発生させないこと
（３）交差点に接続するエッジの接続順序が、簡略化前と簡略化後で変わらないこと（例えば、簡略化前の地図データにおいて、交差点に接続するエッジが交差点の周囲に反時計回りにｅ１、ｅ２、ｅ３の順序で並んでいる場合、簡略化後もｅ１、ｅ２、ｅ３の順序となること）
【００３８】
以下、初期配置部３３の処理内容の具体例を説明する。
ここでは、最終的にエッジ方向が水平、垂直又は斜め４５度方向の８方向に量子化されているデフォルメ結果が得られるように、初期配置部３３がノードの移動処理を実施する例を説明する。
【００３９】
初期配置部３３は、変形条件算出部３２から分割領域内の道路の形状を変形する際の条件を受け取り、隣接エッジ統合部２４から隣接エッジ統合結果を受け取ると、その条件に基づいて、隣接統合処理で削除されずに残っているノードの座標を変換し、そのノードを配置位置決定部１３により配置位置が決定された分割領域内に移動させる。
図１３は移動後のノードからなる道路を示す説明図である。
図において、点Ｐは交差点ノードであり、ノードＰＱ間、ノードＰＲ間、ノードＰＳ間のエッジ列はリンクである。また、ノードＱ，Ｒ，Ｓは非接続地点のノードである。
【００４０】
次に、初期配置部３３は、エッジ長やエッジ方向を基準にして、移動後のノードや、当該ノードから構成されるエッジの変形処理を実施する。
即ち、初期配置部３３は、形状のデフォルメにおいて最重要視する基準としてエッジ方向を量子化するものとし、エッジ方向の中でも、特に水平方向及び垂直方向の２方向への量子化を行うものとする。
具体的には、図１３のエッジ列に対して、水平方向、あるいは、垂直方向とのなす角度が閾値以下であるエッジを抽出し、そのエッジ方向が水平方向又は垂直方向になるように、そのエッジのノードの移動後の座標を算出する。
移動後のノードの座標を算出すると、元の道路の接続関係が維持されているか否かを判定し、元の道路の接続関係が維持されている場合には、そのノードに対して座標値を更新する。道路の接続関係が維持されているか否かを判定する判断基準としては、上述した判断基準を使用する。
図１４は水平方向及び垂直方向の２方向への量子化が行われてノードが移動された道路を示す説明図である。
【００４１】
形状変形部３１のグループ生成部３４は、初期配置部３３がノードの移動処理を実施すると、複数のノードから構成されるエッジをグループ分けして、複数のグループを生成する。
複数のエッジをグループ分けする基準としては、エッジ長やエッジ方向を用いることができる。
図１５は初期配置部３３によるノードの移動処理結果（図１４を参照）に対して、斜め方向のエッジを基準としてグループを生成した例を示す説明図である。
図１５の例では、エッジ方向が斜め方向のエッジに着目して、その斜め方向のエッジに連なっている水平方向又は垂直方向のエッジを１つのグループにまとめており、グループ（１）〜グループ（４）が生成されている。
なお、グループ生成部３４は、グループＩＤ、グループを構成するエッジのＩＤ、当該エッジの両端のノードの座標、エッジの接続関係などをグループに関する情報としてエッジ列形状変形部３５に出力する。
【００４２】
形状変形部３１のエッジ列形状変形部３５は、グループ生成部３４が複数のグループを生成すると、グループ毎に、当該グループに属するエッジ列の形状を変形する処理を実施する。
即ち、エッジ列形状変形部３５は、グループ生成部３４からグループに関する情報を受けると、まだ移動させていないノードを動かすことを基本として、ノードやエッジの変形配置を行う。グループを用いた変形配置処理は、下記の（Ａ）（Ｂ）である。
（Ａ）複数のエッジ列をまとめた座標変換
（Ｂ）グループ内の一部分のエッジ列に対して、その特性を用いてエッジ列の形状を変形し、簡略化度合を変える
【００４３】
以下、エッジ列形状変形部３５の処理内容を具体的に説明する。
最初に、図１６〜図１８を用いて、変形配置処理（Ａ）を説明する。
まず、グループの一つとして、グループ（１）に関する情報を取得し、その情報を参照して、グループ（１）に属するノードの中から、非交差点ノードであり、かつ、初期配置部３３で移動させていないノードを特定する。ここでは、説明の便宜上、ノードｎ１を特定したものとする。
次に、ノードｎ１とノードＰを両端とするエッジのエッジ方向が、斜め４５度方向となるように、ノードｎ１の移動後の座標を算出する。ただし、初期配置部３３と同様に、道路の接続関係が崩れない範囲で移動後の座標を算出するものとする。
図１６のノードｎ１’は、ノードｎ１が移動されたノードである。
【００４４】
続いて、グループを構成するエッジ列のうち、残りのエッジ列（図１６の場合、エッジｎ１’ｎ２、エッジｎ２ｎ３、エッジｎ３ｎ４、エッジｎ４ｎ５、エッジｎ５ｎ６、エッジｎ６Ｑ）全体の座標変換を実施して、これらのエッジ列が移動後のノード位置ｎ１’に接続されるようにする。
このようにして、ノードｎ１’の移動後の座標に基づいて、残りのエッジ列（ここでは、水平方向及び垂直方向からなるエッジ列）の座標変換を実施する。
図１７はグループ（１）内のエッジのデフォルメ結果を示す説明図である。
【００４５】
斜め方向のエッジを除いた残りのエッジ列全体の座標変換を行う際にも、元の地図にない道路の交差が発生することがないように、道路の接続関係が維持されるか否かの判定を実施し、道路のトポロジーが崩れないようにグループ内のノード座標を再算出する。
以上が、グループ（１）に関する変形配置処理（Ａ）である。
グループ（２）、グループ（３）、グループ（４）についても同様に、斜め方向のエッジの移動後のノードの座標に基づいてグループ内の他のエッジ列を座標変換する。
図１８はエッジ列形状変形部３５によるデフォルメ結果を示す説明図である。
【００４６】
次に、図１９〜図２０を用いて、変形配置処理（Ｂ）を説明する。
ここでは、グループ生成部３４のグループ生成結果が図１９であるものとする。
まず、エッジ列形状変形部３５は、グループ生成部３４からグループに関する情報を取得して、グループ内のエッジの特性を認識し、その特性を利用して各グループ内のエッジの形状に対する簡略化度合を設定する。
図２０はグループ（１）とグループ（２）におけるエッジの形状に対する簡略化度合が異なる例を示す説明図である。
【００４７】
図２０では、図１９と比べて、グループ（１）が、エッジの形状に対する簡略化度合が高い設定（詳細形状を保つ状態に設定）になされており、グループ（１）では、エッジ列が水平方向又は垂直方向のエッジ列であるという特性があるため、一つのエッジａｂの部分が、水平方向と垂直方向からなる３つのエッジ（エッジａｐ、エッジｐｑ、エッジｑｂ’）として作成されている。
図２０では、図１９と比べて、グループ（２）が、エッジの形状に対する簡略化度合が低い設定（形状を簡略化する状態に設定）になされており、エッジｃｄ、エッジｄｅ、エッジｅｆ、エッジｆｇの部分が簡素化されて、エッジｃｓとされている。
このようにして、エッジの特性を利用して、一つのエッジを複数のエッジからなる詳細な形状に変形させたり、エッジの一部を除去してエッジ列を簡素化させたりすることができる。
【００４８】
形状変形部３１の削除点挿入部３６は、データ削減部２２により間引かれたノードのうち、最終的なデフォルメ地図に必要なノードがあれば、エッジ列形状変形部３５の変形処理結果であるデフォルメ結果に対して、そのノードを挿入する処理を実施する。
図２１から図２３はノードの挿入例を示す説明図であり、特に図２１は隣接エッジ統合部２４により隣接エッジが統合される前の状態を示しており、エッジｎ３ｎ４の長さがｄ１、エッジｎ４ｎ５の長さがｄ２である。
また、図２２は隣接エッジ統合部２４やエッジ列形状変形部３５において、エッジの統合やエッジ方向の量子化が行われた結果を示しており、ノードｎ４が間引かれている。
このとき、削除点挿入部３６は、図２２の状態に対して、エッジｎ３’ｎ５’間をｄ１：ｄ２の比率で分割した位置を算出し、図２３に示すように、その分割した位置に間引かれたノードｎ４をノードｎ４’として挿入配置する。
【００４９】
表示処理部５は、領域内デフォルメ部４によるデフォルメ処理が完了すると、デフォルメ処理後の各分割領域を大局的レイアウト決定部３により決定された配置位置に表示する表示指令を表示部２に出力する。
これにより、表示部２は、デフォルメ処理後の各分割領域を大局的レイアウト決定部３により決定された配置位置に表示する。
【００５０】
以上で明らかなように、この実施の形態１によれば、デフォルメ対象の地図を複数の領域に分割して、各分割領域を表示部２の画面領域に応じて大局的に変形し、各分割領域の配置位置を大まかに決定する大局的レイアウト決定部３を設け、領域内デフォルメ部４が大局的レイアウト決定部３により配置位置が決定された各分割領域内の地図を示す地図データを変更して、各分割領域内の地図の形状を変形するように構成したので、ユーザが意図する内容に近いデフォルメ地図を表示することができる効果を奏する。
即ち、大局的なレイアウト（デフォルメ対象領域中のどの領域が画面領域のどの辺りに配置されるか）と、局所的な変形（各分割領域内で道路の形状をどのように簡略化・変形させるか）の双方をフレキシブルに行うことが可能であるため、ユーザの意図する内容に近いデフォルメ結果を得ることができる。特に、局所的な変形を行う前に大局的なレイアウトを決めることができるので、道路を構成する個々のエッジを変形させた結果、思うような範囲にデフォルメされないという状況を回避することができる。
【００５１】
また、大局的なレイアウト位置を変えたり、分割領域内の局所的なデフォルメにおいて、グループ内のエッジの簡略化度合を変えたりすることで、様々なバリエーションのデフォルメ結果を容易に生成することができる。いくつかの生成結果の中からユーザが意図する内容に近いものを選択することも可能となる。
また、デフォルメ結果を出力する画面領域を考慮して、大局的なレイアウトを決定するため、デフォルメ結果を画面に表示したり、紙面に印刷したりする際に、無駄な部分を残さずに済み、画面領域を有効に活用したデフォルメ地図を生成することができる。
【００５２】
さらに、局所的なデフォルメにおいて個々のエッジを変形させる際、最重要視する基準に基づいて初期配置を行った後に、未移動のノードについて移動後の座標を算出するという２段階の処理に分けることにより、最も重要視する基準に対する視認性を向上させたデフォルメ結果を得ることが可能となる。
また、初期配置後の結果に対して複数のエッジをグルーピングし、グループを用いて変形配置を行うことにより、道路が複雑に交差している場合であっても、エッジの変形配置を容易に行うことができる。
【００５３】
実施の形態２．
上記実施の形態１では、初期配置部３３が、形状のデフォルメにおいて最重要視する基準がエッジ方向であり、エッジ方向の量子化（最終的に量子化する８方向の中でも、特に、水平・垂直の２方向への方向量子化）を実施して初期配置を定めるものについて示したが、最重要視する基準は、エッジ方向に限るものではなく、例えば、エッジの長さ（理想的な長さや、元地図と同じ長さ）や、付近のノードとの距離であってもよい。
例えば、最重要視する基準がエッジの長さであれば、エッジの長さの量子化を実施して初期配置を定めるようにする。
【００５４】
実施の形態３．
上記実施の形態１では、グループ生成部３４がグループを生成する際、斜め方向のエッジに着目し、斜め方向のエッジに連なっている水平方向又は垂直方向のエッジを１つのグループにまとめて、グループを生成するものについて示したが、斜め方向のエッジを基準とするものに限るものではなく、例えば、エッジの長さを基準とするようにしてもよい。
例えば、エッジの長さを基準とする場合、エッジの長さが同程度のエッジ同士を一つのグループにまとめるようにする。
また、交差点ノードに連なっている一定個数のエッジを同じグループにまとめるようにしてもよい。
【００５５】
実施の形態４．
上記実施の形態１では、領域分割部１１がデフォルメ対象領域を分割する際、データ密度や領域の重要性などによって自動的に分割するものについて示したが、デフォルメ対象領域を表示部２に表示し、ユーザがマウス等のデバイスを用いて、分割後の領域を画面上で指定するようにしてもよい。
【００５６】
実施の形態５．
上記実施の形態１では、エッジ列形状変形部３５がエッジを８方向の方向量子化を実施するものについて示したが、方向量子化における方向は8方向に限るものではなく、例えば、４方向の方向量子化でも、１６方向の方向量子化でもよい。
【００５７】
実施の形態６．
上記実施の形態１では、デフォルメ対象の地図を示す地図データが、道路を構成する補間点の座標や、道路の接続関係を示す道路ネットワークデータであり、道路の形状を変形するものについて示したが、道路の形状を変形するものに限るものではない。
例えば、デフォルメ対象の地図を示す地図データが、上下水道を構成する補間点の座標や、上下水道の接続関係を示す上下水道ネットワークデータであれば、上下水道の形状を変形して、上下水道のデフォルメ地図を生成することができる。
【００５８】
実施の形態７．
上記実施の形態１では、補間点削減部２３が、隣接エッジ統合部２４でエッジ形状を簡略化する際の対象ノード数を削減しているものについて示したが、地図記憶部１に記憶されている元の道路の地図データが少ない補間点から構成されている場合には、補間点削減部２３を省略するようにしてもよい。
【００５９】
実施の形態８．
上記実施の形態１では、表示部２の画面領域を考慮して、重要な領域を画面領域内のどの辺りに表示させるかを決めることができるものについて示したが、表示部２の画面領域を特に考慮しない場合には、大局的レイアウト決定部３を省略するようにしてもよい。
この場合、図１において、大局的レイアウト決定部３と、領域内デフォルメ部４の接続地点設定部２１が除かれた構成になる。
【００６０】
実施の形態９．
上記実施の形態１では、デフォルメ対象とする道路を特に限定しないものについて示したが、特定の道路のみをデフォルメ対象に限定するようにしてもよい。
ここで、図２４はカーナビゲーションの全ルートの表示例を示す説明図である。図２４では、出発地から目的地までのルートが３ルートある例を示している。
この状態に対して、大局的レイアウト決定部３では、ルート（１）、ルート（２）、ルート（３）が分離するように領域を分割し、３つの分割領域を図２５に示すような位置関係にレイアウトしている。
【００６１】
ここで、矩形ＰＱＲＳは、表示部２の画面領域の４隅であり、領域内デフォルメ部４では、このレイアウト結果に対して、ルート（１）、ルート（２）、ルート（３）を構成するノードやエッジのデフォルメ処理を行う。このデフォルメ処理は、上記実施の形態１で説明した処理と同じ処理である。
【図面の簡単な説明】
【００６２】
【図１】この発明の実施の形態１によるデフォルメ地図生成装置を示す構成図である。
【図２】地図データを構成しているノード等を示す説明図である。
【図３】デフォルメ対象領域を伸張することが可能な伸張領域を示す説明図である。
【図４】配置位置決定部１３により決定された各分割領域の配置位置の一例を示す説明図である。
【図５】配置位置決定部１３により決定された各分割領域の配置位置の一例を示す説明図である。
【図６】各分割領域の移動変形を示す説明図である。
【図７】補間点削減部２３によりノードの間引き処理が実施された道路を構成するエッジを示す説明図である。
【図８】エッジ統合後の道路を示す説明図である。
【図９】領域分割部１１によりデフォルメ対象領域が３つの分割領域Ａ，Ｂ，Ｃに分割され、接続地点設定部２１により接続地点のノードｐ１〜ｐ５が設定されている例を示す説明図である。
【図１０】配置位置決定部１３により決定された分割領域Ａ，Ｂ，Ｃの配置位置を示す説明図である。
【図１１】分割領域Ａ内の道路を構成するノード及びエッジの移動範囲を示す説明図である。
【図１２】分割領域Ｃ内の道路を構成するノード及びエッジの移動範囲を示す説明図である。
【図１３】移動後のノードからなる道路を示す説明図である。
【図１４】水平方向及び垂直方向の２方向への量子化が行われてノードが移動された道路を示す説明図である。
【図１５】初期配置部３３によるノードの移動処理結果（図１４を参照）に対して、斜め方向のエッジを基準としてグループを生成した例を示す説明図である。
【図１６】エッジ列形状変形部３５によるノードの移動を示す説明図である。
【図１７】グループ（１）内のエッジのデフォルメ結果を示す説明図である。
【図１８】エッジ列形状変形部３５によるデフォルメ結果を示す説明図である。
【図１９】グループ生成部３４によるグループ生成例を示す説明図である。
【図２０】グループ（１）とグループ（２）におけるエッジの形状に対する簡略化度合が異なる例を示す説明図である。
【図２１】隣接エッジ統合部２４により隣接エッジが統合される前の状態を示す説明図である。
【図２２】隣接エッジ統合部２４やエッジ列形状変形部３５において、エッジの統合やエッジ方向の量子化が行われた結果を示す説明図である。
【図２３】削除点挿入部３６によりノードが挿入された結果を示す説明図である。
【図２４】カーナビゲーションの全ルートの表示例を示す説明図である。
【図２５】大局的レイアウト決定部３のレイアウト結果を示す説明図である。
【図２６】デフォルメ対象領域を示す説明図である。
【図２７】デフォルメ後の対象領域を示す説明図である。
【符号の説明】
【００６３】
１  地図記憶部、２  表示部（表示手段）、３  大局的レイアウト決定部（レイアウト決定手段）、４  領域内デフォルメ部（デフォルメ手段）、５  表示処理部（表示手段）、１１  領域分割部、１２  伸張領域検出部、１３  配置位置決定部、２１  接続地点設定部、２２  データ削減部、２３  補間点削減部、２４  隣接エッジ統合部、３１  形状変形部、３２  変形条件算出部、３３  初期配置部、３４  グループ生成部、３５  エッジ列形状変形部、３６  削除点挿入部。
【図１】
0005478008.tif 000002
【図２】
0005478008.tif 000003
【図３】
0005478008.tif 000004
【図４】
0005478008.tif 000005
【図５】
0005478008.tif 000006
【図６】
0005478008.tif 000007
【図７】
0005478008.tif 000008
【図８】
0005478008.tif 000009
【図９】
0005478008.tif 000010
【図１０】
0005478008.tif 000011
【図１１】
0005478008.tif 000012
【図１２】
0005478008.tif 000013
【図１３】
0005478008.tif 000014
【図１４】
0005478008.tif 000015
【図１５】
0005478008.tif 000016
【図１６】
0005478008.tif 000017
【図１７】
0005478008.tif 000018
【図１８】
0005478008.tif 000019
【図１９】
0005478008.tif 000020
【図２０】
0005478008.tif 000021
【図２１】
0005478008.tif 000022
【図２２】
0005478008.tif 000023
【図２３】
0005478008.tif 000024
【図２４】
0005478008.tif 000025
【図２５】
0005478008.tif 000026
【図２６】
0005478008.tif 000027
【図２７】
0005478008.tif 000028