(57)【要約】【課題】  地図データにおいて、詳細形状を表す詳細ポリゴンをデフォルメして、広域図用の概略形状を表す概略ポリゴンを効率的に生成する。【解決手段】  概略ポリゴンを生成すべき対象について、詳細ポリゴンのデータを地図ＤＢから読み出す。ポリゴン形状を規定する点列間に、ボロノイ分割用の母点を配置した上で、ボロノイ多角形を生成する。ボロノイ多角形の頂点の中から、ポリゴンを線分に縮退させる処理に用いるべき頂点として、頂点から母点までの距離が、ポリゴンの半幅以下など予め設定された所定値以下という条件を満たす頂点を抽出する。こうして抽出された頂点を結んで線分を得ることにより、ポリゴン形状の一部を線分化することができ、広域図用の地図データとしての概略ポリゴンを得ることができる。【選択図】  図３
2007121668.tif 000002
【特許請求の範囲】
【請求項１】
拡大図用に用意され地形の詳細形状を表示可能な詳細ポリゴンから、広域図用に概略形状を表示するための概略ポリゴンを生成する地図データ生成装置であって、
前記詳細ポリゴンを入力するデータ入力部と、
前記詳細ポリゴンを構成する構成点、および前記詳細ポリゴンの辺上に所定の条件で生成される生成点から、ボロノイ分割の母点を設定する母点設定部と、
前記母点に基づき、前記詳細ポリゴンをボロノイ分割するボロノイ分割部と、
前記ボロノイ分割によって得られた頂点から母点までの距離に基づいて、前記詳細ポリゴンの構成点のうち次に行う変形処理の対象となるべき構成点を選択する構成点選択部と、
前記選択された構成点の少なくとも一部を削除して前記詳細ポリゴンを変形させる変形処理を実行し、前記概略ポリゴンを生成する変形処理部とを有する地図データ生成装置。
【請求項２】
請求項１記載の地図データ生成装置であって、
前記変形処理部は、該頂点から母点までの距離に基づいて前記頂点の一部を選択し、前記詳細ポリゴンの少なくとも一部を、前記選択された頂点に基づいて定義される折れ線で表現する縮退処理を実行する地図データ生成装置。
【請求項３】
請求項２記載の地図データ生成装置であって、
前記変形処理部は、更に、所定長さ以下の折れ線を形成することとなる頂点を除外して前記縮退処理を実行する地図データ生成装置。
【請求項４】
請求項１記載の地図データ生成装置であって、
前記変形処理部は、前記選択された構成点のうち一部を削除した残りの構成点を用いて、前記詳細ポリゴンの少なくとも一部を、折れ線で表現する線分化処理を実行する地図データ生成装置。
【請求項５】
請求項１〜４いずれか記載の地図データ生成装置であって、
前記構成点選択部は、前記距離が、前記詳細ポリゴンの幅の半分以下となる頂点を選択する地図データ生成装置。
【請求項６】
拡大図用に用意され地形の詳細形状を表示可能な詳細ポリゴンから、広域図用に概略形状を表示するための概略ポリゴンを生成する地図データ生成装置であって、
前記詳細ポリゴンを入力するデータ入力部と、
前記詳細ポリゴンを表示する表示部と、
前記表示上で後に行うボロノイ分割の対象となるべき領域の指定を受け付ける領域指定受付部と、
前記指定された領域について、詳細ポリゴンの辺上に、所定の条件でボロノイ分割の母点を生成する母点設定部と、
前記母点に基づき、前記詳細ポリゴンをボロノイ分割するボロノイ分割部と、
前記詳細ポリゴンの少なくとも一部を、前記頂点に基づいて定義される折れ線で表現する縮退処理を実行し、前記概略ポリゴンを生成する縮退処理部とを有する地図データ生成装置。
【請求項７】
請求項６記載の地図データ生成装置であって、
前記表示部は、更に、前記ボロノイ分割がなされた後、該ボロノイ分割の結果を前記詳細ポリゴンに重ねて表示可能であり、
前記表示上で、前記変形処理の対象となるべき頂点の指定を受け付ける頂点指定受付部を有し、
前記変形処理部は、前記指定された頂点を対象として前記変形処理を実行する地図データ生成装置。
【請求項８】
拡大図用に用意され地形の詳細形状を表示可能な詳細ポリゴンから、広域図用に概略形状を表示するための概略ポリゴンを生成する地図データ生成方法であって、
コンピュータが実行する工程として、
前記詳細ポリゴンを入力するデータ入力工程と、
前記詳細ポリゴンを構成する構成点、および前記詳細ポリゴンの辺上に所定の条件で生成される生成点から、ボロノイ分割の母点を設定する母点設定工程と、
前記母点に基づき、前記詳細ポリゴンをボロノイ分割するボロノイ分割工程と、
前記ボロノイ分割によって得られた頂点から母点までの距離に基づいて、前記詳細ポリゴンの構成点のうち次に行う変形処理の対象となるべき構成点を選択する構成点選択工程と、
前記選択された構成点の少なくとも一部を削除して前記詳細ポリゴンを変形させる変形処理を実行し、前記概略ポリゴンを生成する変形処理工程とを有する地図データ生成方法。
【請求項９】
拡大図用に用意され地形の詳細形状を表示可能な詳細ポリゴンから、広域図用に概略形状を表示するための概略ポリゴンを生成する地図データ生成方法であって、
コンピュータが実行する工程として、
前記詳細ポリゴンを入力するデータ入力工程と、
前記詳細ポリゴンを表示する表示工程と、
前記表示上で後に行うボロノイ分割の対象となるべき領域の指定を受け付ける領域指定受付工程と、
前記指定された領域について、詳細ポリゴンの辺上に、所定の条件でボロノイ分割の母点を生成する母点生成工程と、
前記母点に基づき、前記詳細ポリゴンをボロノイ分割するボロノイ分割工程と、
前記詳細ポリゴンの少なくとも一部を、前記頂点に基づいて定義される折れ線で表現する縮退処理を実行し、前記概略ポリゴンを生成する縮退処理工程とを有する地図データ生成方法。
【請求項１０】
拡大図用に用意され地形の詳細形状を表示可能な詳細ポリゴンから、広域図用に概略形状を表示するための概略ポリゴンを生成するためのコンピュータプログラムであって、
前記詳細ポリゴンを入力するデータ入力サブプログラムと、
前記詳細ポリゴンを構成する構成点、および前記詳細ポリゴンの辺上に所定の条件で生成される生成点から、ボロノイ分割の母点を設定する母点設定サブプログラムと、
前記母点に基づき、前記詳細ポリゴンをボロノイ分割するボロノイ分割サブプログラムと、
前記ボロノイ分割によって得られた頂点から母点までの距離に基づいて、前記詳細ポリゴンの構成点のうち次に行う変形処理の対象となるべき構成点を選択する構成点選択サブプログラムと、
前記選択された構成点の少なくとも一部を削除して前記詳細ポリゴンを変形させる変形処理を実行し、前記概略ポリゴンを生成する変形処理サブプログラムとを有するコンピュータプログラム。
【請求項１１】
拡大図用に用意され地形の詳細形状を表示可能な詳細ポリゴンから、広域図用に概略形状を表示するための概略ポリゴンを生成するコンピュータプログラムであって、
前記詳細ポリゴンを入力するデータ入力サブプログラムと、
前記詳細ポリゴンを表示する表示サブプログラムと、
前記表示上で後に行うボロノイ分割の対象となるべき領域の指定を受け付ける領域指定受付サブプログラムと、
前記指定された領域について、詳細ポリゴンの辺上に、所定の条件でボロノイ分割の母点を生成する母点生成サブプログラムと、
前記母点に基づき、前記詳細ポリゴンをボロノイ分割するボロノイ分割サブプログラムと、
前記詳細ポリゴンの少なくとも一部を、前記頂点に基づいて定義される折れ線で表現する縮退処理を実行し、前記概略ポリゴンを生成する縮退処理サブプログラムとを有するコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子地図データにおいて地形を表すための地形ポリゴンの生成方法に関し、詳しくは、詳細形状を表す地形ポリゴンを修正して、概略形状を表す地形ポリゴンを生成する方法に関する。
【背景技術】
【０００２】
電子地図データは、種々の縮尺で地図を表示可能である。電子地図データには、陸地、河川などの地形、道路や建築物などの地物を表示可能なポリゴンが格納されている。これらのポリゴンは、縮尺のレベルに応じて階層的に用意されるのが通常である。即ち、縮尺が大きい拡大図を表示するためのデータとして、地形や地物の形状を比較的詳細に表した下位レベルのポリゴンが用意され、縮尺が小さい広域図を表示するためのデータとして、地形や地物の概略形状を表した上位レベルのポリゴンが用意されている。両者の間に中間的な階層のポリゴンが用意されていることもある。このようにレベルの異なる多階層のポリゴンを用意しておくことにより、地図表示に要する時間が長くなることを抑えつつ、それぞれの縮尺に応じた精度で地図を表示することができる。
【０００３】
従来、多階層の地図データは、オペレータの手作業によって作成されていた。まず、航空写真や測量結果等に基づいて詳細表示用、即ち下位レベルのポリゴンが生成される。そして、このポリゴンを、縮尺に応じてオペレータが簡略化して、上位レベルのポリゴンを生成していた。この作業は、非常に煩雑であり、オペレータの処理負荷は多大であった。
【０００４】
【特許文献１】特開２００３−１３２３５３号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来、オペレータの負荷を軽減するために、地図データの生成処理を自動化する提案がなされている。例えば、特許文献１では、道路を表すポリゴンに基づいて、ボロノイ分割を用いて当該道路の中心線を表すデータを生成する技術が開示されている。ボロノイ分割とは、計算幾何学の分野で周知の処理であり、与えられた複数の母点の勢力範囲を表す図である。ある母点を含むボロノイ多角形内であればいずれの点においても、当該母点への距離が他の母点への距離よりも短くなる。
【０００６】
ボロノイ分割は、ポリゴンを線分化するのに利用可能な処理ではあるが、これを河川などの水系に適用しても所望の概略形状は得られない。道路と異なりこれらの水系は幅が一定ではないため、ボロノイ分解の結果は非常に複雑となるからである。また、水系の場合には、例えば、池の中央付近など、概略形状だからといって必ずしも線分化すべきではない部分もある。特許文献１記載の技術では、このような領域についても画一的に線分化されてしまうおそれがあった。
【０００７】
上述の課題は、水系に限らず、陸地を表すための海岸線ポリゴン、高さに応じて等高線に従って陸地の色を塗り分けるために用意される等高線ポリゴンなどでも同様の課題が生じ得た。本発明は、これらの課題に鑑み、電子地図データに用いられる詳細形状の地形ポリゴンを変形して、軽い負荷で概略形状の地形ポリゴンを生成可能とすることを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、拡大図用に用意され地形の詳細形状を表示可能な詳細ポリゴンから、広域図用に概略形状を表示するための概略ポリゴンを生成する地図データ生成装置として構成することができる。地図データ生成装置は、まず詳細ポリゴンを入力する。詳細ポリゴンは、地図データ生成装置内に予め格納しておくようにしてもよいし、ＣＤ−ＲＯＭなどの記憶媒体から提供したり、ネットワークを介して所定のサーバから提供するようにしてもよい。詳細ポリゴンは、本発明の地図データ生成装置用に用意されたものだけでなく、電子地図データとして用意されたものであってもよい。
【０００９】
地図データ生成装置は、詳細ポリゴンを構成する構成点、および詳細ポリゴンの辺上に所定の条件で生成された生成点から、ボロノイ分割の母点を設定する。生成点を生成する条件としては、例えば、生成点同士の間隔を所定値以下に抑えるという条件、ポリゴンの構成点間を所定数で分割した点に生成点を設けるという条件などが考えられる。こうして生成された点のみを母点としてもよいし、ポリゴンの構成点のみを母点としてもよいし、両者を混在させて母点として用いてもよい。前記所定値や所定数は、目的とする概略図の縮尺に依存して定めてもよい。
【００１０】
地図データ生成装置は、こうして得られた母点に基づき、詳細ポリゴンをボロノイ分割する。ボロノイ分割によって、詳細ポリゴン内外には、多数の多角形が形成され、この多角形を規定する頂点が生成される。地図データ生成装置は、ボロノイ分割によって得られた各頂点から母点までの距離に基づいて、次に行う変形処理の対象となるべき構成点を選択する。上述の距離と所定値との大小関係に基づいて選択してもよいし、所定半径内に存在する頂点の中から、上記距離が最小または最大となるもののみを選択し、その頂点を含むボロノイ多角形に含まれる構成点を選択するようにしてもよい。後者の処理で選択対象となる頂点は、詳細ポリゴン内に存在するものに限ってもよい。次に、地図データ生成装置は、変形処理、即ち選択された構成点の少なくとも一部を削除して詳細ポリゴンを変形させる処理を実行し、概略ポリゴンを生成する。
【００１１】
本発明の地図データ生成装置によれば、詳細ポリゴンの構成点の少なくとも一部を削除することで概略ポリゴンを生成することができる。削除の対象となる構成点の選択は、ボロノイ分割の頂点から母点への距離に基づいて行われる。母点は詳細ポリゴンの構成点または辺上に生成された点であるから、上述の距離を基準とすることにより、構成点の選択時にポリゴンの形状が考慮されていることになる。従って、本発明によれば、処理対象となる地形に応じて適切な変形処理を実現することができる。
【００１２】
変形処理の一例として、縮退処理を行うようにしてもよい。縮退処理とは、頂点から母点までの距離に基づいてボロノイ分割で得られた頂点の一部を選択し、詳細ポリゴンの少なくとも一部を、この選択された頂点に基づいて定義される折れ線で表現する処理を言う。詳細ポリゴンのうち、先に説明した処理で選択された構成点は削除される。この結果、詳細ポリゴンの一部を削除するとともに、上述の折れ線が接続された形状の概略ポリゴンが生成されることになる。変形処理の負荷を軽減するとともに、変形後の折れ線とポリゴンとが分離されるという支障が生じることを回避するため、縮退処理を実行する際に頂点を選択するための基準と、詳細ポリゴンの構成点を選択する基準とは統一しておくことが好ましい。
【００１３】
縮退処理において、上述した頂点の選択では、一例として、上述の距離が詳細ポリゴンの幅の半分以下となる頂点を選択する方法を採ることができる。こうすることにより、例えば、池の中央付近など非常にポリゴンの外周から遠く離れた場所に生成された頂点を、縮退処理の対象外とすることができる。上述の「半分」は厳密な値ではなく、選択の基準値は、半分よりも大きい値や半分よりも小さい値に設定することも可能である。
【００１４】
また、「詳細ポリゴンの幅」も種々の設定が可能である。例えば、処理時に入力された値や、予め属性値として登録された値などを用いることができる。また、処理対象となっている詳細ポリゴン全体の最大幅、最小幅、または平均幅を採用するものとしてもよい。それぞれの頂点近傍の領域で幅を計測するようにしてもよい。
【００１５】
地図データ生成装置は、更に、選択された頂点のうち、縮退処理によって所定長さ以下の折れ線を形成する頂点を除外するようにしてもよい。こうすることにより、縮退によって短い線が発生することを回避することができる。一般に概略ポリゴンは、広域図などの小さい縮尺で用いられることが多い。かかる場合には、短い線分で表示された形状は認識されないことが多く、これを表示することによって地図が見にくくなるおそれがある。上記態様によれば、縮退処理において短い線分の発生を回避することができるため、こうした弊害を回避することが可能となる。
【００１６】
変形処理の他の例として、選択された構成点のうち一部を削除した残りの構成点を用いて、詳細ポリゴンの少なくとも一部を、折れ線で表現する線分化処理を実行するものとしてもよい。こうすることで、縮退処理よりも軽い負荷で、詳細ポリゴンの一部を線分で表現した概略ポリゴンを生成することが可能となる。縮退処理では、詳細ポリゴンの中心付近を走る線分が定義されるのに対し、この態様では詳細ポリゴンの端部に沿う線分が定義されることになる。従って、表示された時の形状の違和感を緩和するため、この態様は、詳細ポリゴンの幅が狭い領域に対して適用することが好ましい。かかる観点から、例えば、詳細ポリゴンの幅に応じて、線分化処理と縮退処理とを使い分けるようにしてもよい。
【００１７】
本発明の地図データ生成装置は、上述した第１の構成とは異なる第２の構成として、詳細ポリゴンを表示し、その表示上でボロノイ分割の対象となるべき領域の指定を受け付け可能としてもよい。母点生成やボロノイ分割は、こうして指定された領域を対象として実行する。縮退処理は、この領域で生成された頂点を用いて行う。領域内の頂点を無条件に用いるようにしてもよいし、先に説明した第１の構成と同様、所定の条件に基づいて縮退処理の対象となるべき頂点を選択するようにしてもよい。
【００１８】
頂点を選択する場合には、例えば、ボロノイ分割がなされた後、その結果を詳細ポリゴンに重ねて表示し、その表示上で、縮退処理の対象となるべき頂点の指定を受け付けるようにしてもよい。縮退処理は、選択された頂点を対象として行うことになる。かかる方法によれば、オペレータは頂点の選択を視覚的に行うことができるため、より人間のイメージに適合した簡略ポリゴンを生成することが可能となる。
【００１９】
本発明は、第１、第２の構成において説明した種々の特徴を全て備えている必要はなく、一部を省略したり、適宜組み合わせたりしてもよい。第１の構成における特徴を第２の構成に取り込んでも良いし、その逆を行っても良い。例えば、第２の構成における特徴を、第１の構成の前処理または後処理として取り込んでもよい。本発明は、地図データ生成装置の他、コンピュータによって地図データを生成する地図データ生成方法として構成することもできる。また、コンピュータにかかる地図データの生成を実行されるためのコンピュータプログラムとして構成してもよい。
【００２０】
更に、このコンピュータプログラムを記録した記録媒体として構成することもできる。ここで、記録媒体としては、フレキシブルディスクやＣＤ−ＲＯＭ、光磁気ディスク、ＩＣカード、ＲＯＭカートリッジ、パンチカード、バーコードなどの符号が印刷された印刷物、コンピュータの内部記憶装置（ＲＡＭやＲＯＭなどのメモリ）および外部記憶装置等、コンピュータが読取り可能な種々の媒体を利用できる。
【発明を実施するための最良の形態】
【００２１】
本発明の実施例について以下の順序で説明する。
Ａ．装置構成：
Ｂ．デフォルメ処理：
Ｂ１．ボロノイ分割：
Ｂ２．頂点選択：
Ｃ．前処理：
Ｄ．後処理：
Ｅ．変形例：
【００２２】
Ａ．装置構成：
図１は実施例としての地図データ生成装置１０の概略構成を示す説明図である。本実施例では、地図データ生成装置１０は、汎用のパーソナルコンピュータに、地図データ生成装置としての機能を実現するためのコンピュータプログラムをインストールすることにより構成される。図中の各機能ブロックは、ソフトウェア的に構成されることになるが、少なくとも一部をハードウェア的に構成することも可能である。また、図の例では、スタンドアロンで機能する装置を例示したが、ネットワークで接続された複数のコンピュータの分散処理によって地図データ生成装置１０を構成するようにしてもよい。
【００２３】
本実施例の地図データ生成装置１０は、既存の地図データを利用して、新たな地図データを生成する機能を奏する。予め地図データとして、拡大図の表示用に詳細な地形または地物形状を表したポリゴン（以下、「詳細ポリゴン」と呼ぶ）が用意されているものとし、この詳細ポリゴンをデフォルメして、広域図の表示用に概略形状を表すポリゴン（以下、「概略ポリゴン」と呼ぶ）を生成するのである。地図データ生成装置には、この他にも道路ネットワークを生成するための機能や、新規にポリゴンを生成する機能など、多様な機能を備えることが可能であるが、図１では、デフォルメにより地図データを生成する機能に関連する部分のみを示した。
【００２４】
地図ＤＢ２０は、階層的に用意された地図データを格納する。上位レベルとは、広域図を表示するための概略形状を表したデータ、即ち概略ポリゴンであり、下位レベルとは、拡大図を表示するための詳細な形状を表したデータ、即ち詳細ポリゴンである。地図ＤＢ２０に備えられる地図データのレベル数は、表示時の縮尺および表示の処理時間に対する要請を考慮して、任意に設定可能である。
【００２５】
地図ＤＢ参照部１６は、地図ＤＢ２０を参照し、デフォルメの処理対象となるポリゴンを抽出する。デフォルメ処理部１５は、この抽出されたポリゴンのデフォルメ処理を実行する。処理の詳細な内容については後述する。デフォルメＤＢ２１はこのデフォルメ処理の設定条件をデータベースとして保持している。ボロノイ分割部１２は、デフォルメ処理部１５からの指示に従って、ポリゴンのデフォルメ処理の過程で用いられるボロノイ分割を実行し、その結果をデフォルメ処理部１５に受け渡す。デフォルメＤＢ２１には、併せて、デフォルメ処理過程における種々のデータを格納してもよい。
【００２６】
デフォルメ修正部１４は、デフォルメ処理された結果に対して、オペレータからのコマンドに応じて、種々の修正を加える。デフォルメ処理部１５による処理結果に対して、修正や確認の必要性がないと考えられる場合には、デフォルメ修正部１４は省略してもよい。デフォルメＤＢ２１は、デフォルメ修正処理の設定条件も併せて保持している。
【００２７】
表示制御部１３は、以上で説明したデフォルメ処理に際して、デフォルメされた結果の表示やデフォルメの条件その他を入力するためのインタフェース画面を提示する。コマンド入力部１１は、キーボードやマウスに対する操作を介して、オペレータからのコマンドを入力する。
【００２８】
Ｂ．デフォルメ処理：
図２は河川ポリゴンのデフォルメ処理例を示す説明図である。左側に、詳細ポリゴンを示し、右側に概略ポリゴンを示した。河川ポリゴンには、それぞれハッチングを付した。本来ならば、概略ポリゴンは広域図に用いられるものであるため、詳細ポリゴンよりも小さいサイズで描かれるものであるが、ここでは説明の便宜上、同じサイズで示した。
【００２９】
地図データ生成装置は、詳細ポリゴンにおいて楕円で囲んだ領域のように、河川が比較的狭く描かれている箇所を、線で表すことによって概略ポリゴンを生成する。このように、ポリゴンを線で置換する処理を縮退（処理）と呼ぶ。以下では、この処理の内容について説明する。
【００３０】
図３はデフォルメ処理のフローチャートである。デフォルメ処理部１５（図１参照）が他の機能ブロックと協同して実現する処理であり、ハードウェア的には地図データ生成装置のＣＰＵが実行する処理である。
【００３１】
処理が開始されると、ＣＰＵは地図ＤＢ２０を用いて地図を表示し、処理対象ポリゴンの指定を入力する（ステップＳ１０）。処理対象ポリゴンの指定は、例えば、地図上でオペレータがマウス等でクリックする方法や、処理対象とすべき河川の名称などを入力する方法を採ることができる。
【００３２】
次に、ＣＰＵはボロノイ分割に使用する母点を設定する（ステップＳ２０）。図中に母点の設定方法を例示した。河川ポリゴンＰＯＬの形状は、黒丸で示した点Ｐ１、Ｐ２等（以下、「ポリゴン構成点」と呼ぶ）によって規定されているとする。第１にこれらのポリゴン構成点Ｐ１、Ｐ２等は、そのまま母点となる。そして、ＣＰＵは、ポリゴン構成点Ｐ１、Ｐ２等の間を等分割して生成点Ｐｍ１、Ｐｍ２を生成する。図中の例では３等分して生成点を生成するものとした。これらの生成点も母点となる。
【００３３】
母点は、上述の方法によらず、種々の方法で生成可能である。例えば、母点間の距離が所定値以下となるように、各ポリゴン構成点Ｐ１，Ｐ２等の間ごとに分割数を設定してもよい。ポリゴン構成点のみを母点として設定してもよいし、生成点のみを母点として設定してもよい。
【００３４】
こうして設定された母点を利用して、ＣＰＵはポリゴンＰＯＬを分割して、ボロノイ多角形を生成する処理を実行する（ステップＳ３０）。ボロノイ多角形への分割処理は、計算幾何学で周知の処理なので、詳細な説明は省略する。図中に、ボロノイ多角形の処理例を示した。この処理によって、ボロノイ多角形の頂点が多数規定されることになる。
【００３５】
ＣＰＵは、ボロノイ多角形の頂点の中から、予め設定された縮退条件に基づき、縮退処理に用いるべき頂点を選択し（ステップＳ４０）、これらの頂点を結ぶとともに、選択された頂点に対応するポリゴン構成点を削除することで縮退処理を行う（ステップＳ５０）。図中の例では、例えば、ＣＰＵは、ポリゴン構成点Ｐ４，Ｐ７よりも右側の破線で示した領域Ａについては、縮退処理を施すべきではないと判断し、これよりも左側の領域についてのみ縮退処理を施すのである。この処理の結果、図中に示すように、ポリゴンＰＯＬは、ポリゴンＰＯＬ１と折れ線ＣＬから表されることになる。縮退処理の対象となるべき頂点を選択するための縮退条件については、後述する。
【００３６】
こうして生成された折れ線ＣＬは、図中に示す通り、非常に凹凸が激しい形状となるのが通常である。ＣＰＵは、このような折れ線ＣＬ上の点をリサンプリングして、平滑化し（ステップＳ６０）、処理を完了する。リサンプリングとは、図中に「■」で示すように、折れ線ＣＬの点列よりも粗い間隔で折れ線ＣＬ上の点を抽出することを言う。こうして抽出された点（図中の「■」）を結ぶことにより、折れ線ＣＬを平滑化することができる。
【００３７】
Ｂ１．ボロノイ分割：
図４はボロノイ分割の処理例を示す説明図である。図中のハッチングを付した部分が河川である。先に説明した通り、河川のポリゴンの輪郭上に、黒丸で示す母点を設定して、ボロノイ分割を施すことにより、実線で示す多数のボロノイ多角形が得られる。
【００３８】
Ｂ２．頂点選択：
図５は縮退処理の対象となる頂点の選択方法および結果を示す説明図である。本実施例では、次の条件を縮退条件として設定した。この縮退条件は、予めデフォルメＤＢ（図１参照）に登録されている。
（条件１）ポリゴンの内側に存在する点であること；
（条件２）母点までの最小距離が所定値以下であること；
所定値は、「河川幅の半分＋実数α」とした。河川幅は、オペレータが入力するものとしてもよいが、本実施例では地図ＤＢに予め属性として登録されている値を用いるものとした。実数αは、河川幅の値に対する余裕であり、任意に設定可能である。所定値は、「河川幅の半分×係数」の形で設定するようにしてもよい。
【００３９】
ここでは、河川幅が図中の楕円で囲んだ領域Ａ１内の河川ポリゴンの平均幅と同等であるものとして説明をする。図中の頂点Ｐ１の場合、最も近い母点までの距離は図中のｄ１と求まる。頂点Ｐ１は河川ポリゴンの内部の点なので条件１は満足し、距離ｄ１が所定値以下であれば、頂点Ｐ１は縮退処理の対象として選択される。これに対し、例えば、頂点Ｐ２は、母点までの距離ｄ２が所定値よりも大きいため、選択されない。このように、上述の条件２を設けることにより、頂点Ｐ２のように、河川ポリゴンの縁線から遠くにある頂点は、縮退の対象から除かれることになる。この処理によって、楕円領域Ａ１，Ａ２，Ａ３内に白丸で付した頂点が縮退処理の対象として選択される。図中では、縮退処理によって得られる折れ線、即ち、選択された頂点を結んだ折れ線を太線で併せて示した。
【００４０】
上述の選択処理では、所定値の基準となる河川幅を別途入力または登録してあるものとして説明した。これに対し、河川幅は、例えば、次の方法で河川ポリゴンから算出するようにしてもよい。まず、母点Ｍに対して、その周囲の母点との距離Ｌ１、Ｌ２、Ｌ３を求める。この中から、母点Ｍと、ポリゴンの同一縁線上にない点を選択し、その距離を母点Ｍにおける河川幅とする。図の例では、距離Ｌ３が河川幅として設定されることになる。この処理を、全母点について実行し、河川ポリゴンの河川幅を、各母点について求められた値の最大値、最小値、平均値などの代表値で設定する。こうすることにより、予め河川幅等が入力または登録されていない場合でも、頂点の選択を行うことが可能となる。
【００４１】
本実施例では、図５で説明した条件に基づく選択に加えて、更に、次の条件３を付加して頂点を選択するものとした。
（条件３）縮退処理によって得られる折り線の長さが所定長以上であること；
所定長は、任意に設定可能である。本実施例では、図中の領域Ａ１の折れ線と、領域Ａ２，Ａ３の折れ線との間で設定した。つまり、本実施例では、領域Ａ１の頂点は縮退処理の対象として選択され、領域Ａ２、Ａ３内の頂点は除外されることになる。条件３を用いることにより、縮退によって無用に短い線分が多数生成されることにより、形状がかえって複雑化することを回避することができる。条件３は、折れ線の長さに基づいて設定する他、折れ線に含まれる頂点数に基づいて設定してもよい。
【００４２】
折れ線によっては、条件１または２で縮退処理対象からはずされた頂点が、途中に１〜２個程度存在することによって、折れ線の長さが条件３を満たさなくなる場合が起こりうる。このような折れ線が縮退処理の対象からはずれることを回避するため、次の処理を施しても良い。まず、折れ線間で脱落している頂点数が所定値（例えば、２個程度）以下となる折れ線群の有無を検出する。このような折れ線群が発見された場合には、その折れ線群を対象として、条件２の所定値を段階的に大きくし、折れ線が連続となるか否かを判定する。条件２の所定値を予め決められた範囲で大きくすることで折れ線が連続となる場合には、脱落していた頂点を縮退対象として選択し、連続した折れ線に基づいて条件３を具備するか否かを判定する。条件２の所定値を予め決められた範囲で大きくしても、折れ線が連続とならない場合には、当初の折れ線で条件３を具備するか否かを判定する。この処理を施すことによって、些細な条件不備によって縮退対象から除かれる頂点を減らすことができ、概略ポリゴン生成の適正化を図ることができる。条件２，３を用いるまでなく、上述の折れ線群を無条件に連続化させてもよい。
【００４３】
図６は概略ポリゴンの生成結果を示す説明図である。図５で示した領域Ａについてのみ縮退処理が施され、その他の部分は詳細ポリゴン形状が維持されている。詳細ポリゴンからは、縮退処理時に選択された頂点を含むボロノイ多角形内の構成点が削除される。このように、実施例で説明したデフォルメ処理によれば、河川のように広幅の部分、狭幅の部分が混在するポリゴンに対しても、いびつな形状を招くことなく概略ポリゴンを生成することができる。上述の処理中で示した条件２の所定値や、条件３の所定長の設定により、多レベルに応じた概略ポリゴンを生成することが可能である。
【００４４】
Ｃ．前処理：
図７は変形例としてのデフォルメ処理のフローチャートである。第１実施例では、河川ポリゴンから縮退対象となる頂点を自動的に選択する例を示した。変形例では、前処理としてデフォルメの対象となる領域をオペレータが指定する例を示す。
【００４５】
処理が開始されると、ＣＰＵは画面上に、地図を表示し、処理対象ポリゴンの指定を入力する（ステップＳ１０Ａ）。図中に表示画面ＤＩＳＰを示した。図の中央のハッチングを付したポリゴンＲＶは河川を表している。オペレータは、この表示画面ＤＩＳＰ上で、マウスなどのポインティングデバイスにより、処理対象として枠Ｚの領域を指定することができる。地図データ生成装置は、河川ポリゴンＲＶのうち、枠Ｚ内にある範囲を処理対象として認識する。
【００４６】
ＣＰＵは、次に、河川ポリゴンＲＶに基づき、指定された領域からなるデフォルメ用の仮想ポリゴンを生成する（ステップＳ１１Ａ）。つまり、河川ポリゴンＲＶのうち、枠Ｚ内にある範囲を、仮想ポリゴンとして切り出す。
【００４７】
こうして設定された仮想ポリゴンを対象として、ＣＰＵは実施例のデフォルメ処理（図３参照）のステップＳ２０以降の処理を実行する。つまり、母点生成、ボロノイ分割、頂点の選択、および縮退処理、リサンプリングによる平滑化の各処理を行うのである。この処理過程では、実施例と同様、条件１〜３に基づいて縮退対象となるべき頂点が選択される。
【００４８】
変形例では、縮退処理に先立って、処理対象となる領域をオペレータが指定することができる。この処理により、一見して縮退処理が不要と考えられる領域を除外することができる。従って、概略ポリゴンを生成するデフォルメ処理の負荷を軽減することが可能となる。
【００４９】
変形例では、実施例と同様の条件によって頂点を選択する場合を例示した。変形例では、オペレータが処理対象となる領域を指定するため、頂点の抽出処理（図３のステップ４０）を省略してもよい。
【００５０】
Ｄ．後処理：
図８はデフォルメ修正処理のフローチャートである。デフォルメ処理（図３および図７参照）が施された後の概略ポリゴンに対する修正を行うための後処理である。
【００５１】
処理が開始されると、ＣＰＵはデフォルメ処理前後の地図データを読込み、両者を重ねて表示する（ステップＳ１００）。図中に表示例を示した。ハッチングの部分は河川ポリゴンを示している。説明の便宜上、図５中の領域Ａ１〜Ａ３全てについて縮退処理が施された状態を例示した。
【００５２】
オペレータが、この表示画面上で、要縮退箇所、縮退不要箇所をそれぞれ指定すると、地図データ生成装置は、その指定を受け付ける（ステップＳ１１０）。図中の例において、例えば、オペレータが、縮退処理で得られた線ＣＬ１だけでは不十分と判断した場合には、この線分ＣＬ１に続く領域Ｚａを要縮退箇所として指定する。逆に、縮退処理不要と判断した箇所に対しては、例えば、領域Ｚｂ、Ｚｃのように縮退結果として得られた線分を取り囲む領域を指定する。
【００５３】
これらの指定を受けると、ＣＰＵは、指定された箇所を対象としてデフォルメ処理を実行する（ステップＳ１２０）。例えば、領域Ｚａに対して、再度デフォルメ処理を行う。この際、従前の処理と同じ結果が得られるのを回避するため、例えば、頂点を抽出する際の条件１〜３で用いられる所定値、所定長を段階的に緩くしたり、いずれか一つの条件を削除するなどの措置を施すことが好ましい。この処理と併せて、ＣＰＵは縮退不要箇所として指定された領域については、従前のポリゴンに戻す処理を実行する。
【００５４】
ＣＰＵは、オペレータが終了を指定するまで（ステップＳ１３０）、以上の処理を繰り返し実行する。この処理を施すことにより、よりオペレータの意図に沿った形で概略ポリゴンを生成させることが可能となる。
【００５５】
Ｅ．変形例：
図９は変形例としてのデフォルメ処理を示す説明図である。図４〜６で用いた河川ポリゴンに対する処理を例示している。変形例のデフォルメ処理では、実施例と同様にして、ボロノイ分割の頂点（図中の白丸）を選択し、この頂点を含むボロノイ多角形内の構成点を選択する。そして、これらの構成点を、削除すべきものと、残すべきものとに分ける。図の例では、選択された頂点（図中の白丸）を結ぶ線分よりも右側に位置する構成点（領域Ｂ１内の構成点）を残すべきものとして選択し、左側の構成点を削除すべきものとした。デフォルメ処理では、こうして残された構成点を線分で結ぶことによって、折れ線Ｌ１を定義し、河川ポリゴンの一部を線分化する。この処理を線分化処理と呼ぶものとする。
【００５６】
変形例の線分化処理によれば、簡易な方法で線分化を実現することができる。また、図９に示すように、河川ポリゴンの辺を定義していた構成点を選択することにより、辺の一部を残す形で線分化が行われることとなる。こうして得られた線分は、十分になめらかであるためリサンプリングによる平滑化（図３のステップＳ６０参照）を省略することができる利点がある。変形例の線分化処理と実施例の縮退処理は、併用することも可能であり、例えば、デフォルメ処理の対象として選択された領域の幅に応じて、両者を使い分けるようにしてもよい。
【００５７】
デフォルメ処理の他の態様を図中の領域Ｂ２に示した。実施例では、処理対象となる頂点を選択する際に、「（条件１）ポリゴンの内側に存在する点であること」という条件を考慮していた。変形例では、この条件を外して頂点を選択する。この結果、領域Ｂ２に示すように河川ポリゴンの凹部を構成する構成点も処理対象として選択される可能性が生じる。変形例では、こうして選択された構成点を削除する。この結果、図中の線分Ｌ２で示すように、凹部も河川ポリゴン内に取り込んだ簡易な形状の概略ポリゴンを得ることができる。この処理では、本来、陸地であった部分を河川として表現することになるため、この領域内に地物が存在する場合には処理の実行を回避した方が好ましい場合もある。従って、この処理の実行に際し、オペレータの確認を取るような態様としてもよい。
【００５８】
以上、本発明の種々の実施例について説明したが、本発明はこれらの実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。上述の例では、河川ポリゴンの処理を例示したが、本実施例は、種々のポリゴンの処理に適用可能である。例えば、等高線で色分けして地図を表示する際に、各等高線に対応したポリゴンのデフォルメに適用してもよい。また、海岸線などのデフォルメに適用してもよい。
【図面の簡単な説明】
【００５９】
【図１】実施例としての地図データ生成装置１０の概略構成を示す説明図である。
【図２】河川ポリゴンのデフォルメ処理例を示す説明図である。
【図３】デフォルメ処理のフローチャートである。
【図４】ボロノイ分割の処理例を示す説明図である。
【図５】変形処理の対象となる頂点の選択方法および結果を示す説明図である。
【図６】概略ポリゴンの生成結果を示す説明図である。
【図７】変形例としてのデフォルメ処理のフローチャートである。
【図８】デフォルメ修正処理のフローチャートである。
【図９】変形例としてのデフォルメ処理を示す説明図である。
【符号の説明】
【００６０】
１０…地図データ生成装置
１１…コマンド入力部
１２…ボロノイ分割部
１３…表示制御部
１４…デフォルメ修正部
１５…デフォルメ処理部
１６…地図ＤＢ参照部
２０…地図ＤＢ
【図１】
2007121668.tif 000003
【図２】
2007121668.tif 000004
【図３】
2007121668.tif 000005
【図４】
2007121668.tif 000006
【図５】
2007121668.tif 000007
【図６】
2007121668.tif 000008
【図７】
2007121668.tif 000009
【図８】
2007121668.tif 000010
【図９】
2007121668.tif 000011