4点の囲む領域の座標

質問

平面座標(X, Y)の4点（平行四辺形）が与えられたとします。ある点が、その4点の座標内にあるか、無いかを調べる方法を教えて頂けないでしょうか？

回答No.5

age_momo

まあ、平行四辺形に限定ですが(三角形でもいいですが）
点A(xa,ya),点B(xb,yb),点C(xc,yc),点D(xd,yd)があって機械的に点P(X,Y)が
内部にあるかどうかを判定するとすると

まず、平行四辺形がどうつながっているか調べます。分かっている時は別に必要ありません。
ベクトル↑ABの成分　(xb-xa,yb-ya)
ベクトル↑CDの成分　(xd-xc,yd-yc)
それぞれが等しい時(つまり、(xb-xa,yb-ya)=(xd-xc,yd-yc))　平行四辺形はABDC
片方に-1倍した時等しい(つまり、(xb-xa,yb-ya)=-(xd-xc,yd-yc))　平行四辺形はABCD
全く違う時(|xb-xa|≠|xd-xc|) 平行四辺形はACBD
それぞれ点Aに対してつながっているのがB,Cの場合とB,Dの場合とC,Dの場合ということです。

AがB,Cとつながっている時の例を書きます。点Dは(xb+xc-2xa,b+yc-2ya)と
なっているはずです。
↑AP=t↑AB+s↑AC　となるt,sを計算すると点Pが平行四辺形内にあるときは
0≦t≦1,0≦s≦1が成り立ちます。いずれかが等号成立のとき、平行四辺形の
辺上ということになります。
実際の計算は行列計算で

(xb-xa,xc-xa)(t) (X)
(yb-ya,yc-ya)(s)=(Y)

となるt,sですから

(xb-xa,xc-xa)
(yb-ya,yc-ya)

の逆行列を作り、これに
(X)
(Y)
をかければいいでしょう。ということで結論として

t={(yc-ya)X+(xa-xc)Y}/{(xb-xa)(yc-ya)-(xc-xa)(yb-ya)}
s={(ya-yb)X+(xb-xa)Y}/{(xb-xa)(yc-ya)-(xc-xa)(yb-ya)}

を計算した時にそれぞれ0≦t≦1,0≦s≦1の範囲内かどうかを判定すればいいと思います。