2. 叉乘法判斷點(diǎn)是否在三角形內
沿著(zhù)三角形的邊按順時(shí)針?lè )较蜃?，判斷該點(diǎn)是否在每條邊的右邊（這可以通過(guò)叉乘判斷），如果該點(diǎn)在每條邊的右邊，則在三角形內，否則在三角形外。這個(gè)算法只用到了三次叉乘，沒(méi)有除法運算和三角函數、開(kāi)根號等運算，所以效率很高，而且精度很高（沒(méi)有浮點(diǎn)誤差）。
設三角形三個(gè)點(diǎn)A(a1,a2),B(b1,b2),C(c1,c2)三條邊方程BC:fa(x,y)=0AC:fb(x,y)=0AB:fc(x,y)=0以BC為例，在三角形內的點(diǎn)必須與點(diǎn)A在BC的同側所以對于點(diǎn)D(x,y)在三角形內首先要滿(mǎn)足fa(x,y)*fa(a1,a2)>0其他邊也同理所以只要比較fa(x,y)*fa(a1,a2)fb(x,y)*fb(b1,b2)fc(x,y)*fc(c1,c2)這三個(gè)數的正負性1三個(gè)數都是正數：D在三角形內2至少有一個(gè)負數：D在三角形外3有且只有一個(gè)0，另兩個(gè)為正數：在三角形邊上4有且只有一個(gè)0，一個(gè)正數一個(gè)負數：在三角形邊的延長(cháng)線(xiàn)上，也算在三角形外，因為滿(mǎn)足25有二個(gè)0：在三角形的頂點(diǎn)上6不可能出現3個(gè)0，或3個(gè)負數，或一個(gè)0兩個(gè)負數的情況
＝＝＝＝＝＝＝＝＝
4.
一、調用API。
二、
設三角形為ABC 所判斷點(diǎn)為P area表示面積函數
判斷 area(PAB)+area(PAC)+area(PBC)-area(ABC)與0關(guān)系
大于0 則在三角形外部
等于0 則在三角形內部
三、http://www.cnblogs.com/aoyihuashao/archive/2009/12/28/1633810.html
設三角形三個(gè)點(diǎn)
A(a1,a2),B(b1,b2),C(c1,c2)
三條邊方程
BC:fa(x,y)=0
AC:fb(x,y)=0
AB:fc(x,y)=0
以BC為例，在三角形內的點(diǎn)必須與點(diǎn)A在BC的同側
所以對于點(diǎn)D(x,y)
在三角形內首先要滿(mǎn)足fa(x,y)*fa(a1,a2)>0
其他邊也同理
所以只要比較
fa(x,y)*fa(a1,a2)
fb(x,y)*fb(b1,b2)
fc(x,y)*fc(c1,c2)
這三個(gè)數的正負性
1三個(gè)數都是正數：D在三角形內
2至少有一個(gè)負數：D在三角形外
3有且只有一個(gè)0，另兩個(gè)為正數：在三角形邊上
4有且只有一個(gè)0，一個(gè)正數一個(gè)負數：在三角形邊的延長(cháng)線(xiàn)上，也算在三角形外，因為滿(mǎn)足2
5有二個(gè)0：在三角形的頂點(diǎn)上
6不可能出現3個(gè)0，或3個(gè)負數，或一個(gè)0兩個(gè)負數的情況
＝＝＝＝＝＝＝
5. 判斷點(diǎn)是否在三角形內（來(lái)自csdn)
http://lhs8600.ycool.com/post.2853038.html
設 ap×ab 代表矢量ap與ab的矢性積，其坐標表達式為
ap×ab = (xp-xa)*(yb-ya)-(yp-ya)*(xb-xa)
于是判別過(guò)程如下：
若 ap×ab>0 and bp×bc>0 and cp×ca>0 或 ap×ab<0 and bp×bc<0 and cp×ca<0
則可判定p在△abc內。
若 ap×ab=0 and (bp×bc>0 and cp×ca>0 或 bp×bc<0 and cp×ca<0)
或 bp×bc=0 and (ap×ab>0 and cp×ca>0 或 ap×ab<0 and cp×ca<0)
或 cp×ca=0 and (ap×ab>0 and bp×bc>0 或 ap×ab<0 and bp×bc<0)
則可判定p在△abc輪廓上。
否則，p在△abc在外。
int inside4(const struct TPoint tr[], struct TPoint p)
...{
struct TPoint arr[3];
memcpy(arr,tr,sizeof(arr));
for(int i=0;i<3;i++) // 求三個(gè)向量
...{
arr[i].x = tr[i].x - p.x;
arr[i].y = tr[i].y - p.y;
}
for(i=0;i<3;i++) // 判斷是否在邊界上
...{
int j=(i+1)%3;
if( arr[i].x*arr[j].y-arr[i].y*arr[j].x==0 ) //點(diǎn)在邊界上，向量對稱(chēng)
...{
if( arr[i].x*arr[j].x>0 || arr[i].y*arr[j].y>0 ) return 0;// 同方向
return 1; // 方向相反
}
}
for(i=0;i<2;i++) // 判斷在內還是外，在此只需判斷兩個(gè)向量，下有說(shuō)明【注1】
...{
int front = (i+2)%3, next = 3-i-front;
int cnt = 0;
int t1 = arr[i].y*arr[front].x - arr[front].y*arr[i].x;
int t2 = arr[i].y*arr[next].x - arr[next].y *arr[i].x;
if( (t1>0)+(t2>0)!=1 ) return 0; //向量分布在同一側，則在外；否則不能確定
}
return 1; // 三個(gè)向量都在不同兩側，則在內
// 【注1】：如果三個(gè)向量分布在同一側，則必定有兩個(gè)向量使得另外的兩個(gè)向量在該向量的同一側
// a b c
// 如 |/ 三條線(xiàn)，b,c在a的一邊， a,b在c的一邊，所以a,b,c中有兩條線(xiàn)都可以判斷
// a,b,c三個(gè)向量對應的三個(gè)頂點(diǎn)在三個(gè)向量原點(diǎn)的一個(gè)方向，所以該點(diǎn)不在此三角形中
}
＝＝＝＝＝＝＝＝＝＝＝＝＝
6.判斷點(diǎn)是否在三角形內(C++測試代碼)
http://www.csplace.cn/html/Program/Software/CPP/185.html
/*---------------------------------------------------------------------
//file name:InTriangleOrNot.cpp
//Coder: rainday163
//E-mail: rainday1631@163.com
//Create date: 2009.11.19
//Last modify date: 2009.11.20
//Test platform: WinXP sp2 & Dev-C++ 4.9.9.2
---------------------------------------------------------------------*/
//判斷點(diǎn)是否在三角形內部
#include <iostream>
#include <cmath>
class Point//點(diǎn)類(lèi)
{
public:
Point():x(0),y(0)
{}
Point(double Vx,double Vy):x(Vx),y(Vy)
{}
Point(Point &p)
{
this->x=p.x;
this->y=p.y;
}
Point &operator=(const Point &p)
{
if(this==&p)
{
return *this;
}
this->x=p.x;
this->y=p.y;
return *this;
}
double x,y;
};
class Segment//線(xiàn)段類(lèi)
{
public:
Segment()
{
begin.x=0,begin.y=0;
end.x=0,end.y=0;
}
Segment(Point A,Point B)
{
begin=A;
end=B;
}
Point begin,end;
};
enum Direct{left,right};
class Half_Line//射線(xiàn)類(lèi)
{
public:
public:
Half_Line():x(0),y(0)
{
source.x=x,source.y=y;
}
Half_Line(Point &p,Direct d)
{
x=p.x,y=p.y;
source=p;
direction=d;
}
double x,y;
Point source;
enum Direct direction;
};
class Triangle//三角形類(lèi)
{
public:
Triangle()
{}
Triangle(Point AP,Point BP,Point CP)
{
A=AP,B=BP,C=CP;
AB.begin=A,AB.end=B;
BC.begin=B,BC.end=C;
AC.begin=A,AC.end=C;
}
Point A,B,C;
Segment AB,BC,AC;
};
// 計算向量AB與向量AC的叉積
double multi(Point const &A,Point const& B,Point const& C)
{
Point AB(B.x-A.x,B.y-A.y);
Point AC(C.x-A.x,C.y-A.y);
return (AB.x*AC.y - AB.y * AC.x);
}
bool PointOfSegment(Point P,Segment L)//判斷點(diǎn)是否在線(xiàn)段上
{
Point AP,AB;
AP.x=P.x-L.begin.x , AP.y=P.y-L.begin.y ;
AB.x=L.end.x-L.begin.x , AB.y=L.end.y - L.begin.y ;
double TempResult = AP.x * AB.y - AP.y * AB.x ;
if(fabs(TempResult)<(double)1e-6 \
&& P.x >= L.begin.x && P.x <= L.end.x)
{
return true;
}
return false;
}
//若線(xiàn)段AB和CD能同時(shí)通過(guò)快速排斥試驗和跨立試驗則返回true
// 否則返回false
bool SegmentCross(Segment AB,Segment CD)
//A、B為AB的端點(diǎn)，C、D為CD的端點(diǎn)
{
Point A,B,C,D;
A=AB.begin,B=AB.end;
C=CD.begin,D=CD.end;
if( ( std::max(A.x,B.x) >= std::min(C.x,D.x) )
&&( std::max(C.x,D.x) >= std::min(A.x,B.x) )
&&( std::max(A.y,B.y) >= std::min(C.y,D.y) )
&&( std::max(C.y,D.y) >= std::min(A.y,B.y) )
&&( multi(C,A,D) * multi(C,B,D) <=0 )
&&( multi(A,C,B) * multi(A,D,B) <=0 )
)
return true;
return false;
}
bool CrossOrNot(Half_Line &P,Segment &L)
//判斷水平方向上射線(xiàn)是否與線(xiàn)段相交
{
Point temp;
if(P.direction == left)
{
temp.x=L.begin.x,temp.y=P.y;
}
if(P.direction == right)
{
temp.x=L.end.x,temp.y=P.y;
}
Point Ptemp=P.source;
Segment OP(temp,Ptemp);
if(!SegmentCross(OP,L))
{
return false;
}
return true;
}
//測試代碼
int main()
{
Point A,B,C,P;
std::cout<<"Please input A,B,C:"<<std::endl;
std::cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y;
std::cout<<"Please input P:"<<std::endl;
std::cin>>P.x>>P.y;
Triangle ABC(A,B,C);
Half_Line PB(P,left),PC(P,right);
if(PointOfSegment(P,ABC.AB) || PointOfSegment(P,ABC.AC) || PointOfSegment(P,ABC.BC))
{
std::cout<<"點(diǎn)在三角形上"<<std::endl;
}
else if(CrossOrNot(PB,ABC.AB) && CrossOrNot(PC,ABC.AC))
{
std::cout<<"在內部"<<std::endl;
}
else
{
std::cout<<"在外部"<<std::endl;
}
std::cin.get();
std::cin.get();
return 0;
}
