计算几何之向量叉积的运用.doc

向量叉积的运用
1. 向量的叉积
(1)定义
两个向量a和b的叉积写作a×b（有时也被写成a∧b，避免和字母x混淆）。
向量积可以被定义为：|向量a×向量b|=|a||b|sinθ在这里θ表示两向量之间的角夹角（0° ≤ θ ≤ 180°），它位于这两个矢量所定义的平面上。
一个简单的确定满足“右手定则”的结果向量的方向的方法是这样的：若坐标系是满足右手定则的，当右手的四指从a以不超过180度的转角转向b时，竖起的大拇指指向是c的方向。向量积c=a×b=|a| |b|sin。c的方向垂直于a与b所决定的平面，c的指向按右手规则从a转向b来确定。
(2)坐标表示
设矢量P =（x1,y1），Q = (x2,y2)，则矢量叉积定义为：P × Q = x1*y2 - x2*y1 得到的是一个标量。
(3)叉乘的重要性质：
设矢量P =（x1,y1），Q = (x2,y2)，则有下列性质：
性质a：
P × Q = - ( Q × P ) P × ( - Q ) = - ( P × Q )
性质b：
若 P × Q > 0 , 则P 在Q的顺时针方向；
若 P × Q < 0 , 则P 在Q的逆时针方向；
若 P × Q = 0 , 则P 与Q共线，但可能同向也可能反向。
性质c：
以P、Q为邻边的平行四边形的面积=abs(P×Q)，三角形的面积=1/2*abs(P×Q)
2. 运用
(1). 判断点是否在线段上
设点为Q，线段为P1P2 ，判断点Q在该线段上的依据是： ( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1，P2为对角顶点的矩形内。
(2). 判断两线段是否相交
如果两线段相交，则两线段必然相互跨立对方。
P1P2跨立Q1Q2 ，则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧，即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0，即 ( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0
当( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时，说明( P1 - Q1 ) 和 ( Q2 - Q1 )共线，P1一定在线段 Q1Q2上或者其延长线上；如果P1在线段 Q1Q2上，不管P2在哪P1P2都会与Q1Q2相交。
(3)判断线段和直线是否相交
如果线段 P1P2和直线Q1Q2相交，则P1P2跨立Q1Q2，即：
( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) ≥ 0
3. 代码
判断两线段是否相交的代码
(PS：判断点是否在线段上和判断线段和直线是否相交都比判断两线段是否相交简单，代码也可以由判断两线段是否相交的代码修改得出，所以这里不列出了)

#include
#define MAXV 4
typedef struct
{
double x,y;
}tpoint;
//返回向量OA和OB叉积的结果
double cross(tpoint O, tpoint A, tpoint B)
{
return (A.x-O.x)*(B.y-O.y)-(B.x-O.x)*(A.y-O.y);
}

double min(double a,double b)
{
if(ab)
return a;
else
return b;
}
//判断点C是否在以A和B为对角线的矩形里面
bool is_onseg(tpoint A, tpoint B, tpoint C)
{
if(C.x>=min(A.x, B.x) && C.x<=max(A.x, B.x) && C.y>=min(A.y, B.y) && C.y<=max(A.y, B.y))
return true;
else
return false;
}
//判断线段P1P2是否与Q1Q2相交
bool is_intersect(tpoint P1,tpoint P2,tpoint Q1,tpoint Q2)
{
double d1,d2,d3,d4;
d1=cross(Q1,Q2,P1);
d2=cross(Q1,Q2,P2);
d3=cross(P1,P2,Q1);
d4=cross(P1,P2,Q2);
if(((d1<0 && d2>0) || (d1>0 && d2<0)) && ((d3<0 && d4>0) || (d3>0 && d4<0)))//d1、d2异号，d3、d4异号，说明相交
return true;
else if(0==d1 && is_onseg(Q1,Q2,P1))//d1=0，说明P1在线段Q1Q2上或者其延长线上；is_onseg(Q1,Q2,P1)为真，说明点P1在以P1和P2为对角线的矩形里面，综合得P1在线段Q1Q2上
return true;
else if(0==d2 && is_onseg(Q1,Q2,P2))
return true;
else if(0==d3 && is_onseg(P1,P2,Q1))
return true;
else if(0==d3 && is_onseg(P1,P2,Q2))
return true;
else
return false;
}
int main()
{
tpoint p[MAXV];
int i;
for(i=0;i<4;i++)
scanf("%lf%lf",&p[i].x,&p[i].y);
if(is_intersect(p[0],p[1],p[2],p[3]))
printf("Yes\n");
else
printf("No\n");
return 0;
}