直線が空間の三角形内部を通るかどうか

空間に3点(a1,b1,c1), (a2,b2,c2), (a3,b3,c3)と
2点(x1,y1,z1),(x2,y2,z2)を通る直線があります。
その3点がなす三角形内を直線が通るかどうか判別したいです。
よろしくお願いいたします。

No.7 ベストアンサー 回答者： 178-tall 回答日時： 2012/08/28 19:29

「三角形内」を意識しすぎ、煩雑な表現になってました。

以下、整理しなおし。

>空間に3点 …
Po (a1,b1,c1), P1 (a2,b2,c2), P2 (a3,b3,c3) にて (例えば) 、
　ベクトル Po →P1 を e (a1, b1, c1)
　ベクトル P1→P2 を f (a2-a1, b2-b1, c2-c1)
　ベクトル P1→P3 を g (a3-a1, b3-b1, c3-c1)
とすれば、始点が原点 O (0, 0, 0) で、終点が三角形 P1-P2-P3 を含む平面上の点であるベクトル p は、
　p = e + s*f + t*g　　　…(1)
と表せる。(三角形がペチャンコでない場合)

> 2点(x1,y1,z1),(x2,y2,z2)を通る直線 …
　ベクトル qo (x1,y1,z1)
　ベクトル q1 (x2,y2,z2)
とすれば、2 点を通る直線上の点であるベクトル q は、
　q = qo + u*(q1-qo)　　　…(2)
と表せる。

(1), (2) を等置した線形方程式は行列表示でき、三角形 P1-P2-P3 を含む平面と 2 点を通る直線との交点における {s, t, u} を求め得ます。
(交点解 {s, t, u} が存在する場合)、交点が三角形内 (凸領域内) にあるか否か、あるいは線分内 (凸領域内) にあるか否か、は {s, t, u} の値から容易に判別できそう。

　　　

No.9 回答者： 178-tall 回答日時： 2012/08/29 07:49

目算できそうな一例でも。

　p = e + s*f + t*g　　　…(1)
　q = qo + u*(q1-qo)　　　…(2)
を等置した線形方程式
　e + s*f + t*g = qo + u*(q1-qo)　　　…(3)
に縦ベクトル e (a1, b1, c1), f (a2-a1, b2-b1, c2-c1), g (a3-a1, b3-b1, c3-c1) , qo (x1,y1,z1), q1 (x2,y2,z2) を代入して、スカラー s, t, u を求めてみると…。

(3) の行列算式では、縦行列 [s ; t ; u ] に
　　　[ -1　-1　 1 ;
M =　　1　 0　 1 ;
　　　 0　 1　 1 ]
を掛けたものが、縦行列 [e - qo] に等しい。
スカラー s, t, u を求めてみると、
　s = t = 1/3, u = 2/3

得られた p を k*{f + h*(g - f)} の形にしてみると、k = kh = 2/3 で、交点は三角形内にある。
また、u = 2/3 なので、交点は線分上 (凸領域内) にある。

　　

この回答へのお礼

何度もご丁寧にありがとうございます。

お礼日時：2012/08/29 10:25

No.8 回答者： muturajcp 回答日時： 2012/08/29 05:46

#7の方とだいたい同じですが、少し具体化しました。

直線
L={(x,y,z)=(x1,y1,z1)+u(x2-x1,y2-y1,z2-z1)|u∈R}
と
3角形
△={(x,y,z)=(a1,b1,c1)+s(a2-a1,b2-b1,c2-c1)+t(a3-a1,b3-b1,c3-c1)|(0≦s)&(0≦t)&(s+t≦1)}
の交点を
(x,y,z)
とすると
(x,y,z)=(x1,y1,z1)+u(x2-x1,y2-y1,z2-z1)
=(a1,b1,c1)+s(a2-a1,b2-b1,c2-c1)+t(a3-a1,b3-b1,c3-c1)

s(a2-a1)+t(a3-a1)+u(x1-x2)=x1-a1
s(b2-b1)+t(b3-b1)+u(y1-y2)=y1-b1
s(c2-c1)+t(c3-c1)+u(z1-z2)=z1-c1
だから
3個の未知数(s,t,u)に関する3元連立1次方程式を解けばよい

A=
(a2-a1,a3-a1,x1-x2)
(b2-b1,b3-b1,y1-y2)
(c2-c1,c3-c1,z1-z2)

X=転(s,t,u),(転(s,t,u)は(s,t,u)の転置縦ベクトル)
B=転(x1-a1,y1-b1,z1-c1)
とすると
Aの行列式|A|≒0のときLと△が平行となるから交点は無い
|A|≠0のときAの逆行列A^{-1}が存在して
転(s,t,u)=X=A^{-1}B
とs,t,uを求めることができる。
求めたs,tに対して
(s<0)or(t<0)or(s+t>1)のときは△の外を直線Lが通る
(0≦s)&(0≦t)&(s+t≦1)のときは△内を直線Lが通る

この回答へのお礼

ありがとうございます。
１つ１つ理解してみます。

お礼日時：2012/08/29 10:24

No.6 回答者： hashioogi 回答日時： 2012/08/28 16:00

立方体を構成する6面をそれぞれ2つの直角三角形に分けて12個の直角三角形にして立方体の内部にある2点を通る直線がそれぞれの3角形の内部を通過するかどうかで立方体と直線の交点を求めて面との交点間の距離を求める作戦だと推測いたします。

私のやり方は手数がかかりますから採用していただけるかどうかはわかりませんが…。
(1) 直線上の2点は確実に立方体の内部にあることが前提です。
(2) 立方体を構成する8点をA～Hとします。立方体の内部の2点をJ、Kとします。
(3) Jが原点になるようにA～H、Kを平行移動します。
(4) KがX軸の上になるようにA～H、Kを原点を中心に回転させます。3×3の回転行列を2回ずつそれぞれの点に掛ければ実現できるはずです。

以下は1つの面について考えますが6回繰り返すと思ってください。
(5) 6面の各面はそれぞれA～Hの中の4点で構成されますが、その内の任意の3点で面の式が決まります。例えば、ある正方形の頂点がABCDならばABCの3点でもBCDの3点でも同じ式になりますからどれか1つの三角形を選べばよいです。
(6) その面の式にY=0、Z=0を代入すれば、面がX軸と交わる点のX座標xが求まります。つまり面はX軸と(x,0,0)で交わるわけです。面がX軸と平行な場合は交点はないので無視します。

(7) 以上を6回繰り返すと最大で6個のxが求まります。X軸に平行な面がなければ6個のxのうち3個は負の値、3個は正の値をとります。平行な面があっても少なくても1つの正のxと負のxが求まるはずです。
(8) 負のxの中で一番大きなxをx0、正のxの中で一番小さなxをx1とした場合、x1-x0が立方体と直線の交点の2点間の長さになります。

このやり方は直線が三角形の内部を通るかどうかの判定は必要としません。

No.5 回答者： 178-tall 回答日時： 2012/08/28 11:00

>挑戦してみます。

ｍが任意ですし、不等式がいくつかあるので、大変そうですが。

　m*q = p = k*{a + h*(b - a)}
の算式化を試行中。

{h, k, m} を未知数とした線形方程式になりそう。
三角形がペチャンコでなく、直線を決める二点が三角形を含む平面上になければ、
一意解 {h, k, m} が得られるでしょう。

　　

この回答へのお礼

ありがとうございます。
挑戦してみます。

お礼日時：2012/08/29 10:22

No.4 回答者： 178-tall 回答日時： 2012/08/27 19:08

>空間に3点(a1,b1,c1), (a2,b2,c2), (a3,b3,c3)と 2点(x1,y1,z1),(x2,y2,z2)を通る直線があります。

その3点がなす三角形内を直線が通るかどうか判別したい …

三角形の一頂点から他の二頂点に向かう二つのベクトル a, b を想定してみる。
三角形内 (とりあえず辺上は除外) の一点 P に向かうベクトル p は、例えば、
　p = k*{a + h*(b - a)}　　 (0 < h, k < 1)
と表せる。(三角形がペチャンコでなければ、一意的だろう)

ついで、(三角形を含む平面上にない) 二点の一方から他方に向かうベクトル q を想定。
ベクトル q の m 倍が三角形を含む平面上にあるとき、
　m*q = p = k*{a + h*(b - a)}
と表せるだろうが、もしも 0 < h, k < 1 が成立てば、そこは三角形内。

…という作戦はいかが？
　　　

この回答へのお礼

ありがとうございます。
挑戦してみます。
ｍが任意ですし、不等式がいくつかあるので、大変そうですが。

他の方の回答も含めて、考えていたのですが、
三角形の平面と直線との交点を求めて、
その交点Oとの三角形の頂点ABCとのベクトルを考えて
それぞれOA,OBの外積、OB,OCの外積、OC,OAの外積が
同じ方向というのはどうでしょう。
外積の３つの空間ベクトルが同じ方向向いている
式の上での判別がわかりませんが。

お礼日時：2012/08/28 09:13

No.3 回答者： ferien 回答日時： 2012/08/27 18:42

ANo.2です。

追加です。

＞その3点がなす三角形内を直線が通るかどうか判別したいです。
三角形内の１点が直線上の点であればいいので、
その点の座標を直線の方程式に代入して、等式が成り立てばいいと思います。
三角形の作る平面との交点を求めて、その座標が三角形内にあるかどうか
調べるでもいいです。

この回答へのお礼

ありがとうございます。
この方法も考えたのですが、
なかなか式が立てられず、困っております。

お礼日時：2012/08/28 08:58

No.2 回答者： ferien 回答日時： 2012/08/27 18:22

三角形がつくる平面と２点を通る直線が平行でなければ、通ると思います。

あとは、５個の点が同じ平面上になければ、いいのではないでしょうか？

No.1 回答者： Tacosan 回答日時： 2012/08/27 18:01

そうですか.

何が疑問なのかさっぱりわかりませんが, 頑張ってください.

この回答へのお礼

質問の意図が伝わらなかったでしょうか？

お礼日時：2012/08/28 08:57