地図ポリゴン描画方法及び装置
【課題】ポリゴン表示を円滑化するため、周縁を構成する要素点のうち、ポリゴンの周辺形状の少ない所定の条件を満たす部分を間引くとき、隣接ポリゴン間に隙間が発生しない「ポリゴン描画方法及び装置」とする。
【解決手段】描画地図の全のポリゴンについて、各ポリゴンの周縁を形成する要素点を取得し、各ポリゴンについしてエッジを設定する。このエッジを構成する要素点について、ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たすとき、その要素点を削除する間引処理を行う。要素点を削除する間引処理を行ったとき、そのエッジが現在間引処理を行っているポリゴンに隣接するポリゴンを構成するエッジと一致するとき、その要素点も自動的に削除されるので前記削除が隣接するポリゴンにも反映される。この処理を全エッジ全ポリゴンに対して行う。
【解決手段】描画地図の全のポリゴンについて、各ポリゴンの周縁を形成する要素点を取得し、各ポリゴンについしてエッジを設定する。このエッジを構成する要素点について、ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たすとき、その要素点を削除する間引処理を行う。要素点を削除する間引処理を行ったとき、そのエッジが現在間引処理を行っているポリゴンに隣接するポリゴンを構成するエッジと一致するとき、その要素点も自動的に削除されるので前記削除が隣接するポリゴンにも反映される。この処理を全エッジ全ポリゴンに対して行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディスプレイに地図を表示するに際して、地図の背景となるポリゴンを描画するとき、ポリゴンの周縁を形成する要素点を間引いて表示する地図ポリゴン描画方法及びその方法を実施する装置に関し、特に隣接するポリゴンのうち片側のポリゴンで間引処理を行うのに対して他側では間引処理を行わないことにより生じる隙間を無くすことができるようにした地図ポリゴン描画方法、及びその方法を実施する装置に関する。
【背景技術】
【０００２】
地図を表示するには、地図帳として表示する以外に、近年は地図の電子データ化により、パソコンやナビゲーション装置を初め、携帯情報端末、携帯電話等々のディスプレイに表示することが多くなっている。このような地図の電子データ化によって、世界中任意の地点について、任意の縮尺で、しかも好みの表示手法によって自由に表示することができるようになっている。
【０００３】
電子データ化された地図はＤＶＤやメモリカード等の各種データ記録媒体に記録する以外に、インターネット等を通じて各種情報機器に取り込むことができるが、このような地図データは、多くの場合各種の縮尺レベルに応じて適当な大きさの経度幅及び緯度幅に区切られており、道路等は経度及び緯度で表現されたノードの座標集合としている。このような地図の表示に際しては、道路表示レイヤの他、地図画面上に道路、建築物、施設、海や河川、森、山岳等の地図上の背景を表示するポリゴン表示レイヤ、更には市町村名などの行政区画名、道路名、交差点名及び施設の名前やその施設のアイコン等の、文字や地図記号を表示するための情報データ表示レイヤ等、多くのレイヤのデータを重ねて表示している。
【０００４】
この中のポリゴンを表示するデータは、地図を利用者にとってわかりやすく、且つ親しみ易く、見栄えがよいように表示するために重要な表示データとなっている。このポリゴンデータは、衛星写真や測量地図を元に整備されており、このポリゴンデータを地図上に表示する際には、その表示データ処理に多大な負担をかけることがあり、地図描画性能を悪化させるため、できる限り地図描画処理負担を軽くするように、ポリゴンの周縁を構成する要素点の間引き処理を行っている。
【０００５】
そのようなポリゴンの周縁を形成する要素点の間引処理に際しては、主として図１１に示すように行われている。図１１に示す例においては、同図（ａ）に示すようなポリゴンＰが存在する時、その一部が同図の要素点２の部分が突出しているとき、その突出部の要素点を間引くか否かは、ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たすときにその要素点を削除して間引く。その時の条件としては例えば同図（ｂ）に示すようにして行う。
【０００６】
即ち第１に、要素点２を中心としてその両隣の要素点１と要素点３との関係を、要素点２における角度αを計測し、そのαが例えば１７０度等の所定の角度αaと、１８０度の間に存在するかを判別する。
【０００７】
第２に、図１１に示す例においては、要素点２を挟む両隣の要素点１と要素点３を結ぶ直線に、要素点２から垂線を降ろし、そのときの長さＬ、即ち要素点２の前記直線との距離を計測して、その長さＬが最大値の閾値としての所定の長さＬa以下であるかを判別して、両条件を満たす時、この要素点２を間引くことにしている。こののような判別条件は、前記第１の条件を満たす場合でも、要素点２の両隣の要素点１と３の距離が大きい時は、この要素点は間引くことが好ましくないものとする。
【０００８】
その処理に際して、前記角度αは、反時計回りを順方向とし、ポリゴン側の角度を測定している。したがって、図１１（ａ）において、図示の例では要素点２がポリゴンにとって突出しているため、角度αは１８０度以下であるのに対して、図示とは逆に要素点２が凹部であるポリゴンの場合は、角度αは１８０度を超えるため、その場合は要素点２の間引き処理を行わないことになる。
【０００９】
上記処理の結果、図１１（ｃ）のように、（１）要素点２について隣接要素点１及び３間の角度αがα１であって、所定角度αａよりも大きく、前記１８０度以下の時、であって、（２）隣接要素点間を結ぶ直線への垂線の長さＬ１が所定の長さＬaよりも小さい時には、同図（ｄ）に示すように要素点を間引き、要素点１と３のみとする。このような間引を行う要素点を選択する条件を満たす要素点２の部分は、ポリゴンの周囲形状の変化が少ない部分ということができる。なお、間引処理を行う条件は、上記以外に種々の手法が提案されている。
【００１０】
前記のような要素点の間引処理の結果、ポリゴンの多くの要素点が間引かれ、ポリゴンの表示処理負担が軽くなり、地図全体の表示が速くなるため、特定地点の地図表示速度を向上し、また現在の地図表示からのスクロール表示や、地図の表示縮尺の変更等において、円滑な表示ができるようになる。
【００１１】
なお、地図表示におけるポリゴンの表示に際して、ポリゴン間に隙間が発生する時、その隙間領域を抽出し、併合釦を操作することにより、隣接ポリゴンに合体して隙間を埋めて修正を行うことができるようにした技術は、特許文献１に開示されている。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２００７−２１３５２４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
前記のように、電子データによって地図を描画する時、その背景となるポリゴンの表示処理負担を軽くするため、ポリゴンの周縁を形成する要素点を、前記のような所定の条件を満たす時に間引く技術では、例えば図１２（ｂ）に示すような隙間Ｓa、Ｓｂを生じることがある。
【００１４】
即ち図示の例では、最初は同図（ａ）に示すように、全ての要素点を用いてポリゴンＡ、Ｂ、Ｃを描画する時には各ポリゴン間で隙間が発生することはないが、前記のような要素点の間引処理を行うとき、ポリゴンＡがその僅かの突出部分で要素点の間引処理を行った部分で、ポリゴンＢは凹部となり、この部分での要素点の間引は行わなかった例を示している。
【００１５】
同様に同図の例においては、ポリゴンＡとポリゴンＣとの関係において、ポリゴンＣがその僅かの突出部分で要素点の間引処理を行ったとき、その部分でポリゴンＡは凹部となっており、この部分での要素点の間引は行わなかった例を示している。その結果ここには隙間Ｓｂが発生している。
【００１６】
このようにして形成されたポリゴンの要素点の間引処理によって発生したポリゴン間の隙間は、例えば図１３（ｂ）に示すような海ポリゴンにおいて、１つの海ポリゴンが他の海ポリゴンと隣接して繋がっている時、そのポリゴンの境界の一部Ｒにおいて、同図のように広域地図表示状態ではほとんどわからないものの、同図（ａ）のように拡大して表示する時には、図中Ｒで示すよな隙間ＳａとＳｂが、周囲の海の色が存在しない、白地となって見えてくる。
【００１７】
このようなポリゴン間の隙間は、地図自体の表示としては大きな問題は生じないものの、地図を拡大する程この隙間は目立ち、地図データの安っぽさを印象づけて見栄えが極めて良くない。そのため、前記特許文献のようにその隙間を埋める処理を行うことも提案されているが、その処理のためには人為的な操作を必要とし、全てのポリゴン間の隙間を無くすには膨大な手数を要する。
【００１８】
なお、上記のようにポリゴンの表示を円滑にするために、ポリゴン周縁を形成する要素点を間引く処理は、地図データを提供する企業が地図データに対して処理を行い、このように処理した地図データを提供する以外に、特に間引処理を行っていない生のデータが提供される時、そのデータに基づいて地図を表示する、例えばパソコンやナビゲーション装置で間引処理ソフトによって処理する場合が存在しうる。
【００１９】
したがって本発明は、地図の背景となるポリゴンの表示に際して、ポリゴン表示の処理負担を軽減するためにポリゴンの周縁を形成する要素点を所定の条件で間引く時、従来の条件では隣接するポリゴン間に隙間が発生し、地図の見栄えが悪くなる問題を、手数を要することなく、容易に解消することができるようにした地図ポリゴン描画方法、及びその方法を実施する装置に関する。
【課題を解決するための手段】
【００２０】
本発明に係る地図ポリゴン描画方法は、前記課題を解決するため、描画する地図に含まれる全てのポリゴンを抽出し、前記抽出したポリゴンについて、各ポリゴンの周縁を形成する要素点を取得し、各ポリゴンについて相互に隣り合う複数の要素点からなる部分にエッジを設定し、前記エッジを構成する要素点について、ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たすとき、地図表示用要素点として削除する間引処理を行い、前記要素点を削除する間引処理を行ったとき、当該要素点が現在間引処理を行っているポリゴンに隣接するポリゴンを構成する要素点と一致するとき、当該隣接するポリゴンの要素点も削除する間引処理を行い、前記間引処理を、指定したエッジを構成する全ての要素点に対して行った後、指定したポリゴンを構成する他のエッジに対しても前記間引処理を行い、前記指定したポリゴンの全てのエッジに対して前記間引処理を行い、その後、前記抽出したポリゴンの全てに対して前記要素点の間引処理を行い、前記間引処理を行ったデータによりポリゴンを描画することを特徴とする。
【００２１】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記指定したポリゴンの全てのエッジに対して前記間引処理を行った後は、当該ポリゴンに隣接するポリゴンを順に指定して前記間引処理を行うことを特徴とする。
【００２２】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記エッジの設定に際しては、当該エッジの前後端の要素点については、少なくとも前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たす要素点以外の要素点を選択することを特徴とする。
【００２３】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記エッジの設定に際しては、当該エッジの前後端の要素点については、前記所定の条件のほか、隣接するポリゴンが変化する要素点を選択することを特徴とする。
【００２４】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記エッジを設定したとき、当該エッジが隣接するポリゴンのエッジと共通するときには、当該エッジを構成する要素点について、両ポリゴンにおいてそれぞれ対応する要素点についての対応データを作成し、一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データによって他方のポリゴンの要素点を削除する間引処理を行うことを特徴とする。
【００２５】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データにより他方のポリゴンの要素点の間引処理を行う際には当該要素点については間引処理を行わないことを特徴とする。
【００２６】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、指示した要素点について隣接する要素点で形成される角度が所定角度以内であることを特徴とする。
【００２７】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、隣接する要素点を結ぶ直線に降ろした垂線の長さが所定以内であることを特徴とする請求項１記載のポリゴン描画方法。
【００２８】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする。
【００２９】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする。
【００３０】
また、本発明に係る地図ポリゴン描画装置は、前記課題を解決するため、描画する地図に含まれる全てのポリゴンを抽出する間引処理ポリゴン抽出手段と、前記間引処理ポリゴン抽出手段で抽出したポリゴンについて、各ポリゴンの周縁を形成する要素点を取得するポリゴン周縁形成要素点取得手段と、前記間引処理ポリゴン抽出手段で抽出した各ポリゴンについて、相互に隣り合う複数の要素点からなる部分にエッジを設定するポリゴン周縁エッジ設定手段と、前記ポリゴン周縁エッジ設定手段で設定したエッジを構成する要素点について、ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たすとき、地図表示用要素点として削除する間引処理を行う要素点間引処理手段とを備え、前記要素点間引処理手段では、要素点を削除する間引処理を行ったとき、当該要素点が現在間引処理を行っているポリゴンに隣接するポリゴンを構成する要素点と一致するときには、当該隣接するポリゴンの要素点も削除する間引処理を行い、前記間引処理を、指定したエッジを構成する全ての要素点に対して行った後、指定したポリゴンを構成する他のエッジに対しても前記間引処理を行い、前記指定したポリゴン法の全てのエッジに対して前記間引処理を行い、その後、前記抽出したポリゴンの全てに対して前記要素点の間引処理を行うことによりポリゴンを描画するデータを作成することを特徴とする。
【００３１】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記要素点間引処理手段では、前記指定したポリゴンの全てのエッジに対して前記間引処理を行った後は、当該ポリゴンに隣接するポリゴンを順に指定して前記間引処理を行うことを特徴とする。
【００３２】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記ポリゴン周縁エッジ設定手段では、前記エッジの設定に際して、当該エッジの前後端の要素点については、少なくとも前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たす要素点以外の要素点を選択することを特徴とする。
【００３３】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記ポリゴン周縁エッジ設定手段では、前記エッジの設定に際して、当該エッジの前後端の要素点については、前記所定の条件のほか、隣接するポリゴンが変化する要素点を選択することを特徴とする。
【００３４】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記要素点間引処理手段では、前記ポリゴン周縁エッジ設定手段でエッジを設定したとき、当該エッジが隣接するポリゴンのエッジと共通するときには、当該エッジを構成する要素点について、両ポリゴンにおいてそれぞれ対応する要素点についての対応データを作成し、
一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データによって他方のポリゴンの要素点を削除する間引処理を行うことを特徴とする。
【００３５】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記要素点間引処理手段では、前記一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データにより他方のポリゴンの要素点の間引処理を行う際には当該要素点については間引処理を行わないことを特徴とする。
【００３６】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、指示した要素点について隣接する要素点で形成される角度が所定角度以内であることを特徴とする。
【００３７】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、隣接する要素点を結ぶ直線に降ろした垂線の長さが所定以内であることを特徴とする。
【００３８】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする。
【００３９】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする。
【発明の効果】
【００４０】
本発明は上記のように構成したので、地図の背景となるポリゴンの表示に際して、ポリゴン表示の処理負担を軽減するためにポリゴンの周縁を形成する要素点を所定の条件で間引く時、従来の条件では隣接するポリゴン間に隙間が発生し、地図の見栄えが悪くなる問題を、手数を要することなく、容易に解消することができるようになる。
【図面の簡単な説明】
【００４１】
【図１】本発明の実施例の機能ブロック図である。
【図２】同実施例の作動フロー図である。
【図３】同実施例で行う要素点間引処理の作動フロー図である。
【図４】ポリゴン毎の要素点の例を示す図である。
【図５】隣接ポリゴンのエッジ設定処理の例を示す図である。
【図６】ポリゴン毎のエッジの要素点対応表の例を示す図である。
【図７】ポリゴンＡの間引処理の例を示す図である。
【図８】その後行われるポリゴンＢの間引処理の例を示す図である。
【図９】その後行われるポリゴンＣの間引処理の例を示す図である。
【図１０】本発明による間引処理前と処理後の状態を示す図である。
【図１１】従来から提案されているポリゴン構成要素点の間引処理例を示す図である。
【図１２】同処理の結果ポリゴン間に隙間が生じる状態の説明図である。
【図１３】従来ポリゴン間に隙間が生じる実際例を示す図である。
【発明を実施するための形態】
【実施例】
【００４２】
本発明の実施例を図面に沿って説明する。図１は本発明における地図ポリゴン描画装置において、特にポリゴンの周縁を形成する要素点の間引処理を行う時、隣接するポリゴン間に隙間が発生しないようにするための処理を行う機能ブロック図を主として示しており、本発明を各種の態様で実施することができるようにした機能ブロック図を示している。なお、同図において、各機能を行う機能部は、それぞれ各機能を行う手段ということができる。
【００４３】
図１の表示ポリゴンの周縁を形成する要素点の間引処理を行う装置の例においては、主として要素点の間引処理を行う対象を選択する間引処理対象選択部１と、その間引処理対象選択部１で選択した間引処理対象について、実際に間引処理を行う要素点間引処理部２とを備えている。
【００４４】
図１の例えば前記両者が互いに連携して作動し、後述するように間引処理対象選択部１で選択したポリゴン、その中のエッジ、それを構成する要素点について間引処理を行うと、同じエッジの次の要素点、同じエッジの全ての要素点に対する処理が終了するとその次のエッジについて同様の処理を行い、そのエッジの処理が終了するとそのポリゴンの他のエッジを順に選択し、同様にして今回の処理を必要とする他のポリゴンに対して処理を行うことにより完了するようにしている。
【００４５】
間引処理対象選択部１には、これから処理を行おうとする地図について、その地図に含まれる全てのポリゴンを抽出するための間引処理ポリゴン抽出部３を備える。間引処理用ポリゴン指定部４では、最終的にその地図の全てのポリゴンを指定することとなるが、順に処理を行うために適宜の順に処理するポリゴンの指定を行う。
【００４６】
ポリゴン周縁形成要素点取得部５では、指定したポリゴンについて、また後述するようにその指定ポリゴンに直接隣接するポリゴンについて、それらのポリゴンの周縁を形成する要素点を全て取得する。それらのデータは従来より、各ポリゴンを表示するための元のデータに整理して記録されている。
【００４７】
隣接ポリゴン検出部６では、前記のように間引処理用ポリゴン指定部４で指定したポリゴンについて、隣接するポリゴンを検出する。それらのポリゴンについても前記のようにポリゴン周縁形成要素点取得部５によって、要素点を取得する処理がなされる。その結果、例えば前記従来例として示した図１２（ａ）と同様の例を示す図４（ａ）のように、間引処理用ポリゴン指定部４で指定するポリゴンがポリゴンＡである時、隣接ポリゴン検出部６ではポリゴンＢとポリゴンＣを検出する。
【００４８】
また、前記ポリゴン周縁形成要素点取得部４では、ポリゴンＡについては要素点Ａ１〜Ａ２４の２４個の要素点を取得し、ポリゴンＢについてはＢ１〜Ｂ１７の１７個の要素点を取得し、ポリゴンＣについてはＣ１〜Ｃ１８の１８個の要素点を取得している。
【００４９】
ポリゴン周縁エッジ設定部７では、間引処理用ポリゴン指定部３で指定したポリゴンと、隣接ポリゴン検出部６で検出したポリゴンについて、ポリゴン周縁を形成するエッジを設定する。この時の「エッジ」とは、各ポリゴンについて隣接する要素点が例えば１０度以上折れ曲がっている要素点、或いは大きな曲折はないものの、その部分で隣接するポリゴンが変わる部分等の予め設定した条件の特徴的な要素点間を結ぶ周縁部分を検出する。それにより、前記のような「エッジ」を決定する。
【００５０】
このようなエッジの検出処理により、前記図４の例においては、図５に示すようにポリゴンＡについて、要素点Ａ１〜Ａ８がほぼ直線状態のためこれをエッジ１とする。このエッジに対してポリゴンＡにおける反時計回りを順方向として、同様に要素点Ａ８〜Ａ１４についてはエッジ２とする。
【００５１】
また、要素点Ａ１６部分については１０度以下の折曲であるときにはこれをエッジの端部とはせず、要素点Ａ１７部分については、隣接するポリゴンがポリゴンＢからポリゴンＣに変わるため、これをエッジの端部として、要素点Ａ１４〜Ａ１７をエッジ３とする。要素点Ａ１８部分については、前記要素点Ａ１６と同様に、例えば１０度以下のわずかな折曲である時にはこれをエッジの端部とはせず、したがって要素点Ａ１７〜Ａ２０をエッジ４とする。また、要素点Ａ２０〜Ａ１については、ほぼ直線上であるのでこの周縁部分をエッジ５としている。
【００５２】
同様に隣接ポリゴンであるポリゴンＢについては、ポリゴンＡで設定したエッジ３は共通するエッジであるので、要素点Ｂ１〜Ｂ４をエッジ３の要素点とする。このエッジからポリゴンＢにとって順方向に、要素点Ｂ４〜Ｂ６をエッジ６とし、要素点Ｂ６〜Ｂ１０をエッジ７とし、要素点Ｂ１２部分の折曲が小さいことによりこれはエッジの端部とはせず、したがって要素点Ｂ１０〜Ｂ１４をエッジ８とする。
【００５３】
ポリゴンＢの要素点Ｂ１４〜Ｂ１についてはほぼ直線状であるのでこれをエッジ９とする。このエッジ９はポリゴンＡに隣接するポリゴンでありポリゴンＢにも隣接するポリゴンＣにおける、要素点Ｃ４〜Ｃ８と共通して構成される。
【００５４】
ポリゴンＣについては、前記ポリゴンＡのエッジ４について、ポリゴンＡにおいては要素点Ａ１７〜Ａ２０が構成しているのに対して、要素点Ｃ１〜４が共通して構成している。ポリゴンＣの要素点Ｃ４〜Ｃ８については、前記のようにポリゴンＢの要素点Ｂ１４〜Ｂ１と共にエッジ９を構成している。
【００５５】
要素点Ｃ１１部分については曲がりが少ないためこれをエッジの端部とはせず、要素点Ｃ８〜Ｃ１５をエッジ１０とする。また、要素点ＣＣ１５〜Ｃ１はエッジ１１とする。上記のようにして、指定ポリゴンＡと、それに隣接するポリゴンであるポリゴンＢとポリゴンＣについて、一連のエッジを設定する。
【００５６】
図１のポリゴン周縁エッジ設定部７では前記のようなエッジの設定を行い、エッジ構成要素点検出部８では前記のような各エッジが構成される各ポリゴンの要素点を検出する。間引処理エッジ指示部９では、前記間引処理用ポリゴン指定部４で指定したポリゴンと、隣接ポリゴン検出部６で検出したポリゴンについて、間引処理を行うエッジの指示を行う。
【００５７】
間引処理要素点指定部１０では、間引処理エッジ指示部９で指示したエッジについて、そのエッジを構成する要素点を順に指示する。このようにして、例えば現在間引処理用ポリゴン指定部４で指定したポリゴンについて要素点の間引処理を行う時、間引処理用エッジ指示部９ではそのポリゴンを構成するエッジを順に指示し、間引処理要素点指示部１０では、そのエッジについてそのポリゴンにおいてエッジを構成する要素点を順に指示する。その後間引処理するポリゴンについて、指定ポリゴンのエッジを全て処理した後は、隣接ポリゴンについて同様の間引処理を行うエッジ及びそれを構成する要素点の間引処理を行い、最終的に全てのポリゴンの処理がなされる。
【００５８】
要素点間引処理部２では、前記のように指示された要素点について、所定の条件を満たすものを間引く処理を行うものであり、基本的には前記従来例で示した図１１の処理を行う。その中の間引可否判別処理部１１では要素点を間引くか否かを判別する処理を行うものであり、その中の隣接要素点間角度計測部１２で計測した、前記図１１の隣接要素点間角度である角度αを計測する。その計測値に基づき、隣接要素点間角度所定域内判別部１３で、図１１（ｂ）（ｃ）に示すように、また同図の説明で述べたように、条件（１）αa＜α１≦１８０度を満たすかどうかを判別する。
【００５９】
また、隣接要素点間直線への垂線長さ計測部１８では、図１１（ｂ）（ｃ）に示すように、また同図の説明で述べたように、隣接する要素点を結ぶ直線への垂線の長さＬ１について、所定の長さＬaより短いか、即ちＬ１＜Ｌaであるか否かを判別する。したがって間引可否判別処理部１１では、前記間引条件（１）と’（２）の条件を満たすか否かを判別し、全て満たす時には間引処理を行う。
【００６０】
間引フラグ処理部１６では、前記間引可否判別処理部１０で、特定の要素点について間引く旨の判別を行った時、図示の例では地図描画データとしてそれを間引いて描画するデータを形成するため、その要素点に間引フラグを立てる。その後このようにして全てのポリゴンについて、全てのエッジの全ての要素点の間引可否判別を行い、間引フラグ処理を行った後は、ポリゴン表示データ形成部１８でポリゴンの表示を行うデータを形成する。
【００６１】
前記のような処理を行う結果、図１（ａ）に示すように多数の要素点からなるポリゴンについて同図（ｃ）に示すように最小限の要素点となり、その際に隣接ポリゴンが共通して構成するエッジについてはｍ、同図においてエッジ３及びエッジ４に示すように、隣接するポリゴンの内、片方で間引処理が行われた時には、他側の間引の判別にかかわらず、間引処理を行うこととなり、隣接するポリゴン間に前記図１３（ａ）に示すような隙間を生じることが無くなる。
【００６２】
これらの間引処理を図２及び図３の作動フローに従い、より詳細に順に説明する。図２の表示ポリゴン周縁形成要素点の間引処理の例においては、最初間引処理するポリゴンの抽出から始めている（ステップＳ１）。この処理は図１の間引処理ポリゴン抽出部３で前記のようにして行っている。
【００６３】
その後間引処理するポリゴンを順に指定する（ステップＳ２）。この処理は図１の間引処理用ポリゴン指定部４で行っている。次いで指定ポリゴンの要素点を取得する（ステップＳ３）、この処理については図１のポリゴン周縁形成要素点取得部５で、間引処理用ポリゴン指定部４で指定したポリゴンについて要素点を取得することにより行っている。
【００６４】
次いで、指定するポリゴンについて隣接するポリゴンを検出する（ステップＳ４）。この処理は図１の隣接ポリゴン検出部６において前記のようにして行っている。その後隣接ポリゴンの要素点を取得する（ステップＳ５）。この処理は図１のポリゴン周縁形成要素点取得部５において、隣接ポリゴン検出部６で検出したポリゴンについて、要素点を検出することにより行っている。このような処理により、前記のように図４に示すような各ポリゴンについて、要素点を取得する。
【００６５】
その後指定ポリゴンに隣接するポリゴンの共通要素点を含むポリゴン周縁のエッジを設定する（ステップＳ６）。この処理は図１のポリゴン周縁エッジ設定部７で前記のようにして行っている。その結果図５に示すようなエッジ１〜エッジ１１を設定することも前記の通りである。
【００６６】
次いで各エッジについて、ポリゴン毎の要素点を対応付ける（ステップＳ７）。この処理は図６に示しており、ポリゴンＡについてはエッジ１〜エッジ５が存在し、それらのエッジを構成する要素点は全て順方向に対応することを示している。同様にポリゴンＢについては、エッジ３、６、７、８、９が存在し、それを構成する要素点はエッジ３についてはポリゴンＡがＡ１４〜Ａ１７と反時計方向で順方向であるのに対して、その要素点にそれぞれ対応するポリゴンＢの要素点はＢ４、３、２、１と逆方向に対応していることを示している。ポリゴンＢについてはその他のエッジは順方向となっている。
【００６７】
ポリゴンＣについては、エッジ４はポリゴンＡの要素点が順方向であるのに対して、前記と同様の対応によってポリゴンＣの要素点は逆方向となる。同様にエッジ９についてはポリゴンＢが順方向である時、ポリゴンＣについては逆方向となる。ポリゴンＣのその他のエッジについては順方向である。
【００６８】
各ポリゴンを構成するエッジについて、その要素点をそれぞれエッジ１〜１１について示している。ここで例えばエッジ３についてはポリゴンＡのエッジ３と、ポリゴンＢのエッジ３が共通し、エッジ４についてはポリゴンＡのエッジ４とポリゴンＣのエッジ４が共通していることを示している。エッジ９についてはポリゴンＢのエッジ９とポリゴンＣのエッジ９が共通していることを示している。
【００６９】
図２の例においてはその後、図３に示すような、ポリゴンの要素点の間引処理を行う。図３に示すポリゴンの周縁を形成する要素点の間引処理の例においては、最初間引処理する要素点を順に指示することから行っている（ステップＳ２１）。図３に示す例においてはその後指定した要素点には既に間引フラグが立っているか否かを判別している（ステップＳ２２）。
【００７０】
即ち、図３に示す処理で最初に作動する状態では未だ間引フラグが立っている状態はないが、その後の処理で後述するステップＳ２８で指定要素点に間引フラグを立てた後、ステップＳ２９で未だ全ての要素点の間引チェックをしていないと判別した時にステップ２１に戻り、新たな要素点を順に指示して同様の処理を繰り返すため、ここでは既に前記のように間引フラグを立てている要素点についてはその後の処理を行う必要がないので、ステップＳ１に戻り、次の要素点の指示を行うようにしている。
【００７１】
ステップＳ２１において指示した要素点は未だ間引フラグが立っていないと判別した時にはステップＳ２３に進み、指定要素点について両隣の要素点とのなすポリゴン側の角度α１を計測する（ステップＳ２３）。即ち、前記図１１（ｂ）（ｃ）の条件（１）の判別を行うため、前記角度α１を計測する。
【００７２】
その後ステップＳ２４において、その計測した角度α１は１８０度以内であるか否かを判別する。ここで１８０度を超えたと判別した時には、この要素点については間引処理を行わないとしてステップＳ２９に進み、未だ全ての要素点の間引チェックをしていないと判別した時にはステップＳ２１に戻って、次の要素点を指示する。それに対して角度α１は１８０度以内であると判別したときにはステップＳ２５に進み、計測した角度α１は例えば１７０度等の所定の角度αaを超えるか否かを判別する。
【００７３】
ここで計測した角度α１が所定の角度αaよりも小さいと判別した時には、この部分はある程度以上の曲がりがあるため、間引きするにはふさわしくないと判別してステップＳ２９に進み、前記作動を行う。それに対して計測した角度は所定の角度αaを超えると判別した時にはステップＳ２６に進み、両隣の要素点を結ぶ直線に対する垂線の長さＬ１を計測する（ステップＳ２６）。
【００７４】
この処理は前記のように図１１（ｂ）（ｃ）の条件（２）を判別するための計測を行うものであり、その計測結果に基づきステップＳ２７で、垂線の長さＬ１は所定長さＬａ以下であるか否かを判別する。ここで垂線の長さが所定長さＬａ以下ではないと判別した時には、その部分での曲がりがある程度あるものとして間引くにはふさわしくないと判別し、ステップＳ２９に進んで前記作動を行う。
【００７５】
ステップＳ２７で垂線の長さＬ１は所定の長さＬａ以下であると判別した時には、図１１（ｂ）（ｃ）の（１）及び（２）の条件を全て満たす時であり、その時にはステップＳ２８に進んで指定要素点について間引フラグを立てる。その後前記ステップＳ２４、ステップＳ２５、ステップＳ２７のいずれかで否と判別された時と共にステップＳ２９に進み、全ての要素点の間引チェックをしていないと判別した時にはステップＳ２１に戻って次の要素点の指示を継続し、全ての要素点の間引チェックを行ったと判別した時にはステップＳ３０に進んで、前記一連の処理を終了する。
【００７６】
図２のステップＳ８で前記図３に示すような処理を行った後、ステップＳ９に進み、間引処理するポリゴンを順に指示する。ここでは前記処理によって最初に指定したポリゴンの処理が終了した後であるので、続いて隣接しているポリゴンについて処理を行うこととなる。そのように指示したポリゴンについても前記図３と同様の間引処理を行うが、その際には先のポリゴンで間引フラグを立てている時には、次のポリゴンでは特に判別することなく、間引処理を行うものとする。
【００７７】
その後指定したポリゴンの全ての隣接ポリゴンの間引処理を行ったか否かを判別し（ステップＳ１１）、未だ全ての隣接ポリゴンの間引処理を行っていないと判別した時にはステップＳ９に戻り、次のポリゴンを順に指示して前記作動を繰り返す。それに対してステップＳ１１で全ての隣接ポリゴンの間引処理を行ったと判別した時には、ステップＳ１２に進み、間引処理するポリゴンを全て処理したか否かを判別し、前記のように指定ポリゴン、それに続くその指定ポリゴンの隣接ポリゴンを処理した後更にそれらに隣接するポリゴンについて、全てを指示する迄、ステップＳ１０で間引処理を行う前記作動を繰り返す。その後全てのポリゴンについて間引処理を行った時には、ステップＳ１３に進んで、間引フラグの立っている要素点を間引いて表示用ポリゴンを作成する。
【００７８】
本発明においては、図１に示す機能ブロックからなる装置を図２及び図３に示す作動フローによって順に作動することにより、所望の機能を行うことができるものであり、前記図６に示した各エッジについてポリゴン毎の要素点を対応付けた後、最初は指定したポリゴンＡについて図７のような処理がなされる。
【００７９】
図７に示すポリゴンＡの間引処理の例においては、ポリゴンＡの構成エッジ１〜５について、それぞれ図示するような要素点によって構成され、例えばエッジ１についてはほぼ直線で且つ他の隣接ポリゴンの影響等もないため、前後両端の要素点である要素点１と要素点８以外は間引処理を行う。図７においては、この時の要素点１〜８はポリゴンＡの対応要素点はＡ１〜８であることを示している。以下も同様の要素点対応表を示している。
【００８０】
ポリゴンＡのエッジ２についても前後両端の要素点以外は間引処理を行う。エッジ３については、ポリゴンＡとポリゴンＢの共通要素点で構成されているが、この部分はポリゴンＡにおける処理によって、要素点２、即ちＡ１５の間引処理を行うことができる。その結果、対応する要素点をもつポリゴンＢにおいて、この部分の要素点Ｂ３に対して間引処理するためのフラグが立てられる。その後、後述するようにポリゴンＢでの処理では既に間引処理が行われるものとして、特に間引処理を行う必要がなくなる。
【００８１】
ポリゴンＡのエッジ４については前記従来例を示す図１２（ｂ）のように、この部分の凹部の底である要素点２（Ａ１９）については間引処理が行われない。但し、その後図９に示すポリゴンＣの処理において、要素点２は間引処理されることとなる。要素点３（Ａ１９）については間引処理が可能である。エッジ５については、前後両端のエッジ以外は間引処理がなされる。
【００８２】
その結果、図７（ｂ）に示すようにポリゴンＡが図示するようなエッジと構成要素点からなる時、同図（ｃ）の処理後の図に示すように、要素点は整理され、特にエッジ３の部分についてはポリゴンＡの処理によって要素点の間引がなされる結果、この部分は直線化する。同時に、ポリゴンＢ側にもこの処理が反映されるため、そのポリゴンＢの要素点Ｂ２、Ｂ３も間引かれる結果、隙間無くポリゴンＡ、Ｂが隣接することとなる。
【００８３】
図８には図７の前記処理の後に行われるポリゴンＢについての間引処理を示しており、エッジ３については前記のようにポリゴンＡの間引処理によって、要素点Ｂ２、Ｂ３が間引かれている。その他の特記するエッジとしてはポリゴンＣと共通するエッジであるエッジ９が存在するが、最初に処理するポリゴンＢの処理で図示するように要素点の間引が行われ、それによりポリゴンＣの対応する要素点Ｃ４、５、６、７、８に間引フラグが立ち、間引かれることとなる。
【００８４】
その処理の結果、同図（ｂ）に示すように、ポリゴンＢの各エッジの各要素点について、同図（ｃ）に示すようにエッジ３は前記ポリゴンＡの処理で間引処理され、エッジ９についてはここでの間引処理がポリゴンＣに反映されることとなる。
【００８５】
図９に示すポリゴンＣの間引処理では、特にエッジ４において、このエッジ４に共通して対応するポリゴンＡの各要素点については、要素点３のみが間引処理されたものであるが、このポリゴンＣにおいては前記従来例を示す図１２（ｂ）のように要素点２の部分も間引処理が可能である。そのため要素点２（ＡＡ１８、Ｃ３）もここで間引処理がなさ得る。その結果、ポリゴンＣの要素点Ｃ３に対応するポリゴンＡの要素点Ａ１８もこの間引きに反映される。エッジ９については前記のようにポリゴンＢの処理において間引かれることとなっている。
【００８６】
その結果最終的に図９（ｃ）に示すように、また、その地図表示状態の拡大図を図１０（ｂ）に示すように、特にエッジ３及びエッジ４において、従来は図１２（ｂ）に示すようにポリゴン間に隙間が生じる部分において、全く隙間を生じることが無くなり、従来の問題を解決することができる。しかもこの処理は全て自動化でき、容易に全間引処理を行ったデータを得ることができる。また、間引前の原データが提供されている時には、地図を描画する機器側が、上記処理を行うソフトウェアによって、素早くポリゴン表示を行うことが可能となる。
【符号の説明】
【００８７】
１ 間引処理対象選択部
２ 要素点間引処理部
３ 間引処理ポリゴン抽出部
４ 間引処理用ポリゴン指定部
５ ポリゴン周縁形成要素点取得部
６ 隣接ポリゴン検出部
７ ポリゴン周縁エッジ設定部
８ エッジ形成要素点検出部
９ 間引処理エッジ指示部
１０ 間引処理要素点指示部
１１ 間引可否判別処理部
１２ 隣接要素点間角度計側部
１３ 隣接要素点間角度所定域内判別部
１４ 隣接要素点間直線への垂線長さ計測部
１５ 垂線長さ所定値以下判別部
１６ 間引フラグ処理部
１７ 間引フラグ検出部
１８ ポリゴン表示データ形成部
【技術分野】
【０００１】
本発明は、ディスプレイに地図を表示するに際して、地図の背景となるポリゴンを描画するとき、ポリゴンの周縁を形成する要素点を間引いて表示する地図ポリゴン描画方法及びその方法を実施する装置に関し、特に隣接するポリゴンのうち片側のポリゴンで間引処理を行うのに対して他側では間引処理を行わないことにより生じる隙間を無くすことができるようにした地図ポリゴン描画方法、及びその方法を実施する装置に関する。
【背景技術】
【０００２】
地図を表示するには、地図帳として表示する以外に、近年は地図の電子データ化により、パソコンやナビゲーション装置を初め、携帯情報端末、携帯電話等々のディスプレイに表示することが多くなっている。このような地図の電子データ化によって、世界中任意の地点について、任意の縮尺で、しかも好みの表示手法によって自由に表示することができるようになっている。
【０００３】
電子データ化された地図はＤＶＤやメモリカード等の各種データ記録媒体に記録する以外に、インターネット等を通じて各種情報機器に取り込むことができるが、このような地図データは、多くの場合各種の縮尺レベルに応じて適当な大きさの経度幅及び緯度幅に区切られており、道路等は経度及び緯度で表現されたノードの座標集合としている。このような地図の表示に際しては、道路表示レイヤの他、地図画面上に道路、建築物、施設、海や河川、森、山岳等の地図上の背景を表示するポリゴン表示レイヤ、更には市町村名などの行政区画名、道路名、交差点名及び施設の名前やその施設のアイコン等の、文字や地図記号を表示するための情報データ表示レイヤ等、多くのレイヤのデータを重ねて表示している。
【０００４】
この中のポリゴンを表示するデータは、地図を利用者にとってわかりやすく、且つ親しみ易く、見栄えがよいように表示するために重要な表示データとなっている。このポリゴンデータは、衛星写真や測量地図を元に整備されており、このポリゴンデータを地図上に表示する際には、その表示データ処理に多大な負担をかけることがあり、地図描画性能を悪化させるため、できる限り地図描画処理負担を軽くするように、ポリゴンの周縁を構成する要素点の間引き処理を行っている。
【０００５】
そのようなポリゴンの周縁を形成する要素点の間引処理に際しては、主として図１１に示すように行われている。図１１に示す例においては、同図（ａ）に示すようなポリゴンＰが存在する時、その一部が同図の要素点２の部分が突出しているとき、その突出部の要素点を間引くか否かは、ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たすときにその要素点を削除して間引く。その時の条件としては例えば同図（ｂ）に示すようにして行う。
【０００６】
即ち第１に、要素点２を中心としてその両隣の要素点１と要素点３との関係を、要素点２における角度αを計測し、そのαが例えば１７０度等の所定の角度αaと、１８０度の間に存在するかを判別する。
【０００７】
第２に、図１１に示す例においては、要素点２を挟む両隣の要素点１と要素点３を結ぶ直線に、要素点２から垂線を降ろし、そのときの長さＬ、即ち要素点２の前記直線との距離を計測して、その長さＬが最大値の閾値としての所定の長さＬa以下であるかを判別して、両条件を満たす時、この要素点２を間引くことにしている。こののような判別条件は、前記第１の条件を満たす場合でも、要素点２の両隣の要素点１と３の距離が大きい時は、この要素点は間引くことが好ましくないものとする。
【０００８】
その処理に際して、前記角度αは、反時計回りを順方向とし、ポリゴン側の角度を測定している。したがって、図１１（ａ）において、図示の例では要素点２がポリゴンにとって突出しているため、角度αは１８０度以下であるのに対して、図示とは逆に要素点２が凹部であるポリゴンの場合は、角度αは１８０度を超えるため、その場合は要素点２の間引き処理を行わないことになる。
【０００９】
上記処理の結果、図１１（ｃ）のように、（１）要素点２について隣接要素点１及び３間の角度αがα１であって、所定角度αａよりも大きく、前記１８０度以下の時、であって、（２）隣接要素点間を結ぶ直線への垂線の長さＬ１が所定の長さＬaよりも小さい時には、同図（ｄ）に示すように要素点を間引き、要素点１と３のみとする。このような間引を行う要素点を選択する条件を満たす要素点２の部分は、ポリゴンの周囲形状の変化が少ない部分ということができる。なお、間引処理を行う条件は、上記以外に種々の手法が提案されている。
【００１０】
前記のような要素点の間引処理の結果、ポリゴンの多くの要素点が間引かれ、ポリゴンの表示処理負担が軽くなり、地図全体の表示が速くなるため、特定地点の地図表示速度を向上し、また現在の地図表示からのスクロール表示や、地図の表示縮尺の変更等において、円滑な表示ができるようになる。
【００１１】
なお、地図表示におけるポリゴンの表示に際して、ポリゴン間に隙間が発生する時、その隙間領域を抽出し、併合釦を操作することにより、隣接ポリゴンに合体して隙間を埋めて修正を行うことができるようにした技術は、特許文献１に開示されている。
【先行技術文献】
【特許文献】
【００１２】
【特許文献１】特開２００７−２１３５２４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１３】
前記のように、電子データによって地図を描画する時、その背景となるポリゴンの表示処理負担を軽くするため、ポリゴンの周縁を形成する要素点を、前記のような所定の条件を満たす時に間引く技術では、例えば図１２（ｂ）に示すような隙間Ｓa、Ｓｂを生じることがある。
【００１４】
即ち図示の例では、最初は同図（ａ）に示すように、全ての要素点を用いてポリゴンＡ、Ｂ、Ｃを描画する時には各ポリゴン間で隙間が発生することはないが、前記のような要素点の間引処理を行うとき、ポリゴンＡがその僅かの突出部分で要素点の間引処理を行った部分で、ポリゴンＢは凹部となり、この部分での要素点の間引は行わなかった例を示している。
【００１５】
同様に同図の例においては、ポリゴンＡとポリゴンＣとの関係において、ポリゴンＣがその僅かの突出部分で要素点の間引処理を行ったとき、その部分でポリゴンＡは凹部となっており、この部分での要素点の間引は行わなかった例を示している。その結果ここには隙間Ｓｂが発生している。
【００１６】
このようにして形成されたポリゴンの要素点の間引処理によって発生したポリゴン間の隙間は、例えば図１３（ｂ）に示すような海ポリゴンにおいて、１つの海ポリゴンが他の海ポリゴンと隣接して繋がっている時、そのポリゴンの境界の一部Ｒにおいて、同図のように広域地図表示状態ではほとんどわからないものの、同図（ａ）のように拡大して表示する時には、図中Ｒで示すよな隙間ＳａとＳｂが、周囲の海の色が存在しない、白地となって見えてくる。
【００１７】
このようなポリゴン間の隙間は、地図自体の表示としては大きな問題は生じないものの、地図を拡大する程この隙間は目立ち、地図データの安っぽさを印象づけて見栄えが極めて良くない。そのため、前記特許文献のようにその隙間を埋める処理を行うことも提案されているが、その処理のためには人為的な操作を必要とし、全てのポリゴン間の隙間を無くすには膨大な手数を要する。
【００１８】
なお、上記のようにポリゴンの表示を円滑にするために、ポリゴン周縁を形成する要素点を間引く処理は、地図データを提供する企業が地図データに対して処理を行い、このように処理した地図データを提供する以外に、特に間引処理を行っていない生のデータが提供される時、そのデータに基づいて地図を表示する、例えばパソコンやナビゲーション装置で間引処理ソフトによって処理する場合が存在しうる。
【００１９】
したがって本発明は、地図の背景となるポリゴンの表示に際して、ポリゴン表示の処理負担を軽減するためにポリゴンの周縁を形成する要素点を所定の条件で間引く時、従来の条件では隣接するポリゴン間に隙間が発生し、地図の見栄えが悪くなる問題を、手数を要することなく、容易に解消することができるようにした地図ポリゴン描画方法、及びその方法を実施する装置に関する。
【課題を解決するための手段】
【００２０】
本発明に係る地図ポリゴン描画方法は、前記課題を解決するため、描画する地図に含まれる全てのポリゴンを抽出し、前記抽出したポリゴンについて、各ポリゴンの周縁を形成する要素点を取得し、各ポリゴンについて相互に隣り合う複数の要素点からなる部分にエッジを設定し、前記エッジを構成する要素点について、ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たすとき、地図表示用要素点として削除する間引処理を行い、前記要素点を削除する間引処理を行ったとき、当該要素点が現在間引処理を行っているポリゴンに隣接するポリゴンを構成する要素点と一致するとき、当該隣接するポリゴンの要素点も削除する間引処理を行い、前記間引処理を、指定したエッジを構成する全ての要素点に対して行った後、指定したポリゴンを構成する他のエッジに対しても前記間引処理を行い、前記指定したポリゴンの全てのエッジに対して前記間引処理を行い、その後、前記抽出したポリゴンの全てに対して前記要素点の間引処理を行い、前記間引処理を行ったデータによりポリゴンを描画することを特徴とする。
【００２１】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記指定したポリゴンの全てのエッジに対して前記間引処理を行った後は、当該ポリゴンに隣接するポリゴンを順に指定して前記間引処理を行うことを特徴とする。
【００２２】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記エッジの設定に際しては、当該エッジの前後端の要素点については、少なくとも前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たす要素点以外の要素点を選択することを特徴とする。
【００２３】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記エッジの設定に際しては、当該エッジの前後端の要素点については、前記所定の条件のほか、隣接するポリゴンが変化する要素点を選択することを特徴とする。
【００２４】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記エッジを設定したとき、当該エッジが隣接するポリゴンのエッジと共通するときには、当該エッジを構成する要素点について、両ポリゴンにおいてそれぞれ対応する要素点についての対応データを作成し、一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データによって他方のポリゴンの要素点を削除する間引処理を行うことを特徴とする。
【００２５】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データにより他方のポリゴンの要素点の間引処理を行う際には当該要素点については間引処理を行わないことを特徴とする。
【００２６】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、指示した要素点について隣接する要素点で形成される角度が所定角度以内であることを特徴とする。
【００２７】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、隣接する要素点を結ぶ直線に降ろした垂線の長さが所定以内であることを特徴とする請求項１記載のポリゴン描画方法。
【００２８】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする。
【００２９】
また、本発明に係る他の地図ポリゴン描画方法は、前記地図ポリゴン描画方法において、前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする。
【００３０】
また、本発明に係る地図ポリゴン描画装置は、前記課題を解決するため、描画する地図に含まれる全てのポリゴンを抽出する間引処理ポリゴン抽出手段と、前記間引処理ポリゴン抽出手段で抽出したポリゴンについて、各ポリゴンの周縁を形成する要素点を取得するポリゴン周縁形成要素点取得手段と、前記間引処理ポリゴン抽出手段で抽出した各ポリゴンについて、相互に隣り合う複数の要素点からなる部分にエッジを設定するポリゴン周縁エッジ設定手段と、前記ポリゴン周縁エッジ設定手段で設定したエッジを構成する要素点について、ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たすとき、地図表示用要素点として削除する間引処理を行う要素点間引処理手段とを備え、前記要素点間引処理手段では、要素点を削除する間引処理を行ったとき、当該要素点が現在間引処理を行っているポリゴンに隣接するポリゴンを構成する要素点と一致するときには、当該隣接するポリゴンの要素点も削除する間引処理を行い、前記間引処理を、指定したエッジを構成する全ての要素点に対して行った後、指定したポリゴンを構成する他のエッジに対しても前記間引処理を行い、前記指定したポリゴン法の全てのエッジに対して前記間引処理を行い、その後、前記抽出したポリゴンの全てに対して前記要素点の間引処理を行うことによりポリゴンを描画するデータを作成することを特徴とする。
【００３１】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記要素点間引処理手段では、前記指定したポリゴンの全てのエッジに対して前記間引処理を行った後は、当該ポリゴンに隣接するポリゴンを順に指定して前記間引処理を行うことを特徴とする。
【００３２】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記ポリゴン周縁エッジ設定手段では、前記エッジの設定に際して、当該エッジの前後端の要素点については、少なくとも前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たす要素点以外の要素点を選択することを特徴とする。
【００３３】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記ポリゴン周縁エッジ設定手段では、前記エッジの設定に際して、当該エッジの前後端の要素点については、前記所定の条件のほか、隣接するポリゴンが変化する要素点を選択することを特徴とする。
【００３４】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記要素点間引処理手段では、前記ポリゴン周縁エッジ設定手段でエッジを設定したとき、当該エッジが隣接するポリゴンのエッジと共通するときには、当該エッジを構成する要素点について、両ポリゴンにおいてそれぞれ対応する要素点についての対応データを作成し、
一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データによって他方のポリゴンの要素点を削除する間引処理を行うことを特徴とする。
【００３５】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記要素点間引処理手段では、前記一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データにより他方のポリゴンの要素点の間引処理を行う際には当該要素点については間引処理を行わないことを特徴とする。
【００３６】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、指示した要素点について隣接する要素点で形成される角度が所定角度以内であることを特徴とする。
【００３７】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、隣接する要素点を結ぶ直線に降ろした垂線の長さが所定以内であることを特徴とする。
【００３８】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする。
【００３９】
また、本発明に係る他の地図ポリゴン描画装置は、前記地図ポリゴン描画装置において、前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする。
【発明の効果】
【００４０】
本発明は上記のように構成したので、地図の背景となるポリゴンの表示に際して、ポリゴン表示の処理負担を軽減するためにポリゴンの周縁を形成する要素点を所定の条件で間引く時、従来の条件では隣接するポリゴン間に隙間が発生し、地図の見栄えが悪くなる問題を、手数を要することなく、容易に解消することができるようになる。
【図面の簡単な説明】
【００４１】
【図１】本発明の実施例の機能ブロック図である。
【図２】同実施例の作動フロー図である。
【図３】同実施例で行う要素点間引処理の作動フロー図である。
【図４】ポリゴン毎の要素点の例を示す図である。
【図５】隣接ポリゴンのエッジ設定処理の例を示す図である。
【図６】ポリゴン毎のエッジの要素点対応表の例を示す図である。
【図７】ポリゴンＡの間引処理の例を示す図である。
【図８】その後行われるポリゴンＢの間引処理の例を示す図である。
【図９】その後行われるポリゴンＣの間引処理の例を示す図である。
【図１０】本発明による間引処理前と処理後の状態を示す図である。
【図１１】従来から提案されているポリゴン構成要素点の間引処理例を示す図である。
【図１２】同処理の結果ポリゴン間に隙間が生じる状態の説明図である。
【図１３】従来ポリゴン間に隙間が生じる実際例を示す図である。
【発明を実施するための形態】
【実施例】
【００４２】
本発明の実施例を図面に沿って説明する。図１は本発明における地図ポリゴン描画装置において、特にポリゴンの周縁を形成する要素点の間引処理を行う時、隣接するポリゴン間に隙間が発生しないようにするための処理を行う機能ブロック図を主として示しており、本発明を各種の態様で実施することができるようにした機能ブロック図を示している。なお、同図において、各機能を行う機能部は、それぞれ各機能を行う手段ということができる。
【００４３】
図１の表示ポリゴンの周縁を形成する要素点の間引処理を行う装置の例においては、主として要素点の間引処理を行う対象を選択する間引処理対象選択部１と、その間引処理対象選択部１で選択した間引処理対象について、実際に間引処理を行う要素点間引処理部２とを備えている。
【００４４】
図１の例えば前記両者が互いに連携して作動し、後述するように間引処理対象選択部１で選択したポリゴン、その中のエッジ、それを構成する要素点について間引処理を行うと、同じエッジの次の要素点、同じエッジの全ての要素点に対する処理が終了するとその次のエッジについて同様の処理を行い、そのエッジの処理が終了するとそのポリゴンの他のエッジを順に選択し、同様にして今回の処理を必要とする他のポリゴンに対して処理を行うことにより完了するようにしている。
【００４５】
間引処理対象選択部１には、これから処理を行おうとする地図について、その地図に含まれる全てのポリゴンを抽出するための間引処理ポリゴン抽出部３を備える。間引処理用ポリゴン指定部４では、最終的にその地図の全てのポリゴンを指定することとなるが、順に処理を行うために適宜の順に処理するポリゴンの指定を行う。
【００４６】
ポリゴン周縁形成要素点取得部５では、指定したポリゴンについて、また後述するようにその指定ポリゴンに直接隣接するポリゴンについて、それらのポリゴンの周縁を形成する要素点を全て取得する。それらのデータは従来より、各ポリゴンを表示するための元のデータに整理して記録されている。
【００４７】
隣接ポリゴン検出部６では、前記のように間引処理用ポリゴン指定部４で指定したポリゴンについて、隣接するポリゴンを検出する。それらのポリゴンについても前記のようにポリゴン周縁形成要素点取得部５によって、要素点を取得する処理がなされる。その結果、例えば前記従来例として示した図１２（ａ）と同様の例を示す図４（ａ）のように、間引処理用ポリゴン指定部４で指定するポリゴンがポリゴンＡである時、隣接ポリゴン検出部６ではポリゴンＢとポリゴンＣを検出する。
【００４８】
また、前記ポリゴン周縁形成要素点取得部４では、ポリゴンＡについては要素点Ａ１〜Ａ２４の２４個の要素点を取得し、ポリゴンＢについてはＢ１〜Ｂ１７の１７個の要素点を取得し、ポリゴンＣについてはＣ１〜Ｃ１８の１８個の要素点を取得している。
【００４９】
ポリゴン周縁エッジ設定部７では、間引処理用ポリゴン指定部３で指定したポリゴンと、隣接ポリゴン検出部６で検出したポリゴンについて、ポリゴン周縁を形成するエッジを設定する。この時の「エッジ」とは、各ポリゴンについて隣接する要素点が例えば１０度以上折れ曲がっている要素点、或いは大きな曲折はないものの、その部分で隣接するポリゴンが変わる部分等の予め設定した条件の特徴的な要素点間を結ぶ周縁部分を検出する。それにより、前記のような「エッジ」を決定する。
【００５０】
このようなエッジの検出処理により、前記図４の例においては、図５に示すようにポリゴンＡについて、要素点Ａ１〜Ａ８がほぼ直線状態のためこれをエッジ１とする。このエッジに対してポリゴンＡにおける反時計回りを順方向として、同様に要素点Ａ８〜Ａ１４についてはエッジ２とする。
【００５１】
また、要素点Ａ１６部分については１０度以下の折曲であるときにはこれをエッジの端部とはせず、要素点Ａ１７部分については、隣接するポリゴンがポリゴンＢからポリゴンＣに変わるため、これをエッジの端部として、要素点Ａ１４〜Ａ１７をエッジ３とする。要素点Ａ１８部分については、前記要素点Ａ１６と同様に、例えば１０度以下のわずかな折曲である時にはこれをエッジの端部とはせず、したがって要素点Ａ１７〜Ａ２０をエッジ４とする。また、要素点Ａ２０〜Ａ１については、ほぼ直線上であるのでこの周縁部分をエッジ５としている。
【００５２】
同様に隣接ポリゴンであるポリゴンＢについては、ポリゴンＡで設定したエッジ３は共通するエッジであるので、要素点Ｂ１〜Ｂ４をエッジ３の要素点とする。このエッジからポリゴンＢにとって順方向に、要素点Ｂ４〜Ｂ６をエッジ６とし、要素点Ｂ６〜Ｂ１０をエッジ７とし、要素点Ｂ１２部分の折曲が小さいことによりこれはエッジの端部とはせず、したがって要素点Ｂ１０〜Ｂ１４をエッジ８とする。
【００５３】
ポリゴンＢの要素点Ｂ１４〜Ｂ１についてはほぼ直線状であるのでこれをエッジ９とする。このエッジ９はポリゴンＡに隣接するポリゴンでありポリゴンＢにも隣接するポリゴンＣにおける、要素点Ｃ４〜Ｃ８と共通して構成される。
【００５４】
ポリゴンＣについては、前記ポリゴンＡのエッジ４について、ポリゴンＡにおいては要素点Ａ１７〜Ａ２０が構成しているのに対して、要素点Ｃ１〜４が共通して構成している。ポリゴンＣの要素点Ｃ４〜Ｃ８については、前記のようにポリゴンＢの要素点Ｂ１４〜Ｂ１と共にエッジ９を構成している。
【００５５】
要素点Ｃ１１部分については曲がりが少ないためこれをエッジの端部とはせず、要素点Ｃ８〜Ｃ１５をエッジ１０とする。また、要素点ＣＣ１５〜Ｃ１はエッジ１１とする。上記のようにして、指定ポリゴンＡと、それに隣接するポリゴンであるポリゴンＢとポリゴンＣについて、一連のエッジを設定する。
【００５６】
図１のポリゴン周縁エッジ設定部７では前記のようなエッジの設定を行い、エッジ構成要素点検出部８では前記のような各エッジが構成される各ポリゴンの要素点を検出する。間引処理エッジ指示部９では、前記間引処理用ポリゴン指定部４で指定したポリゴンと、隣接ポリゴン検出部６で検出したポリゴンについて、間引処理を行うエッジの指示を行う。
【００５７】
間引処理要素点指定部１０では、間引処理エッジ指示部９で指示したエッジについて、そのエッジを構成する要素点を順に指示する。このようにして、例えば現在間引処理用ポリゴン指定部４で指定したポリゴンについて要素点の間引処理を行う時、間引処理用エッジ指示部９ではそのポリゴンを構成するエッジを順に指示し、間引処理要素点指示部１０では、そのエッジについてそのポリゴンにおいてエッジを構成する要素点を順に指示する。その後間引処理するポリゴンについて、指定ポリゴンのエッジを全て処理した後は、隣接ポリゴンについて同様の間引処理を行うエッジ及びそれを構成する要素点の間引処理を行い、最終的に全てのポリゴンの処理がなされる。
【００５８】
要素点間引処理部２では、前記のように指示された要素点について、所定の条件を満たすものを間引く処理を行うものであり、基本的には前記従来例で示した図１１の処理を行う。その中の間引可否判別処理部１１では要素点を間引くか否かを判別する処理を行うものであり、その中の隣接要素点間角度計測部１２で計測した、前記図１１の隣接要素点間角度である角度αを計測する。その計測値に基づき、隣接要素点間角度所定域内判別部１３で、図１１（ｂ）（ｃ）に示すように、また同図の説明で述べたように、条件（１）αa＜α１≦１８０度を満たすかどうかを判別する。
【００５９】
また、隣接要素点間直線への垂線長さ計測部１８では、図１１（ｂ）（ｃ）に示すように、また同図の説明で述べたように、隣接する要素点を結ぶ直線への垂線の長さＬ１について、所定の長さＬaより短いか、即ちＬ１＜Ｌaであるか否かを判別する。したがって間引可否判別処理部１１では、前記間引条件（１）と’（２）の条件を満たすか否かを判別し、全て満たす時には間引処理を行う。
【００６０】
間引フラグ処理部１６では、前記間引可否判別処理部１０で、特定の要素点について間引く旨の判別を行った時、図示の例では地図描画データとしてそれを間引いて描画するデータを形成するため、その要素点に間引フラグを立てる。その後このようにして全てのポリゴンについて、全てのエッジの全ての要素点の間引可否判別を行い、間引フラグ処理を行った後は、ポリゴン表示データ形成部１８でポリゴンの表示を行うデータを形成する。
【００６１】
前記のような処理を行う結果、図１（ａ）に示すように多数の要素点からなるポリゴンについて同図（ｃ）に示すように最小限の要素点となり、その際に隣接ポリゴンが共通して構成するエッジについてはｍ、同図においてエッジ３及びエッジ４に示すように、隣接するポリゴンの内、片方で間引処理が行われた時には、他側の間引の判別にかかわらず、間引処理を行うこととなり、隣接するポリゴン間に前記図１３（ａ）に示すような隙間を生じることが無くなる。
【００６２】
これらの間引処理を図２及び図３の作動フローに従い、より詳細に順に説明する。図２の表示ポリゴン周縁形成要素点の間引処理の例においては、最初間引処理するポリゴンの抽出から始めている（ステップＳ１）。この処理は図１の間引処理ポリゴン抽出部３で前記のようにして行っている。
【００６３】
その後間引処理するポリゴンを順に指定する（ステップＳ２）。この処理は図１の間引処理用ポリゴン指定部４で行っている。次いで指定ポリゴンの要素点を取得する（ステップＳ３）、この処理については図１のポリゴン周縁形成要素点取得部５で、間引処理用ポリゴン指定部４で指定したポリゴンについて要素点を取得することにより行っている。
【００６４】
次いで、指定するポリゴンについて隣接するポリゴンを検出する（ステップＳ４）。この処理は図１の隣接ポリゴン検出部６において前記のようにして行っている。その後隣接ポリゴンの要素点を取得する（ステップＳ５）。この処理は図１のポリゴン周縁形成要素点取得部５において、隣接ポリゴン検出部６で検出したポリゴンについて、要素点を検出することにより行っている。このような処理により、前記のように図４に示すような各ポリゴンについて、要素点を取得する。
【００６５】
その後指定ポリゴンに隣接するポリゴンの共通要素点を含むポリゴン周縁のエッジを設定する（ステップＳ６）。この処理は図１のポリゴン周縁エッジ設定部７で前記のようにして行っている。その結果図５に示すようなエッジ１〜エッジ１１を設定することも前記の通りである。
【００６６】
次いで各エッジについて、ポリゴン毎の要素点を対応付ける（ステップＳ７）。この処理は図６に示しており、ポリゴンＡについてはエッジ１〜エッジ５が存在し、それらのエッジを構成する要素点は全て順方向に対応することを示している。同様にポリゴンＢについては、エッジ３、６、７、８、９が存在し、それを構成する要素点はエッジ３についてはポリゴンＡがＡ１４〜Ａ１７と反時計方向で順方向であるのに対して、その要素点にそれぞれ対応するポリゴンＢの要素点はＢ４、３、２、１と逆方向に対応していることを示している。ポリゴンＢについてはその他のエッジは順方向となっている。
【００６７】
ポリゴンＣについては、エッジ４はポリゴンＡの要素点が順方向であるのに対して、前記と同様の対応によってポリゴンＣの要素点は逆方向となる。同様にエッジ９についてはポリゴンＢが順方向である時、ポリゴンＣについては逆方向となる。ポリゴンＣのその他のエッジについては順方向である。
【００６８】
各ポリゴンを構成するエッジについて、その要素点をそれぞれエッジ１〜１１について示している。ここで例えばエッジ３についてはポリゴンＡのエッジ３と、ポリゴンＢのエッジ３が共通し、エッジ４についてはポリゴンＡのエッジ４とポリゴンＣのエッジ４が共通していることを示している。エッジ９についてはポリゴンＢのエッジ９とポリゴンＣのエッジ９が共通していることを示している。
【００６９】
図２の例においてはその後、図３に示すような、ポリゴンの要素点の間引処理を行う。図３に示すポリゴンの周縁を形成する要素点の間引処理の例においては、最初間引処理する要素点を順に指示することから行っている（ステップＳ２１）。図３に示す例においてはその後指定した要素点には既に間引フラグが立っているか否かを判別している（ステップＳ２２）。
【００７０】
即ち、図３に示す処理で最初に作動する状態では未だ間引フラグが立っている状態はないが、その後の処理で後述するステップＳ２８で指定要素点に間引フラグを立てた後、ステップＳ２９で未だ全ての要素点の間引チェックをしていないと判別した時にステップ２１に戻り、新たな要素点を順に指示して同様の処理を繰り返すため、ここでは既に前記のように間引フラグを立てている要素点についてはその後の処理を行う必要がないので、ステップＳ１に戻り、次の要素点の指示を行うようにしている。
【００７１】
ステップＳ２１において指示した要素点は未だ間引フラグが立っていないと判別した時にはステップＳ２３に進み、指定要素点について両隣の要素点とのなすポリゴン側の角度α１を計測する（ステップＳ２３）。即ち、前記図１１（ｂ）（ｃ）の条件（１）の判別を行うため、前記角度α１を計測する。
【００７２】
その後ステップＳ２４において、その計測した角度α１は１８０度以内であるか否かを判別する。ここで１８０度を超えたと判別した時には、この要素点については間引処理を行わないとしてステップＳ２９に進み、未だ全ての要素点の間引チェックをしていないと判別した時にはステップＳ２１に戻って、次の要素点を指示する。それに対して角度α１は１８０度以内であると判別したときにはステップＳ２５に進み、計測した角度α１は例えば１７０度等の所定の角度αaを超えるか否かを判別する。
【００７３】
ここで計測した角度α１が所定の角度αaよりも小さいと判別した時には、この部分はある程度以上の曲がりがあるため、間引きするにはふさわしくないと判別してステップＳ２９に進み、前記作動を行う。それに対して計測した角度は所定の角度αaを超えると判別した時にはステップＳ２６に進み、両隣の要素点を結ぶ直線に対する垂線の長さＬ１を計測する（ステップＳ２６）。
【００７４】
この処理は前記のように図１１（ｂ）（ｃ）の条件（２）を判別するための計測を行うものであり、その計測結果に基づきステップＳ２７で、垂線の長さＬ１は所定長さＬａ以下であるか否かを判別する。ここで垂線の長さが所定長さＬａ以下ではないと判別した時には、その部分での曲がりがある程度あるものとして間引くにはふさわしくないと判別し、ステップＳ２９に進んで前記作動を行う。
【００７５】
ステップＳ２７で垂線の長さＬ１は所定の長さＬａ以下であると判別した時には、図１１（ｂ）（ｃ）の（１）及び（２）の条件を全て満たす時であり、その時にはステップＳ２８に進んで指定要素点について間引フラグを立てる。その後前記ステップＳ２４、ステップＳ２５、ステップＳ２７のいずれかで否と判別された時と共にステップＳ２９に進み、全ての要素点の間引チェックをしていないと判別した時にはステップＳ２１に戻って次の要素点の指示を継続し、全ての要素点の間引チェックを行ったと判別した時にはステップＳ３０に進んで、前記一連の処理を終了する。
【００７６】
図２のステップＳ８で前記図３に示すような処理を行った後、ステップＳ９に進み、間引処理するポリゴンを順に指示する。ここでは前記処理によって最初に指定したポリゴンの処理が終了した後であるので、続いて隣接しているポリゴンについて処理を行うこととなる。そのように指示したポリゴンについても前記図３と同様の間引処理を行うが、その際には先のポリゴンで間引フラグを立てている時には、次のポリゴンでは特に判別することなく、間引処理を行うものとする。
【００７７】
その後指定したポリゴンの全ての隣接ポリゴンの間引処理を行ったか否かを判別し（ステップＳ１１）、未だ全ての隣接ポリゴンの間引処理を行っていないと判別した時にはステップＳ９に戻り、次のポリゴンを順に指示して前記作動を繰り返す。それに対してステップＳ１１で全ての隣接ポリゴンの間引処理を行ったと判別した時には、ステップＳ１２に進み、間引処理するポリゴンを全て処理したか否かを判別し、前記のように指定ポリゴン、それに続くその指定ポリゴンの隣接ポリゴンを処理した後更にそれらに隣接するポリゴンについて、全てを指示する迄、ステップＳ１０で間引処理を行う前記作動を繰り返す。その後全てのポリゴンについて間引処理を行った時には、ステップＳ１３に進んで、間引フラグの立っている要素点を間引いて表示用ポリゴンを作成する。
【００７８】
本発明においては、図１に示す機能ブロックからなる装置を図２及び図３に示す作動フローによって順に作動することにより、所望の機能を行うことができるものであり、前記図６に示した各エッジについてポリゴン毎の要素点を対応付けた後、最初は指定したポリゴンＡについて図７のような処理がなされる。
【００７９】
図７に示すポリゴンＡの間引処理の例においては、ポリゴンＡの構成エッジ１〜５について、それぞれ図示するような要素点によって構成され、例えばエッジ１についてはほぼ直線で且つ他の隣接ポリゴンの影響等もないため、前後両端の要素点である要素点１と要素点８以外は間引処理を行う。図７においては、この時の要素点１〜８はポリゴンＡの対応要素点はＡ１〜８であることを示している。以下も同様の要素点対応表を示している。
【００８０】
ポリゴンＡのエッジ２についても前後両端の要素点以外は間引処理を行う。エッジ３については、ポリゴンＡとポリゴンＢの共通要素点で構成されているが、この部分はポリゴンＡにおける処理によって、要素点２、即ちＡ１５の間引処理を行うことができる。その結果、対応する要素点をもつポリゴンＢにおいて、この部分の要素点Ｂ３に対して間引処理するためのフラグが立てられる。その後、後述するようにポリゴンＢでの処理では既に間引処理が行われるものとして、特に間引処理を行う必要がなくなる。
【００８１】
ポリゴンＡのエッジ４については前記従来例を示す図１２（ｂ）のように、この部分の凹部の底である要素点２（Ａ１９）については間引処理が行われない。但し、その後図９に示すポリゴンＣの処理において、要素点２は間引処理されることとなる。要素点３（Ａ１９）については間引処理が可能である。エッジ５については、前後両端のエッジ以外は間引処理がなされる。
【００８２】
その結果、図７（ｂ）に示すようにポリゴンＡが図示するようなエッジと構成要素点からなる時、同図（ｃ）の処理後の図に示すように、要素点は整理され、特にエッジ３の部分についてはポリゴンＡの処理によって要素点の間引がなされる結果、この部分は直線化する。同時に、ポリゴンＢ側にもこの処理が反映されるため、そのポリゴンＢの要素点Ｂ２、Ｂ３も間引かれる結果、隙間無くポリゴンＡ、Ｂが隣接することとなる。
【００８３】
図８には図７の前記処理の後に行われるポリゴンＢについての間引処理を示しており、エッジ３については前記のようにポリゴンＡの間引処理によって、要素点Ｂ２、Ｂ３が間引かれている。その他の特記するエッジとしてはポリゴンＣと共通するエッジであるエッジ９が存在するが、最初に処理するポリゴンＢの処理で図示するように要素点の間引が行われ、それによりポリゴンＣの対応する要素点Ｃ４、５、６、７、８に間引フラグが立ち、間引かれることとなる。
【００８４】
その処理の結果、同図（ｂ）に示すように、ポリゴンＢの各エッジの各要素点について、同図（ｃ）に示すようにエッジ３は前記ポリゴンＡの処理で間引処理され、エッジ９についてはここでの間引処理がポリゴンＣに反映されることとなる。
【００８５】
図９に示すポリゴンＣの間引処理では、特にエッジ４において、このエッジ４に共通して対応するポリゴンＡの各要素点については、要素点３のみが間引処理されたものであるが、このポリゴンＣにおいては前記従来例を示す図１２（ｂ）のように要素点２の部分も間引処理が可能である。そのため要素点２（ＡＡ１８、Ｃ３）もここで間引処理がなさ得る。その結果、ポリゴンＣの要素点Ｃ３に対応するポリゴンＡの要素点Ａ１８もこの間引きに反映される。エッジ９については前記のようにポリゴンＢの処理において間引かれることとなっている。
【００８６】
その結果最終的に図９（ｃ）に示すように、また、その地図表示状態の拡大図を図１０（ｂ）に示すように、特にエッジ３及びエッジ４において、従来は図１２（ｂ）に示すようにポリゴン間に隙間が生じる部分において、全く隙間を生じることが無くなり、従来の問題を解決することができる。しかもこの処理は全て自動化でき、容易に全間引処理を行ったデータを得ることができる。また、間引前の原データが提供されている時には、地図を描画する機器側が、上記処理を行うソフトウェアによって、素早くポリゴン表示を行うことが可能となる。
【符号の説明】
【００８７】
１ 間引処理対象選択部
２ 要素点間引処理部
３ 間引処理ポリゴン抽出部
４ 間引処理用ポリゴン指定部
５ ポリゴン周縁形成要素点取得部
６ 隣接ポリゴン検出部
７ ポリゴン周縁エッジ設定部
８ エッジ形成要素点検出部
９ 間引処理エッジ指示部
１０ 間引処理要素点指示部
１１ 間引可否判別処理部
１２ 隣接要素点間角度計側部
１３ 隣接要素点間角度所定域内判別部
１４ 隣接要素点間直線への垂線長さ計測部
１５ 垂線長さ所定値以下判別部
１６ 間引フラグ処理部
１７ 間引フラグ検出部
１８ ポリゴン表示データ形成部
【特許請求の範囲】
【請求項１】
描画する地図に含まれる全てのポリゴンを抽出し、
前記抽出したポリゴンについて、各ポリゴンの周縁を形成する要素点を取得し、
各ポリゴンについて相互に隣り合う複数の要素点からなる部分にエッジを設定し、
前記エッジを構成する要素点について、ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たすとき、地図表示用要素点として削除する間引処理を行い、
前記要素点を削除する間引処理を行ったとき、当該要素点が現在間引処理を行っているポリゴンに隣接するポリゴンを構成する要素点と一致するとき、当該隣接するポリゴンの要素点も削除する間引処理を行い、
前記間引処理を、指定したエッジを構成する全ての要素点に対して行った後、指定したポリゴンを構成する他のエッジに対しても前記間引処理を行い、前記指定したポリゴンの全てのエッジに対して前記間引処理を行い、
その後、前記抽出したポリゴンの全てに対して前記要素点の間引処理を行い、
前記間引処理を行ったデータによりポリゴンを描画することを特徴とするポリゴン描画方法。
【請求項２】
前記指定したポリゴンの全てのエッジに対して前記間引処理を行った後は、当該ポリゴンに隣接するポリゴンを順に指定して前記間引処理を行うことを特徴とする請求項１記載のポリゴン描画方法。
【請求項３】
前記エッジの設定に際しては、当該エッジの前後端の要素点については、少なくとも前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たす要素点以外の要素点を選択することを特徴とする請求項１記載のポリゴン描画方法。
【請求項４】
前記エッジの設定に際しては、当該エッジの前後端の要素点については、前記所定の条件のほか、隣接するポリゴンが変化する要素点を選択することを特徴とする請求項３記載のポリゴン描画方法。
【請求項５】
前記エッジを設定したとき、当該エッジが隣接するポリゴンのエッジと共通するときには、当該エッジを構成する要素点について、両ポリゴンにおいてそれぞれ対応する要素点についての対応データを作成し、
一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データによって他方のポリゴンの要素点を削除する間引処理を行うことを特徴とする請求項１記載のポリゴン描画方法。
【請求項６】
前記一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データにより他方のポリゴンの要素点の間引処理を行う際には当該要素点については間引処理を行わないことを特徴とする請求項５記載のポリゴン描画方法。
【請求項７】
前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、指示した要素点について隣接する要素点で形成される角度が所定角度以内であることを特徴とする請求項１記載のポリゴン描画方法。
【請求項８】
前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、隣接する要素点を結ぶ直線に降ろした垂線の長さが所定以内であることを特徴とする請求項１記載のポリゴン描画方法。
【請求項９】
前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする請求項１記載のポリゴン描画方法。
【請求項１０】
前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする請求項１記載のポリゴン描画方法。
【請求項１１】
描画する地図に含まれる全てのポリゴンを抽出する間引処理ポリゴン抽出手段と、
前記間引処理ポリゴン抽出手段で抽出したポリゴンについて、各ポリゴンの周縁を形成する要素点を取得するポリゴン周縁形成要素点取得手段と、
前記間引処理ポリゴン抽出手段で抽出した各ポリゴンについて、相互に隣り合う複数の要素点からなる部分にエッジを設定するポリゴン周縁エッジ設定手段と、
前記ポリゴン周縁エッジ設定手段で設定したエッジを構成する要素点について、ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たすとき、地図表示用要素点として削除する間引処理を行う要素点間引処理手段とを備え、
前記要素点間引処理手段では、要素点を削除する間引処理を行ったとき、当該要素点が現在間引処理を行っているポリゴンに隣接するポリゴンを構成する要素点と一致するときには、当該隣接するポリゴンの要素点も削除する間引処理を行い、
前記間引処理を、指定したエッジを構成する全ての要素点に対して行った後、指定したポリゴンを構成する他のエッジに対しても前記間引処理を行い、前記指定したポリゴン法の全てのエッジに対して前記間引処理を行い、
その後、前記抽出したポリゴンの全てに対して前記要素点の間引処理を行うことによりポリゴンを描画するデータを作成することを特徴とするポリゴン描画装置。
【請求項１２】
前記要素点間引処理手段では、前記指定したポリゴンの全てのエッジに対して前記間引処理を行った後は、当該ポリゴンに隣接するポリゴンを順に指定して前記間引処理を行うことを特徴とする請求項１１記載のポリゴン描画装置。
【請求項１３】
前記ポリゴン周縁エッジ設定手段では、前記エッジの設定に際して、当該エッジの前後端の要素点については、少なくとも前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たす要素点以外の要素点を選択することを特徴とする請求項１１記載のポリゴン描画装置。
【請求項１４】
前記ポリゴン周縁エッジ設定手段では、前記エッジの設定に際して、当該エッジの前後端の要素点については、前記所定の条件のほか、隣接するポリゴンが変化する要素点を選択することを特徴とする請求項１３記載のポリゴン描画装置。
【請求項１５】
前記要素点間引処理手段では、前記ポリゴン周縁エッジ設定手段でエッジを設定したとき、当該エッジが隣接するポリゴンのエッジと共通するときには、当該エッジを構成する要素点について、両ポリゴンにおいてそれぞれ対応する要素点についての対応データを作成し、
一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データによって他方のポリゴンの要素点を削除する間引処理を行うことを特徴とする請求項１１記載のポリゴン描画装置。
【請求項１６】
前記要素点間引処理手段では、前記一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データにより他方のポリゴンの要素点の間引処理を行う際には当該要素点については間引処理を行わないことを特徴とする請求項１５記載のポリゴン描画装置。
【請求項１７】
前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、指示した要素点について隣接する要素点で形成される角度が所定角度以内であることを特徴とする請求項１１記載のポリゴン描画装置。
【請求項１８】
前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、隣接する要素点を結ぶ直線に降ろした垂線の長さが所定以内であることを特徴とする請求項１１記載のポリゴン描画装置。
【請求項１９】
前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする請求項１記載のポリゴン描画。装置
【請求項２０】
前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする請求項１１記載のポリゴン描画装置。
【請求項１】
描画する地図に含まれる全てのポリゴンを抽出し、
前記抽出したポリゴンについて、各ポリゴンの周縁を形成する要素点を取得し、
各ポリゴンについて相互に隣り合う複数の要素点からなる部分にエッジを設定し、
前記エッジを構成する要素点について、ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たすとき、地図表示用要素点として削除する間引処理を行い、
前記要素点を削除する間引処理を行ったとき、当該要素点が現在間引処理を行っているポリゴンに隣接するポリゴンを構成する要素点と一致するとき、当該隣接するポリゴンの要素点も削除する間引処理を行い、
前記間引処理を、指定したエッジを構成する全ての要素点に対して行った後、指定したポリゴンを構成する他のエッジに対しても前記間引処理を行い、前記指定したポリゴンの全てのエッジに対して前記間引処理を行い、
その後、前記抽出したポリゴンの全てに対して前記要素点の間引処理を行い、
前記間引処理を行ったデータによりポリゴンを描画することを特徴とするポリゴン描画方法。
【請求項２】
前記指定したポリゴンの全てのエッジに対して前記間引処理を行った後は、当該ポリゴンに隣接するポリゴンを順に指定して前記間引処理を行うことを特徴とする請求項１記載のポリゴン描画方法。
【請求項３】
前記エッジの設定に際しては、当該エッジの前後端の要素点については、少なくとも前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たす要素点以外の要素点を選択することを特徴とする請求項１記載のポリゴン描画方法。
【請求項４】
前記エッジの設定に際しては、当該エッジの前後端の要素点については、前記所定の条件のほか、隣接するポリゴンが変化する要素点を選択することを特徴とする請求項３記載のポリゴン描画方法。
【請求項５】
前記エッジを設定したとき、当該エッジが隣接するポリゴンのエッジと共通するときには、当該エッジを構成する要素点について、両ポリゴンにおいてそれぞれ対応する要素点についての対応データを作成し、
一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データによって他方のポリゴンの要素点を削除する間引処理を行うことを特徴とする請求項１記載のポリゴン描画方法。
【請求項６】
前記一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データにより他方のポリゴンの要素点の間引処理を行う際には当該要素点については間引処理を行わないことを特徴とする請求項５記載のポリゴン描画方法。
【請求項７】
前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、指示した要素点について隣接する要素点で形成される角度が所定角度以内であることを特徴とする請求項１記載のポリゴン描画方法。
【請求項８】
前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、隣接する要素点を結ぶ直線に降ろした垂線の長さが所定以内であることを特徴とする請求項１記載のポリゴン描画方法。
【請求項９】
前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする請求項１記載のポリゴン描画方法。
【請求項１０】
前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする請求項１記載のポリゴン描画方法。
【請求項１１】
描画する地図に含まれる全てのポリゴンを抽出する間引処理ポリゴン抽出手段と、
前記間引処理ポリゴン抽出手段で抽出したポリゴンについて、各ポリゴンの周縁を形成する要素点を取得するポリゴン周縁形成要素点取得手段と、
前記間引処理ポリゴン抽出手段で抽出した各ポリゴンについて、相互に隣り合う複数の要素点からなる部分にエッジを設定するポリゴン周縁エッジ設定手段と、
前記ポリゴン周縁エッジ設定手段で設定したエッジを構成する要素点について、ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たすとき、地図表示用要素点として削除する間引処理を行う要素点間引処理手段とを備え、
前記要素点間引処理手段では、要素点を削除する間引処理を行ったとき、当該要素点が現在間引処理を行っているポリゴンに隣接するポリゴンを構成する要素点と一致するときには、当該隣接するポリゴンの要素点も削除する間引処理を行い、
前記間引処理を、指定したエッジを構成する全ての要素点に対して行った後、指定したポリゴンを構成する他のエッジに対しても前記間引処理を行い、前記指定したポリゴン法の全てのエッジに対して前記間引処理を行い、
その後、前記抽出したポリゴンの全てに対して前記要素点の間引処理を行うことによりポリゴンを描画するデータを作成することを特徴とするポリゴン描画装置。
【請求項１２】
前記要素点間引処理手段では、前記指定したポリゴンの全てのエッジに対して前記間引処理を行った後は、当該ポリゴンに隣接するポリゴンを順に指定して前記間引処理を行うことを特徴とする請求項１１記載のポリゴン描画装置。
【請求項１３】
前記ポリゴン周縁エッジ設定手段では、前記エッジの設定に際して、当該エッジの前後端の要素点については、少なくとも前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件を満たす要素点以外の要素点を選択することを特徴とする請求項１１記載のポリゴン描画装置。
【請求項１４】
前記ポリゴン周縁エッジ設定手段では、前記エッジの設定に際して、当該エッジの前後端の要素点については、前記所定の条件のほか、隣接するポリゴンが変化する要素点を選択することを特徴とする請求項１３記載のポリゴン描画装置。
【請求項１５】
前記要素点間引処理手段では、前記ポリゴン周縁エッジ設定手段でエッジを設定したとき、当該エッジが隣接するポリゴンのエッジと共通するときには、当該エッジを構成する要素点について、両ポリゴンにおいてそれぞれ対応する要素点についての対応データを作成し、
一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データによって他方のポリゴンの要素点を削除する間引処理を行うことを特徴とする請求項１１記載のポリゴン描画装置。
【請求項１６】
前記要素点間引処理手段では、前記一方のポリゴンの要素点を前記間引処理により削除するとき、前記対応データにより他方のポリゴンの要素点の間引処理を行う際には当該要素点については間引処理を行わないことを特徴とする請求項１５記載のポリゴン描画装置。
【請求項１７】
前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、指示した要素点について隣接する要素点で形成される角度が所定角度以内であることを特徴とする請求項１１記載のポリゴン描画装置。
【請求項１８】
前記ポリゴンの周囲形状の変化が少ないことを示す所定の条件は、隣接する要素点を結ぶ直線に降ろした垂線の長さが所定以内であることを特徴とする請求項１１記載のポリゴン描画装置。
【請求項１９】
前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする請求項１記載のポリゴン描画。装置
【請求項２０】
前記間引処理したデータは、地図表示用データとしてデータベースに保存することを特徴とする請求項１１記載のポリゴン描画装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１２−１７４０６７（Ｐ２０１２−１７４０６７Ａ）
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願番号】特願２０１１−３６４７８（Ｐ２０１１−３６４７８）
【出願日】平成２３年２月２２日（２０１１．２．２２）
【出願人】（０００１０１７３２）アルパイン株式会社 (2,424)
【Ｆターム（参考）】
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願日】平成２３年２月２２日（２０１１．２．２２）
【出願人】（０００１０１７３２）アルパイン株式会社 (2,424)
【Ｆターム（参考）】
[ Back to top ]