任意の座標が、閉図形の内側か外側かの判別

(x1,y1)(x2,y2)(x3,y3)…で構成された閉図形に対して、任意のポイント(xx,yy)が図形の内側にあるか、外側にあるかの判断はどのような計算式で求めることが出来るでしょうか？

VB6にて作成しております。
よろしくお願いします。

No.4 ベストアンサー 回答者： nag0720 回答日時： 2009/09/30 13:36

＃２です。

すみません、訂正です。

偶奇の判定が間違ってました。正しくは、
・交差する線分が偶数なら閉図形の外側、奇数なら閉図形の内側です。

この回答へのお礼

何とか作れそうです。
ありがとうございました。

お礼日時：2009/09/30 16:48

No.3 回答者： nag0720 回答日時： 2009/09/30 11:16

＃２です。

追記です。

線分(x1,y1)-(x2,y2)と、線分(xx,yy)-(x0,y0)とが交差するかどうかを調べる方法ですが、

x=x1+s(x2-x1)
y=y1+s(y2-y1)
x=xx+t(x0-xx)
y=yy+t(y0-yy)
の方程式から、sを求め、
0＜s≦1
なら、交差していると判定できます。

No.2 回答者： nag0720 回答日時： 2009/09/30 10:47

とりあえず、ぱっと思いつく方法を。

・閉図形外のポイント(x0,y0)を１つ決める。
・閉図形の各線分(xi,yi)-(x(i+1),y(i+1))と、線分(xx,yy)-(x0,y0)とが交差するかどうか調べる。
（ただし、閉図形の線分の始点は交点に含めない）
・交差する線分が偶数なら閉図形の内側、奇数なら閉図形の外側です。


イメージ的には、ポイント(xx,yy)から閉図形の外側に直線を引いて、閉図形の境界と何箇所で交差するかを調べるという方法です。

No.1 回答者： fujillin 回答日時： 2009/09/30 10:22

図形に関してはまったく知りませんが、三角形に限定してよいのなら高校数学程度でも解けそうなので…

三角形の各辺を辿るとして（右回りでも左回りでも可）、任意のポイント（Ｐとする）が常に辺に対して同じ側にあれば内側と判定できると思われます。
確か、数学のテストで、ある式の正負が辺のどちら側にあるかに一致することを証明せよという問題が出たような…（式は忘れてしまった）

今の知識で解くなら、辺を座標軸に一致するように座標変換したときのＰのX(またはY）座標の正負を求めるだけなので、それほど難しくはないと思う。
机上で解いておけば、↑の式も求められそうな気がするけれど、なんせ遠い昔の話なので…

という計算を各辺に対して行って、Ｐの位置（どちら側か）を確認すると言う方法ではいかがでしょうか？

実際に使われている実用的な方法があると思いますが、それについては他の方の回答にお任せいたします。