《編程之美》讀書筆記14： 4.4 是否在三角形內(nèi)
對(duì)幾何題目，常用到矢量。若P點(diǎn)在三角形內(nèi)部，則矢量PA沿時(shí)鐘某個(gè)方向三次旋轉(zhuǎn)分別經(jīng)過(guò)PB、PC再回到PA，每次旋轉(zhuǎn)角度都不會(huì)超過(guò)180度。即PA×PB、PB×PC和PC×PA這三個(gè)矢量積應(yīng)該都為正，或都為負(fù)。如果P在三角形邊上，則這三個(gè)矢量積應(yīng)該一個(gè)為0，其它兩個(gè)同正或同負(fù)。若在三角形某個(gè)頂點(diǎn)，則三個(gè)矢量積，必有兩個(gè)為0，一個(gè)不為0。若A B C三點(diǎn)共線，P在這直線上，則所有矢量積均為0，若P不在這直線上，則為兩正一負(fù)或兩負(fù)一正。
struct Point
{
double x;
double y;
};
static int direction(const Point& a, const Point& b, const Point& p)
{
const double zero=1e-6;
double tmp=(p.x-a.x)*(p.y-b.y)-(p.x-b.x)*(p.y-a.y);
if (tmp > zero) return 1;
if (tmp < -1*zero) return 4;
return 0;
}
bool is_in_triangle(const Point& a, const Point& b, const Point& c, const Point& p)
{
int t= direction(a,b,p)+ direction(b,c,p) + direction(c,a,p);
/**//*
if (t==3 || t==12) return true; //在三角形ABC內(nèi)
if (t==1 || t==4) return true; //與點(diǎn)A B C之一重合
if (t==2 || t==8) return true; //在三角形ABC邊上。
*/
if (t>=1 && t<=4) return true;
if (t==8 || t==12) return true;
return false;
//在三角形內(nèi)a[3]=a[12]=1 在邊上 a[2]=a[8]=1 在頂點(diǎn)a[1]=a[4]=1;
//int a[]={0, 1,1,1,1, 0,0,0, 1, 0,0,0, 1};
//return a[direction(a,b,p)+direction(b,c,p)+direction(c,a,p)];
}