http://www.cnblogs.com/cgwolver/archive/2009/03/26/1257611.html
假定在右手坐標(biāo)系中的三角形3點(diǎn)坐標(biāo)為A，B，C，判斷P是否在ABC之內(nèi)
( 主要來(lái)自 3D引擎研發(fā)QQ群（38224573 ）的各位朋友的討論 ，我僅僅算做個(gè)總結(jié)吧，特別感謝各位朋友的熱情支持。 ）
方法1：三個(gè)Perplane的方法
設(shè)AB，BC，AC邊上的垂直平面為Perplane[3]，垂直朝向內(nèi)側(cè)的法向?yàn)閚[3]
1）先根據(jù)任意兩邊叉出法向N
N = AB.CrossProduct(AC);
N.Normalize();
D = A.DotProduct( N );
2）如果P在三角形所在平面之外，可直接判定不在平面之內(nèi)（ 假定方程為 ax+by+cz+d = 0 )
if( P.DotProduct( N ) + D > 0 ) return false;
3）然后法向和各邊叉出垂直平面的法向
n[0] = N.CrossProduct(AB); //朝向內(nèi)側(cè)
n[0].Normalize();
Perplane[0].dist = A.DotProduct(n[0]);
Perplane[0].normal = n[0];
同樣方法求得Perplane[1],Perlane[2];
3）因?yàn)槿齻€(gè)Perplane都朝向三角形內(nèi)側(cè)，P在三角形內(nèi)的條件是同時(shí)在三個(gè)Perplane前面；如果給定點(diǎn)P在任意一個(gè)垂直平面之后，那么可判定P在三角形外部
for( int i = 0;i<3;j++ )
{
if( P.DotProduct( Perplane[i].normal ) + Perplane[i].dist < 0 )
return false;
}
return true;//如果P沒(méi)有在任意一條邊的外面，可判斷定在三角形之內(nèi)，當(dāng)然包括在邊上的情況
方法2：三個(gè)部分面積與總面積相等的方法
S(PAB) + S(PAC) + S( PBC) = S(ABC) 則判定在三角形之內(nèi)
用矢量代數(shù)方法計(jì)算三角形的面積為
S = 1/2*|a|*|b|*sin(theta)
= 1/2*|a|*|b|*sqrt(1-cos^2(theta))
= 1/2*|a|*|b|*sqrt(1- (a.DotProduct(b)/(|a|*|b|))^2);
另一種計(jì)算面積的方法是 S = 1/2*|a.CrossProduct(b)|
比較一下，發(fā)現(xiàn)后者的精確度和效率都高于前者，因?yàn)榍罢咝枰_(kāi)方和求矢量長(zhǎng)度，矢量長(zhǎng)度相當(dāng)于一次點(diǎn)乘，三個(gè)點(diǎn)乘加一個(gè)開(kāi)方，顯然不如
后者一次叉乘加一次矢量長(zhǎng)度（注，一次叉乘計(jì)算相當(dāng)于2次點(diǎn)乘，一次矢量長(zhǎng)度計(jì)算相當(dāng)于一次點(diǎn)乘），后者又對(duì)又快。
S(ABC) = AB.CrossProduct(AC)；//*0.5;
S(PAB) = PA.CrossProduct(PB)；//*0.5;
S(PBC) = PB.CrossProduct(PC)；//*0.5;
S(PAC) = PC.CrossProduct(PA)；//*0.5;
if( S(PAB) + S(PBC) + S(PAC) == S(ABC) )
return true;
return false;
另一種計(jì)算三角形面積的矢量方法是 1/2*a.CrossProdcuct(b) ，CrossProduct = ( y1*z2 - y2*z1 , x1*z2 - x2*z1, x1*y2 - x2*z1 )
可以看到CrossProduct 的計(jì)算要比DotProduct多3個(gè)乘法計(jì)算，效率沒(méi)有上面的方法高
方法3：三個(gè)向量歸一化后相加為0
這個(gè)方法很怪異，發(fā)現(xiàn)自http://flipcode.spaces.live.com/blog/cns!8e578e7901a88369!903.entry 下面的一個(gè)回帖
如上圖三角形ABC，P為AB外側(cè)一點(diǎn)，N1，N2，N3 分別為BP，AP，CP的歸一化矢量；NM為N1，N2夾角的角平分線
可以看出角A-P-B是三角形內(nèi)角，必然小于180度，那么角N1-P-N2等于A-P-B；NM是N1-P-N2的角平分線，那么角B-P-N等于角N-P-A，而CPN必然小于其中一個(gè)，
即小于180/2 = 90度。結(jié)論是角N1，N2的合矢量方向與N3的夾角為銳角。所以N1，N2，N3的合向量模大于1.
這里注意，N3不一定在N1，N2之間，不能假定N2-P-N3 和N3-P-N1這兩個(gè)角一定是銳角
同樣可以推導(dǎo)出如果P在三角形內(nèi)，N1+N2+N3必然小于0；若N1+N2+N3 = 0則P在三角形的邊上。
有沒(méi)有更簡(jiǎn)單的推導(dǎo)方法？
這個(gè)方法看起來(lái)很精巧，但是善于優(yōu)化的朋友會(huì)立刻發(fā)現(xiàn)，三個(gè)矢量歸一化，需要三個(gè)開(kāi)方。迭代式開(kāi)方太慢了，而快速開(kāi)方有的時(shí)候又不滿足精度要求。
方法4：重心坐標(biāo)之和為1
{
BaryCenter = ( S(PAB)/S(PABC),S(PBC)/S(PABC),S(PAC)/S(PABC)) // 點(diǎn)P在三角形內(nèi)的重心坐標(biāo)
if( BaryCenter.x + BaryCenter.y + BaryCenter.z >0.f )
return false
return true;
}
其中S(PAB)，S(ABC)，S(PBC)，S(PBC) 用上述的方法二種提到的計(jì)算三角形面積方法計(jì)算。
綜合比較
方法1必須求叉乘，雖然可以通過(guò)首先排除不在平面內(nèi)的點(diǎn)，但是后面仍要求三個(gè)叉乘和3個(gè)點(diǎn)乘（當(dāng)然還可排除法優(yōu)化）
方法2看起來(lái)之需要求4個(gè)點(diǎn)乘，如果用叉乘方法計(jì)算面積，可能會(huì)導(dǎo)致效率低下
方法3是看起來(lái)是最精巧的方法，但是效率也不能保證...3個(gè)開(kāi)方
方法4和方法2的效率差不多
本文來(lái)自CSDN博客，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/boyzk2008/archive/2009/08/07/4421106.aspx