逆时针方向

图示

讯享网

图中都是以p0为源点,p0p1为基准线,判断p0p2相对p0p1的位置关系!

怎么只通过3个点的坐标来判断呢?

我们还是以向量的形式,运用向量的知识进行判断,需要用到向量的内积、外积知识不了解点击下方链接!

内积、外积知识

首线上面这些问题都可以归结到判断是否是逆时针方向问题!

判断逆时针

向量a、b的外积模为 |axb|=|a|x|b|sinθ,0<θ<180° sinθ>0,也就是从向量a出发逆时针旋转θ(右手螺旋定则),0<θ<180°时我们可以看出向量b在向量a的逆时针方向!

通过上述描述,我们可以运用向量的外积模,如果外积模>0,则向量b在向量a的时针方向!

判断顺时针

有了上面的铺垫,想必大家一目了然,也就是向量外积模小于0,θ>180°的时候向量b在向量a的顺时针方向!

图示

正下方

正下方情况也就是θ=180°的时候,这个时候外积|a|x|b|sinθ=0,并且正上方的θ=0°,外积也为0。

如何判断在θ=0°,是在正上方还是正下方呢?

正上方
那么位于正上方是不是内积大于0呢?

答案是否定的!!!

为什么呢?

我们看最后一种情况,点位于线段内的情况,这种情况的内积也满足θ=0°,内积>0所以无法判断是在正上方!!!

究竟如何判定呢?

其实非常简单,当位于正上方时,向量b的模是大于向量a的模的!也就是向量b长于向量a!

图示

我们只要对向量a、b进行取模比较长度即可!

点在线段上

点在线段上就非常简单,首先外积等于0,内积大于0,只要b的模小于a的模就可以满足点在线段上!

(代码中,只要不满足前4中情况就是点在线段上)

实现代码

#include <bits/stdc++.h> using namespace std; class Point { 
    public: double x,y; Point(double x=0,double y=0):x(x),y(y) { 
   } //向量大小(取模) double abs() { 
    return sqrt(norm()); } //向量范数(模的平方) double norm() { 
    return x*x+y*y; } }; typedef Point Vector; //向量内积 double dot(Vector a,Vector b) { 
    return a.x*b.x+a.y*b.y; } //向量外积 double cross(Vector a,Vector b) { 
    return a.x*b.y-a.y*b.x; } //逆时针方向 string ccw(Point p0,Point p1,Point p2) { 
    Vector a(p1.x-p0.x,p1.y-p0.y); Vector b(p2.x-p0.x,p2.y-p0.y); //逆时针-->顺时针-->p2在p0正下方-->p2在p1正上方-->p2在p0,p1线段上 if(cross(a,b)>0) return"逆时针方向"; if(cross(a,b)<0) return "顺时针方向"; if(dot(a,b)<0) return"p2在p0正下方"; if(a.norm()<b.norm()) return "p2在p1正上方"; return "p2在线段p0p1上"; } int main() { 
    int t; int x0,y0,x1,y1; cin>>x0>>y0>>x1>>y1; cin>>t;//t组测试数据 int x2,y2; while(t--) { 
    cin>>x2>>y2; Point p0(x0,y0); Point p1(x1,y1); Point p2(x2,y2); cout<<ccw(p0,p1,p2)<<endl; } return 0; } 

测试用例

输入

0 0 2 0
5
-1 1
-1 -1
-1 0
0 0
3 0

输出

逆时针
顺时针
正下方
线段中间
正下方

相交判断

有了逆时针的铺垫,判断相交就格外容易。

首先给大家列出相交的几种情况
图示一

(重合我们也算作相交)
如何把相交的判断和逆时针关联起来呢?

我们可以拿出一条线段,取出一个端点,与另一条线段构成两个向量，进而判断这两个向量的关系,再拿出另外一个点,构成两个向量判断关系!如果满足:
“另一条线段的两个端点分别位于当前线段的顺时针和逆时针方向”,则两条线段相交

我们拿图中第一组例子进行图解

所以我们将判断逆时针方法改为返回值为int类型,并进行如下操作

讯享网const int Counter_ClockWise=1;//逆时针 const int ClockWise=-1;//顺时针 const int Online_Back=2;//p2在p1p0正下方 const int Online_Front=-2;//p2在p1p0正上方 const int On_Segment=0;//在线段上 

如果满足ccw(p3,p4,p1)*ccw(p3,p4,p2)<0,并且ccw(p1,p2,p3)*ccw(p1,p2,p4)<0,也就是满足一个顺时针一个逆时针,则两条线段相交!

如果只满足一组可以达到同样的效果么?

也就是两条线段只拿出一条进行判断!

显然是不行的!
图示二

显然这组样例也满足,一个顺时针,一个逆时针,但是两个线段并不相交!

我们来讨论ccw()返回值为的情况

ccw返回值为0,就是3个点有一个点在线段上,所以放到判断线段相交,其中一个线段的端点在另外一个线段上(图示一第3种情况)那么这两条线段必然相交!

所以我们在ccw()<0的基础上,加上等于0

对于一个点在正上方,一个点在正下方的情况
图示

在代码中同样设置了正上方返回-2,正下方返回2,也同样满足ccw<0

宇宙无敌之判断之线段相交完整代码

#include <bits/stdc++.h> using namespace std; const int Counter_ClockWise=1;//逆时针 const int ClockWise=-1;//顺时针 const int Online_Back=2;//p2在p1p0正下方 const int Online_Front=-2;//p2在p1p0正上方 const int On_Segment=0;//在线段上 class Point { 
    public: double x,y; Point(double x=0,double y=0):x(x),y(y) { 
   } //向量大小 double abs() { 
    return sqrt(norm()); } //向量范数 double norm() { 
    return x*x+y*y; } bool operator<(const Point &p) const { 
    return x!=p.x?x<p.x:y<p.y; } bool operator==(const Point &p)const { 
    return x-p.x<1e-10&&y-p.y<1e-10; } }; typedef Point Vector; //向量内积 double dot(Vector a,Vector b) { 
    return a.x*b.x+a.y*b.y; } //向量外积 double cross(Vector a,Vector b) { 
    return a.x*b.y-a.y*b.x; } //逆时针方向 int ccw(Point p0,Point p1,Point p2) { 
    Vector a(p1.x-p0.x,p1.y-p0.y); Vector b(p2.x-p0.x,p2.y-p0.y); //逆时针-->顺时针-->p2在p0正下方-->p2在p1正上方-->p2在p0,p1线段上 if(cross(a,b)>0) return Counter_ClockWise; if(cross(a,b)<0) return ClockWise; if(dot(a,b)<0) return Online_Back; if(a.norm()<b.norm()) return Online_Front; return On_Segment; } //判断线段相交 bool intersect(Point p1,Point p2,Point p3,Point p4) { 
    return (ccw(p1,p2,p3)*ccw(p1,p2,p4)<=0&&ccw(p3,p4,p1)*ccw(p3,p4,p2)<=0); } int main() { 
    int t; cin>>t;//t组测试数据 int x1,y1,x2,y2,x3,y3,x4,y4; while(t--) { 
    cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4; Point p1(x1,y1); Point p2(x2,y2); Point p3(x3,y3); Point p4(x4,y4); cout<<intersect(p1,p2,p3,p4)<<endl; } return 0; } 

测试用例

输入

3
0 0 3 0 1 1 2 -1
0 0 3 0 3 1 3 -1
0 0 3 0 3 -2 5 0

输出

1
1
0