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

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


当前回答

这里是一个用golang写的解决方案。这个方法和这里发布的其他一些答案类似,但不完全相同。它易于实现,并已经过测试。以下是步骤:

Translate coordinates so that the circle is at the origin. Express the line segment as parametrized functions of t for both the x and y coordinates. If t is 0, the function's values are one end point of the segment, and if t is 1, the function's values are the other end point. Solve, if possible, the quadratic equation resulting from constraining values of t that produce x, y coordinates with distances from the origin equal to the circle's radius. Throw out solutions where t is < 0 or > 1 ( <= 0 or >= 1 for an open segment). Those points are not contained in the segment. Translate back to original coordinates.

这里导出了二次曲线的A、B和C的值,其中(n-et)和(m-dt)分别是直线x坐标和y坐标的方程。R是圆的半径。

(n-et)(n-et) + (m-dt)(m-dt) = rr
nn - 2etn + etet + mm - 2mdt + dtdt = rr
(ee+dd)tt - 2(en + dm)t + nn + mm - rr = 0

因此A = ee+dd, B = - 2(en + dm), C = nn + mm - rr。

下面是函数的golang代码:

package geom

import (
    "math"
)

// SegmentCircleIntersection return points of intersection between a circle and
// a line segment. The Boolean intersects returns true if one or
// more solutions exist. If only one solution exists, 
// x1 == x2 and y1 == y2.
// s1x and s1y are coordinates for one end point of the segment, and
// s2x and s2y are coordinates for the other end of the segment.
// cx and cy are the coordinates of the center of the circle and
// r is the radius of the circle.
func SegmentCircleIntersection(s1x, s1y, s2x, s2y, cx, cy, r float64) (x1, y1, x2, y2 float64, intersects bool) {
    // (n-et) and (m-dt) are expressions for the x and y coordinates
    // of a parameterized line in coordinates whose origin is the
    // center of the circle.
    // When t = 0, (n-et) == s1x - cx and (m-dt) == s1y - cy
    // When t = 1, (n-et) == s2x - cx and (m-dt) == s2y - cy.
    n := s2x - cx
    m := s2y - cy

    e := s2x - s1x
    d := s2y - s1y

    // lineFunc checks if the  t parameter is in the segment and if so
    // calculates the line point in the unshifted coordinates (adds back
    // cx and cy.
    lineFunc := func(t float64) (x, y float64, inBounds bool) {
        inBounds = t >= 0 && t <= 1 // Check bounds on closed segment
        // To check bounds for an open segment use t > 0 && t < 1
        if inBounds { // Calc coords for point in segment
            x = n - e*t + cx
            y = m - d*t + cy
        }
        return
    }

    // Since we want the points on the line distance r from the origin,
    // (n-et)(n-et) + (m-dt)(m-dt) = rr.
    // Expanding and collecting terms yeilds the following quadratic equation:
    A, B, C := e*e+d*d, -2*(e*n+m*d), n*n+m*m-r*r

    D := B*B - 4*A*C // discriminant of quadratic
    if D < 0 {
        return // No solution
    }
    D = math.Sqrt(D)

    var p1In, p2In bool
    x1, y1, p1In = lineFunc((-B + D) / (2 * A)) // First root
    if D == 0.0 {
        intersects = p1In
        x2, y2 = x1, y1
        return // Only possible solution, quadratic has one root.
    }

    x2, y2, p2In = lineFunc((-B - D) / (2 * A)) // Second root

    intersects = p1In || p2In
    if p1In == false { // Only x2, y2 may be valid solutions
        x1, y1 = x2, y2
    } else if p2In == false { // Only x1, y1 are valid solutions
        x2, y2 = x1, y1
    }
    return
}

我用这个函数进行了测试,确认解点在线段内和圆上。它创建了一个测试段,并围绕给定的圆进行扫描:

package geom_test

import (
    "testing"

    . "**put your package path here**"
)

func CheckEpsilon(t *testing.T, v, epsilon float64, message string) {
    if v > epsilon || v < -epsilon {
        t.Error(message, v, epsilon)
        t.FailNow()
    }
}

func TestSegmentCircleIntersection(t *testing.T) {
    epsilon := 1e-10      // Something smallish
    x1, y1 := 5.0, 2.0    // segment end point 1
    x2, y2 := 50.0, 30.0  // segment end point 2
    cx, cy := 100.0, 90.0 // center of circle
    r := 80.0

    segx, segy := x2-x1, y2-y1

    testCntr, solutionCntr := 0, 0

    for i := -100; i < 100; i++ {
        for j := -100; j < 100; j++ {
            testCntr++
            s1x, s2x := x1+float64(i), x2+float64(i)
            s1y, s2y := y1+float64(j), y2+float64(j)

            sc1x, sc1y := s1x-cx, s1y-cy
            seg1Inside := sc1x*sc1x+sc1y*sc1y < r*r
            sc2x, sc2y := s2x-cx, s2y-cy
            seg2Inside := sc2x*sc2x+sc2y*sc2y < r*r

            p1x, p1y, p2x, p2y, intersects := SegmentCircleIntersection(s1x, s1y, s2x, s2y, cx, cy, r)

            if intersects {
                solutionCntr++
                //Check if points are on circle
                c1x, c1y := p1x-cx, p1y-cy
                deltaLen1 := (c1x*c1x + c1y*c1y) - r*r
                CheckEpsilon(t, deltaLen1, epsilon, "p1 not on circle")

                c2x, c2y := p2x-cx, p2y-cy
                deltaLen2 := (c2x*c2x + c2y*c2y) - r*r
                CheckEpsilon(t, deltaLen2, epsilon, "p2 not on circle")

                // Check if points are on the line through the line segment
                // "cross product" of vector from a segment point to the point
                // and the vector for the segment should be near zero
                vp1x, vp1y := p1x-s1x, p1y-s1y
                crossProd1 := vp1x*segy - vp1y*segx
                CheckEpsilon(t, crossProd1, epsilon, "p1 not on line ")

                vp2x, vp2y := p2x-s1x, p2y-s1y
                crossProd2 := vp2x*segy - vp2y*segx
                CheckEpsilon(t, crossProd2, epsilon, "p2 not on line ")

                // Check if point is between points s1 and s2 on line
                // This means the sign of the dot prod of the segment vector
                // and point to segment end point vectors are opposite for
                // either end.
                wp1x, wp1y := p1x-s2x, p1y-s2y
                dp1v := vp1x*segx + vp1y*segy
                dp1w := wp1x*segx + wp1y*segy
                if (dp1v < 0 && dp1w < 0) || (dp1v > 0 && dp1w > 0) {
                    t.Error("point not contained in segment ", dp1v, dp1w)
                    t.FailNow()
                }

                wp2x, wp2y := p2x-s2x, p2y-s2y
                dp2v := vp2x*segx + vp2y*segy
                dp2w := wp2x*segx + wp2y*segy
                if (dp2v < 0 && dp2w < 0) || (dp2v > 0 && dp2w > 0) {
                    t.Error("point not contained in segment ", dp2v, dp2w)
                    t.FailNow()
                }

                if s1x == s2x && s2y == s1y { //Only one solution
                    // Test that one end of the segment is withing the radius of the circle
                    // and one is not
                    if seg1Inside && seg2Inside {
                        t.Error("Only one solution but both line segment ends inside")
                        t.FailNow()
                    }
                    if !seg1Inside && !seg2Inside {
                        t.Error("Only one solution but both line segment ends outside")
                        t.FailNow()
                    }

                }
            } else { // No intersection, check if both points outside or inside
                if (seg1Inside && !seg2Inside) || (!seg1Inside && seg2Inside) {
                    t.Error("No solution but only one point in radius of circle")
                    t.FailNow()
                }
            }
        }
    }
    t.Log("Tested ", testCntr, " examples and found ", solutionCntr, " solutions.")
}

下面是测试的输出:

=== RUN   TestSegmentCircleIntersection
--- PASS: TestSegmentCircleIntersection (0.00s)
    geom_test.go:105: Tested  40000  examples and found  7343  solutions.

最后,该方法很容易扩展到射线从一点开始,经过另一点并延伸到无穷远的情况,只需测试t > 0或t < 1,而不是两者都测试。

其他回答

似乎没人考虑投影,我是不是完全跑题了?

将向量AC投影到AB上,投影的向量AD就得到了新的点D。 如果D和C之间的距离小于(或等于)R,我们有一个交点。

是这样的:

社区编辑:

对于稍后无意中看到这篇文章并想知道如何实现这样一个算法的人来说,这里是一个使用常见向量操作函数用JavaScript编写的通用实现。

/**
 * Returns the distance from line segment AB to point C
 */
function distanceSegmentToPoint(A, B, C) {
    // Compute vectors AC and AB
    const AC = sub(C, A);
    const AB = sub(B, A);

    // Get point D by taking the projection of AC onto AB then adding the offset of A
    const D = add(proj(AC, AB), A);

    const AD = sub(D, A);
    // D might not be on AB so calculate k of D down AB (aka solve AD = k * AB)
    // We can use either component, but choose larger value to reduce the chance of dividing by zero
    const k = Math.abs(AB.x) > Math.abs(AB.y) ? AD.x / AB.x : AD.y / AB.y;

    // Check if D is off either end of the line segment
    if (k <= 0.0) {
        return Math.sqrt(hypot2(C, A));
    } else if (k >= 1.0) {
        return Math.sqrt(hypot2(C, B));
    }

    return Math.sqrt(hypot2(C, D));
}

对于这个实现,我使用了两个常见的矢量操作函数,无论您在什么环境中工作,都可能已经提供了这些函数。但是,如果您还没有这些可用的功能,下面介绍如何实现它们。

// Define some common functions for working with vectors
const add = (a, b) => ({x: a.x + b.x, y: a.y + b.y});
const sub = (a, b) => ({x: a.x - b.x, y: a.y - b.y});
const dot = (a, b) => a.x * b.x + a.y * b.y;
const hypot2 = (a, b) => dot(sub(a, b), sub(a, b));

// Function for projecting some vector a onto b
function proj(a, b) {
    const k = dot(a, b) / dot(b, b);
    return {x: k * b.x, y: k * b.y};
}

这个Java函数返回一个DVec2对象。它用DVec2表示圆心,用DVec2表示半径,用Line表示直线。

public static DVec2 CircLine(DVec2 C, double r, Line line)
{
    DVec2 A = line.p1;
    DVec2 B = line.p2;
    DVec2 P;
    DVec2 AC = new DVec2( C );
    AC.sub(A);
    DVec2 AB = new DVec2( B );
    AB.sub(A);
    double ab2 = AB.dot(AB);
    double acab = AC.dot(AB);
    double t = acab / ab2;

    if (t < 0.0) 
        t = 0.0;
    else if (t > 1.0) 
        t = 1.0;

    //P = A + t * AB;
    P = new DVec2( AB );
    P.mul( t );
    P.add( A );

    DVec2 H = new DVec2( P );
    H.sub( C );
    double h2 = H.dot(H);
    double r2 = r * r;

    if(h2 > r2) 
        return null;
    else
        return P;
}

这里你需要一些数学知识:

假设A = (Xa, Ya), B = (Xb, Yb), C = (Xc, Yc)。从A到B的直线上的任意一点都有坐标(*Xa + (1-)Xb, * ya + (1-)*Yb) = P

如果点P的距离是R到C,它一定在圆上。你想要的是解决

distance(P, C) = R

这是

(alpha*Xa + (1-alpha)*Xb)^2 + (alpha*Ya + (1-alpha)*Yb)^2 = R^2
alpha^2*Xa^2 + alpha^2*Xb^2 - 2*alpha*Xb^2 + Xb^2 + alpha^2*Ya^2 + alpha^2*Yb^2 - 2*alpha*Yb^2 + Yb^2=R^2
(Xa^2 + Xb^2 + Ya^2 + Yb^2)*alpha^2 - 2*(Xb^2 + Yb^2)*alpha + (Xb^2 + Yb^2 - R^2) = 0

如果你将abc公式应用到这个方程来求解,并使用alpha的解来计算P的坐标,你会得到交点,如果存在的话。

虽然我认为使用线圆交点,然后检查交点是否在端点之间更好,可能更便宜,但我想添加这个更直观的解决方案。

我喜欢把这个问题想象成“香肠上的点问题”,在不改变算法的情况下,它可以在任何维度上工作。 这个解找不到交点。

以下是我想到的:

(我使用“小于”,但“小于或等于”也可以使用,这取决于我们测试的内容。)

确保Circle_Point小于到无限线的半径距离。(这里使用最喜欢的方法)。 计算从两个Segment_Points到Circle_Point的距离。 测试较大的Circle_Point-Segment_Point距离是否小于根号(Segment_Length^2+Radius^2)。 (这是从一个分段点到一个理论点的距离,也就是从另一个分段点到无限线(直角)的半径距离。见图片)。

3 t。如果为true: Circle_Point在sausage内部。 3 f。如果为false:如果较小的Circle_Point- segment_point距离小于Radius,则Circle_Point在sausage内部。

图片:最粗的线段是选定的线段,没有示例圆。有点粗糙,有些像素有点不对。

function boolean pointInSausage(sp1,sp2,r,c) {
  if ( !(pointLineDist(c,sp1,sp2) < r) ) {
    return false;
  }
  double a = dist(sp1,c);  
  double b = dist(sp2,c);
  double l;
  double s;
  if (a>b) {
    l = a;
    s = b;
  } else {
    l = b;
    s = a;
  }
  double segLength = dist(sp1,sp2);
  if ( l < sqrt(segLength*segLength+r*r) ) {
    return true;
  }
  return s < r;
}  

如果发现任何问题,告诉我,我会编辑或撤回。

圆真的是一个坏人:)所以一个好办法是避免真正的圆,如果可以的话。如果你正在为游戏做碰撞检查,你可以进行一些简化,只做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;
}

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