C/C++の宿題やらせてください。9代目
>>894
コードを短くするのに悩みそうなのでアイデアだけ。
以下では3次元ベクトル u, v の内積と外積を i(u,v), o(u,v) で表す。
またPを任意の点とする。四点A,B,C,Dに対し、
a0,a1,a2,a3,b0,b1,b2,b3 をそれぞれベクトル
AP,AB,AC,AD,BP,BC,BD,BA とし、
s1 = o(a2,a3), s2 = o(a3,a1), s3 = o(a1,a2), t1 = o(b2,b3)
とするとき、四面体ABCDの体積を vol は vol = fabs(i(s1,a1))/6 で求まる。
そして点Pが四面体ABCDの内部にあることは次と必要十分。
vol != 0 &&
i(s1,a1)*i(s1,a0) >= 0 &&
i(s2,a2)*i(s2,a0) >= 0 &&
i(s3,a3)*i(s3,a0) >= 0 &&
i(t1,b1)*i(s0,b0) >= 0
なぜなら、s1 = o(a2,a3) は△ACDを含む平面の法線ベクトルなので
この平面に関して点Pと点Bが同じ側にある場合に限り、
内積 i(s1,a1) と i(s1,a0) の正負は一致する、
つまり i(s1,a1)*i(s1,a0) >= 0 となる。ただし、等号は
vol == 0 の場合か△ACDを含む平面上に点Pが存在する場合に成立。
同様の検査が4つの面について合格し、なおかつ体積 vol が 0 でない場合、
そしてその場合に限り、点Pは四面体ABCDの内部にあるといえる。
コードを短くするのに悩みそうなのでアイデアだけ。
以下では3次元ベクトル u, v の内積と外積を i(u,v), o(u,v) で表す。
またPを任意の点とする。四点A,B,C,Dに対し、
a0,a1,a2,a3,b0,b1,b2,b3 をそれぞれベクトル
AP,AB,AC,AD,BP,BC,BD,BA とし、
s1 = o(a2,a3), s2 = o(a3,a1), s3 = o(a1,a2), t1 = o(b2,b3)
とするとき、四面体ABCDの体積を vol は vol = fabs(i(s1,a1))/6 で求まる。
そして点Pが四面体ABCDの内部にあることは次と必要十分。
vol != 0 &&
i(s1,a1)*i(s1,a0) >= 0 &&
i(s2,a2)*i(s2,a0) >= 0 &&
i(s3,a3)*i(s3,a0) >= 0 &&
i(t1,b1)*i(s0,b0) >= 0
なぜなら、s1 = o(a2,a3) は△ACDを含む平面の法線ベクトルなので
この平面に関して点Pと点Bが同じ側にある場合に限り、
内積 i(s1,a1) と i(s1,a0) の正負は一致する、
つまり i(s1,a1)*i(s1,a0) >= 0 となる。ただし、等号は
vol == 0 の場合か△ACDを含む平面上に点Pが存在する場合に成立。
同様の検査が4つの面について合格し、なおかつ体積 vol が 0 でない場合、
そしてその場合に限り、点Pは四面体ABCDの内部にあるといえる。
|
|
|