我有一条从a到B的直线和一个半径为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;
}

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

其他回答

奇怪的是,我可以回答,但不能评论…… 我喜欢Multitaskpro的方法,它可以移动所有东西,使圆的中心落在原点上。不幸的是,他的代码中有两个问题。首先在平方根下的部分,你需要去掉双倍的幂。所以不是:

is underRadical = Math.pow((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2));

but:

under Radical = Math.pow(r,2)*(Math.pow(m,2)+1)) - Math.pow(b,2);

在最后的坐标中,他忘记把解移回来。所以不是:

var i1 = {x:t1,y:m*t1+b}

but:

Var i1 = {x:t1+c。x, y: m * t1 + b +陈守惠};

整个函数就变成:

function interceptOnCircle(p1, p2, c, r) {
    //p1 is the first line point
    //p2 is the second line point
    //c is the circle's center
    //r is the circle's radius

    var p3 = {x:p1.x - c.x, y:p1.y - c.y}; //shifted line points
    var p4 = {x:p2.x - c.x, y:p2.y - c.y};

    var m = (p4.y - p3.y) / (p4.x - p3.x); //slope of the line
    var b = p3.y - m * p3.x; //y-intercept of line

    var underRadical = Math.pow(r,2)*Math.pow(m,2) + Math.pow(r,2) - Math.pow(b,2); //the value under the square root sign 

    if (underRadical < 0) {
        //line completely missed
        return false;
    } else {
        var t1 = (-m*b + Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //one of the intercept x's
        var t2 = (-m*b - Math.sqrt(underRadical))/(Math.pow(m,2) + 1); //other intercept's x
        var i1 = {x:t1+c.x, y:m*t1+b+c.y}; //intercept point 1
        var i2 = {x:t2+c.x, y:m*t2+b+c.y}; //intercept point 2
        return [i1, i2];
    }
}

采取

E是射线的起点, L是射线的端点, C是你测试的圆心 R是球面的半径

计算: d = L - E(射线方向矢量,从头到尾) f = E - C(从中心球到射线起点的向量)

然后通过…找到交点。 堵塞: P = E + t * d 这是一个参数方程 Px = Ex + tdx Py = Ey + tdy 成 (x - h)2 + (y - k)2 = r2 (h,k) =圆心。

注意:我们在这里将问题简化为2D,我们得到的解决方案也适用于3D

得到:

Expand x2 - 2xh + h2 + y2 - 2yk + k2 - r2 = 0 Plug x = ex + tdx y = ey + tdy ( ex + tdx )2 - 2( ex + tdx )h + h2 + ( ey + tdy )2 - 2( ey + tdy )k + k2 - r2 = 0 Explode ex2 + 2extdx + t2dx2 - 2exh - 2tdxh + h2 + ey2 + 2eytdy + t2dy2 - 2eyk - 2tdyk + k2 - r2 = 0 Group t2( dx2 + dy2 ) + 2t( exdx + eydy - dxh - dyk ) + ex2 + ey2 - 2exh - 2eyk + h2 + k2 - r2 = 0 Finally, t2( d · d ) + 2t( e · d - d · c ) + e · e - 2( e · c ) + c · c - r2 = 0 Where d is the vector d and · is the dot product. And then, t2( d · d ) + 2t( d · ( e - c ) ) + ( e - c ) · ( e - c ) - r2 = 0 Letting f = e - c t2( d · d ) + 2t( d · f ) + f · f - r2 = 0

所以我们得到: T2 *(d·d) + 2t*(f·d) + (f·f - r2) = 0

求解二次方程:

float a = d.Dot( d ) ;
float b = 2*f.Dot( d ) ;
float c = f.Dot( f ) - r*r ;

float discriminant = b*b-4*a*c;
if( discriminant < 0 )
{
  // no intersection
}
else
{
  // ray didn't totally miss sphere,
  // so there is a solution to
  // the equation.
  
  discriminant = sqrt( discriminant );

  // either solution may be on or off the ray so need to test both
  // t1 is always the smaller value, because BOTH discriminant and
  // a are nonnegative.
  float t1 = (-b - discriminant)/(2*a);
  float t2 = (-b + discriminant)/(2*a);

  // 3x HIT cases:
  //          -o->             --|-->  |            |  --|->
  // Impale(t1 hit,t2 hit), Poke(t1 hit,t2>1), ExitWound(t1<0, t2 hit), 

  // 3x MISS cases:
  //       ->  o                     o ->              | -> |
  // FallShort (t1>1,t2>1), Past (t1<0,t2<0), CompletelyInside(t1<0, t2>1)
  
  if( t1 >= 0 && t1 <= 1 )
  {
    // t1 is the intersection, and it's closer than t2
    // (since t1 uses -b - discriminant)
    // Impale, Poke
    return true ;
  }

  // here t1 didn't intersect so we are either started
  // inside the sphere or completely past it
  if( t2 >= 0 && t2 <= 1 )
  {
    // ExitWound
    return true ;
  }
  
  // no intn: FallShort, Past, CompletelyInside
  return false ;
}

这里是一个用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,而不是两者都测试。

基于@Joe Skeen的python解决方案

def check_line_segment_circle_intersection(line, point, radious):
    """ Checks whether a point intersects with a line defined by two points.

    A `point` is list with two values: [2, 3]

    A `line` is list with two points: [point1, point2]

    """
    line_distance = distance(line[0], line[1])
    distance_start_to_point = distance(line[0], point)
    distance_end_to_point = distance(line[1], point)

    if (distance_start_to_point <= radious or distance_end_to_point <= radious):
        return True

    # angle between line and point with law of cosines
    numerator = (math.pow(distance_start_to_point, 2)
                 + math.pow(line_distance, 2)
                 - math.pow(distance_end_to_point, 2))
    denominator = 2 * distance_start_to_point * line_distance
    ratio = numerator / denominator
    ratio = ratio if ratio <= 1 else 1  # To account for float errors
    ratio = ratio if ratio >= -1 else -1  # To account for float errors
    angle = math.acos(ratio)

    # distance from the point to the line with sin projection
    distance_line_to_point = math.sin(angle) * distance_start_to_point

    if distance_line_to_point <= radious:
        point_projection_in_line = math.cos(angle) * distance_start_to_point
        # Intersection occurs whent the point projection in the line is less
        # than the line distance and positive
        return point_projection_in_line <= line_distance and point_projection_in_line >= 0
    return False

def distance(point1, point2):
    return math.sqrt(
        math.pow(point1[1] - point2[1], 2) +
        math.pow(point1[0] - point2[0], 2)
    )

这是一个Javascript实现。我的方法是首先将线段转换成一条无限的直线,然后找到交点。从那里,我检查是否找到的点在线段上。代码有良好的文档记录,您应该能够跟随。

您可以在这个现场演示中试用代码。 代码是从我的算法仓库里拿的。

// Small epsilon value
var EPS = 0.0000001;

// point (x, y)
function Point(x, y) {
  this.x = x;
  this.y = y;
}

// Circle with center at (x,y) and radius r
function Circle(x, y, r) {
  this.x = x;
  this.y = y;
  this.r = r;
}

// A line segment (x1, y1), (x2, y2)
function LineSegment(x1, y1, x2, y2) {
  var d = Math.sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) );
  if (d < EPS) throw 'A point is not a line segment';
  this.x1 = x1; this.y1 = y1;
  this.x2 = x2; this.y2 = y2;
}

// An infinite line defined as: ax + by = c
function Line(a, b, c) {
  this.a = a; this.b = b; this.c = c;
  // Normalize line for good measure
  if (Math.abs(b) < EPS) {
    c /= a; a = 1; b = 0;
  } else { 
    a = (Math.abs(a) < EPS) ? 0 : a / b;
    c /= b; b = 1; 
  }
}

// Given a line in standard form: ax + by = c and a circle with 
// a center at (x,y) with radius r this method finds the intersection
// of the line and the circle (if any). 
function circleLineIntersection(circle, line) {

  var a = line.a, b = line.b, c = line.c;
  var x = circle.x, y = circle.y, r = circle.r;

  // Solve for the variable x with the formulas: ax + by = c (equation of line)
  // and (x-X)^2 + (y-Y)^2 = r^2 (equation of circle where X,Y are known) and expand to obtain quadratic:
  // (a^2 + b^2)x^2 + (2abY - 2ac + - 2b^2X)x + (b^2X^2 + b^2Y^2 - 2bcY + c^2 - b^2r^2) = 0
  // Then use quadratic formula X = (-b +- sqrt(a^2 - 4ac))/2a to find the 
  // roots of the equation (if they exist) and this will tell us the intersection points

  // In general a quadratic is written as: Ax^2 + Bx + C = 0
  // (a^2 + b^2)x^2 + (2abY - 2ac + - 2b^2X)x + (b^2X^2 + b^2Y^2 - 2bcY + c^2 - b^2r^2) = 0
  var A = a*a + b*b;
  var B = 2*a*b*y - 2*a*c - 2*b*b*x;
  var C = b*b*x*x + b*b*y*y - 2*b*c*y + c*c - b*b*r*r;

  // Use quadratic formula x = (-b +- sqrt(a^2 - 4ac))/2a to find the 
  // roots of the equation (if they exist).

  var D = B*B - 4*A*C;
  var x1,y1,x2,y2;

  // Handle vertical line case with b = 0
  if (Math.abs(b) < EPS) {

    // Line equation is ax + by = c, but b = 0, so x = c/a
    x1 = c/a;

    // No intersection
    if (Math.abs(x-x1) > r) return [];

    // Vertical line is tangent to circle
    if (Math.abs((x1-r)-x) < EPS || Math.abs((x1+r)-x) < EPS)
      return [new Point(x1, y)];

    var dx = Math.abs(x1 - x);
    var dy = Math.sqrt(r*r-dx*dx);

    // Vertical line cuts through circle
    return [
      new Point(x1,y+dy),
      new Point(x1,y-dy)
    ];

  // Line is tangent to circle
  } else if (Math.abs(D) < EPS) {

    x1 = -B/(2*A);
    y1 = (c - a*x1)/b;

    return [new Point(x1,y1)];

  // No intersection
  } else if (D < 0) {

    return [];

  } else {

    D = Math.sqrt(D);

    x1 = (-B+D)/(2*A);
    y1 = (c - a*x1)/b;

    x2 = (-B-D)/(2*A);
    y2 = (c - a*x2)/b;

    return [
      new Point(x1, y1),
      new Point(x2, y2)
    ];

  }

}

// Converts a line segment to a line in general form
function segmentToGeneralForm(x1,y1,x2,y2) {
  var a = y1 - y2;
  var b = x2 - x1;
  var c = x2*y1 - x1*y2;
  return new Line(a,b,c);
}

// Checks if a point 'pt' is inside the rect defined by (x1,y1), (x2,y2)
function pointInRectangle(pt,x1,y1,x2,y2) {
  var x = Math.min(x1,x2), X = Math.max(x1,x2);
  var y = Math.min(y1,y2), Y = Math.max(y1,y2);
  return x - EPS <= pt.x && pt.x <= X + EPS &&
         y - EPS <= pt.y && pt.y <= Y + EPS;
}

// Finds the intersection(s) of a line segment and a circle
function lineSegmentCircleIntersection(segment, circle) {

  var x1 = segment.x1, y1 = segment.y1, x2 = segment.x2, y2 = segment.y2;
  var line = segmentToGeneralForm(x1,y1,x2,y2);
  var pts = circleLineIntersection(circle, line);

  // No intersection
  if (pts.length === 0) return [];

  var pt1 = pts[0];
  var includePt1 = pointInRectangle(pt1,x1,y1,x2,y2);

  // Check for unique intersection
  if (pts.length === 1) {
    if (includePt1) return [pt1];
    return [];
  }

  var pt2 = pts[1];
  var includePt2 = pointInRectangle(pt2,x1,y1,x2,y2);

  // Check for remaining intersections
  if (includePt1 && includePt2) return [pt1, pt2];
  if (includePt1) return [pt1];
  if (includePt2) return [pt2];
  return [];

}