図形の問題

質問

ある閉じた曲線で描かれた任意の図形があります（２次元）。ある点がその図形の内部に含まれるか否かを判定するにはどのようにすれば良いでしょうか？

図形はN-1個の点から成っていて、(x_i,y_i) (i=1,N; x_N=x_1,y_N=y_1)はデータとして蓄えられています。この時、ある点(x,y)がこの図形の内側にあるかどうかを判定したいのです。データ点が多いため、できるだけ効率的な判定法を探しています。

問題の図形はほぼ長方形ですが、所々でこぼこしていたり、大局的に辺が歪曲していたりするため、長方形で近似はできません。

回答No.2

麻野 なぎ（@AsanoNagi） · ベストアンサー

こんなページを見つけました。

http://www.tensyo.com/urame/prog/linealgo.htm
（直線のアルゴリズム）

多角形の外か中かの判定方法とサンプルが説明されています。
その他にも、非常に興味深いアルゴリズムがあります。

お礼

おお！こういう賢いのを探してました。ベクターが一回転するかどうか・・・素晴らしいですね。ありがとうございます。

回答No.1

Cupper

図形の外からその点に向かって直線を引き
図形の線を横切った数が
　奇数なら図形の内側
　偶数なら図形の外側
そういう判断方法もあります
横切った数を求める数式は…すみません。自身で考えてください

お礼

なるほど、直線との交点の数で判定できるのですね。直線と図形の交点の数を求めるのに一苦労しそうですが、一歩前進しました。ありがとうございます。