TOP > 国内特許検索 > 図形データ処理方法、図形データ処理プログラム及びそのプログラムを記録した記録媒体

図形データ処理方法、図形データ処理プログラム及びそのプログラムを記録した記録媒体

国内特許コード P100000984
掲載日 2010年9月30日
出願番号 特願2003-354037
公開番号 特開2005-122302
登録番号 特許第3988945号
出願日 平成15年10月14日(2003.10.14)
公開日 平成17年5月12日(2005.5.12)
登録日 平成19年7月27日(2007.7.27)
発明者
  • 飯嶋 孝史
  • 石田 憲冶
  • 松森 堅治
  • 嶺田 拓也
出願人
  • 独立行政法人農業・食品産業技術総合研究機構
発明の名称 図形データ処理方法、図形データ処理プログラム及びそのプログラムを記録した記録媒体
発明の概要


【課題】 地理情報システムによって表示、加工等の処理を行うことを目的として作成された図形データを自動的に修正する図形データ処理方法を提供する。
【解決手段】 図形データ処理方法は、自己交差する多角形を自己交点又は自己接点で複数の多角形に分割する自己交差多角形分割処理と、交差する複数の多角形を重なり合いのない複数の多角形に変換する重複解消処理と、複数の多角形が入れ子状になっている場合に、最も外側の多角形の頂点列の方向を時計回りとして、内側の多角形の頂点列の方向をそのすぐ外側の多角形の頂点列の方向の逆方向にする頂点列方向調整処理と、平面領域を構成する全ての多角形の頂点列の終点に、頂点列の始点と同じ座標値の頂点を追加する後処理と、を含み、これらの処理を全ての平面領域のデータに対して行う。
【選択図】 図2

従来技術、競合技術の概要


地理情報システムで使用するデータ形式として広く採用されているシェープファイル形式では、例えば市町村の区域のような飛び地や穴のある平面領域を次の規則に従って複数の多角形で表すこととしている。
(1) 多角形が自己交差しないこと。
(2) 多角形同士が交差しないこと。なお、頂点で接しても良いが、辺を共有してはならない。
(3) 多角形の頂点列の方向に対して右側を当該多角形が表そうとする平面領域の内部としていること。
(4) 多角形が閉じていること。つまり、多角形の頂点列の始点と終点が同じ座標値であること。



しかし、地理情報システムで使われるデータはデジタイザ等を用いて手動操作により地図から読み込んで作成することも多く、細部にわたって完璧に上記規則に従ったものとするのは困難であり、部分的に規則に従わないデータが混在する場合がある。そして、たとえごく一部であっても規則に従わないデータが混在している場合には、地理情報システムはそれを正常に処理できないことがあり、また、多量のデータの中から規則に従わない部分を検出して修正するのには多大な労力を要するという問題がある。

【特許文献1】特開昭61-180378号公報

【特許文献2】特開平10-154237号公報

【特許文献3】特開平10-21367号公報

産業上の利用分野


本発明は、平面領域を多角形として表示する図形データの処理方法に関し、特に、地理情報システムで使用する図形データを修正するための図形データ処理方法に関する。

特許請求の範囲 【請求項1】
図形データとプログラムを格納する記憶装置と、上記図形データを一時的に格納するRAMと、上記図形データを用いて上記プログラムを実行するCPUと、を有するコンピュータを用いて、平面領域を複数の多角形によって表す図形データを処理する図形データ処理方法において、
上記記憶装置から多角形の図形データを読出し、上記RAMに格納する図形データ読出ステップと、
自己交差する多角形を自己交点又は自己接点で分割して自己交差のない複数の多角形に変換する自己交差多角形分割ステップと、
互いに交差する複数の多角形を交差しない複数の多角形に変換する複数多角形の重複解消ステップと、
入れ子状の多角形のうち、内包関係にあり且つ面積の大きさの順番が隣接する2つの多角形の頂点列の方向が互いに逆向きになるように、頂点列を調整する入れ子状多角形頂点列方向調整ステップと、
を上記CPUによって実行し、
上記自己交差多角形分割ステップは、
自己交差する多角形の頂点列に自己交点又は自己接点に等しい頂点を挿入する頂点挿入ステップと、
上記自己交差する多角形の頂点列より座標値が等しい2個の頂点の組み合わせを探索する組み合わせ探索ステップと、
座標値が等しい2個の頂点が見出された場合に当該頂点で上記多角形を2分割する多角形分割ステップと、
上記2分割後の多角形の各々について自己交差がなくなるまで上記組み合わせ探索ステップ及び上記多角形分割ステップを繰り返すことと、
を含むことを特徴とする図形データ処理方法。

【請求項2】
請求項1記載の図形データ処理方法において、上記複数多角形の重複解消ステップは、上記自己交差多角形分割ステップによって得られた自己交差のない多角形の全てについて、多角形の頂点列の方向を判定する頂点列方向判定処理ステップと、
多角形の頂点列の方向を時計回り又は反時計回りに統一化する頂点列方向統一化処理ステップと、
一方の多角形の辺が他方の多角形の辺と交差する2個の多角形の組み合わせ、又は、一方の多角形の頂点が他方の多角形の辺に接する2個の多角形の組み合わせ、を探索する交点探索処理ステップと、
該交点探索処理ステップにて検出された2個の多角形の頂点列に交点又は接点の座標値に等しい頂点を挿入する頂点挿入処理ステップと、
互いに交差する2個の多角形を探索する多角形重畳検索処理ステップと、
交差する2個の多角形を頂点追跡法の原理により結合領域を囲む多角形と穴領域を囲む多角形に変換する多角形変換ステップと、
上記交差する2個の多角形の組み合わせがなくなるまで上記多角形重畳検索処理ステップと上記多角形変換ステップを繰り返すことを特徴とする図形データ処理方法。

【請求項3】
請求項記載の図形データ処理方法において、上記頂点列方向判定処理ステップは、
多角形の頂点列のうち、x座標値が最小の頂点p2と、当該頂点列におけるその直前の頂点p1及び直後の頂点p3を選び、ベクトルp2p1とベクトルp2p3の外積Gを計算することと、
上記外積Gが非ゼロの場合には、その正負により当該頂点列の回転方向を判定することと、
上記外積Gがゼロの場合には頂点p2と頂点p3、又は頂点p2と頂点p1のy座標値の大小関係により当該頂点列の回転方向を判定することと、
を含むことを特徴とする図形データ処理方法。

【請求項4】
請求項記載の図形データ処理方法において、上記多角形重畳検索処理ステップは、
上記頂点挿入処理ステップによって得られた座標値が等しい頂点が挿入された2個の多角形の頂点列において、一方の多角形の頂点列における当該頂点と、その直前及び直後の頂点を結ぶ線分上に任意の2個の点を選ぶ2点選択ステップと、
上記2点選択ステップにて選んだ2個の点の一方が他方の多角形の内部にあり、かつ、2個の点の他方が他方の多角形の外部にある場合に、当該頂点は交点であると判定する交点判定ステップと、
該交点判定ステップにて当該頂点は交点であると判定されないとき当該頂点は接点であると判定する接点判定ステップと、を含むことを特徴とする図形データ処理方法。

【請求項5】
請求項記載の図形データ処理方法において、上記交点判定ステップにおいて、2個の点の一方が他方の多角形の内部にあり、かつ、2個の点の他方が他方の多角形の外部にあると判定する工程は、
判定対象点を端とする半直線を引く半直線ステップと、
隣接する任意の2つの頂点を始点候補及び終点候補として選択し、該始点候補及び終点候補が上記半直線を含む直線上にあるか否かを判定し、上記始点候補及び上記終点候補が上記半直線を含む直線上にない場合には、上記始点候補及び上記終点候補を始点及び終点に選定する始点終点選定ステップと、
上記始点終点選定ステップにて、上記始点候補が上記半直線を含む直線上にあると判定された場合には、上記始点候補から頂点を1つずつ順次後退させ、上記半直線を含む直線上にない最初の頂点が見つかったらそれを始点とする始点選定ステップと、
上記始点終点選定ステップにて、上記終点候補が上記半直線を含む直線上にあると判定された場合には、上記終点候補から頂点を1つずつ順次前進させ、上記半直線を含む直線上にない最初の頂点が見つかったらそれを終点とする終点選定ステップと、
上記始点終点選定ステップ、又は、上記始点選定ステップ及び終点選定ステップにて選定された始点と終点の間を「判定対象の辺の範囲」に選定する判定対象の辺の範囲選定ステップと、
上記判定対象の辺の範囲にて、上記半直線が多角形と交差するか否かを判定する交差判定ステップと、
該交差判定ステップにて、上記半直線が多角形と交差すると判定された場合には交差回数を1増加し、交差しないと判定された場合には交差回数をそのままにする交差計数ステップと、
上記始点終点選定ステップ、上記始点選定ステップ、上記終点選定ステップ、上記判定対象の辺の範囲選定ステップ、上記交差判定ステップ及び上記交差計数ステップを、多角形の全周に渡って、順次繰り返す繰返しステップと、
上記交差計数ステップにて計数した交差回数が偶数である場合には、判定対象点は多角形の外部にあると判定し、交差回数が奇数である場合には、判定対象点は多角形の内部にあると判定する判定対象点判定ステップと、
を含むことを特徴とする図形データ処理方法。

【請求項6】
請求項1記載の図形データ処理方法において、上記入れ子状多角形頂点列方向調整ステップは、
上記複数の多角形がn個の多角形であるとし、該n個の多角形のうち面積最大の多角形を選択し、該面積最大の多角形とそれより面積が小さい全ての多角形との間の内包関係を調べる第1の内包関係検索ステップと、
上記面積最大の多角形を表す頂点列を時計回り又は反時計回りにし、上記面積最大の多角形に内包される全ての多角形の頂点列を上記面積最大の多角形を表す頂点列の方向とは逆の方向にし、上記面積最大の多角形に内包されない全ての多角形の頂点列を上記面積最大の多角形を表す頂点列の方向と同一の方向にする第1ステップと、
上記n個の多角形のうちk(k=2~n-1)番目に面積が大きい多角形を選択し、該k番目に面積が大きい多角形とそれより面積が小さい全ての多角形との間の内包関係を調べる第2の内包関係検索ステップと、
上記k番目に面積が大きい多角形の頂点列はそのままにし、上記k番目に面積が大きい多角形に内包される全ての多角形の頂点列の方向を反転し、上記k番目に面積が大きい多角形に内包されない且つ上記k番目に面積が大きい多角形より面積が小さい多角形の頂点列はそのままにする第2のステップと、
を含み、上記第2の内包関係検索ステップ及び第2のステップをインデックスkを2から1ずつ増やしながらn-1まで処理を繰り返すことを特徴とする図形データ処理方法。

【請求項7】
請求項記載の図形データ処理方法において、上記入れ子状多角形検索ステップの第1及び第2の内包関係検索ステップは、
内包関係を調べる対象として互いに交わらない2個の多角形を設定することと、
該2個の多角形のうち面積が小さい方の多角形と面積が大きい方の多角形を判定することと、
面積が小さい方の多角形の少なくとも1個の頂点が面積が大きい方の多角形の外部にある場合には面積が小さい方の多角形は面積が大きい方の多角形に内包されないと判定することと、
面積が小さい方の多角形の全ての頂点が面積が大きい方の多角形の内部にある場合には面積が小さい方の多角形は面積が大きい方の多角形に内包されると判定することと、
を含むことを特徴とする図形データ処理方法。

【請求項8】
請求項1~のいずれか1項記載の図形データ処理方法をコンピュータに実行させるためのコンピュータにより読み取り可能なプログラム。

【請求項9】
請求項記載のプログラムを格納したコンピュータにより読み取り可能な媒体。

【請求項10】
図形データとプログラムを格納する記憶装置と、上記図形データを一時的に格納するRAMと、上記図形データを用いて上記プログラムを実行するCPUと、を有するコンピュータを用いて、自己交差する多角形を分割するための図形データ処理方法において、
上記記憶装置から多角形の図形データを読出し、上記RAMに格納する図形データ読出ステップと、
多角形を表す頂点列より座標値が等しい連続する複数の頂点があったとき、該連続する複数の頂点より1個の頂点を残し他の頂点を削除する重複頂点削除ステップと、
多角形を表す頂点列より多角形の辺と辺が交差する自己交点及び頂点が辺と接する自己接点の座標値を求める交点等座標値検出ステップと、
多角形の頂点列に上記自己交点及び自己接点の座標値に等しい頂点を挿入する頂点挿入ステップと、
上記頂点列より座標値が等しい2個の頂点の組み合わせを探索する組み合わせ探索ステップと、
座標値が等しい2個の頂点が見出された場合に当該頂点で上記多角形を2分割する2分割ステップと、
上記2分割後の多角形の各々について自己交差がなくなるまで上記組み合わせ探索ステップ及び上記2分割ステップを繰り返すことと、
を上記CPUによって実行することを特徴とする図形データ処理方法

【請求項11】
請求項10に記載の図形データ処理方法をコンピュータに実行させるためのコンピュータにより読み取り可能なプログラム。

【請求項12】
請求項11に記載のプログラムを格納したコンピュータにより読み取り可能な媒体。

【請求項13】
図形データとプログラムを格納する記憶装置と、上記図形データを一時的に格納するRAMと、上記図形データを用いて上記プログラムを実行するCPUと、を有するコンピュータを用いて、頂点列によって表される多角形と判定対象点が与えられたとき該判定対象点が上記多角形の内部にあるか又は外部にあるかを判定する図形データ処理方法において、
上記記憶装置から多角形の図形データを読出し、上記RAMに格納する図形データ読出ステップと、
判定対象点を端とする半直線を引く半直線ステップと、
隣接する任意の2つの頂点を始点候補及び終点候補として選択し、該始点候補及び終点候補が上記半直線を含む直線上にあるか否かを判定し、上記始点候補及び上記終点候補が上記半直線を含む直線上にない場合には、上記始点候補及び上記終点候補を始点及び終点に選定する始点終点選定ステップと、
上記始点終点選定ステップにて、上記始点候補が上記半直線を含む直線上にあると判定された場合には、上記始点候補から頂点を1つずつ順次後退させ、上記半直線を含む直線上にない最初の頂点が見つかったらそれを始点とする始点選定ステップと、
上記始点終点選定ステップにて、上記終点候補が上記半直線を含む直線上にあると判定された場合には、上記終点候補から頂点を1つずつ順次前進させ、上記半直線を含む直線上にない最初の頂点が見つかったらそれを終点とする終点選定ステップと、
上記始点終点選定ステップ、又は、上記始点選定ステップ及び終点選定ステップにて選定された始点と終点の間を「判定対象の辺の範囲」に選定する判定対象の辺の範囲選定ステップと、
上記判定対象の辺の範囲にて、上記半直線が多角形と交差するか否かを判定する交差判定ステップと、
該交差判定ステップにて、上記半直線が多角形と交差すると判定された場合には交差回数を1増加し、交差しないと判定された場合には交差回数をそのままにする交差計数ステップと、
上記始点終点選定ステップ、上記始点選定ステップ、上記終点選定ステップ、上記判定対象の辺の範囲選定ステップ、上記交差判定ステップ及び上記交差計数ステップを、多角形の全周に渡って、順次繰り返す繰返しステップと、
上記交差計数ステップにて計数した交差回数が偶数である場合には、判定対象点は多角形の外部にあると判定し、交差回数が奇数である場合には、判定対象点は多角形の内部にあると判定する判定対象点判定ステップと、
を上記CPUによって実行することを特徴とする図形データ処理方法

【請求項14】
請求項13記載の図形データ処理方法において、上記交差判定ステップは、
上記半直線の方向をy軸の正の方向に設定するとき、判定対象点のx座標値が上記始点のx座標値と上記終点のx座標値の間にあるか否かを判定するx座標値判定ステップと、
上記x座標値判定ステップにて、判定対象点のx座標値が上記始点のx座標値と上記終点のx座標値の間にないと判定された場合には、上記交差判定ステップを終了する終了ステップと、
上記x座標値判定ステップにて、判定対象点のx座標値が上記始点のx座標値と上記終点のx座標値の間にあると判定された場合で、上記始点と上記終点が多角形の連続する2頂点である場合には、上記始点と上記終点を結ぶ直線と上記半直線を含む直線の交点のy座標値と判定対象点のy座標値とを比較し、上記始点又は上記終点が上記始点選定ステップ又は終点選定ステップにて選定された頂点である場合には、上記始点と上記終点の間にある頂点のy座標値と判定対象点のy座標値とを比較するy座標値比較ステップと、
上記y座標値比較ステップにおける比較結果から、上記判定対象の辺の範囲にて上記半直線が多角形と交差するか否かを判定する比較結果交差判定ステップと、
を有することを特徴とする図形データ処理方法

【請求項15】
請求項13記載の図形データ処理方法において、上記始点終点選定ステップは、2回目以降のループでは、前回のループにおける終点を始点として選択し、該始点から頂点を1つ前進させた頂点を終点候補として選択し、該終点候補が上記半直線を含む直線上にあるか否かを判定し、上記終点候補が上記半直線を含む直線上にない場合には、上記終点候補を終点とし、上記終点候補が上記半直線を含む直線上にある場合には、上記終点候補から頂点を1つずつ順次前進させ、上記半直線を含む直線上にない最初の頂点が見つかったらそれを終点とすることを特徴とする図形データ処理方法

【請求項16】
請求項1315のいずれか1項記載の図形データ処理方法をコンピュータに実行させるためのコンピュータにより読み取り可能なプログラム。

【請求項17】
請求項16記載のプログラムを格納したコンピュータにより読み取り可能な媒体。
産業区分
  • 計算機応用
  • 運動娯楽用
国際特許分類(IPC)
Fターム
画像

※ 画像をクリックすると拡大します。

JP2003354037thum.jpg
出願権利状態 権利存続中


PAGE TOP

close
close
close
close
close
close
close