ポリゴン分割装置およびポリゴン分割方法
【課題】ポリゴンを重なりや隙間が発生しないように分割することができるポリゴン分割装置を提供する。
【解決手段】第二分割手段は、ポリゴン３２の内部に存在する点であって線分３７ａ，３７ｂ上に存在する任意の点を新たな内部構成点３６ａ，３６ｂとして選択する。なお、内部構成点３６ａ，３６ｂについてはこれら内部構成点３６ａ，３６ｂのｙ座標が同一となるような点が選択される。次に、第二分割手段は、構成点３１ａと内部構成点３６ａとを繋ぐ線３７ａ、構成点３１ｂと内部構成点３６ｂとを繋ぐ線３７ｂ、および内部構成点３６ａと内部構成点３６ｂとを繋ぐ線３８によって、ポリゴン３２を分割する。なお、内部構成点３６ａと内部構成点３６ｂとを繋ぐ線３８は、仮想線３３に対して垂直な線となる。
【解決手段】第二分割手段は、ポリゴン３２の内部に存在する点であって線分３７ａ，３７ｂ上に存在する任意の点を新たな内部構成点３６ａ，３６ｂとして選択する。なお、内部構成点３６ａ，３６ｂについてはこれら内部構成点３６ａ，３６ｂのｙ座標が同一となるような点が選択される。次に、第二分割手段は、構成点３１ａと内部構成点３６ａとを繋ぐ線３７ａ、構成点３１ｂと内部構成点３６ｂとを繋ぐ線３７ｂ、および内部構成点３６ａと内部構成点３６ｂとを繋ぐ線３８によって、ポリゴン３２を分割する。なお、内部構成点３６ａと内部構成点３６ｂとを繋ぐ線３８は、仮想線３３に対して垂直な線となる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ベクトルデータとして記述された電子地図データの一部であるポリゴンを複数に分割する技術に関するものである。
【背景技術】
【０００２】
ベクトルデータとして記述された電子地図データは、直交するＸ軸、Ｙ軸の二次元座標上に定義された１つの構成点のみからなる点データ、二つの構成点とこれら構成点を繋ぐ線（ここで線とは、直線あるいは曲線である）からなる線データ、そして複数の構成点とその構成点を相互に接続する線とによって外形を模ったポリゴンデータの集合体である。この様な電子地図データは、大規模なＧＩＳシステムから携帯用の簡易機器、例えばパーソナルナビゲーションデバイス（PND:Personal
Navigation Device）や携帯ゲーム機にまで利用される。
【０００３】
電子地図データが簡易機器で利用される場合、ポリゴンデータの取り扱いに注意が必要となる。簡易機器に採用されるＣＰＵの処理能力、記憶領域のサイズなどから、ポリゴンデータとして処理できる構成点の数に制限があるからである。例えば、最も簡単な機器構成では許容される構成点の数が３個であり、この場合にはポリゴンデータとしては三角形しか取り扱うことが出来ない。そこで、この様な簡易機器にて複雑な形状のポリゴンデータを取り扱い可能とするための事前の処理として、多数の構成点からなるポリゴンデータを、簡易機器が許容する構成点の数以下となるように分割するポリゴン分割処理が行われる。
【０００４】
例えば、上述した最も簡単な機器構成である簡易機器にて５角形ポリゴンを処理可能とするために、５角形ポリゴンを３個あるいはそれ以上の三角形ポリゴンに分割するのである。
この様なポリゴン分割技術としては各種の手法が開発されており、利用者はその目的に応じて何れかのポリゴン分割技術を選択しあるいは複数のポリゴン分割技術を組み合わせ、複雑なポリゴンデータを所定値以下の構成点からなるポリゴンデータの組み合わせとして扱っている。
【０００５】
その中の一つとして、ベクトルデータの一種であるアウトラインフォント塗りつぶしの際、進入頂点リスト、左右稜線リスト、アクティブエッジリストの生成処理を含めず、処理を高速化するためにポリゴンを分割する技術がる（特許文献１）。この技術では、ポリゴンを分割する線分は例えばＹ軸に平行な線分であり、ポリゴンを左右に分割された２つのポリゴンによって共有する。その一端は分割前の図形の１頂点で、Ｙ座標が極大または極小となる凹頂点である。この様なポリゴン分割を繰り返すことにより、分割終了後の各々のポリゴン形状は、進入頂点および退出頂点が各１個の単純な形状となる。したがって、複雑なアウトラインフォント塗りつぶし処理は、単純な図形塗りつぶし処理の繰り返しによって代替されることになり、簡単な回路により実現される。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平６−２７９２７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
従来、各種のポリゴン分割技術が開発されているが、その目的は、構成点数の多い複雑な形状のポリゴンデータを回転、拡縮などの図形処理、塗りつぶしなどの表示処理することにある。すなわち、従来のポリゴン分割技術の何れも、構成点数の多いポリゴンデータを構成点が所定値以下のポリゴンデータの組み合わせに変換することを目的としており、分割後のポリゴンデータの構成点数が所定値以下となれば目的を達成することになる。
【０００８】
しかし、近年のデジタル技術、通信技術の進歩によって電子地図データを処理対象とする機器は飛躍的に増加し、かつ、それぞれが互いに通信し合ってデータを共有することで情報処理の効率化を図っている。この様な環境変化により、ある機器での取り扱いに適したようにポリゴン分割を行った後に、他の機器で分割後のポリゴンデータを更に再分割するような事態が頻発することになる。この様な場合において後段の他の機器は、前段の機器で行われたポリゴン分割の結果を単に受け取るだけであり、受け取ったポリゴンデータが単一のポリゴンデータであるかあるいはポリゴン分割した結果物であって複数のポリゴンデータの組み合わせにより単一の複雑なポリゴンデータを表現しているのかを知るすべはない。
【０００９】
このため、例えば互いに接しており、構成点やその構成点相互を接続する線が互いに共通している一方のポリゴンデータを更に再分割する場合、その一方のポリゴンの共通している線上に新たな構成点を設定するなど相互のデータの共通性が崩れる事態が発生するのである。このデータの共通性の崩れは、新たな構成点が座標点に再配置された際にポリゴンの重なりや隙間発生の原因となる。
【００１０】
一例として、従来のポリゴン分割装置を用いて、図１１に示すポリゴン９１を分割する場合を説明する。まず、当該ポリゴン９１を構成する複数の構成点９２から任意の構成点９２ａ，９２ｂを抽出する。次に、これら構成点９２ａ，９２ｂを結ぶ分割線分９３でポリゴン９１を分割して２つのポリゴン９１ａ，９１ｂを生成する。
このように分割されたポリゴン９１ａを、他の装置で任意の構成点数となるように分割する。例えば、図１２に示すように、任意の構成点９２と、構成点９２ａ，９２ｂを結ぶポリゴン９１ａの線分９４に交差する点９５とを繋ぐ分割線分９６で、ポリゴン９１ａを複数のポリゴンに分割する。
【００１１】
すると、図１２の拡大図に示すように、線分９４に交差する点９５が直交するＸ軸９７、Ｙ軸９８の二次元座標上に存在しないことがあるため、線分９４に交差する点９５がＸ軸９７、Ｙ軸９８上の点に設定されることになる。このことは、ポリゴン９１ｂについてもいえる。
【００１２】
したがって、ＰＮＤや携帯端末で、このように分割されたポリゴン９１ａ，９１ｂを表示させた場合、これらポリゴン９１ａ，９１ｂの間に、図１３に示すような隙間９９が生じることになる。このポリゴン９１ａ，９１ｂが湖に関するポリゴンであった場合には、この隙間９９は、描画されない領域となるため、ライン状のノイズとなって地図に表示されることになる。
本発明は、こうした課題を解決することのできるポリゴン分割装置、およびポリゴン分割方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記課題を解決するために、本発明は、直交するＸ軸、Ｙ軸の二次元座標上に定義されたベクトルデータにより地物を表現する電子地図データの一部であって、複数の構成点とその構成点を相互に接続する線とによって外形を模ったポリゴンを複数に分割するポリゴン分割装置であって、ポリゴンデータの構成点が所定値以上であって前記ポリゴンを分割する必要があるとき、そのポリゴンをＸ軸あるいはＹ軸と平行に略二等分する仮想線の端点それぞれに最も近接している前記ポリゴンの構成点を選択する分割点選択手段と、該分割点選択手段により選択された２つの構成点をそれぞれ一方の端点とする、前記仮想線に平行な線分である第一分割線分が一直線上にあるとき、当該第一分割線分により前記ポリゴンを分割する第一分割手段と、前記第一分割線分が一直線上にないとき、前記ポリゴン内部に存在する点であって第一分割線分上に存在する点を新たな構成点とし、前記第一分割線分と相互の新たな構成点を繋ぐ前記仮想線に垂直な第二分割線分とにより前記ポリゴンを分割する第二分割手段とを備えることを特徴とする。
なお、上述した特徴は、本発明の特徴のすべてを列挙したものではなく、これらを要部とする構成（または方法）もまた発明となり得る。
【発明の効果】
【００１４】
本発明によれば、ある機器での取り扱いに適したようにポリゴン分割を行った後に、他の機器で分割後のポリゴンデータを更に再分割する場合であっても、分割後のポリゴンを表示させた場合に隙間が発生することを防止することができる。
【図面の簡単な説明】
【００１５】
【図１】本実施例におけるポリゴン分割装置の構成図。
【図２】ポリゴン分割処理のフローチャート。
【図３】ポリゴン分割処理のフローチャート。
【図４】ポリゴン分割処理の説明図。
【図５】ポリゴン分割処理の説明図。
【図６】ポリゴン分割処理の説明図。
【図７】ポリゴン分割処理の説明図。
【図８】ポリゴン分割処理のフローチャート。
【図９】ポリゴン分割処理の説明図。
【図１０】ポリゴン分割処理の説明図。
【図１１】従来技術の説明図。
【図１２】従来技術の説明図。
【図１３】従来技術の説明図。
【発明を実施するための形態】
【００１６】
以下、本発明を具体化したポリゴン分割装置について説明する。
図１に示すように、本実施例におけるポリゴン分割装置１１はコンピュータであり、記憶手段としてのハードディスク１２、分割点選択手段１３、第一分割手段１４、第二分割手段１５、制御手段１６を備える。
分割点選択手段１３、第一分割手段１４、第二分割手段１５、制御手段１６は、実際には、ポリゴン分割装置１１が有する図示しないＣＰＵ（Central Processing Unit ）がハードディスク１２やメモリ等に記憶されている各種プログラムを実行することにより実現される。
【００１７】
ハードディスク１２には、電子地図データが記憶されている。この電子地図データは、建物の形状、道路の形状、海域の形状、都道府県や市区町村等の領域形状等をベクトルデータとして記述したポリゴンデータを含んでいる。
【００１８】
分割点選択手段１３は、ポリゴンデータの構成点が所定値以上であってそのポリゴンを分割する必要があると判断された場合、そのポリゴンをＸ軸あるいはＹ軸と平行に略二等分する仮想線の端点それぞれに最も近接しているポリゴンの構成点を選択する機能を有する。ここで、所定値は、分割されたポリゴンを利用する装置におけるＣＰＵの処理能力、記憶領域のサイズなどを考慮して決定される値であればよく、任意の値に設定することが可能である。例えば、構成点が数千点である地図データのポリゴンデータを分割する場合には、所定値として８００が設定される。
【００１９】
第一分割手段１４および第二分割手段１５は、ポリゴンを分割する分割処理機能を有する。
第一分割手段１４は、分割点選択手段１３によって選択されたポリゴンにおける２つの構成点をそれぞれ一方の端点とする仮想線に平行な線分である第一分割線分が一直線上にあるとき、その第一分割線分によりポリゴンを分割する機能を有する。
【００２０】
第二分割手段１５は、第一分割線分が一直線上にないとき、ポリゴンの内部であって第一分割線分のそれぞれの他方の端点を新たな構成点とし、相互の新たな構成点を繋ぐ仮想線に垂直な第二分割線分によりそのポリゴンを分割する機能を有する。
制御手段１６は、ポリゴン分割装置１１が備える各手段１２〜１５の動作をメモリ等に記録されている所定のプログラムに基づいて制御する機能を有する。
【００２１】
次に、本実施例におけるポリゴン分割装置１１を用いてポリゴンを分割する処理方法について説明する。
図２に示すように、まず、制御手段１６は、電子地図データに含まれているポリゴンデータをハードディスク１２から読み出す（ステップＳ２０１）。次に、分割点選択手段１３が、ポリゴンの構成点数をカウントするとともに、その構成点数が予め設定されている所定の数よりも多い場合に、そのポリゴンを分割する必要があると判断する（ステップＳ２０２）。一方、構成点数が予め設定されている所定の数よりも少ない場合には、次のポリゴンデータをハードディスク１２から読み出す（ステップＳ２０１）。
【００２２】
分割する必要があると判断された場合、図３に示すように、分割点選択手段１３は、ポリゴン３２の構成点３１のうち、Ｘ軸（またはＹ軸）と平行に略二等分する仮想線３３の端点３４ａ，３４ｂにそれぞれに最も近接しているポリゴンの構成点３１ａ，３１ｂを選択する（ステップＳ２０３）。例えば、分割点選択手段１３は、端点３４ａ，３４ｂの位置からの直線距離が最も短くなる構成点３１を選択する。なお、仮想線３３は、ポリゴン３２の重心点を通る線とすればよい。
【００２３】
次に、第一分割手段１４が、第一分割処理を実行する。図４に示すように、第一分割手段１４は、分割点選択手段１３によって選択された２つの構成点３１ａ，３１ｂをそれぞれ一方の端点としており、仮想線３３に平行な線分であるそれぞれの線分３５ａ，３５ｂが一直線上にあるか否かを判定する（ステップＳ２０４）。線分３５ａ，３５ｂが一直線上にあると判定した場合、換言すれば線分３５ａ，３５ｂが同一線であると判定した場合、第一分割手段１４は、その線分３５ａ，３５ｂ（第一分割線分）によりポリゴン３２を分割する（ステップＳ２０５）。図４の例では、線分３５ａ，３５ｂは一直線上に存在していないため、線分３５ａまたは線分３５ｂによってポリゴン３２が分割されることはない。
【００２４】
なお、第一分割手段１４は、仮想線３３がＹ軸に平行であって、２つの構成点３１ａ，３１ｂのｘ座標が同一である場合に、構成点３１ａ，３１ｂを通る線分によりポリゴン３２を分割するようにしてもよい。また、仮想線３３がＸ軸に平行であって、２つの構成点３１ａ，３１ｂのｙ座標が同一である場合も同様である。
【００２５】
一方、第一分割手段１４によって線分３５ａ，３５ｂが一直線上にないと判定されたときには、第二分割手段１５によって、第二分割処理が実行される。
まず、図５に示すように、第二分割手段１５は、ポリゴン３２の内部に存在する点であって線分３５ａ，３５ｂ上に存在する任意の点を新たな内部構成点３６ａ，３６ｂとして選択する（ステップＳ２０６）。なお、内部構成点３６ａ，３６ｂについてはこれら内部構成点３６ａ，３６ｂのｙ座標が同一となるような点が選択される。
【００２６】
次に、図６に示すように、第二分割手段１５は、構成点３１ａと内部構成点３６ａとを繋ぐ線３７ａ、構成点３１ｂと内部構成点３６ｂとを繋ぐ線３７ｂ、および内部構成点３６ａと内部構成点３６ｂとを繋ぐ線３８（第二分割線分）によって、ポリゴン３２を分割する（ステップＳ２０７）。なお、内部構成点３６ａと内部構成点３６ｂとを繋ぐ線３８は、仮想線３３に対して垂直な線となる。
【００２７】
次に、制御手段１６は、第一分割手段１４または第二分割手段１５によって分割されたそれぞれのポリゴンについて構成点数をカウントするとともに、当該構成点数と予め設定されている所定の数とを比較する（ステップＳ２０８）。構成点数が所定の数よりも多い場合には、制御手段１６は、当該構成点数が所定の数よりも多いポリゴンについて、更なる分割処理を実行する（ステップＳ２０３）。なお、制御手段１６は、分割されたポリゴンをハードディスク１２に記憶する。
【００２８】
そして制御手段１６は、電子地図データに含まれるすべてのポリゴンについて分割処理を実行したか否かを判定する（ステップＳ２０９）。分割処理が実行されていないポリゴンが存在していると判定した場合、制御手段１６は、当該ポリゴンをハードディスク１２から読み出すとともに、上述した分割処理を当該読み出されたポリゴンに対して実行する。一方、すべてのポリゴンについて分割処理を実行したと判定した場合には、制御手段１６は分割処理を終了する。
【００２９】
（実施例の効果）
図７に示すように、本実施例におけるポリゴン分割装置１１によって分割されたポリゴン３２を、他の装置において更に任意の分割線４１で複数のポリゴンに分割した場合であって、ポリゴン３２を表示させた場合にポリゴン間に図１３に示すような隙間が生じることはない。これは、ポリゴン分割装置１１によって分割されたポリゴン３２ａにおける構成点３１ａから構成点３１ｂまでの線分であって、新たな構成点３１ａ，３１ｂを通る線分の上の点は、すべて座標線４２，４３で規定される座標線上に存在している。そのため、分割線４１をなす一方の端点として当該線分上の点が指定されたとしても、当該端点は必ずＸ軸４２、Ｙ軸４３の二次元座標上に存在するためである。
【００３０】
（他の実施例）
上述した実施例における分割処理については、以下の方法で実現してもよい。
図８、図９に示すように、まず、第一分割手段１４は、ポリゴン３２の構成点５１のうち、任意の１点を開始構成点５１ａとして抽出する（ステップＳ８０１）。次に、第一分割手段１４は、構成点５１の数をカウントして、ほぼ開始構成点５１ａと反対側の位置に存在する構成点５１を終了構成点５１ｂとして抽出する（ステップＳ８０２）。
【００３１】
次に、第一分割手段１４は、開始構成点５１ａからポリゴン３２の内部に向けてＹ軸に平行な線５２を引く（ステップＳ８０３）。そして、第一分割手段１４は、当該線５２がポリゴン３２を構成する線分と交差する点が終了構成点５１ｂを含む何れかの構成点５１であるか否かを判定する（ステップＳ８０４）。交差する点が構成点５１である場合には、第一分割手段１４は、開始構成点５１ａとその構成点５１とを繋いだ線でポリゴン３２を分割する（ステップＳ８０５）。
【００３２】
一方、交差する点が構成点５１でない場合には、第二分割手段１５が、線５２の先端の位置を開始構成点５１ａの方向へ数ドット（例えば２ドット）だけ戻すとともに、図１０に示すように、その戻した位置から終了構成点５１ｂに近づく方向へ、線５２と垂直な線５３を引く（ステップＳ８０６）。つまり線５３は、Ｘ軸に平行な線である。そして、第二分割手段１５は、線５３のｘ座標が終了構成点５１ｂのｘ座標と一致する位置まで線５３を引くとともに、最後に、当該位置から終了構成点５１ｂまでＹ軸に平行な線５４を引く（ステップＳ８０７）。
【００３３】
なお、線５３を引いている途中で当該線５３がポリゴン３２を構成する線分と交差した場合には、線５３の先端の位置を開始構成点５１ａの方向へ更に数ドットだけ戻す処理を実行したり、最終構成点５１ｂを変更したりするなどの処理を実行する。
そして、第二分割手段１５は、引かれた線５２〜５４によって、ポリゴン３２を分割する（ステップＳ８０７）。
【符号の説明】
【００３４】
１１…ポリゴン分割装置
１２…ハードディスク
１３…分割点選択手段
１４…第一分割手段
１５…第二分割手段
１６…制御手段
【技術分野】
【０００１】
本発明は、ベクトルデータとして記述された電子地図データの一部であるポリゴンを複数に分割する技術に関するものである。
【背景技術】
【０００２】
ベクトルデータとして記述された電子地図データは、直交するＸ軸、Ｙ軸の二次元座標上に定義された１つの構成点のみからなる点データ、二つの構成点とこれら構成点を繋ぐ線（ここで線とは、直線あるいは曲線である）からなる線データ、そして複数の構成点とその構成点を相互に接続する線とによって外形を模ったポリゴンデータの集合体である。この様な電子地図データは、大規模なＧＩＳシステムから携帯用の簡易機器、例えばパーソナルナビゲーションデバイス（PND:Personal
Navigation Device）や携帯ゲーム機にまで利用される。
【０００３】
電子地図データが簡易機器で利用される場合、ポリゴンデータの取り扱いに注意が必要となる。簡易機器に採用されるＣＰＵの処理能力、記憶領域のサイズなどから、ポリゴンデータとして処理できる構成点の数に制限があるからである。例えば、最も簡単な機器構成では許容される構成点の数が３個であり、この場合にはポリゴンデータとしては三角形しか取り扱うことが出来ない。そこで、この様な簡易機器にて複雑な形状のポリゴンデータを取り扱い可能とするための事前の処理として、多数の構成点からなるポリゴンデータを、簡易機器が許容する構成点の数以下となるように分割するポリゴン分割処理が行われる。
【０００４】
例えば、上述した最も簡単な機器構成である簡易機器にて５角形ポリゴンを処理可能とするために、５角形ポリゴンを３個あるいはそれ以上の三角形ポリゴンに分割するのである。
この様なポリゴン分割技術としては各種の手法が開発されており、利用者はその目的に応じて何れかのポリゴン分割技術を選択しあるいは複数のポリゴン分割技術を組み合わせ、複雑なポリゴンデータを所定値以下の構成点からなるポリゴンデータの組み合わせとして扱っている。
【０００５】
その中の一つとして、ベクトルデータの一種であるアウトラインフォント塗りつぶしの際、進入頂点リスト、左右稜線リスト、アクティブエッジリストの生成処理を含めず、処理を高速化するためにポリゴンを分割する技術がる（特許文献１）。この技術では、ポリゴンを分割する線分は例えばＹ軸に平行な線分であり、ポリゴンを左右に分割された２つのポリゴンによって共有する。その一端は分割前の図形の１頂点で、Ｙ座標が極大または極小となる凹頂点である。この様なポリゴン分割を繰り返すことにより、分割終了後の各々のポリゴン形状は、進入頂点および退出頂点が各１個の単純な形状となる。したがって、複雑なアウトラインフォント塗りつぶし処理は、単純な図形塗りつぶし処理の繰り返しによって代替されることになり、簡単な回路により実現される。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開平６−２７９２７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
従来、各種のポリゴン分割技術が開発されているが、その目的は、構成点数の多い複雑な形状のポリゴンデータを回転、拡縮などの図形処理、塗りつぶしなどの表示処理することにある。すなわち、従来のポリゴン分割技術の何れも、構成点数の多いポリゴンデータを構成点が所定値以下のポリゴンデータの組み合わせに変換することを目的としており、分割後のポリゴンデータの構成点数が所定値以下となれば目的を達成することになる。
【０００８】
しかし、近年のデジタル技術、通信技術の進歩によって電子地図データを処理対象とする機器は飛躍的に増加し、かつ、それぞれが互いに通信し合ってデータを共有することで情報処理の効率化を図っている。この様な環境変化により、ある機器での取り扱いに適したようにポリゴン分割を行った後に、他の機器で分割後のポリゴンデータを更に再分割するような事態が頻発することになる。この様な場合において後段の他の機器は、前段の機器で行われたポリゴン分割の結果を単に受け取るだけであり、受け取ったポリゴンデータが単一のポリゴンデータであるかあるいはポリゴン分割した結果物であって複数のポリゴンデータの組み合わせにより単一の複雑なポリゴンデータを表現しているのかを知るすべはない。
【０００９】
このため、例えば互いに接しており、構成点やその構成点相互を接続する線が互いに共通している一方のポリゴンデータを更に再分割する場合、その一方のポリゴンの共通している線上に新たな構成点を設定するなど相互のデータの共通性が崩れる事態が発生するのである。このデータの共通性の崩れは、新たな構成点が座標点に再配置された際にポリゴンの重なりや隙間発生の原因となる。
【００１０】
一例として、従来のポリゴン分割装置を用いて、図１１に示すポリゴン９１を分割する場合を説明する。まず、当該ポリゴン９１を構成する複数の構成点９２から任意の構成点９２ａ，９２ｂを抽出する。次に、これら構成点９２ａ，９２ｂを結ぶ分割線分９３でポリゴン９１を分割して２つのポリゴン９１ａ，９１ｂを生成する。
このように分割されたポリゴン９１ａを、他の装置で任意の構成点数となるように分割する。例えば、図１２に示すように、任意の構成点９２と、構成点９２ａ，９２ｂを結ぶポリゴン９１ａの線分９４に交差する点９５とを繋ぐ分割線分９６で、ポリゴン９１ａを複数のポリゴンに分割する。
【００１１】
すると、図１２の拡大図に示すように、線分９４に交差する点９５が直交するＸ軸９７、Ｙ軸９８の二次元座標上に存在しないことがあるため、線分９４に交差する点９５がＸ軸９７、Ｙ軸９８上の点に設定されることになる。このことは、ポリゴン９１ｂについてもいえる。
【００１２】
したがって、ＰＮＤや携帯端末で、このように分割されたポリゴン９１ａ，９１ｂを表示させた場合、これらポリゴン９１ａ，９１ｂの間に、図１３に示すような隙間９９が生じることになる。このポリゴン９１ａ，９１ｂが湖に関するポリゴンであった場合には、この隙間９９は、描画されない領域となるため、ライン状のノイズとなって地図に表示されることになる。
本発明は、こうした課題を解決することのできるポリゴン分割装置、およびポリゴン分割方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記課題を解決するために、本発明は、直交するＸ軸、Ｙ軸の二次元座標上に定義されたベクトルデータにより地物を表現する電子地図データの一部であって、複数の構成点とその構成点を相互に接続する線とによって外形を模ったポリゴンを複数に分割するポリゴン分割装置であって、ポリゴンデータの構成点が所定値以上であって前記ポリゴンを分割する必要があるとき、そのポリゴンをＸ軸あるいはＹ軸と平行に略二等分する仮想線の端点それぞれに最も近接している前記ポリゴンの構成点を選択する分割点選択手段と、該分割点選択手段により選択された２つの構成点をそれぞれ一方の端点とする、前記仮想線に平行な線分である第一分割線分が一直線上にあるとき、当該第一分割線分により前記ポリゴンを分割する第一分割手段と、前記第一分割線分が一直線上にないとき、前記ポリゴン内部に存在する点であって第一分割線分上に存在する点を新たな構成点とし、前記第一分割線分と相互の新たな構成点を繋ぐ前記仮想線に垂直な第二分割線分とにより前記ポリゴンを分割する第二分割手段とを備えることを特徴とする。
なお、上述した特徴は、本発明の特徴のすべてを列挙したものではなく、これらを要部とする構成（または方法）もまた発明となり得る。
【発明の効果】
【００１４】
本発明によれば、ある機器での取り扱いに適したようにポリゴン分割を行った後に、他の機器で分割後のポリゴンデータを更に再分割する場合であっても、分割後のポリゴンを表示させた場合に隙間が発生することを防止することができる。
【図面の簡単な説明】
【００１５】
【図１】本実施例におけるポリゴン分割装置の構成図。
【図２】ポリゴン分割処理のフローチャート。
【図３】ポリゴン分割処理のフローチャート。
【図４】ポリゴン分割処理の説明図。
【図５】ポリゴン分割処理の説明図。
【図６】ポリゴン分割処理の説明図。
【図７】ポリゴン分割処理の説明図。
【図８】ポリゴン分割処理のフローチャート。
【図９】ポリゴン分割処理の説明図。
【図１０】ポリゴン分割処理の説明図。
【図１１】従来技術の説明図。
【図１２】従来技術の説明図。
【図１３】従来技術の説明図。
【発明を実施するための形態】
【００１６】
以下、本発明を具体化したポリゴン分割装置について説明する。
図１に示すように、本実施例におけるポリゴン分割装置１１はコンピュータであり、記憶手段としてのハードディスク１２、分割点選択手段１３、第一分割手段１４、第二分割手段１５、制御手段１６を備える。
分割点選択手段１３、第一分割手段１４、第二分割手段１５、制御手段１６は、実際には、ポリゴン分割装置１１が有する図示しないＣＰＵ（Central Processing Unit ）がハードディスク１２やメモリ等に記憶されている各種プログラムを実行することにより実現される。
【００１７】
ハードディスク１２には、電子地図データが記憶されている。この電子地図データは、建物の形状、道路の形状、海域の形状、都道府県や市区町村等の領域形状等をベクトルデータとして記述したポリゴンデータを含んでいる。
【００１８】
分割点選択手段１３は、ポリゴンデータの構成点が所定値以上であってそのポリゴンを分割する必要があると判断された場合、そのポリゴンをＸ軸あるいはＹ軸と平行に略二等分する仮想線の端点それぞれに最も近接しているポリゴンの構成点を選択する機能を有する。ここで、所定値は、分割されたポリゴンを利用する装置におけるＣＰＵの処理能力、記憶領域のサイズなどを考慮して決定される値であればよく、任意の値に設定することが可能である。例えば、構成点が数千点である地図データのポリゴンデータを分割する場合には、所定値として８００が設定される。
【００１９】
第一分割手段１４および第二分割手段１５は、ポリゴンを分割する分割処理機能を有する。
第一分割手段１４は、分割点選択手段１３によって選択されたポリゴンにおける２つの構成点をそれぞれ一方の端点とする仮想線に平行な線分である第一分割線分が一直線上にあるとき、その第一分割線分によりポリゴンを分割する機能を有する。
【００２０】
第二分割手段１５は、第一分割線分が一直線上にないとき、ポリゴンの内部であって第一分割線分のそれぞれの他方の端点を新たな構成点とし、相互の新たな構成点を繋ぐ仮想線に垂直な第二分割線分によりそのポリゴンを分割する機能を有する。
制御手段１６は、ポリゴン分割装置１１が備える各手段１２〜１５の動作をメモリ等に記録されている所定のプログラムに基づいて制御する機能を有する。
【００２１】
次に、本実施例におけるポリゴン分割装置１１を用いてポリゴンを分割する処理方法について説明する。
図２に示すように、まず、制御手段１６は、電子地図データに含まれているポリゴンデータをハードディスク１２から読み出す（ステップＳ２０１）。次に、分割点選択手段１３が、ポリゴンの構成点数をカウントするとともに、その構成点数が予め設定されている所定の数よりも多い場合に、そのポリゴンを分割する必要があると判断する（ステップＳ２０２）。一方、構成点数が予め設定されている所定の数よりも少ない場合には、次のポリゴンデータをハードディスク１２から読み出す（ステップＳ２０１）。
【００２２】
分割する必要があると判断された場合、図３に示すように、分割点選択手段１３は、ポリゴン３２の構成点３１のうち、Ｘ軸（またはＹ軸）と平行に略二等分する仮想線３３の端点３４ａ，３４ｂにそれぞれに最も近接しているポリゴンの構成点３１ａ，３１ｂを選択する（ステップＳ２０３）。例えば、分割点選択手段１３は、端点３４ａ，３４ｂの位置からの直線距離が最も短くなる構成点３１を選択する。なお、仮想線３３は、ポリゴン３２の重心点を通る線とすればよい。
【００２３】
次に、第一分割手段１４が、第一分割処理を実行する。図４に示すように、第一分割手段１４は、分割点選択手段１３によって選択された２つの構成点３１ａ，３１ｂをそれぞれ一方の端点としており、仮想線３３に平行な線分であるそれぞれの線分３５ａ，３５ｂが一直線上にあるか否かを判定する（ステップＳ２０４）。線分３５ａ，３５ｂが一直線上にあると判定した場合、換言すれば線分３５ａ，３５ｂが同一線であると判定した場合、第一分割手段１４は、その線分３５ａ，３５ｂ（第一分割線分）によりポリゴン３２を分割する（ステップＳ２０５）。図４の例では、線分３５ａ，３５ｂは一直線上に存在していないため、線分３５ａまたは線分３５ｂによってポリゴン３２が分割されることはない。
【００２４】
なお、第一分割手段１４は、仮想線３３がＹ軸に平行であって、２つの構成点３１ａ，３１ｂのｘ座標が同一である場合に、構成点３１ａ，３１ｂを通る線分によりポリゴン３２を分割するようにしてもよい。また、仮想線３３がＸ軸に平行であって、２つの構成点３１ａ，３１ｂのｙ座標が同一である場合も同様である。
【００２５】
一方、第一分割手段１４によって線分３５ａ，３５ｂが一直線上にないと判定されたときには、第二分割手段１５によって、第二分割処理が実行される。
まず、図５に示すように、第二分割手段１５は、ポリゴン３２の内部に存在する点であって線分３５ａ，３５ｂ上に存在する任意の点を新たな内部構成点３６ａ，３６ｂとして選択する（ステップＳ２０６）。なお、内部構成点３６ａ，３６ｂについてはこれら内部構成点３６ａ，３６ｂのｙ座標が同一となるような点が選択される。
【００２６】
次に、図６に示すように、第二分割手段１５は、構成点３１ａと内部構成点３６ａとを繋ぐ線３７ａ、構成点３１ｂと内部構成点３６ｂとを繋ぐ線３７ｂ、および内部構成点３６ａと内部構成点３６ｂとを繋ぐ線３８（第二分割線分）によって、ポリゴン３２を分割する（ステップＳ２０７）。なお、内部構成点３６ａと内部構成点３６ｂとを繋ぐ線３８は、仮想線３３に対して垂直な線となる。
【００２７】
次に、制御手段１６は、第一分割手段１４または第二分割手段１５によって分割されたそれぞれのポリゴンについて構成点数をカウントするとともに、当該構成点数と予め設定されている所定の数とを比較する（ステップＳ２０８）。構成点数が所定の数よりも多い場合には、制御手段１６は、当該構成点数が所定の数よりも多いポリゴンについて、更なる分割処理を実行する（ステップＳ２０３）。なお、制御手段１６は、分割されたポリゴンをハードディスク１２に記憶する。
【００２８】
そして制御手段１６は、電子地図データに含まれるすべてのポリゴンについて分割処理を実行したか否かを判定する（ステップＳ２０９）。分割処理が実行されていないポリゴンが存在していると判定した場合、制御手段１６は、当該ポリゴンをハードディスク１２から読み出すとともに、上述した分割処理を当該読み出されたポリゴンに対して実行する。一方、すべてのポリゴンについて分割処理を実行したと判定した場合には、制御手段１６は分割処理を終了する。
【００２９】
（実施例の効果）
図７に示すように、本実施例におけるポリゴン分割装置１１によって分割されたポリゴン３２を、他の装置において更に任意の分割線４１で複数のポリゴンに分割した場合であって、ポリゴン３２を表示させた場合にポリゴン間に図１３に示すような隙間が生じることはない。これは、ポリゴン分割装置１１によって分割されたポリゴン３２ａにおける構成点３１ａから構成点３１ｂまでの線分であって、新たな構成点３１ａ，３１ｂを通る線分の上の点は、すべて座標線４２，４３で規定される座標線上に存在している。そのため、分割線４１をなす一方の端点として当該線分上の点が指定されたとしても、当該端点は必ずＸ軸４２、Ｙ軸４３の二次元座標上に存在するためである。
【００３０】
（他の実施例）
上述した実施例における分割処理については、以下の方法で実現してもよい。
図８、図９に示すように、まず、第一分割手段１４は、ポリゴン３２の構成点５１のうち、任意の１点を開始構成点５１ａとして抽出する（ステップＳ８０１）。次に、第一分割手段１４は、構成点５１の数をカウントして、ほぼ開始構成点５１ａと反対側の位置に存在する構成点５１を終了構成点５１ｂとして抽出する（ステップＳ８０２）。
【００３１】
次に、第一分割手段１４は、開始構成点５１ａからポリゴン３２の内部に向けてＹ軸に平行な線５２を引く（ステップＳ８０３）。そして、第一分割手段１４は、当該線５２がポリゴン３２を構成する線分と交差する点が終了構成点５１ｂを含む何れかの構成点５１であるか否かを判定する（ステップＳ８０４）。交差する点が構成点５１である場合には、第一分割手段１４は、開始構成点５１ａとその構成点５１とを繋いだ線でポリゴン３２を分割する（ステップＳ８０５）。
【００３２】
一方、交差する点が構成点５１でない場合には、第二分割手段１５が、線５２の先端の位置を開始構成点５１ａの方向へ数ドット（例えば２ドット）だけ戻すとともに、図１０に示すように、その戻した位置から終了構成点５１ｂに近づく方向へ、線５２と垂直な線５３を引く（ステップＳ８０６）。つまり線５３は、Ｘ軸に平行な線である。そして、第二分割手段１５は、線５３のｘ座標が終了構成点５１ｂのｘ座標と一致する位置まで線５３を引くとともに、最後に、当該位置から終了構成点５１ｂまでＹ軸に平行な線５４を引く（ステップＳ８０７）。
【００３３】
なお、線５３を引いている途中で当該線５３がポリゴン３２を構成する線分と交差した場合には、線５３の先端の位置を開始構成点５１ａの方向へ更に数ドットだけ戻す処理を実行したり、最終構成点５１ｂを変更したりするなどの処理を実行する。
そして、第二分割手段１５は、引かれた線５２〜５４によって、ポリゴン３２を分割する（ステップＳ８０７）。
【符号の説明】
【００３４】
１１…ポリゴン分割装置
１２…ハードディスク
１３…分割点選択手段
１４…第一分割手段
１５…第二分割手段
１６…制御手段
【特許請求の範囲】
【請求項１】
直交するＸ軸、Ｙ軸の二次元座標上に定義されたベクトルデータにより地物を表現する電子地図データの一部であって、複数の構成点とその構成点を相互に接続する線とによって外形を模ったポリゴンを複数に分割するポリゴン分割装置であって、
ポリゴンデータの構成点が所定値以上であって前記ポリゴンを分割する必要があるとき、そのポリゴンをＸ軸あるいはＹ軸と平行に略二等分する仮想線の端点それぞれに最も近接している前記ポリゴンの構成点を選択する分割点選択手段と、
該分割点選択手段により選択された２つの構成点をそれぞれ一方の端点とする、前記仮想線に平行な線分である第一分割線分が一直線上にあるとき、当該第一分割線分により前記ポリゴンを分割する第一分割手段と、
前記第一分割線分が一直線上にないとき、前記ポリゴン内部に存在する点であって第一分割線分上に存在する点を新たな構成点とし、前記第一分割線分と相互の新たな構成点を繋ぐ前記仮想線に垂直な第二分割線分とにより前記ポリゴンを分割する第二分割手段と
を備えることを特徴とするポリゴン分割装置。
【請求項２】
直交するＸ軸、Ｙ軸の二次元座標上に定義されたベクトルデータにより地物を表現する電子地図データの一部であって、複数の構成点とその構成点を相互に接続する線とによって外形を模ったポリゴンを複数に分割するポリゴン分割装置を用いたポリゴン分割方法であって、
コンピュータが、
ポリゴンデータの構成点が所定値以上であって前記ポリゴンを分割する必要があるとき、そのポリゴンをＸ軸あるいはＹ軸と平行に略二等分する仮想線の端点それぞれに最も近接している前記ポリゴンの構成点を選択する分割点選択工程と、
該分割点選択工程により選択された２つの構成点をそれぞれ一方の端点とする、前記仮想線に平行な線分である第一分割線分が一直線上にあるとき、当該第一分割線分により前記ポリゴンを分割する第一分割工程と、
前記第一分割線分が一直線上にないとき、前記ポリゴン内部に存在する点であって第一分割線分上に存在する点を新たな構成点とし、前記第一分割線分と相互の新たな構成点を繋ぐ前記仮想線に垂直な第二分割線分とにより前記ポリゴンを分割する第二分割工程と
を実行することを特徴とするポリゴン分割方法。
【請求項１】
直交するＸ軸、Ｙ軸の二次元座標上に定義されたベクトルデータにより地物を表現する電子地図データの一部であって、複数の構成点とその構成点を相互に接続する線とによって外形を模ったポリゴンを複数に分割するポリゴン分割装置であって、
ポリゴンデータの構成点が所定値以上であって前記ポリゴンを分割する必要があるとき、そのポリゴンをＸ軸あるいはＹ軸と平行に略二等分する仮想線の端点それぞれに最も近接している前記ポリゴンの構成点を選択する分割点選択手段と、
該分割点選択手段により選択された２つの構成点をそれぞれ一方の端点とする、前記仮想線に平行な線分である第一分割線分が一直線上にあるとき、当該第一分割線分により前記ポリゴンを分割する第一分割手段と、
前記第一分割線分が一直線上にないとき、前記ポリゴン内部に存在する点であって第一分割線分上に存在する点を新たな構成点とし、前記第一分割線分と相互の新たな構成点を繋ぐ前記仮想線に垂直な第二分割線分とにより前記ポリゴンを分割する第二分割手段と
を備えることを特徴とするポリゴン分割装置。
【請求項２】
直交するＸ軸、Ｙ軸の二次元座標上に定義されたベクトルデータにより地物を表現する電子地図データの一部であって、複数の構成点とその構成点を相互に接続する線とによって外形を模ったポリゴンを複数に分割するポリゴン分割装置を用いたポリゴン分割方法であって、
コンピュータが、
ポリゴンデータの構成点が所定値以上であって前記ポリゴンを分割する必要があるとき、そのポリゴンをＸ軸あるいはＹ軸と平行に略二等分する仮想線の端点それぞれに最も近接している前記ポリゴンの構成点を選択する分割点選択工程と、
該分割点選択工程により選択された２つの構成点をそれぞれ一方の端点とする、前記仮想線に平行な線分である第一分割線分が一直線上にあるとき、当該第一分割線分により前記ポリゴンを分割する第一分割工程と、
前記第一分割線分が一直線上にないとき、前記ポリゴン内部に存在する点であって第一分割線分上に存在する点を新たな構成点とし、前記第一分割線分と相互の新たな構成点を繋ぐ前記仮想線に垂直な第二分割線分とにより前記ポリゴンを分割する第二分割工程と
を実行することを特徴とするポリゴン分割方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１１−２０３７８５（Ｐ２０１１−２０３７８５Ａ）
【公開日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願番号】特願２０１０−６７８４８（Ｐ２０１０−６７８４８）
【出願日】平成２２年３月２４日（２０１０．３．２４）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
【公開日】平成２３年１０月１３日（２０１１．１０．１３）
【国際特許分類】
【出願日】平成２２年３月２４日（２０１０．３．２４）
【出願人】（５９７１５１５６３）株式会社ゼンリン (155)
【Ｆターム（参考）】
[ Back to top ]