精华内容
下载资源
问答
  • 判断顶点是否位于线段上 分类: 算法2013-07-21 16:47 68人阅读 评论(0) 收藏 举报 算法 假设线段的两个端点分别:A、B,另外一点 P。 问题:判断 P 点是否位于线段 AB 上。 方法1:通过线段确定的...

    判断顶点是否位于线段上

    分类: 算法 68人阅读 评论(0) 收藏 举报
    假设线段的两个端点分别为:A、B,另外一点为 P。
    问题:判断 P 点是否位于线段 AB 上。

    方法1:通过线段确定的直线方程判断。
    (1) 在二维空间中,三点坐标表示为:A(xa,ya), B(xb,yb), P(xp,yp)。
    AB确定的直线方程(点斜式)为:
          k = (yb - ya) * 1 / (xb - xa) 
          y = k * (x - xa) + ya
    P点若位于直线上,首先应该满足直线的方程:
          yp = k * (xp - xa) + ya。
    若上式成立,说明A、B、P共线,接下来只需判断 P 位于 A 和 B 中间,即
         (xa < xb && xa <= xp <= xb) || (xa > xb && xa >= xp >= xb)
         (ya < yb && ya <= yp <= yb) || (ya > yb && ya >= yp >= yb)
    同时成立。否则,P 不在线段AB上。

    注意到直线方程中有除法运算,需做一步AB是否重合的判断,否则除数为零。上式稍作变形,便可去掉除法运算,即:
         (y - ya) / (yb - ya) = (x - xa) / (xb - xa)
    进而
         (y - ya) * (xb - xa) - (yb - ya) * (x - xa) = 0。
    上式成立的条件,(x,y)与A或B点重合,或者(x,y)、A、B三点共线。接下来再做 P 是否位于AB中间的判断即可。

    上述变形后的等式,其实表示的是二维平面中向量的一种运算:叉积(cross product),
          A x B = xa*yb - ya*xb
    由直线方程的启示,不难理解叉积为零,则可判定两向量共线或者一个向量为零。

    变形后的直线方程和向量的叉积是二维空间向三维空间推广的基础。

    (2) 在三维空间中,三点坐标分别为A(xa,ya,za), B(xb,yb,zb), P(xp,yp,zp)。
    AB确定的直线方程相应变为:
         (y - ya) / (yb - ya) = (x - xa) / (xb - xa) = (z - za) / (zb - za)。
    按(1)中所述,将P点代入直线方程成立后,只需再多做一步 z 轴坐标的判断:
         (za < zb && za <= zp <= zb) || (za > zb && za >= zp >= zb)。
    所有条件同时成立,则 P 点位于线段 AB 上。

    三维空间中的叉积判断就是接下来的方法2。

    方法2:利用向量的叉积做判断[3]。
    二维空间中的叉积定义已经介绍,三维空间的描述可以参考「4」,叉积可以作为判定两个向量是否共线的一个工具,三维空间中的叉积结果会得到一个新的向量。
    先求得两个向量:v1 = B - A, v2 = P - A。然后 v1 和 v2 做叉积:v = v1 x v2,如果 v 是零向量,即 v 的x、y、z分量都为 0,则v1 和 v2 至少有一个为零或者两个向量共线。
          if v2 == 0,then P == A;
          else if v1 == 0 then  A == B  AND P doesn't lie in AB ; // v2 != 0
          else P,A,B are colinear;
          end
    如果判定共线后,接下来判断 P 是否位于 AB 内的方式同方法1.

    方法3:面积法。
    如果A、B、P三点组成的三角形的面积为零,那么可以得出三点共线的结论。
    三角形面积可以使用海伦公式直接得出,另外上述v1和v2叉积得到的向量的长度的一半,也是三点组成的三角形的面积(参考叉积的定义)。
    不过这两种方式都涉及到开根号的运算,代价较高。

    另外在判定了三点共线后,v1 和 v2 的夹角要么0度,要么180度,点积的符号可以用来确定P点的位置,如:v1 ・ v2  < 0。那么,v1 和 v2 夹角为180,反向,P点位于AB之外。
    接下来再以 B 点为基准做两个向量v1’ = A - B, v2’ = P - B,若v1’ ・ v2’ > 0,即可断定 P 位于线段AB上。
    如果不以 B 为基准做两个向量,可以通过长度来判断,由内积的定义可以知道:
         v1 ・ v2 = |v1| |v2| cos<v1, v2> = |v1| |v2| cos(0) = |v1| |v2|。
    如果v1 ・ v2  > |v1|*|v1| = v1 ・ v1 => |v2| > |v1|,即PA的长度大于BA,又PA和BA同向,那么P点一定位于AB之外。

    不过上述的点积判定符号的方法,包含了许多乘法的运算,进行坐标比较的方法反而更加直接简单。综上所述,方法2更值得推荐。

    参考:
    [1]http://stackoverflow.com/questions/328107/how-can-you-determine-a-point-is-between-two-other-points-on-a-line-segment
    [2]http://stackoverflow.com/questions/7050186/find-if-point-lay-on-line-segment
    上一篇:有关struct的构造函数
     

    判断顶点是否位于三角形内

    分类: 算法 110人阅读 评论(0) 收藏 举报
    这是一个三维空间中的平面问题(三角形确定一个平面),假设三角形的三个顶点为A(xa, ya, za)、B(xb, yb, zb)、C(xc, yc, zc),另外一个顶点为P(xp, yp, zp)。
    问题:判断顶点 P 是否位于ABC组成的三角形上(内部和边界)。

    方法1:效率较低的方法。

    (1) 利用面积判断。如果顶点落在三角形上,那么顶点P分别和ABC三点连接后组成的三个小三角形的面积之和一定等于三角形ABC的面积,否则P位于三角形ABC之外。三角形面积的求法有海伦公式,叉积法等。

    (2) 利用角度判断。连接顶点P和三角形的三个顶点ABC,每两条边的夹角之和如果等于 2*PI,则 P 位于三角形上,否则位于三角形外。两个向量之间的夹角可以利用向量的点积来求,不过要求反三角函数。

    方法2:同侧检测:判定顶点是否位于三角形三条边的同侧。

    如果顶点P位于三角形的内部,那么按顺时针或者逆时针将三角形的三条边形成的向量首尾相接(AB, BC, CA),顶点P一定是位于三个向量的同侧。如果顶点相对于三向量的位置发生了改变,比如逆时针时由左侧变为了右侧,则顶点一定位于三角形的外部。

    如何判定顶点P位于向量的哪侧呢?我们知道向量的叉积是一个新的向量,具有方向。所以,通过向量叉积即可确定一个顶点位于一个向量的哪一侧。

    那么又如何确定顺时针还是逆时针呢?其实,不需考虑顺时针还是逆时针。只要顶点 P 与三角形除却判断的向量(比如AB)外余下的那个顶点(比如C)位于同一侧,就可以判定P的相对位置。

    接下来就是如何确定两点位于一个向量的同侧?因为向量的点积可以确定两个向量夹角的大小,当两个向量的点积大于0时,夹角小于 PI/2,可认为同向,否则两向量反向。于是,确定两个顶点P、C是否位于线段AB同侧的方法为:
    构造三个向量:v1 = B - A,v2 = P - A,v3 = C - A;
    判断P、C相对于AB的方向,做叉积:vp = v1 x v2, vc = v3 x v1;
    判断vp、vc是否同向,做点积:d = vp ・ vc;
    如果 d >= 0,说明叉积向量同向,进而推出P、C位于AB的同侧。

    最后,如果针对三角形的三条边,P都和另外的一个顶点同向的话,那么P一定位于三角形上。

    所以整个算法的流程如下:
    function SameSide(p1,p2, a,b)
        cp1 = CrossProduct(b-a, p1-a)
        cp2 = CrossProduct(b-a, p2-a)
        if DotProduct(cp1, cp2) >= 0 then return true
        else return false

    function PointInTriangle(p, a,b,c)
        if SameSide(p,a, b,c) and SameSide(p,b, a,c) and SameSide(p,c, a,b) then 
                return true
        else 
                return false
    算法没有开根号和反三角函数的求解,所以效率相对较高。

    方法3:重心法(barycentric technique)

    在三角形确定的平面上的任意一点P,都可以使用一个重心坐标的形式来表示P的坐标:
         P = uA + vB + wC,u + v + w = 1;
    消去w:
         P - C = u(A - C) + v(B - C)
    上式可以理解为,平面上的任意一个向量都能表示成两个不共线的向量的线性形式。如果P位于三角形上,那么u、v需要满足:
         0 <= u, v <= 1 && u + v <= 1
    为简化书写,我们做以下标记:
         v2 = P - C, v0 = A - C, v1 = B - C
    进而
         v2 = u*v0 + v*v1
    接下来就是求得u、v。因为v0、v1和v2是已知向量,可以直接利用坐标来求解。但是三维空间中,可以得到三个(xyz)关于u、v的方程,而我们只需要两个方程即可,如何选择需要进一步的做些判断,如果选择方程组不合理可能无法解出u、v。

    这里有个避免上述选择的做法,就是利用向量的点积,将向量转化为实数,方程两边同时点积一个向量:
        (v2) ・ v0 = (u * v0 + v * v1) ・ v0
        (v2) ・ v1 = (u * v0 + v * v1) ・ v1
    进而
        v2 ・ v0 = u * (v0 ・ v0) + v * (v1 ・ v0)
        v2 ・ v1 = u * (v0 ・ v1) + v * (v1 ・ v1)
    利用线性方程组的求解方法可以得到u、v:
        u = ((v1・v1)(v2・v0)-(v1・v0)(v2・v1)) / ((v0・v0)(v1・v1) - (v0・v1)(v1・v0))
        v = ((v0・v0)(v2・v1)-(v0・v1)(v2・v0)) / ((v0・v0)(v1・v1) - (v0・v1)(v1・v0))

    此处,看到出现了除法,不能保证除数不等于0。可以分析什么情况下除数为0,预先判断即可。
         (v0・v0)(v1・v1) - (v0・v1)(v1・v0) = 0
    上式中如果 v0 或 v1 等于 0,则三角形便会退化成线段或者点的情况,这变成了点位于线段上的问题。
    当v0、v1都不为0时,由内积公式,上式转变为:
              (v0・v1)(v0・v1) / ((v0・v0)(v1・v1))
           = |v0|^2 * |v1|^2 * (cos<v0,v1> )^2 / (|v0|^2 * |v1|^2)
           = (cos<v0,v1>)^2 
           = 1
    进而可以知道:
         <v0, v1> = 0 或者 <v0, v1> = PI
    v0和v1的夹角无论是哪一种情况,都表示v0和v1是共线的。剩下的又变成了顶点是否位于线段上的问题。

    当 (v0・v0)(v1・v1) - (v0・v1)(v1・v0) != 0 时,便可求解u、v,进而确定P相对于三角形的位置。

    算法的描述如下:
          function PointInTriangle(p, a,b,c)
              v0 = a - c; v1 = b -c; v2 = p - c;
              dot00 = dot(v0, v0); dot01 = dot(v0, v1); dot11 = dot(v1, v1);
              invDemon = dot00 * dot11 - dot01 * dot01;
              if (invDemon < epsilon && invDemon > -epsilon)
                         return PointInLineSegment(p, a, b) || PointInLineSegment(p, a, c) || PointInLineSegment(p, b, c)
              invDemon = 1 / invDemon;
              dot02 = dot(v0, v2); dot12 = dot(v1, v2);
              u = (dot11*dot02 - dot01*dot12) * invDemon;
              v = (dot00*dot12 - dot01*dot02) * invDemon;
              return 0<= u、v <= 1 && u + v <= 1

    顶点是否位于线段上的判定算法PointInLineSegment,参看前篇博文。

    重心法相较方法2中的同侧比较运算要少,所以更高效些。详细讨论见[1].

    参考:
    上一篇:判断顶点是否位于线段上

    展开全文
  • 题目:给定两条线段判断这两条线段是否相交,线段AB的表示形式是A(x1,y1)B(x2,y2),线段CD的表示形式C(x3,y3)D(x4,y4)。那么我们如何判断线段AB与线段CD是否相交。 解析:在介绍如何解决线段相交问题之前,...
        题目:给定两条线段,判断这两条线段是否相交,线段AB的表示形式是A(x1,y1)B(x2,y2),线段CD的表示形式为C(x3,y3)D(x4,y4)。那么我们如何判断线段AB与线段CD是否相交。
        解析:在介绍如何解决线段相交问题之前,我们先介绍向量的叉积。如下图所示:
        下面的图(1)表示p1向量在p2向量的顺时针方向,图(2)表示p1向量在p2向量逆时针方向,图(3)表示p1向量与p2向量共线,我们只画出了同向共线的情况,反向共线的情况同理可得。
    
        有了上面的叉积运算,很容易判断两条线段是否相交,比如说我们要判断线段p1p2与线段p3p4是否相交。(1)计算p1p3向量与p1p2向量的叉积值。(2)计算p1p4向量与p1p2向量的叉积值。(3)判断这两个叉积值是否为异号。(4)计算p3p1向量与p3p4向量的叉积值。(5)计算p3p2向量与p3p4向量的叉积值。(6)判断这两个叉积值是否为异号。(7)如果这两对叉积值都为异号,则说明两条线段相交,否则则不想交。如下图所示:
    
        有一种特殊情况:比如说下图中的左图中线段p1p2与线段p3p4相交。向量p1p3与向量p1p2的叉积值为零。右图中线段p1p2与线段p3p4不相交。但是向量p1p3与向量p1p2的叉积值也为零。那么我们如何处理这种情况:我们只需要判断p3点在p1点与p2点之间即可,也就是说x1<=x3<=x2且y1<=y3<=y2。
    
    #include<iostream>
    #include<vector>
    using namespace std;
    
    struct Point
    {
    	int x;
    	int y;
    	Point(int myX, int myY) :x(myX), y(myY)
    	{}
    	Point(){}
    };
    
    bool isIntersect(vector<Point> &line1, vector<Point> &line2)
    {
    	int x1 = line1[0].x;
    	int y1 = line1[0].y;
    	int x2 = line1[1].x;
    	int y2 = line1[1].y;
    	int x3 = line2[0].x;
    	int y3 = line2[0].y;
    	int x4 = line2[1].x;
    	int y4 = line2[1].y;
    	int num1 = (x4 - x1)*(y2 - y1) - (y4 - y1)*(x2 - x1);
    	int num2 = (x3 - x1)*(y2 - y1) - (y3 - y1)*(x2 - x1);
    	int num3 = (x1 - x3)*(y4 - y3) - (y1 - y3)*(x4 - x3);
    	int num4 = (x2 - x3)*(y4 - y3) - (y2 - y3)*(x4 - x3);
    	if (num1*num2 < 0 && num3*num4 < 0)
    	{
    		return true;
    	}
    	if (num1 == 0)
    	{
    		if ((x4 > x1 && x4 > x2) || (x4 < x1 && x4 < x2))
    		{
    			return false;
    		}
    	}
    	if (num2 == 0)
    	{
    		if ((x3 > x1 && x3 > x2) || (x3 < x1 && x3 < x2))
    		{
    			return false;
    		}
    	}
    	if (num3 == 0)
    	{
    		if ((x2 > x3 && x2 > x4) || (x2 < x3 && x2 < x4))
    		{
    			return false;
    		}
    	}
    	if (num4 == 0)
    	{
    		if ((x1 > x3 && x1 > x4) || (x1 < x3 && x1 < x4))
    		{
    			return false;
    		}
    	}
    	return true;
    }
    
    int main(void)
    {
    	system("pause");
    	return 0;
    }
    
    
    
    
    
    
    展开全文
  • 线段1的坐标x11,x12 线段2的坐标x21,x22 如果两条线段满足min(x12,x22) < max(x11,x12),那么两条线段有交集。 两个矩形是否有重叠部分的问题: 如果两个矩形有重叠部分,那么重叠部分也是一个矩阵,重叠...

    线段1的坐标为x11,x12
    线段2的坐标为x21,x22
    如果两条线段满足min(x12,x22) < max(x11,x12),那么两条线段有交集。


    两个矩形是否有重叠部分的问题:

    如果两个矩形有重叠部分,那么重叠部分也是一个矩阵,重叠矩阵的水平边投影到x轴是一条线段,垂直边投影到y轴也是一条线段。
    问题可以转换为:
    两个矩阵的水平边投影到x轴上的两条线段是否有交集
    && 两个矩阵的垂直边投影到y轴上的两条线段是否有交集

    展开全文
  • 我们的问题是这样的:给定一条线段的起点$A_1$、终点$A_2$,另一条线段的起点$B_1$、终点$B_2$,问线段$A_1A_2$和线段$B_1B_2$是否相交? 我们首先解释一下,两条线段相交的概念是指,存在一个点,这个点...

    我们的问题是这样的:给定一条线段的起点为$A_1$、终点为$A_2$,另一条线段的起点为$B_1$、终点为$B_2$,问线段$A_1A_2$和线段$B_1B_2$是否相交?

    我们首先解释一下,两条线段相交的概念是指,存在一个点,这个点同时在两条线段上。

    方法一(解方程法):

    容易知道,线段$A_1A_2$上的点的集合为$A = A_1 * (1 - r_1) + A_2 * r_1$,其中$r_1 \in [0, 1]$;同理,线段$B_1B_2$上的点的集合为$B = B_1 * (1 - r_2) + B_2 * r_2$,其中$r_2 \in [0, 1]$。一般的,如果不对$r_1$(或$r_2$)的范围作约束,得到的点集构成该线段所在的直线。那么这个问题就简单了,我们可以首先将两条线段延展成直线,求出两条直线的交点,根据交点位置可以分别求出$r_1$和$r_2$,然后判断$r_1$和$r_2$是否同时在$[0, 1]$区间即可。我们把$r_1$($r_2$)叫做点$A$($B$)在线段$A_1A_2$(线段$B_1B_2$)上的比例。

    两直线的交点满足$A_1 * (1 - r_1) + A_2 * r_1 = B_1 * (1 - r_2) + B_2 * r_2$,稍微变形可得$(A_2 - A_1) * r_1 - (B_2 - B_1) * r_2 = B_1 - A_1$,即$$\overrightarrow{A_1A_2} * r_1 - \overrightarrow{B_1B_2} * r_2 = \overrightarrow{A_1B_1}$$,表示为向量矩阵的形式为(令$\overrightarrow{r} = (r_1, r_2)^T$):$$[\overrightarrow{A_1A_2}, - \overrightarrow{B_1B_2}] * \overrightarrow{r} = \overrightarrow{A_1B_1}$$

    我们的目的是根据以上二元方程组求出$r_1$和$r_2$,但是在此之前,我们要判断一些特殊情况:

    (1). 如果$\overrightarrow{A_1A_2} = \overrightarrow{0}$,即线段$A_1A_2$是一个点,这时,等式退化为$- \overrightarrow{B_1B_2} * r_2 = \overrightarrow{A_1B_1}$,两个方程一个未知量,如果有解,则点$A_1$(或$A_2$)在线段$B_1B_2$上,即两“线段”相交;否则,不相交。

    (2). 如果$\overrightarrow{B_1B_2} = \overrightarrow{0}$,即线段$B_1B_2$是一个点,这时,等式退化为$\overrightarrow{A_1A_2} * r_1 = \overrightarrow{A_1B_1}$,两个方程一个未知量,如果有解,则点$B_1$(或$B_2$)在线段$A_1A_2$上,即两“线段”相交;否则,不相交。

    (3). 除以上两种情况以外,如果两直线平行即$\overrightarrow{A_1A_2} // \overrightarrow{B_1B_2}$,这时要分两种情况,如果两线段平行且有平行距离,则不相交;否则,两线段在同一直线上,这时又分两种情况,两线段是否有重合部分,如果有则相交,如果没有则不相交。至于如何判断在同一直线上的两条线段是否有重合部分,可以利用快速排斥实验,后面还会讲到。

    (4). 除以上三种情况外,矩阵$[\overrightarrow{A_1A_2}, - \overrightarrow{B_1B_2}]$可逆,我们可以直接求出$r_1$和$r_2$,然后判断$r_1$和$r_2$是否同时在$[0, 1]$区间即可。

    方法二(外积法):

     可以看到,解方程法需要判断几种特殊情况,而且涉及到除法运算,在计算机实现时对调用频率比价高、效率要求比较高的场景也不够“完美”。下面介绍一种基于向量外积的方法,判断逻辑更简洁,而且也不涉及除法操作。

    向量外积:

    首先简单介绍一下向量外积。向量外积,也叫向量叉乘。与内积不同的是,向量外积的结果还是一个向量,它的模为两个向量围成的平行四边形的面积,方向与平行四边形所在的平面垂直,指向由右手螺旋定则确定。写成公式为:

    $$\left | \overrightarrow{a} \times \overrightarrow{b} \right | = \left | \overrightarrow{a} \right | \bullet \left | \overrightarrow{b} \right | \bullet sin \theta $$

    其中,$\theta$为两个向量的夹角。

    如果知道两个向量的坐标$\overrightarrow{a} = (a_x, a_y, a_z)$、$\overrightarrow{b} = (b_x, b_y, b_z)$,则两个向量的外积的坐标运算为:

    $$\overrightarrow{a} \times \overrightarrow{b} = (a_yb_z - a_zb_y) \overrightarrow{i} + (a_zb_x - a_xb_z)\overrightarrow{j} + (a_xb_y - a_yb_x)\overrightarrow{k}$$

    为了便于记忆,还可以写为三阶行列式的形式:

    $$\overrightarrow{a} \times \overrightarrow{b} = det \left | \begin{array}{cc} \overrightarrow{i} & \overrightarrow{j} & \overrightarrow{k} \\ a_x & a_y & a_z \\ b_x & b_y & b_z \end{array} \right |$$

    利用外积判断点与线段的相对位置:

    假设有向线段为$\overrightarrow{AB}$,点为$C$,首先计算外积$\overrightarrow{AC} \times \overrightarrow{AB} = (\overrightarrow{AC}_x \cdot \overrightarrow{AB}_y - \overrightarrow{AC}_y \cdot \overrightarrow{AB}_x)\overrightarrow{k}$ (因为有$\overrightarrow{AB}_z = 0 $、$\overrightarrow{AC}_z = 0 $)。根据右手螺旋定则,如果$\overrightarrow{k}$的系数为正数,说明点C在线段AB的右侧;如果为负数,说明点C在线段AB的左侧;如果为0,说明点C在线段AB所在的直线上。写成伪代码为:

      //*************************************************************************
      // \brief: 计算两个向量的外积(叉乘)。可以根据结果的符号判断三个点的位置关系。
      // \Param: Point A 两个向量的公共起点。
      // \Param: Point B 第一个向量的终点。
      // \Param: Point C 第二个向量的终点。
      // \Returns: double 向量AC与向量AB的外积。如果结果为正数,表明点C在直线AB(直线方向为从A到B)的右侧;
      // 如果结果为负数,表明点C在直线AB(直线方向为从A到B)的左侧;如果结果为0,表明点C在直线AB上。
     //*************************************************************************

    double cross(Point A, Point B, Point C) {
        double cross1 = (C.x - A.x) * (B.y - A.y);
        double cross2 = (C.y - A.y) * (B.x - A.x);
        return (cross1 - cross2);
    }

    线段相交判断:

    回到一开始的问题,要判断线段$A_1A_2$和线段$B_1B_2$是否相交,首先计算:

    T1 = cross(A1, A2, B1);
    T2 = cross(A1, A2, B2);
    T3 = cross(B1, B2, A1);
    T4 = cross(B1, B2, A2);

    根据以上结果即可判断两条线段的相交关系:

    (1). 如果(T1 * T2) > 0) || (T3 * T4) > 0,说明一条线段的两个端点在另一条线段的同侧,这两条线段肯定不相交。

    (2). 如果T1 == 0 && T2 == 0,说明两条线段共线,是否相交还需要进一步判断。这时可以通过判断两条线段张成的矩形是否相交来判断,而两个矩形是否相交可以通过快速排斥实验来判断。快速排斥实验稍后介绍。

    (3). 其他情况,两个线段一定相交。

    可以看到,这种方法不需要对线段的起终点重合(线段退化为一个点)做特殊判断,也不需要对线段平行(除了共线的情况)做特殊判断。纯几何方法,逻辑更简洁。

    对第3种情况补充说明如下:除了第1、2种情况外(T1、T2不同号、且不同为0),T1、T2的取值还有6种情况:(+, 0)、(+, -)、(-, 0)、(-, +)、(0, +)、(0, -)。当T1、T2为(+, 0)时,T3、T4的取值只可能是(-, 0)、(-, +)、(0, +),无论哪种情况,两线段都相交。当T1、T2为(+, -)时,T3、T4的取值只可能是(-, 0)、(-, +)、(0, +),无论哪种情况,两线段都相交;当T1、T2为(-, 0)或(-, +)时,情况与前两个类似。当T1、T2为(0, +)时,T3、T4的取值只可能是(0, -)、(+, -)、(+, 0),无论哪种情况,两线段都相交;当T1、T2为(0, -)时,与前一种情况类似。

     

    补充:快速排斥实验

    快速排斥实验用于判断两个矩形是否相交,因为是比较简单、也比较基础的方法,在这里就不详细介绍了,对原理感兴趣的可以参考http://blog.sina.com.cn/s/blog_71dbfe2e0101f7zb.html 一文。直接给出伪代码实现:

    //*************************************************************************
    // \brief: 	快速排斥实验,判断两个线段张成的矩形区域是否相交。
    // \Param: 	Point S1 第一条线段的起点。
    // \Param: 	Point E1 第一条线段的终点。
    // \Param: 	Point S2 第二条线段的起点。
    // \Param: 	Point E2 第二条线段的终点。
    // \Returns: 	bool 两个线段张成的矩形区域是否相交。具有对称性,即交换两条线段(参数S1与S2交换、E1与E2交换),结果不变。
    //*************************************************************************
    bool rectsIntersect(Point S1, Point E1, Point S2, Point E2) {
      if ( Gmin(S1.y, E1.y) <= Gmax(S2.y, E2.y) && Gmax(S1.y, E1.y) >= Gmin(S2.y, E2.y) && Gmin(S1.x, E1.x) <= Gmax(S2.x, E2.x) && Gmax(S1.x, E1.x) >= Gmin(S2.x, E2.x)) { return true; } return false; }

    因此,判断两条线段相交的伪代码为:

    bool segmentsIntersect(Point A1, Point A2, Point B1, Point B2) {
        double T1 = cross(A1, A2, B1);
        double T2 = cross(A1, A2, B2);
    double T3 = cross(B1, B2, A1);
    double T4 = cross(B1, B2, A2);
      if (((T1 * T2) > 0) || ((T3 * T4) > 0)) { // 一条线段的两个端点在另一条线段的同侧,不相交。(可能需要额外处理以防止乘法溢出,视具体情况而定。) return false; } else if(T1 == 0 && T2 == 0) { // 两条线段共线,利用快速排斥实验进一步判断。此时必有 T3 == 0 && T4 == 0。 return rectsIntersect(A1, A2, B1, B2); } else { // 其它情况,两条线段相交。 return true;
    } }

    此文完。

    转载于:https://www.cnblogs.com/kane1990/p/5742830.html

    展开全文
  • 判断两条线段是否相交 计算几何

    千次阅读 2016-12-08 21:31:14
    关键问题是:如何判断直线AB是否线段CD相交呢? 设直线AB的方程:f(x,y) = 0,直线方程可以通过两点式求得。 当C和D点不在直线的同侧时,直线AB必然与线段CD相交,也就是说直线AB与线段CD相交的条件:f(C) * ...
  • 1 function judgeIntersect... 5 //两个线段为对角线组成的矩形,如果这两个矩形没有重叠的部分,那么两条线段是不可能出现重叠的 6 7 //这里的确如此,这一步是判定两矩形是否相交 8 //1.线段ab的低点低于c...
  • 判断两个线段是否相交 &gt; 作者:kane1990 写的非常详细,推荐使用 方法二(外积法).大致意思是一条线段的两个点在另外一个线段的同一侧(通过叉积法).令线段1的起终点a,b.线段2的起终点c,d.则ab向量与ac...
  • C#判断线段是否相交

    千次阅读 2017-04-20 17:14:17
    线段是否相交,一种是从几何上就是判断两个线段有没有交点,还有一种是通过向量叉乘(也就是向量积)来判断。因为向量叉乘的结果是一个垂直于原来两个向量的新向量,可以简单的理解垂直于原来两向量所在平面的向量...
  • 一、判断两条线段是否相交 主要依据是通过矢量的叉积(行列式)的性质: /* 设矢量 P = (x1, y1),Q = ( x2, y2 ),则矢量叉积(行列式)定义:P × Q = x1*y2 - x2*y1 叉积的一个非常重要性质是可以通过它的...
  • 判断点(P)是否在多边形中,可以先以点p向左引一条射线(L),我们知道,从射线L左端的无穷远处开始一直到点P的过程中,当遇到多边形的第一个交点时L进入了多边形,当遇到第二个交点时,L穿出了多边形。。。。。。...
  • 判断线段和圆是否相交判断圆和线段相交,分两种情况: 1. 如图A所示,当圆心与线段的距离大于圆的半径时,线段与圆肯定不相交2. 如图B,C所示,两个端点都不在圆内,那么看圆心到线段所在直线的垂足是否小于半径且...
  • 原理:如果两条线段相交,那么必须跨立,就是以一条线段为标准,另一条线段的两端点一定在这条线段的两段 也就是说a b两点在线段cd的两端,c d两点在线段ab的两端struct point() { double x,y; }; double multi...
  • 设以线段A1A2和线段B1B2对角线的矩形M,N; 若M,N 不相交,则两个线段显然不相交; 所以:满足第一个条件时:两个线段可能相交。   b.跨立实验   如果两线段相交,则两线段必然相互跨...
  • 题意大概就是给一些线段,问能不能找到一条直线使得这些线段在直线上的投影的交不空。 线段数不大于100。 分析 要是投影的交不空,那么就是至少有一条垂直于那个直线的直线能经过所有线段。 而且可以说明,...
  • 判断线段是否相交并求交点 公式推导 设两条线段AB和CD,其端点分别(xa,ya),(xb,yb)(xc,yc),(xd,yd)(x_a,y_a),(x_b,y_b) (x_c,y_c),(x_d,y_d)(xa​,ya​),(xb​,yb​)(xc​,yc​),(xd​,yd​).需要判断2条线段是否...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 924
精华内容 369
关键字:

判断是否为线段