我有一条从a到B的直线和一个半径为R的圆。

用什么算法来检查直线是否与圆相交?它在圆边的哪个坐标上?


当前回答

如果直线的坐标为A.x, A.y和B.x, B.y,圆心为C.x, C.y,则直线公式为:

x = A.x * t + B.x * (1 - t)

y = A.y * t + B.y * (1 - t)

0 < = t < = 1

这个圆是

(C.x - x)²+ (C.y - y)²= R²

如果你把直线的x和y公式代入圆公式,你会得到一个t的二阶方程,它的解是交点(如果有的话)。如果你得到的t小于0或大于1,那么它不是一个解,但它表明这条线“指向”圆的方向。

其他回答

好吧,我不会给你代码,但既然你已经标记了这个算法,我认为这对你来说无关紧要。 首先,你要得到一个垂直于这条直线的向量。

y = ax + c是一个未知变量c是未知变量 为了解决这个问题,计算直线经过圆心时的值。

也就是说, 将圆心的位置代入直线方程,解出c。 然后计算原直线与其法线的交点。

这样就能得到直线上离圆最近的点。 计算该点到圆中心之间的距离(使用矢量的大小)。 如果这个小于圆的半径,看,我们有一个交点!

另一种解决方案,首先考虑不关心碰撞位置的情况。请注意,这个特定的函数是在假设xB和yB为向量输入的情况下构建的,但如果情况并非如此,则可以轻松修改。变量名在函数的开头定义

#Line segment points (A0, Af) defined by xA0, yA0, xAf, yAf; circle center denoted by xB, yB; rB=radius of circle, rA = radius of point (set to zero for your application)
def staticCollision_f(xA0, yA0, xAf, yAf, rA, xB, yB, rB): #note potential speed up here by casting all variables to same type and/or using Cython
    
    #Build equations of a line for linear agents (convert y = mx + b to ax + by + c = 0 means that a = -m, b = 1, c = -b
    m_v = (yAf - yA0) / (xAf - xA0)
    b_v = yAf - m_v * xAf
    rEff = rA + rB #radii are added since we are considering the agent path as a thin line

    #Check if points (circles) are within line segment (find center of line segment and check if circle is within radius of this point)
    segmentMask = np.sqrt( (yB - (yA0+yAf)/2)**2 + (xB - (xA0+xAf)/2)**2 ) < np.sqrt( (yAf - yA0)**2 + (xAf - xA0)**2 ) / 2 + rEff

    #Calculate perpendicular distance between line and a point
    dist_v = np.abs(-m_v * xB + yB - b_v) / np.sqrt(m_v**2 + 1)
    collisionMask = (dist_v < rEff) & segmentMask

    #return True if collision is detected
    return collisionMask, collisionMask.any()

如果您需要碰撞的位置,您可以使用这个站点上详细介绍的方法,并将其中一个代理的速度设置为零。这种方法也适用于矢量输入:http://twobitcoder.blogspot.com/2010/04/circle-collision-detection.html

圆真的是一个坏人:)所以一个好办法是避免真正的圆,如果可以的话。如果你正在为游戏做碰撞检查,你可以进行一些简化,只做3个点积,并进行一些比较。

我称之为“胖点”或“瘦圈”。它是平行于线段方向上半径为0的椭圆。而是垂直于线段方向的全半径

首先,我会考虑重命名和切换坐标系统,以避免过多的数据:

s0s1 = B-A;
s0qp = C-A;
rSqr = r*r;

其次,hvec2f中的索引h意味着vector必须支持水平操作,如dot()/det()。这意味着它的组件被放置在一个单独的xmm寄存器中,以避免shuffle /hadd'ing/hsub'ing。现在我们开始,最简单的2D游戏碰撞检测的最佳性能版本:

bool fat_point_collides_segment(const hvec2f& s0qp, const hvec2f& s0s1, const float& rSqr) {
    auto a = dot(s0s1, s0s1);
    //if( a != 0 ) // if you haven't zero-length segments omit this, as it would save you 1 _mm_comineq_ss() instruction and 1 memory fetch
    {
        auto b = dot(s0s1, s0qp);
        auto t = b / a; // length of projection of s0qp onto s0s1
        //std::cout << "t = " << t << "\n";
        if ((t >= 0) && (t <= 1)) // 
        {
            auto c = dot(s0qp, s0qp);
            auto r2 = c - a * t * t;
            return (r2 <= rSqr); // true if collides
        }
    }   
    return false;
}

我怀疑你能进一步优化它。我正在用它进行神经网络驱动的赛车碰撞检测,处理数百万个迭代步骤。

另一种方法使用三角形ABC面积公式。交点检验比投影法简单高效,但求交点坐标需要更多的工作。至少它会被推迟到需要的时候。

三角形面积的计算公式为:area = bh/2

b是底长,h是高。我们选择线段AB作为底,使h是圆心C到直线的最短距离。

因为三角形的面积也可以用向量点积来计算,所以我们可以确定h。

// compute the triangle area times 2 (area = area2/2)
area2 = abs( (Bx-Ax)*(Cy-Ay) - (Cx-Ax)(By-Ay) )

// compute the AB segment length
LAB = sqrt( (Bx-Ax)² + (By-Ay)² )

// compute the triangle height
h = area2/LAB

// if the line intersects the circle
if( h < R )
{
    ...
}        

更新1:

您可以通过使用这里描述的快速平方根倒数计算来优化代码,以获得1/LAB的良好近似值。

计算交点并不难。开始了

// compute the line AB direction vector components
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB

// compute the distance from A toward B of closest point to C
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)

// t should be equal to sqrt( (Cx-Ax)² + (Cy-Ay)² - h² )

// compute the intersection point distance from t
dt = sqrt( R² - h² )

// compute first intersection point coordinate
Ex = Ax + (t-dt)*Dx
Ey = Ay + (t-dt)*Dy

// compute second intersection point coordinate
Fx = Ax + (t+dt)*Dx
Fy = Ay + (t+dt)*Dy

如果h = R,则直线AB与圆相切,且值dt = 0, E = F。点的坐标为E和F的坐标。

如果在应用程序中出现这种情况,您应该检查A与B是否不同,并且段长度不为空。

也许有另一种方法来解决这个问题,使用坐标系的旋转。

通常,如果一个线段是水平的或垂直的,这意味着平行于x轴或y轴,交点的求解很容易,因为我们已经知道交点的一个坐标,如果有的话。剩下的显然是用圆的方程找到另一个坐标。

受此启发,我们可以利用坐标系旋转,使一个轴的方向与线段的方向重合。

让我们以圆x^2+y^2=1和线段P1-P2为例,P1(-1.5,0.5)和P2(-0.5,-0.5)在x-y系统中。下面的方程提醒你旋转的原理,其中是逆时针方向的角度,x'-y'是旋转后的方程组:

x'=x*cos () + y*sin () y' = - x*sin () + y*cos ()

和反向

X = X ' * cos - y' * sin Y = x' * sin + Y ' * cos

考虑P1-P2方向(用-x表示为45°),我们可以取=45°。将第二个旋转方程转化为x-y系统中的圆方程:x^2+y^2=1,经过简单的运算,我们得到x'-y'系统中的“相同”方程:x'^2+y'^2=1。

利用第一个旋转方程=> P1(-根号(2)/2,根号(2)),P2(-根号(2)/ 2,0),线段端点变成x'-y'系统。

假设交点为p,在x'-y'中,Px = -根号2 /2。使用新的圆方程,我们得到Py = +根号(2)/2。将P转换成原始的x-y系统,最终得到P(-1,0)

为了实现这个数值,我们可以先看看线段的方向:水平,垂直或不垂直。如果它属于前两种情况,很简单。如果是最后一种情况,应用上述算法。

为了判断是否有交集,我们可以将解与端点坐标进行比较,看看它们之间是否有一个根。

我相信只要我们有了它的方程,这个方法也可以应用于其他曲线。唯一的缺点是,我们应该在x'-y'坐标系下解方程,这可能很难。