精华内容
下载资源
问答
  •  若 P1P2 跨立 Q1Q2,则 P1,P2 分别在 Q1Q2 所在直线的两端,则有 (P1 - Q1)*(Q2 - Q1) *(Q2 - Q1)*(P2 - Q1) > 0,当 (P1 - Q1)*(Q2 - Q1) = 0 时,说明 (P1 - Q1)与 (Q2 - Q1) 共线,但由于已经经过快速排斥试验...

    矢量

         如果一条线段的端点是有次序之分的话,那么这种线段就称为 有向线段,如果有向线段p1p2的起点p1在坐标的原点,则可以把它称为矢量p2

    矢量的加减

         设二维矢量 P = (x1, y1), Q = (x2, y2),则 P + Q = (x1 + x2, y1 + y2), P -Q = (x1 - x2, y1 - y2),且有 P + Q = Q + P, P - Q = -(Q - P)

    矢量叉积

         设矢量 P = (x1, y1), Q = (x2, y2),则 P * Q = x1 * y2 - x2 * y1; 其结果是一个由(0, 0), P, Q, P + Q 所组成的平行四边形的 带符号的面积,P * Q = -(Q * P), P * (- Q) =-(P * Q)

         叉积的一个非常重要的性质是可以通过它的符号来判断两矢量相互之间的顺逆时针关系:

               若 P * Q > 0,则 P 在 Q 的顺时针方向

               若 P * Q < 0, 则 P 在 Q 的逆时针方向

               若 P * Q = 0,则 P 与 Q 共线,但不确定 P, Q 的方向是否相同

    折线段的拐向判断

         如图,假设有折线段 p0p1p2 ,要确定 p1p2 相对于 p0p1 是向左拐还是向右拐,可以通过计算(p2 - p0)*(p1 -p0) 的符号来确定折线的拐向(点 p2 - p0 实际上就是向量 p2,但这里要注意线段和矢量的区别)

    判断点是否在线段上

         设点 Q = (x, y), P1 = (x1, y1), P2 = (x2, y2),若 (Q - P1)*(P2 - P1) =0 且 min(x1, x2) <= x <= max(x1, x2) && min(y1, y2)<= y <= max(y1, y2),则点 Q 在线段 P1P2 上

    判断两线段是否相交

    1)快速排斥试验

         设以线段 P1P2 为对角线的矩形为 R,设以线段 Q1Q2 为对角线的矩形为 T,若 R、T 不相交,则两线段不可能相交

         假设 P1 = (x1, y1), P2 = (x2, y2), Q1 = (x3, y3), Q2 = (x4, y4),设矩形 R的 x 坐标的最小边界为 minRX = min(x1, x2),以此类推,将矩形表示为 R = (minRX, minRY,maxRX, maxRY) 的形式,若两矩形相交,则相交的部分构成了一个新的矩形 F,如图所示,我们可以知道 F 的 minFX =max(minRX, minTX), minFY = max(minRY, minTY), maxFX = min(maxRX,maxTX), maxFY = min(maxRY, maxTX),得到 F 的各个值之后,只要判断矩形 F 是否成立就知道 R 和T 到底有没有相交了,若 minFX > maxFX 或 minFY > maxFy 则 F 无法构成,RT不相交,否则RT相交

    2)跨立试验

         若 P1P2 跨立 Q1Q2,则 P1,P2 分别在 Q1Q2 所在直线的两端,则有 (P1 - Q1)*(Q2 - Q1) *(Q2 - Q1)*(P2 - Q1) > 0,当 (P1 - Q1)*(Q2 - Q1) = 0 时,说明 (P1 - Q1)与 (Q2 - Q1) 共线,但由于已经经过快速排斥试验,所以 Q1 必为 P1P2 与 Q1Q2的交点,依然满足线段相交的条件,则跨立试验可改为:

         当 (P1 - Q1)*(Q2 - Q1) * (Q2 - Q1)*(P2 - Q1) >= 0,则 P1P2 跨立Q1Q2,当 Q1Q2 也跨立 P1P2 的时候,则 P1P2 相交

         (注意式子中被隔开的 * 代表两个叉积的值的相乘,而另外的两个 * 则代表计算矢量叉积)

     

     

     

    转自:http://blog.sina.com.cn/s/blog_71dbfe2e0101f7zb.html

    展开全文
  • 快速排斥实验能很快的排除掉线段不相交的情况,但并没法成为线段相交的充要条件,在快速排斥实验之后接上跨立实验就能完全的判断两线段是否相交,但其实只用跨立实验这一种办法也能作为判断线段相交的充要条件。...

    1.快速排序实验

    两条线段有且仅有一个公共点,且这个点不是任何一条线段的端点时,称这两条线段是严格相交的。快速排斥实验能很快的排除掉线段不相交的情况,但并没法成为线段相交的充要条件,在快速排斥实验之后接上跨立实验就能完全的判断两线段是否相交,但其实只用跨立实验这一种办法也能作为判断线段相交的充要条件。

    判断以这两个点为对角线的矩形和另两个点决定的矩形是否相交

    在这里插入图片描述、通过快速排斥实验,那么矩形相交

    P1坐标为(p1x,p1y),P2坐标为(p2x,p2y),Q1的坐标为(q1x,q1y),Q2的坐标为(q2x,q2y)。

    条件:`

    min(p1x,p2x) <= max(q1x,q2x) &&
    min(q1x,q2x) <= max(p1x,p2x) &&
    min(p1y,p2y) <= max(q1y,q2y) &&
    min(q1y,q2y) <= max(p1y,p2y);
    

    2.跨立实验
    在这里插入图片描述
    在这里插入图片描述
    取其中一个向量作为中间向量,中间向量中开始端点作为另外两个向量的起点,判断三个向量之间的位置关系即可:

    第一个图中: (ca × cd)(cd × cb) >= 0 我们即可判断满足跨立条件

    //顺序不能写错,,,,,,

    第二个图中: (bc × ba)(ba × bd) >=0 我们即可判断满足跨立条件

    第三个图中: (bc × ba)(ba × bd) < 0不满足跨立条件

    第四个图中: (ca × cd)(cd × cb) >= 0我们即可判断满足跨立条件

    那么我们就可以知道上面条件就是判断跨立是否成立的条件了,那么这样我们线段是否相交就已经可以解决了.

    解释:
    向量相乘根据右手定则会确定乘以后的方向,举个例子:ca叉乘cd 与 cd 叉乘 ca 的结果是不一样的,一个为正 一个为负 ,代表着方向(向上以及向下)

    在这里插入图片描述
    代码:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    const int MAXN = 2100;
    struct Point
    {
        double x,y;
    }line[MAXN][2];
    
    bool Judge(Point &a,Point &b,Point &c,Point &d)
    {
    
        if(!(min(a.x,b.x)<=max(c.x,d.x) && min(c.y,d.y)<=max(a.y,b.y)&&min(c.x,d.x)<=max(a.x,b.x) && min(a.y,b.y)<=max(c.y,d.y)))
            return false;
        double u,v,w,z;
        u=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
        v=(d.x-a.x)*(b.y-a.y)-(b.x-a.x)*(d.y-a.y);
        w=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y);
        z=(b.x-c.x)*(d.y-c.y)-(d.x-c.x)*(b.y-c.y);
        return (u*v<=0.00000001 && w*z<=0.00000001);
    }
    int main()
    {
        int n;
        scanf("%d",&n);
            int num=0;
            for(int i = 0;i < n;i ++)
                scanf("%lf%lf%lf%lf",&line[i][0].x,&line[i][0].y,&line[i][1].x,&line[i][1].y);
            for(int i = 0;i < n;i ++)
                for(int j = i+1;j < n;j ++)
                {
                    if(Judge(line[i][0],line[i][1],line[j][0],line[j][1]))
                    {
                       num++;
                       //cout<<num<<endl;
                    }
                }
          cout<<num<<endl;
    }
    
    
    展开全文
  • 快速排斥实验能很快的排除掉线段不相交的情况,但并没法成为线段相交的充要条件,在快速排斥实验之后接上跨立实验就能完全的判断两线段是否相交,但其实只用跨立实验这一种办法也能作为判断线段相交的充要条件。...

    1.快速排序实验

    两条线段有且仅有一个公共点,且这个点不是任何一条线段的端点时,称这两条线段是严格相交的。快速排斥实验能很快的排除掉线段不相交的情况,但并没法成为线段相交的充要条件,在快速排斥实验之后接上跨立实验就能完全的判断两线段是否相交,但其实只用跨立实验这一种办法也能作为判断线段相交的充要条件。

    判断以这两个点为对角线的矩形和另两个点决定的矩形是否相交

    通过快速排斥实验,那么矩形相交

    P1坐标为(p1x,p1y),P2坐标为(p2x,p2y),Q1的坐标为(q1x,q1y),Q2的坐标为(q2x,q2y)。

    条件:`

    min(p1x,p2x) <= max(q1x,q2x) &&
    min(q1x,q2x) <= max(p1x,p2x) &&
    min(p1y,p2y) <= max(q1y,q2y) &&
    min(q1y,q2y) <= max(p1y,p2y);

    2.跨立实验

     

    取其中一个向量作为中间向量,中间向量中开始端点作为另外两个向量的起点,判断三个向量之间的位置关系即可:

    第一个图中: (ca × cd)(cd × cb) >= 0 我们即可判断满足跨立条件

    //顺序不能写错,,,,,,

    第二个图中: (bc × ba)(ba × bd) >=0 我们即可判断满足跨立条件

    第三个图中: (bc × ba)(ba × bd) < 0不满足跨立条件

    第四个图中: (ca × cd)(cd × cb) >= 0我们即可判断满足跨立条件

    那么我们就可以知道上面条件就是判断跨立是否成立的条件了,那么这样我们线段是否相交就已经可以解决了.

    解释:
    向量相乘根据右手定则会确定乘以后的方向,举个例子:ca叉乘cd 与 cd 叉乘 ca 的结果是不一样的,一个为正 一个为负 ,代表着方向(向上以及向下)


    代码:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    const int MAXN = 2100;
    struct Point
    {
        double x,y;
    }line[MAXN][2];
    
    bool Judge(Point &a,Point &b,Point &c,Point &d)
    {
    
        if(!(min(a.x,b.x)<=max(c.x,d.x) && min(c.y,d.y)<=max(a.y,b.y)&&min(c.x,d.x)<=max(a.x,b.x) && min(a.y,b.y)<=max(c.y,d.y)))
            return false;
        double u,v,w,z;
        u=(c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y);
        v=(d.x-a.x)*(b.y-a.y)-(b.x-a.x)*(d.y-a.y);
        w=(a.x-c.x)*(d.y-c.y)-(d.x-c.x)*(a.y-c.y);
        z=(b.x-c.x)*(d.y-c.y)-(d.x-c.x)*(b.y-c.y);
        return (u*v<=0.00000001 && w*z<=0.00000001);
    }
    int main()
    {
        int n;
        scanf("%d",&n);
            int num=0;
            for(int i = 0;i < n;i ++)
                scanf("%lf%lf%lf%lf",&line[i][0].x,&line[i][0].y,&line[i][1].x,&line[i][1].y);
            for(int i = 0;i < n;i ++)
                for(int j = i+1;j < n;j ++)
                {
                    if(Judge(line[i][0],line[i][1],line[j][0],line[j][1]))
                    {
                       num++;
                       //cout<<num<<endl;
                    }
                }
          cout<<num<<endl;
    }

    原文链接:https://blog.csdn.net/flymoyu/article/details/90452598

    展开全文
  • 用到快速排斥实验和 跨立实验 快速排斥实验,是跨立实验的前提和基础. 假设有点 P1(x1,y1) P2(x2,y2) Q1(x3,y3) Q2(x4,y4) 构成线段 P1P2 Q1Q2 问 P1P2与Q1Q2是否相交 快速排斥实验:   P1P2 对角线构成矩形...

    计算几何中,有 判断两个线段是否相交问题. 用到快速排斥实验和 跨立实验

    快速排斥实验,是跨立实验的前提和基础.

    假设有点 P1(x1,y1) P2(x2,y2)  Q1(x3,y3) Q2(x4,y4)  构成线段 P1P2  Q1Q2 问 P1P2与Q1Q2是否相交

    快速排斥实验:  

     P1P2 对角线构成矩形R, Q1Q2对角线构成矩形T  若 R与T 相交着 通过快速排斥, 否则不通过

     矩形相交判断:

    §  方法:  假设 P1 = (x1, y1), P2 = (x2, y2), Q1 = (x3, y3),Q2 = (x4, y4)

     设矩形 R x坐标的最小边界为 RX1 = min(x1, x2)RX2=max(x1,x2) ,RY1=min(y1,y2)

     以此类推,将矩形表示为 R = (RX1, RY1, RX2, RY2)的形式,若两矩形相交,

     则相交的部分构成了一个新的矩形 F,我们可以知道 F FX1 = max(RX1, TX1), FY2 = max(RY1, TY1),

     FX2 = min(RX2,TX2), FY2 = min(RY2, TX2),得到 F 的各个值之后,

     只要判断矩形 F是否成立就知道 R T到底有没有相交了

      FX1 > FX2 FY1 > Fy1 F无法构成,RT不相交,否则 RT相交

     § 

    跨立实验:(互相跨立)

     

    若 P1P2 跨立 Q1Q2,则 P1,P2 分别在 Q1Q2 所在直线的两端,

    则有 (P1 - Q1)*(Q2 - Q1) * (Q2 - Q1)*(P2 - Q1) > 0,当 (P1 - Q1)*(Q2 - Q1) = 0 时,

    说明 (P1 - Q1) 与 (Q2 - Q1) 共线,但由于已经经过快速排斥试验,所以 Q1 必为 P1P2 与 Q1Q2 的交点,

    依然满足线段相交的条件,则跨立试验可改为:

     当 (P1 - Q1)*(Q2 - Q1) * (Q2 - Q1)*(P2 - Q1) >= 0,则 P1P2 跨立 Q1Q2,当 Q1Q2 也跨立 P1P2 的时候,则 P1P2 相交



    [代码实现]


    #include <iostream>
    #include <bits/stdc++.h>
    using namespace std;
    
    typedef struct Node{
    	double x,y;
    }point;
    typedef struct Segments{
    	point line;
    }Line;
    typedef struct Rectangle{
    	point A,B;
    }Rec; 
    double x1,x2,x3,x4,y1,y2,y3,y4;
    bool judge1(Rec R,Rec T)
    {
    	Rec F;
    	R.A.x=min(x1,x2);R.A.y=min(y1,y2);
    	R.B.x=max(x1,x2);R.B.y=max(y1,y2);
    	
    	T.A.x=min(x3,x4);T.A.y=min(y3,y4);
    	T.B.x=max(x3,x4);T.B.y=max(y3,y4);
    	
    	F.A.x=max(R.A.x,T.A.x); F.A.y=max(R.A.y,T.A.y);
    	F.B.x=min(R.B.x,T.B.x); F.B.y=min(R.B.y,T.B.y);
    	
    	if(F.A.x>=F.B.x || F.A.y>=F.B.y)
    		return false;
    	return true;
    }
    bool judge2()
    {
    	Line P1Q1,P2Q1,Q2Q1,Q2P2,P1P2,Q1P2;
    	P1Q1.line={x1-x3,y1-y3};P2Q1.line={x2-x3,y2-y3};Q2Q1.line={x4-x3,y4-y3};
    	Q2P2.line={x4-x3,y4-y2};Q1P2.line={x3-x2,y3-y2};P1P2.line={x1-x2,y1-y2};
    	// 叉乘  A(x1,y1) X B(x2,y2) = x1y2-x2y1 
    	if( (P1Q1.line.x*Q2Q1.line.y-Q2Q1.line.x*P1Q1.line.y)*(Q2Q1.line.x*P2Q1.line.y-P2Q1.line.x*Q2Q1.line.y)>=0 )
    	{
    		if( (Q1P2.line.x*Q2P2.line.y-Q2P2.line.x*Q1P2.line.y)*(Q2P2.line.x*P1P2.line.y-P1P2.line.x*Q2P2.line.y)>=0 )
    			return true;
    		else
    			return false;
    	}
    	return false;
    }
    int main()
    {
    	Rec R,T;
    	cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
    	if(!judge1(R,T))
    		cout<<"矩阵R与T矩阵不相交 即 线段P1P2 与线段Q1Q2不相交"<<endl;
    	else
    	{
    		if(judge2)
    			cout<<"线段P1P2 与 线段 Q1Q2 相交"<<endl;
    		else
    			cout<<"不相交"<<endl; 
    	} 
    	return 0;
    }
    /*
    -2 0
    1 2
    -1 1
    2 -1
    */



     



    展开全文
  • 第1 步:快速排斥试验,如果分别以P1P2 ,P3P4 为对角线做矩形,而这两个矩形不相交,则这两条线段肯定不相交,如下左图;即使两个矩形相交,这两条线段也不一定相交,如下右图,这时再用第2 步判断;   ...
  • P1P2 跨立 Q1Q2,则 P1,P2 分别在 Q1Q2 所在直线的两端,则有 (P1 - Q1)×(Q2 - Q1) * (Q2 - Q1)×(P2 - Q1) > 0,当 (P1 - Q1)×(Q2 - Q1) = 0 时,说明 (P1 - Q1) 与 (Q2 - Q1) 共线,但由于已经经过快速排斥试验...
  • 在判断两条线段是否相交时,我们常用快速排斥实验跟跨立实验这两种方法,快速排斥实验能很快的排除掉线段不相交的情况,但并没法成为线段相交的充要条件,在快速排斥实验之后接上跨立实验就能完全的判断两...
  • // 快速排斥 好理解版本 判断在不在矩形内. if (IsPointInRectangle(C, A, B) && IsPointInRectangle(D, A, B)) return false; if (GetCross(A, C, B) * GetCross(A, D, B) GetCross(C, A, D) * GetCross(C, B...
  • 快速排斥试验 以线段P1P2为对角线的矩形R 以线段Q1Q2为对角线的矩形T 【思路】如果R和T不相交 =&amp;amp;gt; 两线段也不相交。但是否相交,还需要第二步的判断:跨立试验 跨立试验 【思路...
  • 线段P1P2, Q1Q2,判断其是否相交,通过快速排斥和跨立实验则说明相交 首先要知道:向量a×向量b(×为向量叉乘),若结果小于0,表示向量b在向量a的逆时针方向;若结果大于0,表示向量b在向量a的顺时针方向;若...
  • 在判断两条线段是否相交时,我们常用快速排斥实验跟跨立实验这两种方法,快速排斥实验能很快的排除掉线段不相交的情况,但并没法成为线段相交的充要条件,在快速排斥实验之后接上跨立实验就能完全...
  • 如果两条线段短点相交,那么这个方法不可判断,只有跨立情况下才可以判断 struct point { int x,y; } p[M]; int cross(point a0,point a1,point a2) { return (a1.x-a0.x)*(a2.y-a0.y)-(a1.y-a0.y)*(a2.x-a0.x);...
  • //快速排斥实验 bool QuiEx(const Point& a, const Point& b, const Point& c, const Point& d) { return min(a.x, b.x) (c.x, d.x) && min(c.x, d.x) (a.x, b.x) && min(a.y, b.y) (c.y, d.y) && min(c.y, d.y...
  • 首先我们看一下快速排斥实验,快速排斥实验也就是以两条线段作为对角线做矩形,判断两个矩形是否相交,那么我们这里可以知道: 1)如果两个矩形不相交,那么线段一定不相交 2)如果两个矩形相交,那么线段不一定相交...
  • 直接使用跨立实验会有问题,比如其中一条线段退化成一个点的情况,可以通过跨立实验,但是不能通过快速排斥实验: 代码 #include <iostream> using namespace std; const int N = 1e5 + 5; typedef
  • 代码实现: import numpy as np import cv2 class Check_line(): def __init__(self): ... 1、执行第一步,进行快速排斥实验-----直线AB与直线CD :param p1: A点坐标 :param p2: B点坐标 :param q1.
  • } bool isIntersect(POINT a1, POINT a2, POINT b1, POINT b2)//该函数用来判断线段a1.a2 与 线段 b1.b2是否相交 { //这个if是快速排斥实验的条件 if(min(a1.x, a2.x) (b1.x, b2.x) && min(b1.x, b2.x) (a1.x, a2.x...
  • 还是那道题 但是这次有一个全新的解法了,涉及到的跨立实验和快速排斥实验,在学习部分我有提及过。 不多说直接上一下核心代码   直接进行双实验,如果快速排斥不通过 直接PASS 之后再进行跨立实验,如果成了...
  • 判断线段是否相交:快速排斥+跨立

    千次阅读 2018-07-26 22:40:06
     若 P1P2 跨立 Q1Q2,则 P1,P2 分别在 Q1Q2 所在直线的两端,则有 (P1 - Q1)*(Q2 - Q1) *(Q2 - Q1)*(P2 - Q1) > 0,当 (P1 - Q1)*(Q2 - Q1) = 0 时,说明 (P1 - Q1)与 (Q2 - Q1) 共线,但由于已经经过快速排斥试验...
  • 首先要知道,我们一定要先通过了快速排斥试验我们才能继续判断是否两条线相交,如果快速排斥试验都没能通过,那么这两条线是一定不会相交的。 [cpp]   view plain   copy   ...
  • 本来想用斜率来算,后来觉得要分太多情况,上网发现用快速排斥+跨立就能做 快速排斥的意思是当两条线段分别构成的矩形范围没有相交,那么两直线肯定没没有交点,如下图 如何判断两个矩形相交?一种错误的思路是一...
  • 我们将用到快速排斥实验 + 跨立实验(poj 2653) 链接:http://blog.sina.com.cn/s/blog_71dbfe2e0101f7zb.html 其实不用快速排斥实验也可以过QAQ 并不知道有没有反例 #include #include #include #...
  • bool intersect(line a,line b) { #define A a.l #define B b.l #define C a.r #define D b.r //这几行的意思就是用ABCD四个点表示两条线段的四个端点 if(cp(C,B,A)*cp(C,D,A)<0&&...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 15,106
精华内容 6,042
关键字:

快速排斥