4点の囲む領域の座標

質問

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

回答No.7

noname#101087

とりあえず、下記問答のファイナル(ANO.6)を利用してみて..... 。
その点(判定対象)について変換後座標 (s t) を求め、0≦s≦1 かつ 0≦t≦1 ならば四辺形の内点か境界、それ以外なら外点。
---------------------------------------
http://personal.okwave.jp/qa2867449.html
>NEC@OKWave / 座標変換

回答No.6

noname#57316

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

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

回答No.4

noname#221368

位相的性質を使うと明快です。といっても大した話じゃありません。

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

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

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

回答No.3

noname#160321

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

回答No.2

aiueo95240

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

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

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

回答No.1

take_5

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