2. 叉乘法判断点是否在三角形内
设三角形三个点
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为例,在三角形内的点必须与点A在BC的同侧
所以对于点D(x,y)
在三角形内首先要满足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)
这三个数的正负性
1三个数都是正数:D在三角形内
2至少有一个负数:D在三角形外
3有且只有一个0,另两个为正数:在三角形边上
4有且只有一个0,一个正数一个负数:在三角形边的延长线上,也算在三角形外,因为满足2
5有二个0:在三角形的顶点上
6不可能出现3个0,或3个负数,或一个0两个负数的情况
=========
4.
一、调用API。
二、
设三角形为ABC 所判断点为P area表示面积函数
判断 area(PAB)+area(PAC)+area(PBC)-area(ABC)与0关系
大于0 则在三角形外部
等于0 则在三角形内部
三、http://www.cnblogs.com/aoyihuashao/archive/2009/12/28/1633810.html
设三角形三个点
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为例,在三角形内的点必须与点A在BC的同侧
所以对于点D(x,y)
在三角形内首先要满足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)
这三个数的正负性
1三个数都是正数:D在三角形内
2至少有一个负数:D在三角形外
3有且只有一个0,另两个为正数:在三角形边上
4有且只有一个0,一个正数一个负数:在三角形边的延长线上,也算在三角形外,因为满足2
5有二个0:在三角形的顶点上
6不可能出现3个0,或3个负数,或一个0两个负数的情况
=======
5. 判断点是否在三角形内(来自csdn)
http://lhs8600./post.2853038.html
设 ap×ab 代表矢量ap与ab的矢性积,其坐标表达式为
ap×ab = (xp-xa)*(yb-ya)-(yp-ya)*(xb-xa)
于是判别过程如下:
若 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++) // 求三个向量
...{
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 ) //点在边界上,向量对称
...{
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++) // 判断在内还是外,在此只需判断两个向量,下有说明【注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; // 三个向量都在不同两侧,则在内
// 【注1】:如果三个向量分布在同一侧,则必定有两个向量使得另外的两个向量在该向量的同一侧
// a b c
// 如 |/ 三条线,b,c在a的一边, a,b在c的一边,所以a,b,c中有两条线都可以判断
// a,b,c三个向量对应的三个顶点在三个向量原点的一个方向,所以该点不在此三角形中
}
=============
6.判断点是否在三角形内(C++测试代码)
http://www./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
---------------------------------------------------------------------*/
//判断点是否在三角形内部
#include <iostream>
#include <cmath>
class Point//点类
{
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//线段类
{
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//射线类
{
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//三角形类
{
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)//判断点是否在线段上
{
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;
}
//若线段AB和CD能同时通过快速排斥试验和跨立试验则返回true
// 否则返回false
bool SegmentCross(Segment AB,Segment CD)
//A、B为AB的端点,C、D为CD的端点
{
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)
//判断水平方向上射线是否与线段相交
{
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<<"点在三角形上"<<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;
}