4点の囲む領域の座標

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

No.7 回答者： noname#101087 回答日時： 2008/03/29 12:20

とりあえず、下記問答のファイナル(ANO.6)を利用してみて..... 。

その点(判定対象)について変換後座標 (s t) を求め、0≦s≦1 かつ 0≦t≦1 ならば四辺形の内点か境界、それ以外なら外点。
---------------------------------------
http://personal.okwave.jp/qa2867449.html
>NEC@OKWave / 座標変換
　

No.6 回答者： noname#57316 回答日時： 2008/03/29 07:32

”ある点”が原点に来るように平行四辺形を平行移動させます。

そして、平行四辺形の四点のX、Y座標の最大値、最小値が
いずれも正と負となっているかどうかを調べることにより、
”ある点”が、平行四辺形の中にあるか否か、分かります。

No.5 回答者： age_momo 回答日時： 2008/03/29 06:26

まあ、平行四辺形に限定ですが(三角形でもいいですが）

点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の範囲内かどうかを判定すればいいと思います。

No.4 回答者： ddtddtddt 回答日時： 2008/03/28 13:02

　位相的性質を使うと明快です。

といっても大した話じゃありません。

　以下の方法は、多角形の頂点が左回りに順序付けられている事を前提にしています。

　多角形の内部に、自分が入っていると想像して下さい。順序付けられた頂点を順番に見ていくと、自分は一回転（θ＝2π）するはずです。
　次に多角形の外にいる場合を想像します。一番近くの頂点（正面）から順番に見ていくと、首の動作は、右回り → 領域の右端 → 左回り → 領域の左端 → 右回り → 正面（終了）となるはずです。この時、首を左右に直角に回すと、多角形が見えない事も想像出来ますよね？。という訳で、θ＜π です。
　さらに境界辺上にいる時は、右に直角に見て、自分のいる辺の右端を見通し、頂点を順にたどれば、首は左に回り、左直角に自分のいる辺の左端を見通して終わりです。よって、θ＝π。
　最後に、頂点上にいる場合は、自分の座標と頂点座標を比較して判定できます。
　従って、
　　・座標比較 → 頂点上だった（境界上）．
　　・座標比較 → 頂点上でない → θ を計算．
で、 内部，外部，境界上を判定できます。

　じつはプログラムでよく使うんですよ。

No.3 回答者： doc_sunday 回答日時： 2008/03/28 08:38

単純なお答えで済みません。

(小学校程度か？)
平行四辺形ＡＢＣＤがあるとき、必ずｘの最大と最小、ｙも最大と最小があります。(だから当たり前)
ある点(X,Y)のXがｘの最大と最小の間にあり、Yもｙの最大と最小の間にあれば、ＡＢＣＤの中にあります。
でもこれは、平行四辺形でなくて凹でない四角形になら何でも当てはまるから、もっと良い方法があるはず。

No.2 回答者： aiueo95240 回答日時： 2008/03/28 00:49

まず、座標平面に３点A,B,Cがあったとします。

A,B,Cが左回りか右回りかを判定する方法があります。
それは、三角形ABCの面積を、行列式を使って表示し、それが正の値をとるか負の値をとるかに対応します。

３点A,B,Cのそれぞれを結ぶ直線で、平面は７つの領域に分けられます。
座標平面にさらに点Dがあったとき、それがどこの領域に属するか?
それは、三角形ABD、三角形BCD、三角形CADの符号付面積の符号の組合わせに対応します。
全部が正のときと全部が負のとき、点Dは三角形ABCの内部に属します。

その事実を質問内容に応用すればいいです。

No.1 回答者： take_5 回答日時： 2008/03/27 23:29

高校数学の正領域・負領域の知識を使うだけ。