数学知识啊.
假设三角形三个顶点 A (x1,y1),B (x2,y2),C (x3,y3),需要判定的点 P (x0,y0)
现在,以A 为原点,判断向量 AP,与 AB,AC 的关系,最简单的办法就是看它们的向量积
AP x AB = [ (x0 - x1)* (y2 - y1) - (x2 - x1)*(y0 - y1) ] i = Kb i
其中 i 是垂直于平面方向的单位向量
AP x AC = [ (x0 - x1)* (y3 - y1) - (x3 - x1)*(y0 - y1) ] i = Kc i
如果 AP 在 AB,AC 之间,那么 Kb,Kc 符号相反,看起来比较聪明的方式是把他们相乘,不过这显然增加了运算量,其实还是用逻辑判断比较好,
double Kb,Kc;
Kb = (x0 - x1)* (y2 - y1) - (x2 - x1)*(y0 - y1);
Kc = (x0 - x1)* (y3 - y1) - (x3 - x1)*(y0 - y1);
if ( ((0 > Kb) && (0 < Kc)) || ((0 < Kb) && (0 > Kc)) ) PinBC = 1;
else PinBC = 0;
.
然后,以 B,C 为原点,分别判断 PinAC,PinAB.
PinBC,PinAC,PinAB 只要有一个不满足,就可以判断 P 不在三角形内了.
可以写成函数比较简洁
int PinAB ( double x0,double y0,double x1,double y1,double x2,double y2)
{
double Kb,Kc;
Kb = x0*y1 - x1*y0;
Kc = x0*y2 - x2*y1;
if ( ((0 > Kb) && (0 < Kc)) || ((0 < Kb) && (0 > Kc)) ) return 1;
return 0;
}
int PinABC ( double x0,double y0,double x1,double y1,double x2,double y2,double x3,double y3)
{
if ( PinAB ( x0 - x1,y0 -y1,x2 - x1,y2 - y1,x3 - x1,y3 - y1) &&
PinAB ( x0 - x2,y0 -y2,x3 - x2,y3 - y2,x1 - x2,y1 - y2) &&
PinAB ( x0 - x3,y0 -y3,x2 - x3,y2 - y3,x1 - x3,y1 - y3) ) return 1;
return 0;
}
当然这个算法没能利用 cpu 的向量计算能力,如果 cpu 支持向量计算,直接算向量的差/积要快不少.
