JPH11144041A - 領域内外判定方法 - Google Patents
領域内外判定方法Info
- Publication number
- JPH11144041A JPH11144041A JP32723297A JP32723297A JPH11144041A JP H11144041 A JPH11144041 A JP H11144041A JP 32723297 A JP32723297 A JP 32723297A JP 32723297 A JP32723297 A JP 32723297A JP H11144041 A JPH11144041 A JP H11144041A
- Authority
- JP
- Japan
- Prior art keywords
- polygon
- point
- outside
- area
- algorithm
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Landscapes
- Processing Or Creating Images (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
- Image Analysis (AREA)
Abstract
(57)【要約】
【課題】 計算を簡略化し、処理時間を短縮することが
できる領域内外判定方法を提供する。 【解決手段】 与えられた点列qi（i＝１〜Ｎｔｏｔ）
を直線で繋いでできる多角形Ａに対し、別に与えられた
点p＝（Ｘp，Ｙp）が多角形で囲まれる領域内に含まれ
るかどうかを判定する。そのために、領域外であること
が分かっている点poと点pを結んだ線分p poを考える。
線分p poと交わる多角形の辺qi qi+1の数を計算するこ
とにより、交わる辺の数が偶数ならば点pは領域外にあ
ると判定され、奇数ならば領域内にあると判定される。
できる領域内外判定方法を提供する。 【解決手段】 与えられた点列qi（i＝１〜Ｎｔｏｔ）
を直線で繋いでできる多角形Ａに対し、別に与えられた
点p＝（Ｘp，Ｙp）が多角形で囲まれる領域内に含まれ
るかどうかを判定する。そのために、領域外であること
が分かっている点poと点pを結んだ線分p poを考える。
線分p poと交わる多角形の辺qi qi+1の数を計算するこ
とにより、交わる辺の数が偶数ならば点pは領域外にあ
ると判定され、奇数ならば領域内にあると判定される。
Description
【０００１】
【発明の属する技術分野】本発明は、計算機を使用した
数値シミュレーションやグラフィック描画装置等に利用
される領域内外判定方法に関する。
数値シミュレーションやグラフィック描画装置等に利用
される領域内外判定方法に関する。
【０００２】
【従来の技術】点列qiを繋いでできる多角形Ａと点pが
与えられたとき、その内外判定の方法には、一般に、図
６に示すように多角形の各辺qi qi+1の、点pからのぞむ
角度αiを計算する手法が用いられている。点pが領域内
に含まれれば、角度の総和は±２πとなり、領域内に含
まれなければ０になる。
与えられたとき、その内外判定の方法には、一般に、図
６に示すように多角形の各辺qi qi+1の、点pからのぞむ
角度αiを計算する手法が用いられている。点pが領域内
に含まれれば、角度の総和は±２πとなり、領域内に含
まれなければ０になる。
【０００３】以下、この手法の概略を図７を用いて説明
する。
する。
【０００４】ここでは多角形の各辺をベクトルと見做
し、ｒi(→) ＝qi qi+1(→)、としている。なお、
（→）は、本明細書において便宜的にベクトルの表示を
示すものとする。また、点pと各辺のつくる三角形の角
度を図７のように表す。同図において、 αi＋βi＋γi＝π ……（１） γi＋βi+1＋θi＝π ……（２） の関係が成立ち、またベクトルｒi(→) とｒi+1(→) か
ら ｒi(→)・ｒi+1(→)＝ｒiｒi+1ｃｏｓθi …（３） となる。ここで、図７に示された角度はすべて向きを持
っていることに注意しなければならない。今、θiはベ
クトルｒiからｒi+1へ向かう角度が時計回りならば正、
反時計回りならば負と定義されているとすると、θiの
符号は、ｒi＝（ｘi，ｙi）として、ｘi+1ｙi−Ｙi+1Ｘ
iの符号に等しい。これより偏角θiは次式で求められ
る。
し、ｒi(→) ＝qi qi+1(→)、としている。なお、
（→）は、本明細書において便宜的にベクトルの表示を
示すものとする。また、点pと各辺のつくる三角形の角
度を図７のように表す。同図において、 αi＋βi＋γi＝π ……（１） γi＋βi+1＋θi＝π ……（２） の関係が成立ち、またベクトルｒi(→) とｒi+1(→) か
ら ｒi(→)・ｒi+1(→)＝ｒiｒi+1ｃｏｓθi …（３） となる。ここで、図７に示された角度はすべて向きを持
っていることに注意しなければならない。今、θiはベ
クトルｒiからｒi+1へ向かう角度が時計回りならば正、
反時計回りならば負と定義されているとすると、θiの
符号は、ｒi＝（ｘi，ｙi）として、ｘi+1ｙi−Ｙi+1Ｘ
iの符号に等しい。これより偏角θiは次式で求められ
る。
【０００５】
【数１】 ここで式（１），（２）より偏角の総和を考えると次の
ようになる。
ようになる。
【０００６】
【数２】 ここで、Ｎtot ＋１＝１としているからΣβi＝Σβi+1
となることを用いている。
となることを用いている。
【０００７】以上より、偏角総和Σθiの値を求めるこ
とによって、点pが内点（Σθi＝±２π）であるか、外
点（Σθi＝０）であるかの判定ができる。
とによって、点pが内点（Σθi＝±２π）であるか、外
点（Σθi＝０）であるかの判定ができる。
【０００８】
【発明が解決しようとする課題】しかしながら、上記従
来の領域内外判定方法においては、角度θiの計算は、
多角形の各辺ごとに逆ＣＯＳ計算をする必要があり、辺
の数が多い場合には相当の処理時間を要する。
来の領域内外判定方法においては、角度θiの計算は、
多角形の各辺ごとに逆ＣＯＳ計算をする必要があり、辺
の数が多い場合には相当の処理時間を要する。
【０００９】従来技術には、角度計算の回数を減らすよ
うに工夫をして計算時間を縮小させたものも提案されて
いるが、各辺の点pからのぞむ角度の総和を計算すると
いう基本的な考え方は変わっていないため、やはり相当
の処理時間を要していた。
うに工夫をして計算時間を縮小させたものも提案されて
いるが、各辺の点pからのぞむ角度の総和を計算すると
いう基本的な考え方は変わっていないため、やはり相当
の処理時間を要していた。
【００１０】本発明は上記従来の問題点に鑑み、計算を
簡略化して処理時間を短縮することができる領域内外判
定方法を提供することを目的とする。
簡略化して処理時間を短縮することができる領域内外判
定方法を提供することを目的とする。
【００１１】
【課題を解決するための手段】上記目的を達成するため
に、第１の発明では、与えられた点列qi（ｉ＝１〜Ｎto
t）を直線でつないでできる多角形Ａに対し、別に与え
られた点pと、前記多角形Ａで囲まれる領域外であるこ
とが分かっている点poとを結んだ線分p poが、前記多角
形Ａの辺qi qi+1（i＝１〜Ｎtot，Ｎtot＋１＝１）の何
本と交わるかを計算し、その計算結果に基づいて前記点
pが前記多角形Ａで囲まれる領域内に含まれるか否かを
判定するアルゴリズムを実行するようにしたものであ
る。
に、第１の発明では、与えられた点列qi（ｉ＝１〜Ｎto
t）を直線でつないでできる多角形Ａに対し、別に与え
られた点pと、前記多角形Ａで囲まれる領域外であるこ
とが分かっている点poとを結んだ線分p poが、前記多角
形Ａの辺qi qi+1（i＝１〜Ｎtot，Ｎtot＋１＝１）の何
本と交わるかを計算し、その計算結果に基づいて前記点
pが前記多角形Ａで囲まれる領域内に含まれるか否かを
判定するアルゴリズムを実行するようにしたものであ
る。
【００１２】第２の発明では、上記第１または第２の発
明において、前記多角形Ａを第一象限に含むように座標
軸を設定して、qi＝（Ｘi，Ｙi），p＝（Ｘp，Ｙp）と
し、領域外の点poをpo＝（Ｘp，０）にとり、前記線分p
poとしてＹ軸に平行な直線を設けて、前記線分p poと
前記多角形Ａの辺qi qi+1とが交わるか否かを判定する
アルゴリズムを実行するようにしたものである。
明において、前記多角形Ａを第一象限に含むように座標
軸を設定して、qi＝（Ｘi，Ｙi），p＝（Ｘp，Ｙp）と
し、領域外の点poをpo＝（Ｘp，０）にとり、前記線分p
poとしてＹ軸に平行な直線を設けて、前記線分p poと
前記多角形Ａの辺qi qi+1とが交わるか否かを判定する
アルゴリズムを実行するようにしたものである。
【００１３】第３の発明では、上記第１または第２の発
明において、前記アルゴリズムは、繰り返しループ中で
の条件文の使用を避けるように符号ビット（０：正、
１：負）を用いるものである。
明において、前記アルゴリズムは、繰り返しループ中で
の条件文の使用を避けるように符号ビット（０：正、
１：負）を用いるものである。
【００１４】第４の発明では、上記第３の発明におい
て、前記符号ビットを用いたアルゴリズムは、多角形の
頂点qi＝（Ｘi，Ｙi）を、与えられた点p＝（Ｘp，
Ｙp）、多角形で囲まれる領域外にある事が分かってい
る点po＝（Ｘo，Ｙo）とし、次式Ｍ１=(Ｘp- Ｘi)(Ｘp-
Ｘi+1)の符号ビットｓｉｇ１（Ｍ１＜０のとき１、Ｍ１
＞０のとき０）と、次式Ｍ２=(Ｘp-Ｘi){(Ｘp-Ｘi)(Ｙ
i+1-Ｙi)-(Ｙp-Ｙi)(Ｘi+1-Ｘi)}の符号ビットｓｉｇ２
( Ｍ２＜０のとき１、Ｍ２＞０のとき０）との積、ｓｉ
ｇ１×ｓｉｇ２の多角形のすべての辺についての和を求
め、これが偶数であるとき、与えられた点p は多角形で
囲まれる領域の外部にあり、奇数であるときには内部に
あると判定するようにしたものである。
て、前記符号ビットを用いたアルゴリズムは、多角形の
頂点qi＝（Ｘi，Ｙi）を、与えられた点p＝（Ｘp，
Ｙp）、多角形で囲まれる領域外にある事が分かってい
る点po＝（Ｘo，Ｙo）とし、次式Ｍ１=(Ｘp- Ｘi)(Ｘp-
Ｘi+1)の符号ビットｓｉｇ１（Ｍ１＜０のとき１、Ｍ１
＞０のとき０）と、次式Ｍ２=(Ｘp-Ｘi){(Ｘp-Ｘi)(Ｙ
i+1-Ｙi)-(Ｙp-Ｙi)(Ｘi+1-Ｘi)}の符号ビットｓｉｇ２
( Ｍ２＜０のとき１、Ｍ２＞０のとき０）との積、ｓｉ
ｇ１×ｓｉｇ２の多角形のすべての辺についての和を求
め、これが偶数であるとき、与えられた点p は多角形で
囲まれる領域の外部にあり、奇数であるときには内部に
あると判定するようにしたものである。
【００１５】第５の発明では、上記第３の発明におい
て、前記符号ビットを用いたアルゴリズムは、多角形の
頂点qi＝（Ｘi，Ｙi）を、与えられた点p＝（Ｘp，
Ｙp）、多角形で囲まれる領域外にある事が分かってい
る点po＝（Ｘo，Ｙo）とし、多角形の各辺について、次
式Ｍ１=(Ｘp- Ｘi)(Ｘp-Ｘi+1)を計算して、これが負で
ある場合のみ、次式Ｍ２=(Ｘp-Ｘi){(Ｘp-Ｘi)(Ｙi+1-
Ｙi)-(Ｙp-Ｙi)(Ｘi+1-Ｘi)}を求めて、その符号ビット
ｓｉｇ２( Ｍ２＜０のとき１、Ｍ２＞０のとき０）の和
を求め、これが偶数であるとき、与えられた点pは多角
形で囲まれる領域の外部にあり、奇数であるときには内
部にあると判定するようにしたものである。
て、前記符号ビットを用いたアルゴリズムは、多角形の
頂点qi＝（Ｘi，Ｙi）を、与えられた点p＝（Ｘp，
Ｙp）、多角形で囲まれる領域外にある事が分かってい
る点po＝（Ｘo，Ｙo）とし、多角形の各辺について、次
式Ｍ１=(Ｘp- Ｘi)(Ｘp-Ｘi+1)を計算して、これが負で
ある場合のみ、次式Ｍ２=(Ｘp-Ｘi){(Ｘp-Ｘi)(Ｙi+1-
Ｙi)-(Ｙp-Ｙi)(Ｘi+1-Ｘi)}を求めて、その符号ビット
ｓｉｇ２( Ｍ２＜０のとき１、Ｍ２＞０のとき０）の和
を求め、これが偶数であるとき、与えられた点pは多角
形で囲まれる領域の外部にあり、奇数であるときには内
部にあると判定するようにしたものである。
【００１６】第６の発明では、与えられた点列qi（i＝
１〜Ｎtot）を直線でつないでできる多角形Ａに対し、
別に与えられた点pと、前記多角形Ａで囲まれる領域外
であることが分かっている点poとを結んだ線分p poが、
前記多角形Ａの辺qi qi+1（i＝１〜Ｎtot，Ｎtot＋１＝
１）の何本と交わるかを計算し、その計算結果に基づい
て前記点pが前記多角形Ａで囲まれる領域内に含まれる
か否かを判定するアルゴリズムを記憶したものである。
１〜Ｎtot）を直線でつないでできる多角形Ａに対し、
別に与えられた点pと、前記多角形Ａで囲まれる領域外
であることが分かっている点poとを結んだ線分p poが、
前記多角形Ａの辺qi qi+1（i＝１〜Ｎtot，Ｎtot＋１＝
１）の何本と交わるかを計算し、その計算結果に基づい
て前記点pが前記多角形Ａで囲まれる領域内に含まれる
か否かを判定するアルゴリズムを記憶したものである。
【００１７】第７の発明では、上記第６の発明におい
て、前記多角形Ａを第一象限に含むように座標軸を設定
して、qi＝（Ｘi，Ｙi），p＝（Ｘp，Ｙp）とし、領域
外の点poをpo＝（Ｘp，０）にとり、前記線分p poとし
てＹ軸に平行な直線を設けて、前記線分p poと前記多角
形Ａの辺qi qi+1とが交わるか否かを判定するアルゴリ
ズムを記憶したものである。
て、前記多角形Ａを第一象限に含むように座標軸を設定
して、qi＝（Ｘi，Ｙi），p＝（Ｘp，Ｙp）とし、領域
外の点poをpo＝（Ｘp，０）にとり、前記線分p poとし
てＹ軸に平行な直線を設けて、前記線分p poと前記多角
形Ａの辺qi qi+1とが交わるか否かを判定するアルゴリ
ズムを記憶したものである。
【００１８】第８の発明では、上記第６または第７の発
明において、前記アルゴリズムは、繰り返しループ中で
の条件文の使用を避けるように符号ビット（０：正、
１：負）を用いたものである。
明において、前記アルゴリズムは、繰り返しループ中で
の条件文の使用を避けるように符号ビット（０：正、
１：負）を用いたものである。
【００１９】第９の発明では、上記第８の発明におい
て、前記符号ビットを用いたアルゴリズムは、多角形の
頂点qi＝（Ｘi，Ｙi）を、与えられた点p＝（Ｘp，
Ｙp）、多角形で囲まれる領域外にある事が分かってい
る点po＝（Ｘo，Ｙo）とし、次式Ｍ１=(Ｘp- Ｘi)(Ｘp-
Ｘi+1)の符号ビットｓｉｇ１（Ｍ１＜０のとき１、Ｍ１
＞０のとき０）と、次式Ｍ２=(Ｘp-Ｘi){(Ｘp-Ｘi)(Ｙ
i+1-Ｙi)-(Ｙp-Ｙi)(Ｘi+1-Ｘi)}の符号ビットｓｉｇ２
( Ｍ２＜０のとき１、Ｍ２＞０のとき０）との積、ｓｉ
ｇ１×ｓｉｇ２の多角形のすべての辺についての和を求
め、これが偶数であるとき、与えられた点p は多角形で
囲まれる領域の外部にあり、奇数であるときには内部に
あると判定するようにしたものである。
て、前記符号ビットを用いたアルゴリズムは、多角形の
頂点qi＝（Ｘi，Ｙi）を、与えられた点p＝（Ｘp，
Ｙp）、多角形で囲まれる領域外にある事が分かってい
る点po＝（Ｘo，Ｙo）とし、次式Ｍ１=(Ｘp- Ｘi)(Ｘp-
Ｘi+1)の符号ビットｓｉｇ１（Ｍ１＜０のとき１、Ｍ１
＞０のとき０）と、次式Ｍ２=(Ｘp-Ｘi){(Ｘp-Ｘi)(Ｙ
i+1-Ｙi)-(Ｙp-Ｙi)(Ｘi+1-Ｘi)}の符号ビットｓｉｇ２
( Ｍ２＜０のとき１、Ｍ２＞０のとき０）との積、ｓｉ
ｇ１×ｓｉｇ２の多角形のすべての辺についての和を求
め、これが偶数であるとき、与えられた点p は多角形で
囲まれる領域の外部にあり、奇数であるときには内部に
あると判定するようにしたものである。
【００２０】第１０の発明では、上記第８の発明におい
て、前記符号ビットを用いたアルゴリズムは、多角形の
頂点qi＝（Ｘi，Ｙi）を、与えられた点p＝（Ｘp，
Ｙp）、多角形で囲まれる領域外にある事が分かってい
る点po＝（Ｘo，Ｙo）とし、多角形の各辺について、次
式Ｍ１=(Ｘp- Ｘi)(Ｘp-Ｘi+1)を計算して、これが負で
ある場合のみ、次式Ｍ２=(Ｘp-Ｘi){(Ｘp-Ｘi)(Ｙi+1-
Ｙi)-(Ｙp-Ｙi)(Ｘi+1-Ｘi)}を求めて、その符号ビット
ｓｉｇ２( Ｍ２＜０のとき１、Ｍ２＞０のとき０）の和
を求め、これが偶数であるとき、与えられた点pは多角
形で囲まれる領域の外部にあり、奇数であるときには内
部にあると判定するようにしたものである。
て、前記符号ビットを用いたアルゴリズムは、多角形の
頂点qi＝（Ｘi，Ｙi）を、与えられた点p＝（Ｘp，
Ｙp）、多角形で囲まれる領域外にある事が分かってい
る点po＝（Ｘo，Ｙo）とし、多角形の各辺について、次
式Ｍ１=(Ｘp- Ｘi)(Ｘp-Ｘi+1)を計算して、これが負で
ある場合のみ、次式Ｍ２=(Ｘp-Ｘi){(Ｘp-Ｘi)(Ｙi+1-
Ｙi)-(Ｙp-Ｙi)(Ｘi+1-Ｘi)}を求めて、その符号ビット
ｓｉｇ２( Ｍ２＜０のとき１、Ｍ２＞０のとき０）の和
を求め、これが偶数であるとき、与えられた点pは多角
形で囲まれる領域の外部にあり、奇数であるときには内
部にあると判定するようにしたものである。
【００２１】
【発明の実施の形態】以下、図面を参照して本発明の実
施の形態を説明する。
施の形態を説明する。
【００２２】図１は、本発明の概念を説明するための図
である。
である。
【００２３】本発明の領域内外判定法は、図１に示すよ
うに、与えられた点列qi（i＝１〜Ｎtot）を直線で繋い
でできる多角形Ａに対し、別に与えられた点p＝（Ｘp，
Ｙp）が多角形で囲まれる領域内に含まれるかどうかを
判定する。そのために、領域外であることが分かってい
る点poと点pを結んだ線分p poを考える。線分p poと交
わる多角形の辺qi qi+1の数を計算することにより、交
わる辺の数が偶数ならば点pは領域外にあると判定さ
れ、奇数ならば領域内にあると判定される。
うに、与えられた点列qi（i＝１〜Ｎtot）を直線で繋い
でできる多角形Ａに対し、別に与えられた点p＝（Ｘp，
Ｙp）が多角形で囲まれる領域内に含まれるかどうかを
判定する。そのために、領域外であることが分かってい
る点poと点pを結んだ線分p poを考える。線分p poと交
わる多角形の辺qi qi+1の数を計算することにより、交
わる辺の数が偶数ならば点pは領域外にあると判定さ
れ、奇数ならば領域内にあると判定される。
【００２４】多角形の辺qi qi+1が線分p poと交わるか
どうかを判定するために、２つの量を考える。１つ目
は、qi，qi+1のＸ座標と線分p poのＸ座標Ｘpの位置関
係を表す量である。図２に示すように、辺qi qi+1が線
分p poと交わるためには、ＸpはＸiとＸi+1の間の値を
とる必要がある。そのため、 Ｍ1 ＝（Ｘp−Ｘi）（Ｘp−Ｘi+1） ……（６） という量を計算すると、Ｍ１＞０ならば、辺qi qi+1と
線分p poは交わらない。
どうかを判定するために、２つの量を考える。１つ目
は、qi，qi+1のＸ座標と線分p poのＸ座標Ｘpの位置関
係を表す量である。図２に示すように、辺qi qi+1が線
分p poと交わるためには、ＸpはＸiとＸi+1の間の値を
とる必要がある。そのため、 Ｍ1 ＝（Ｘp−Ｘi）（Ｘp−Ｘi+1） ……（６） という量を計算すると、Ｍ１＞０ならば、辺qi qi+1と
線分p poは交わらない。
【００２５】次に、辺qi qi+1と線分p poの位置関係を
考える。
考える。
【００２６】Ｍ１＜０の条件は満たされているとする
と、図３（ａ），（ｂ）に示したように、辺qi qi+1と
線分p poと交わるためには、辺qi qi+1 が線分qi pより
下方にある必要がある。Ｘi＜Ｘp＜Ｘi+1あるいはＸi+1
＜Ｘp＜Ｘiによって条件は違うから、次のような量を計
算する。
と、図３（ａ），（ｂ）に示したように、辺qi qi+1と
線分p poと交わるためには、辺qi qi+1 が線分qi pより
下方にある必要がある。Ｘi＜Ｘp＜Ｘi+1あるいはＸi+1
＜Ｘp＜Ｘiによって条件は違うから、次のような量を計
算する。
【００２７】 Ｍ2 ＝（Ｘp−Ｘi）｛（Ｘp−Ｘi）（Ｙi+1−Ｙi）−（Ｙp−Ｙi）（Ｘi+1 −Ｘi）｝……（７） Ｍ2 ＞０のとき、辺qi qi+1と線分p poとは交わらない
ことがわかる。
ことがわかる。
【００２８】以上の議論から、多角形の辺qi qi+1が線
分p poと交わるための条件は、Ｍ1＜０でかつＭ2 ＜０
であることがわかる。この両方の条件を満たす辺の数を
効率よく求めるアルゴリズムを考えればよいことにな
る。
分p poと交わるための条件は、Ｍ1＜０でかつＭ2 ＜０
であることがわかる。この両方の条件を満たす辺の数を
効率よく求めるアルゴリズムを考えればよいことにな
る。
【００２９】以下、具体的に第１実施形態を説明する。
【００３０】第１実施形態では、最も単純な方法とし
て、全ての辺に対してＭ1 とＭ2 を計算するものが挙げ
られる。
て、全ての辺に対してＭ1 とＭ2 を計算するものが挙げ
られる。
【００３１】図４は、本発明の第１実施形態の処理を示
すフローチャートである。
すフローチャートである。
【００３２】多角形Ａの辺の総数をＮtotとすると、Ｎt
ot回の繰り返しループ内で各辺qi qi+1についてＭ1 ，
Ｍ2 を計算する。それぞれの符号ビットの値を求め、ｓ
ｉｇ１，ｓｉｇ２とする。
ot回の繰り返しループ内で各辺qi qi+1についてＭ1 ，
Ｍ2 を計算する。それぞれの符号ビットの値を求め、ｓ
ｉｇ１，ｓｉｇ２とする。
【００３３】符号ビットは値が負のときには１となり、
正のときには０となるから、条件に合う場合すなわち辺
qi qi+1と線分p poが交わる場合は、Ｍ1 ＜０でかつＭ2
＜０より、ｓｉｇ１×ｓｉｇ２＝１となり、それ以外
ではｓｉｇ１×ｓｉｇ２＝０となる。
正のときには０となるから、条件に合う場合すなわち辺
qi qi+1と線分p poが交わる場合は、Ｍ1 ＜０でかつＭ2
＜０より、ｓｉｇ１×ｓｉｇ２＝１となり、それ以外
ではｓｉｇ１×ｓｉｇ２＝０となる。
【００３４】よって全ての辺に対してｓｉｇ１×ｓｉｇ
２を計算し、その総和をとれば（ステップＳ１１）、そ
の偶数／奇数により点pの内外判定ができる（ステップ
Ｓ１２）。すなわち、偶数ならば点pは領域外にあると
判定され（ステップＳ１３）、奇数ならば領域内にある
と判定される（ステップＳ１４）。
２を計算し、その総和をとれば（ステップＳ１１）、そ
の偶数／奇数により点pの内外判定ができる（ステップ
Ｓ１２）。すなわち、偶数ならば点pは領域外にあると
判定され（ステップＳ１３）、奇数ならば領域内にある
と判定される（ステップＳ１４）。
【００３５】このように、本実施形態では、初等的な代
数のみを用いて領域の内外判定を行う。その際に、条件
文を多用すると計算時間が増大し、初等的な代数のみを
用いる利点が失われてしまうため、条件文を使わずに済
む方法を工夫している。
数のみを用いて領域の内外判定を行う。その際に、条件
文を多用すると計算時間が増大し、初等的な代数のみを
用いる利点が失われてしまうため、条件文を使わずに済
む方法を工夫している。
【００３６】要するに、本実施形態では、領域の内外判
定に際し角度の計算を含まないため、逆ＣＯＳ関数のよ
うな計算時間のかかる演算を必要とせず、初等的な演算
のみからアルゴリズムを構成することができる。また符
号ビットを利用することにより条件文を使わないように
工夫がなされているため、計算時間を大幅に短縮するこ
とができる。
定に際し角度の計算を含まないため、逆ＣＯＳ関数のよ
うな計算時間のかかる演算を必要とせず、初等的な演算
のみからアルゴリズムを構成することができる。また符
号ビットを利用することにより条件文を使わないように
工夫がなされているため、計算時間を大幅に短縮するこ
とができる。
【００３７】次に、本発明の第２実施形態を説明する。
【００３８】第２実施形態では、多角形の辺の数Ｎtot
が常に大きい場合を考える。上記第１実施形態では辺の
数だけ回るループの中でＭ1 とＭ2 の両方を計算してい
る。しかし実際には、Ｍ1 ＞０の場合にはＭ2 の値にか
かわらず、qi qi+1と線分p poは交わらないといえるか
ら、第２実施形態のように、まずＭ1 を計算して条件に
合うもののみを選択し、そしてＭ2 を計算した方が計算
時間を縮小できる。
が常に大きい場合を考える。上記第１実施形態では辺の
数だけ回るループの中でＭ1 とＭ2 の両方を計算してい
る。しかし実際には、Ｍ1 ＞０の場合にはＭ2 の値にか
かわらず、qi qi+1と線分p poは交わらないといえるか
ら、第２実施形態のように、まずＭ1 を計算して条件に
合うもののみを選択し、そしてＭ2 を計算した方が計算
時間を縮小できる。
【００３９】図５は、本発明の第２実施形態の処理を示
すフローチャートである。
すフローチャートである。
【００４０】始めのループではまずＭ1 を計算し、Ｍ1
＜０の時のみポインタに座標値をいれる（ステップＳ２
１）。Ｍ1 ＜０となる辺の数をＮmidとすると、２番目
のループはＮmid回のループであり、その中でＭ2 を計
算して（ステップＳ２２）、最終的に条件に合うかどう
か、すなわちqi qi+1と線分p poが交わるかどうかをＭ2
の正負により判定する。
＜０の時のみポインタに座標値をいれる（ステップＳ２
１）。Ｍ1 ＜０となる辺の数をＮmidとすると、２番目
のループはＮmid回のループであり、その中でＭ2 を計
算して（ステップＳ２２）、最終的に条件に合うかどう
か、すなわちqi qi+1と線分p poが交わるかどうかをＭ2
の正負により判定する。
【００４１】本実施形態では、ｓｉｇ２を計算し、その
総和をとれば（ステップＳ２２）、その偶数／奇数によ
り点pの内外判定ができる（ステップＳ２３）。すなわ
ち、偶数ならば点pは領域外にあると判定され（ステッ
プＳ２４）、奇数ならば領域内にあると判定される（ス
テップＳ２５）。Ｎtot＞＞Ｎmidならば、上記第１実施
形態に比べてかなり計算時間を短縮することができる。
総和をとれば（ステップＳ２２）、その偶数／奇数によ
り点pの内外判定ができる（ステップＳ２３）。すなわ
ち、偶数ならば点pは領域外にあると判定され（ステッ
プＳ２４）、奇数ならば領域内にあると判定される（ス
テップＳ２５）。Ｎtot＞＞Ｎmidならば、上記第１実施
形態に比べてかなり計算時間を短縮することができる。
【００４２】上記図４または図５に示すフローチャート
に従ったプログラムを計算機の記憶装置に格納し動作す
ることにより、計算機を利用した様々な応用分野、例え
ば数値シミュレーションやグラフィックの基本ツール群
としてグラフィック描画装置に応用して、上述の領域内
外判定方法を実現させることが可能となる。そのプログ
ラムは、例えば、計算機に接続された外部記憶装置（Ｆ
Ｄ、ＣＤ−ＲＯＭ、ＲＯＭ、磁気テープ等）の記憶媒体
に記憶されており、計算機内の読み取り装置によって、
計算機内に読み取られる。
に従ったプログラムを計算機の記憶装置に格納し動作す
ることにより、計算機を利用した様々な応用分野、例え
ば数値シミュレーションやグラフィックの基本ツール群
としてグラフィック描画装置に応用して、上述の領域内
外判定方法を実現させることが可能となる。そのプログ
ラムは、例えば、計算機に接続された外部記憶装置（Ｆ
Ｄ、ＣＤ−ＲＯＭ、ＲＯＭ、磁気テープ等）の記憶媒体
に記憶されており、計算機内の読み取り装置によって、
計算機内に読み取られる。
【００４３】
【発明の効果】以上詳述したように、本発明の領域内外
判定方法によれば、初等的な計算と単純な（条件文を含
まない）ループによりアルゴリズムを構成することがで
きるので、処理時間が短縮して実用上極めて有効であ
る。
判定方法によれば、初等的な計算と単純な（条件文を含
まない）ループによりアルゴリズムを構成することがで
きるので、処理時間が短縮して実用上極めて有効であ
る。
【００４４】さらに、符号ビットを利用することによ
り、繰り返しループ中での条件文の使用が回避されるた
め、ベクトル化等を利用した処理の高速化にも対応でき
る。
り、繰り返しループ中での条件文の使用が回避されるた
め、ベクトル化等を利用した処理の高速化にも対応でき
る。
【図１】本発明の概念図である。
【図２】Ｍ1 の計算を説明するための図である。
【図３】Ｍ2 の計算を説明するための図である。
【図４】本発明の第１実施形態の処理を示すフローチャ
ートである。
ートである。
【図５】本発明の第２実施形態の処理を示すフローチャ
ートである。
ートである。
【図６】従来の角度計算の模式図である。
【図７】従来の角度計算を説明するための図である。
qi 与えられた点列 Ａ 与えられた点列qiを直線でつないでできる多角形 p 与えられた点
Claims (10)
- 【請求項１】 与えられた点列qi（ｉ＝１〜Ｎtot）を
直線でつないでできる多角形Ａに対し、別に与えられた
点pと、前記多角形Ａで囲まれる領域外であることが分
かっている点poとを結んだ線分p poが、前記多角形Ａの
辺qi qi+1（i＝１〜Ｎtot，Ｎtot＋１＝１）の何本と交
わるかを計算し、 その計算結果に基づいて前記点pが前記多角形Ａで囲ま
れる領域内に含まれるか否かを判定するアルゴリズムを
実行することを特徴とする領域内外判定方法。 - 【請求項２】 前記多角形Ａを第一象限に含むように座
標軸を設定して、qi＝（Ｘi，Ｙi），p＝（Ｘp，Ｙp）
とし、領域外の点poをpo＝（Ｘp，０）にとり、前記線
分p poとしてＹ軸に平行な直線を設けて、前記線分p po
と前記多角形Ａの辺qi qi+1とが交わるか否かを判定す
るアルゴリズムを実行することを特徴とする請求項１記
載の領域内外判定方法。 - 【請求項３】 前記アルゴリズムは、繰り返しループ中
での条件文の使用を避けるように符号ビット（０：正、
１：負）を用いたことを特徴とする請求項１または請求
項２記載の領域内外判定方法。 - 【請求項４】 前記符号ビットを用いたアルゴリズム
は、多角形の頂点qi＝（Ｘi，Ｙi）を、与えられた点p
＝（Ｘp，Ｙp）、多角形で囲まれる領域外にある事が分
かっている点po＝（Ｘo，Ｙo）とし、次式 Ｍ１=(Ｘp- Ｘi)(Ｘp-Ｘi+1) の符号ビットｓｉｇ１（Ｍ１＜０のとき１、Ｍ１＞０の
とき０）と、次式 Ｍ２=(Ｘp-Ｘi){(Ｘp-Ｘi)(Ｙi+1-Ｙi)-(Ｙp-Ｙi)(Ｘ
i+1-Ｘi)} の符号ビットｓｉｇ２( Ｍ２＜０のとき１、Ｍ２＞０の
とき０）との積、ｓｉｇ１×ｓｉｇ２の多角形のすべて
の辺についての和を求め、これが偶数であるとき、与え
られた点p は多角形で囲まれる領域の外部にあり、奇数
であるときには内部にあると判定することを特徴とする
請求項３記載の領域内外判定方法。 - 【請求項５】 前記符号ビットを用いたアルゴリズム
は、多角形の頂点qi＝（Ｘi，Ｙi）を、与えられた点p
＝（Ｘp，Ｙp）、多角形で囲まれる領域外にある事が分
かっている点po＝（Ｘo，Ｙo）とし、多角形の各辺につ
いて、次式 Ｍ１=(Ｘp- Ｘi)(Ｘp-Ｘi+1) を計算して、これが負である場合のみ、次式 Ｍ２=(Ｘp-Ｘi){(Ｘp-Ｘi)(Ｙi+1-Ｙi)-(Ｙp-Ｙi)(Ｘ
i+1-Ｘi)} を求めて、その符号ビットｓｉｇ２( Ｍ２＜０のとき
１、Ｍ２＞０のとき０）の和を求め、これが偶数である
とき、与えられた点pは多角形で囲まれる領域の外部に
あり、奇数であるときには内部にあると判定することを
特徴とする請求項３記載の領域内外判定方法。 - 【請求項６】 与えられた点列qi（i＝１〜Ｎtot）を直
線でつないでできる多角形Ａに対し、別に与えられた点
pと、前記多角形Ａで囲まれる領域外であることが分か
っている点poとを結んだ線分p poが、前記多角形Ａの辺
qi qi+1（i＝１〜Ｎtot，Ｎtot＋１＝１）の何本と交わ
るかを計算し、その計算結果に基づいて前記点pが前記
多角形Ａで囲まれる領域内に含まれるか否かを判定する
アルゴリズムを記憶したことを特徴とする機械読み出し
可能な記憶媒体。 - 【請求項７】 前記多角形Ａを第一象限に含むように座
標軸を設定して、qi＝（Ｘi，Ｙi），p＝（Ｘp，Ｙp）
とし、領域外の点poをpo＝（Ｘp，０）にとり、前記線
分p poとしてＹ軸に平行な直線を設けて、前記線分p po
と前記多角形Ａの辺qi qi+1とが交わるか否かを判定す
るアルゴリズムを記憶したことを特徴とする請求項６記
載の機械読み出し可能な記憶媒体。 - 【請求項８】 前記アルゴリズムは、繰り返しループ中
での条件文の使用を避けるように符号ビット（０：正、
１：負）を用いたことを特徴とする請求項６または請求
項７記載の機械読み出し可能な記憶媒体。 - 【請求項９】 前記符号ビットを用いたアルゴリズム
は、多角形の頂点qi＝（Ｘi，Ｙi）を、与えられた点p
＝（Ｘp，Ｙp）、多角形で囲まれる領域外にある事が分
かっている点po＝（Ｘo，Ｙo）とし、次式 Ｍ１=(Ｘp- Ｘi)(Ｘp-Ｘi+1) の符号ビットｓｉｇ１（Ｍ１＜０のとき１、Ｍ１＞０の
とき０）と、次式 Ｍ２=(Ｘp-Ｘi){(Ｘp-Ｘi)(Ｙi+1-Ｙi)-(Ｙp-Ｙi)(Ｘ
i+1-Ｘi)} の符号ビットｓｉｇ２( Ｍ２＜０のとき１、Ｍ２＞０の
とき０）との積、ｓｉｇ１×ｓｉｇ２の多角形のすべて
の辺についての和を求め、これが偶数であるとき、与え
られた点p は多角形で囲まれる領域の外部にあり、奇数
であるときには内部にあると判定することを特徴とする
請求項８記載の機械読み出し可能な記憶媒体。 - 【請求項１０】 前記符号ビットを用いたアルゴリズム
は、多角形の頂点qi＝（Ｘi，Ｙi）を、与えられた点p
＝（Ｘp，Ｙp）、多角形で囲まれる領域外にある事が分
かっている点po＝（Ｘo，Ｙo）とし、多角形の各辺につ
いて、次式 Ｍ１=(Ｘp- Ｘi)(Ｘp-Ｘi+1) を計算して、これが負である場合のみ、次式 Ｍ２=(Ｘp-Ｘi){(Ｘp-Ｘi)(Ｙi+1-Ｙi)-(Ｙp-Ｙi)(Ｘ
i+1-Ｘi)} を求めて、その符号ビットｓｉｇ２( Ｍ２＜０のとき
１、Ｍ２＞０のとき０）の和を求め、これが偶数である
とき、与えられた点pは多角形で囲まれる領域の外部に
あり、奇数であるときには内部にあると判定することを
特徴とする請求項８記載の機械読み出し可能な記憶媒
体。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP32723297A JPH11144041A (ja) | 1997-11-13 | 1997-11-13 | 領域内外判定方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP32723297A JPH11144041A (ja) | 1997-11-13 | 1997-11-13 | 領域内外判定方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH11144041A true JPH11144041A (ja) | 1999-05-28 |
Family
ID=18196806
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP32723297A Pending JPH11144041A (ja) | 1997-11-13 | 1997-11-13 | 領域内外判定方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH11144041A (ja) |
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20160073147A (ko) * | 2014-12-16 | 2016-06-24 | 삼성전자주식회사 | Gpu 기반 벡터 그래픽을 위한 메쉬 생성 장치, 방법 및 컴퓨터 프로그램 |
| CN106970396A (zh) * | 2016-12-30 | 2017-07-21 | 重庆多道电子技术有限公司 | 确定目标对象有效进入指定地理区域的方法 |
| CN106980128A (zh) * | 2016-12-30 | 2017-07-25 | 重庆多道电子技术有限公司 | 数据处理装置 |
| CN109613577A (zh) * | 2018-12-25 | 2019-04-12 | 北京锐安科技有限公司 | 一种位置确定方法、装置、终端设备和存储介质 |
| US20240087463A1 (en) * | 2022-09-09 | 2024-03-14 | The Boeing Company | Identifying an object in an area of interest |
-
1997
- 1997-11-13 JP JP32723297A patent/JPH11144041A/ja active Pending
Cited By (8)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR20160073147A (ko) * | 2014-12-16 | 2016-06-24 | 삼성전자주식회사 | Gpu 기반 벡터 그래픽을 위한 메쉬 생성 장치, 방법 및 컴퓨터 프로그램 |
| CN106970396A (zh) * | 2016-12-30 | 2017-07-21 | 重庆多道电子技术有限公司 | 确定目标对象有效进入指定地理区域的方法 |
| CN106980128A (zh) * | 2016-12-30 | 2017-07-25 | 重庆多道电子技术有限公司 | 数据处理装置 |
| CN109613577A (zh) * | 2018-12-25 | 2019-04-12 | 北京锐安科技有限公司 | 一种位置确定方法、装置、终端设备和存储介质 |
| CN109613577B (zh) * | 2018-12-25 | 2021-07-09 | 北京锐安科技有限公司 | 一种位置确定方法、装置、终端设备和存储介质 |
| US20240087463A1 (en) * | 2022-09-09 | 2024-03-14 | The Boeing Company | Identifying an object in an area of interest |
| EP4343734A1 (en) * | 2022-09-09 | 2024-03-27 | The Boeing Company | Identifying an object in an area of interest |
| US12354487B2 (en) * | 2022-09-09 | 2025-07-08 | The Boeing Company | Identifying an object in an area of interest |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US4864520A (en) | Shape generating/creating system for computer aided design, computer aided manufacturing, computer aided engineering and computer applied technology | |
| KR900004251B1 (ko) | 부품 삽입용 수치 제어 데이터의 작성 방법 및 장치 | |
| US9341475B2 (en) | Geomagnetism measurement apparatus | |
| US9001127B2 (en) | Method and device for processing vector graphics | |
| US7187390B2 (en) | Method and program for determing intersection point of triangle with line segment | |
| Fleischer et al. | On simultaneous inner and outer approximation of shapes | |
| JPH11144041A (ja) | 領域内外判定方法 | |
| JPH0833301B2 (ja) | 地磁気センサの着磁補正法 | |
| CN109636879A (zh) | 带岛的多边形曲线偏移算法 | |
| EP0349182B1 (en) | Method and apparatus for approximating polygonal line to curve | |
| JP2008009719A (ja) | 直線描画方法、直線描画プログラム及び直線描画装置 | |
| CN118114620B (zh) | 一种电路板钻孔标志的数据交换方法、装置、设备及介质 | |
| EP0278527B1 (en) | Circuit for detecting an end point of an arc | |
| US7548838B2 (en) | Method for designing development drawing of developable surface | |
| JPS63186329A (ja) | 三角関数前処理装置 | |
| US6226014B1 (en) | Ellipse filling graphics method | |
| JPH1166328A (ja) | 曲線描画装置 | |
| CN111331600B (zh) | 轨迹调整方法及相关设备 | |
| US20050280658A1 (en) | Method of accurate fixed-point line clipping | |
| JP2728193B2 (ja) | 図面のトレース方法及び装置 | |
| JPH11339067A (ja) | 図形処理方法及び記憶媒体 | |
| JPH1049652A (ja) | ３次元ｃａｄにおけるｂ−スプライン曲線と直線との交点算出方法 | |
| JPH11110569A (ja) | 図形の内点判定方法 | |
| JP2783143B2 (ja) | 計算機支援設計装置 | |
| JPH10275240A (ja) | 円弧補間処理方法 |