圆线段碰撞检测算法？

#1 楼

以


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

得到：


展开
x2-2xh + h2 + y2-2yk + k2-r2 = 0

插件
x = ex + tdx
y = ey + tdy
（ex + tdx）2-2（ex + tdx）h + h2 +
（ey + tdy）2-2（ey + tdy）k + k2-r2 = 0

爆炸
ex2 + 2extdx + t2dx2-2exh-2tdxh + h2 +

组
t2（dx2 + dy2）+
2t（exdx + eydy-dxh-dyk）+
ex2 + ey2-
2exh-2eyk + h2 + k2-r2 = 0

最后，
t2（d·d）+ 2t（e·d-d·c）+ e·e-2（e·c）+ c·c-r2 = 0
其中d是向量d，·是点积。

然后，
t2（d·d）+ 2t（d·（e-c） ）+（e-c）·（e-c）-r2 = 0

离开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 ;
}

#2 楼

似乎没有人考虑投影，我在这里完全偏离轨道吗？

将向量AC投影到AB上。投影的矢量AD给出了新点D。
如果D与C之间的距离小于（或等于）R，则我们有一个交点。 br />

#3 楼

我将使用该算法来计算点（圆心）和直线（AB线）之间的距离。然后可以用来确定直线与圆的交点。

我们有点A，B，C。Ax和Ay是A点的x和y分量。 B和C相同。标量R是圆半径。

此算法要求A，B和C是不同的点，并且R不为0。

此处是算法

// compute the euclidean distance between A and B
LAB = sqrt( (Bx-Ax)²+(By-Ay)² )

// compute the direction vector D from A to B
Dx = (Bx-Ax)/LAB
Dy = (By-Ay)/LAB

// the equation of the line AB is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= LAB.

// compute the distance between the points A and E, where
// E is the point of AB closest the circle center (Cx, Cy)
t = Dx*(Cx-Ax) + Dy*(Cy-Ay)    

// compute the coordinates of the point E
Ex = t*Dx+Ax
Ey = t*Dy+Ay

// compute the euclidean distance between E and C
LEC = sqrt((Ex-Cx)²+(Ey-Cy)²)

// test if the line intersects the circle
if( LEC < R )
{
    // compute distance from t to circle intersection point
    dt = sqrt( R² - LEC²)

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

    // compute second intersection point
    Gx = (t+dt)*Dx + Ax
    Gy = (t+dt)*Dy + Ay
}

// else test if the line is tangent to circle
else if( LEC == R )
    // tangent point to circle is E

else
    // line doesn't touch circle

#4 楼

好的，我不会给您代码，但是由于您已经标记了此算法，所以我认为这对您来说并不重要。
首先，您必须获得与线垂直的向量。

在y = ax + c中将有一个未知变量（c将是未知）
要解决此问题，请计算线穿过圆心时的值。

即，将圆心的位置插入到直线方程中，并求解c。然后计算原始线与其法线的交点。

这将为您提供直线上最接近圆的点。
计算该点与圆心之间的距离（使用矢量的大小）。
如果这小于圆的半径-瞧，我们有一个相交点！

#5 楼

另一种方法使用三角形ABC面积公式。相交测试比投影方法更简单，更有效，但是找到相交点的坐标需要做更多的工作。至少会延迟到所需的时间。

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

其中b是基长， h是高度。我们选择AB段作为基准，因此h是从C（圆心）到直线的最短距离。

由于也可以通过矢量点积计算三角形面积，因此可以确定h。
您可以使用此处描述的快速平方根逆运算来优化代码，以获得1 / LAB的近似值。

计算交点并不困难。在这里

// 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 )
{
    ...
}        

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

如果应用程序中可能发生这种情况，则应检查A与B是否不同，并且段长度不为null。

#6 楼

我编写了一个小脚本，通过将圆的中心点投影到线上来测试相交。

vector distVector = centerPoint - projectedPoint;
if(distVector.length() < circle.radius)
{
    double distance = circle.radius - distVector.length();
    vector moveVector = distVector.normalize() * distance;
    circle.move(moveVector);
}

http://jsfiddle.net/ercang/ornh3594/1/

如果需要检查与线段的碰撞，您还需要考虑圆心的起点和终点距离。

vector distVector = centerPoint - startPoint;
if(distVector.length() < circle.radius)
{
    double distance = circle.radius - distVector.length();
    vector moveVector = distVector.normalize() * distance;
    circle.move(moveVector);
}

https://jsfiddle.net/ercang/menp0991/

#7 楼

我发现这个解决方案似乎比其他一些解决方案容易一些。

接：

p1 and p2 as the points for the line, and
c as the center point for the circle and r for the radius

我将求解斜率截距形式的直线方程。但是，我不想以c为点来处理困难的方程，所以我只是将坐标系移到了圆上，以使圆位于0,0处。 />顺便说一句，每当我相互减去点时，我就减去x，然后减去y，并将它们放到新的点，以防万一有人不知道。
< br不管怎样，我现在用p3和p4求解直线方程：

p3 = p1 - c
p4 = p2 - c

好。现在，我需要将这些等式设置为相等。首先，我需要解决x的圆的方程

m = (p4_y - p3_y) / (p4_x - p3) (the underscore is an attempt at subscript)
y = mx + b
y - mx = b (just put in a point for x and y, and insert the m we found)

，然后将它们设置为相等：

x^2 + y^2 = r^2
y^2 = r^2 - x^2
y = sqrt(r^2 - x^2)

并求解二次方程（0 = ax^2 + bx + c）：

mx + b = sqrt(r^2 - x^2)

现在我有了a，b和c。

(mx + b)^2 = r^2 - x^2
(mx)^2 + 2mbx + b^2 = r^2 - x^2
0 = m^2 * x^2 + x^2 + 2mbx + b^2 - r^2
0 = (m^2 + 1) * x^2 + 2mbx + b^2 - r^2

，所以我将其放入二次公式中： >

a = m^2 + 1
b = 2mb
c = b^2 - r^2

这几乎可以简化。最后，用±分离出方程：

(-b ± sqrt(b^2 - 4ac)) / 2a

，然后将这两个方程的结果简单地插入x中的mx + b中。为了清楚起见，我编写了一些JavaScript代码来演示如何使用它：

(-2mb ± sqrt(b^2 - 4ac)) / 2a
(-2mb ± sqrt((-2mb)^2 - 4(m^2 + 1)(b^2 - r^2))) / 2(m^2 + 1)
(-2mb ± sqrt(4m^2 * b^2 - 4(m^2 * b^2 - m^2 * r^2 + b^2 - r^2))) / 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * b^2 - (m^2 * b^2 - m^2 * r^2 + b^2 - r^2))))/ 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * b^2 - m^2 * b^2 + m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2
(-2mb ± sqrt(4 * (m^2 * r^2 - b^2 + r^2)))/ 2m^2 + 2
(-2mb ± sqrt(4) * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(m^2 * r^2 - b^2 + r^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(m^2 * r^2 + r^2 - b^2))/ 2m^2 + 2
(-2mb ± 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2

我希望这会有所帮助！如果有人发现任何错误或有任何建议，请发表评论。我很新，欢迎所有帮助/建议。

#8 楼

通过将矢量AC投影到矢量AB上，可以在最接近圆心的无限线上找到一个点。计算该点与圆心之间的距离。如果大于R，则没有交集。如果距离等于R，则直线是圆的切线，而最接近圆心的点实际上是相交点。如果距离小于R，则存在2个交点。它们位于距圆心最近的点相同的距离处。可以使用勾股定理轻松计算该距离。这是伪代码中的算法：

{
dX = bX - aX;
dY = bY - aY;
if ((dX == 0) && (dY == 0))
  {
  // A and B are the same points, no way to calculate intersection
  return;
  }

dl = (dX * dX + dY * dY);
t = ((cX - aX) * dX + (cY - aY) * dY) / dl;

// point on a line nearest to circle center
nearestX = aX + t * dX;
nearestY = aY + t * dY;

dist = point_dist(nearestX, nearestY, cX, cY);

if (dist == R)
  {
  // line segment touches circle; one intersection point
  iX = nearestX;
  iY = nearestY;

  if (t < 0 || t > 1)
    {
    // intersection point is not actually within line segment
    }
  }
else if (dist < R)
  {
  // two possible intersection points

  dt = sqrt(R * R - dist * dist) / sqrt(dl);

  // intersection point nearest to A
  t1 = t - dt;
  i1X = aX + t1 * dX;
  i1Y = aY + t1 * dY;
  if (t1 < 0 || t1 > 1)
    {
    // intersection point is not actually within line segment
    }

  // intersection point farthest from A
  t2 = t + dt;
  i2X = aX + t2 * dX;
  i2Y = aY + t2 * dY;
  if (t2 < 0 || t2 > 1)
    {
    // intersection point is not actually within line segment
    }
  }
else
  {
  // no intersection
  }
}

编辑：添加了代码以检查找到的相交点是否确实在线段内。

#9 楼

奇怪的是我可以回答，但不能发表评论...
我喜欢Multitaskpro的移动所有东西以使圆心落在原点上的方法。不幸的是，他的代码中存在两个问题。首先，在平方根下，您需要移除双倍功效。所以不是：

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

但是：

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

在最终坐标中，他忘记了将解移回。而不是：

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

但是：

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

然后整个功能变为：

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];
    }
}

#10 楼

您需要在此处进行一些数学运算：

假设A =（Xa，Ya），B =（Xb，Yb）和C =（Xc，Yc）。从A到B的直线上的任何点的坐标（alpha * Xa +（1-alpha）Xb，alphaYa +（1-alpha）* Yb）= P

如果点P的距离为R到C，它必须在圆上。您要解决的是

如果将ABC公式应用于将该方程求解为alpha，然后使用alpha的解计算P的坐标，则将得到相交点（如果存在）。

#11 楼

如果您发现球体中心（由于是3D，我假设您是指球体而不是圆形）与直线之间的距离，请检查该距离是否小于将完成此操作的半径。

碰撞点显然是线与球之间的最近点（当您计算球与线之间的距离时将计算该点）

点与线之间的距离：http：//mathworld.wolfram.com/Point-LineDistance3-Dimensional.html

#12 楼

' VB.NET - Code

Function CheckLineSegmentCircleIntersection(x1 As Double, y1 As Double, x2 As Double, y2 As Double, xc As Double, yc As Double, r As Double) As Boolean
    Static xd As Double = 0.0F
    Static yd As Double = 0.0F
    Static t As Double = 0.0F
    Static d As Double = 0.0F
    Static dx_2_1 As Double = 0.0F
    Static dy_2_1 As Double = 0.0F

    dx_2_1 = x2 - x1
    dy_2_1 = y2 - y1

    t = ((yc - y1) * dy_2_1 + (xc - x1) * dx_2_1) / (dy_2_1 * dy_2_1 + dx_2_1 * dx_2_1)

    If 0 <= t And t <= 1 Then
        xd = x1 + t * dx_2_1
        yd = y1 + t * dy_2_1

        d = Math.Sqrt((xd - xc) * (xd - xc) + (yd - yc) * (yd - yc))
        Return d <= r
    Else
        d = Math.Sqrt((xc - x1) * (xc - x1) + (yc - y1) * (yc - y1))
        If d <= r Then
            Return True
        Else
            d = Math.Sqrt((xc - x2) * (xc - x2) + (yc - y2) * (yc - y2))
            If d <= r Then
                Return True
            Else
                Return False
            End If
        End If
    End If
End Function

#13 楼

这是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 [];

}
 

#14 楼

在这篇文章中，将通过检查圆心与线段上的点之间的距离（Ipoint）来检查圆线碰撞，线段上的点代表法线N（图2）从圆心到线段之间的交点。

（https://i.stack.imgur.com/3o6do.png）

在图1上显示了一个圆和一条线，矢量A点到线起点，向量B指向直线终点，向量C指向圆心。现在我们必须找到向量E（从线起点到圆心）和向量D（从线起点到线终点），该计算如图1所示。

（https：// i .stack.imgur.com / 7098a.png）

在图2中，我们可以看到向量E通过向量E和单位向量D的“点积”投影到向量D上乘积是标量Xp，代表向量N与矢量D的线起点和交点（Ipoint）之间的距离。
下一个矢量X是通过将单位矢量D与标量Xp相乘而得出的。 />现在，我们需要找到向量Z（向量到Ipoint），它很容易将向量A（向量的起始点）和向量X进行简单的向量相加。接下来，我们需要处理特殊情况，我们必须检查的是线段上的Ipoint ，如果不是必须找出它是它的左边还是右边，我们将使用最接近的向量来确定最接近圆的点。

（https://i.stack.imgur.com/p9WIr.png）

当投影Xp为负时Ipoint位于线段的左边，矢量最接近的点相等到线起点的向量，当投影Xp大于矢量D的大小，则Ipoint在线段的右边，则最接近的向量等于线终点的向量，在任何其他情况下，最接近的向量等于向量Z。 >
现在，当我们有最接近的向量时，我们需要找到从圆心到Ipoint的向量（距离向量），这很简单，我们只需要从中心向量中减去最近的向量即可。接下来，只需检查向量dist的大小是否小于圆半径，然后如果它们没有碰撞就发生碰撞。

（https://i.stack.imgur.com/QJ63q。最后，我们可以返回一些值来解决碰撞，最简单的方法是返回碰撞的重叠部分（从向量dist量中减去半径）并返回碰撞轴（其向量D）。如果需要，交点是向量Z。

#15 楼

如果直线的坐标为Ax，Ay和Bx，By，圆心为Cx，Cy，则直线公式为：

x = Ax * t + Bx *（1-t）

y = Ay * t + *（1-t）

其中0 <= t <= 1

圆为

（Cx-x）^ 2 +（Cy-y）^ 2 = R ^ 2

如果将直线的x和y公式替换为圆形公式，则得到二阶t的等式及其解是交点（如果有）。如果您得到的t小于0或大于1，则它不是解决方案，但表明该线“指向”圆的方向。

#16 楼

只是此线程的一个补充...
下面是pahlevan发布的代码的一个版本，但对于C＃/ XNA并进行了整理：

#17 楼

我已经按照chmike

+ (NSArray *)intersectionPointsOfCircleWithCenter:(CGPoint)center withRadius:(float)radius toLinePoint1:(CGPoint)p1 andLinePoint2:(CGPoint)p2
{
    NSMutableArray *intersectionPoints = [NSMutableArray array];

    float Ax = p1.x;
    float Ay = p1.y;
    float Bx = p2.x;
    float By = p2.y;
    float Cx = center.x;
    float Cy = center.y;
    float R = radius;


    // compute the euclidean distance between A and B
    float LAB = sqrt( pow(Bx-Ax, 2)+pow(By-Ay, 2) );

    // compute the direction vector D from A to B
    float Dx = (Bx-Ax)/LAB;
    float Dy = (By-Ay)/LAB;

    // Now the line equation is x = Dx*t + Ax, y = Dy*t + Ay with 0 <= t <= 1.

    // compute the value t of the closest point to the circle center (Cx, Cy)
    float t = Dx*(Cx-Ax) + Dy*(Cy-Ay);

    // This is the projection of C on the line from A to B.

    // compute the coordinates of the point E on line and closest to C
    float Ex = t*Dx+Ax;
    float Ey = t*Dy+Ay;

    // compute the euclidean distance from E to C
    float LEC = sqrt( pow(Ex-Cx, 2)+ pow(Ey-Cy, 2) );

    // test if the line intersects the circle
    if( LEC < R )
    {
        // compute distance from t to circle intersection point
        float dt = sqrt( pow(R, 2) - pow(LEC,2) );

        // compute first intersection point
        float Fx = (t-dt)*Dx + Ax;
        float Fy = (t-dt)*Dy + Ay;

        // compute second intersection point
        float Gx = (t+dt)*Dx + Ax;
        float Gy = (t+dt)*Dy + Ay;

        [intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Fx, Fy)]];
        [intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Gx, Gy)]];
    }

    // else test if the line is tangent to circle
    else if( LEC == R ) {
        // tangent point to circle is E
        [intersectionPoints addObject:[NSValue valueWithCGPoint:CGPointMake(Ex, Ey)]];
    }
    else {
        // line doesn't touch circle
    }

    return intersectionPoints;
}

给出的答案为iOS创建了此功能

#18 楼

c＃中的另一个（部分Circle类）。
经过测试，像魅力一样。

public class Circle : IEquatable<Circle>
{
    // ******************************************************************
    // The center of a circle
    private Point _center;
    // The radius of a circle
    private double _radius;

   // ******************************************************************
    /// <summary>
    /// Find all intersections (0, 1, 2) of the circle with a line defined by its 2 points.
    /// Using: http://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle
    /// Note: p is the Center.X and q is Center.Y
    /// </summary>
    /// <param name="linePoint1"></param>
    /// <param name="linePoint2"></param>
    /// <returns></returns>
    public List<Point> GetIntersections(Point linePoint1, Point linePoint2)
    {
        List<Point> intersections = new List<Point>();

        double dx = linePoint2.X - linePoint1.X;

        if (dx.AboutEquals(0)) // Straight vertical line
        {
            if (linePoint1.X.AboutEquals(Center.X - Radius) || linePoint1.X.AboutEquals(Center.X + Radius))
            {
                Point pt = new Point(linePoint1.X, Center.Y);
                intersections.Add(pt);
            }
            else if (linePoint1.X > Center.X - Radius && linePoint1.X < Center.X + Radius)
            {
                double x = linePoint1.X - Center.X;

                Point pt = new Point(linePoint1.X, Center.Y + Math.Sqrt(Radius * Radius - (x * x)));
                intersections.Add(pt);

                pt = new Point(linePoint1.X, Center.Y - Math.Sqrt(Radius * Radius - (x * x)));
                intersections.Add(pt);
            }

            return intersections;
        }

        // Line function (y = mx + b)
        double dy = linePoint2.Y - linePoint1.Y;
        double m = dy / dx;
        double b = linePoint1.Y - m * linePoint1.X;

        double A = m * m + 1;
        double B = 2 * (m * b - m * _center.Y - Center.X);
        double C = Center.X * Center.X + Center.Y * Center.Y - Radius * Radius - 2 * b * Center.Y + b * b;

        double discriminant = B * B - 4 * A * C;

        if (discriminant < 0)
        {
            return intersections; // there is no intersections
        }

        if (discriminant.AboutEquals(0)) // Tangeante (touch on 1 point only)
        {
            double x = -B / (2 * A);
            double y = m * x + b;

            intersections.Add(new Point(x, y));
        }
        else // Secant (touch on 2 points)
        {
            double x = (-B + Math.Sqrt(discriminant)) / (2 * A);
            double y = m * x + b;
            intersections.Add(new Point(x, y));

            x = (-B - Math.Sqrt(discriminant)) / (2 * A);
            y = m * x + b;
            intersections.Add(new Point(x, y));
        }

        return intersections;
    }

    // ******************************************************************
    // Get the center
    [XmlElement("Center")]
    public Point Center
    {
        get { return _center; }
        set
        {
            _center = value;
        }
    }

    // ******************************************************************
    // Get the radius
    [XmlElement]
    public double Radius
    {
        get { return _radius; }
        set { _radius = value; }
    }

    //// ******************************************************************
    //[XmlArrayItemAttribute("DoublePoint")]
    //public List<Point> Coordinates
    //{
    //    get { return _coordinates; }
    //}

    // ******************************************************************
    // Construct a circle without any specification
    public Circle()
    {
        _center.X = 0;
        _center.Y = 0;
        _radius = 0;
    }

    // ******************************************************************
    // Construct a circle without any specification
    public Circle(double radius)
    {
        _center.X = 0;
        _center.Y = 0;
        _radius = radius;
    }

    // ******************************************************************
    // Construct a circle with the specified circle
    public Circle(Circle circle)
    {
        _center = circle._center;
        _radius = circle._radius;
    }

    // ******************************************************************
    // Construct a circle with the specified center and radius
    public Circle(Point center, double radius)
    {
        _center = center;
        _radius = radius;
    }

    // ******************************************************************
    // Construct a circle based on one point
    public Circle(Point center)
    {
        _center = center;
        _radius = 0;
    }

    // ******************************************************************
    // Construct a circle based on two points
    public Circle(Point p1, Point p2)
    {
        Circle2Points(p1, p2);
    }

必需： br />

#19 楼

圈子真的是个坏人:)因此，一个好的方法是避免真正的圈子。如果您要进行游戏的碰撞检查，则可以进行一些简化，只有3个点积，并进行一些比较。

我将其称为“胖点”或“瘦圈”。它是一种椭圆，在平行于线段的方向上半径为零。但在垂直于线段的方向上具有完整半径

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

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

其次，hvec2f中的索引h表示向量必须支持水平操作，例如dot（）/ det（）。这意味着其组件将放置在单独的xmm寄存器中，以避免混洗/添加/添加。接下来，我们将为2D游戏提供性能最强的最简单碰撞检测版本：我将其用于神经网络驱动的赛车碰撞检测，以处理数百万个迭代步骤。

#20 楼

我知道自从该线程打开以来已经有一段时间了。从chmike给出的答案到Aqib Mumtaz的改进。他们给出了很好的答案，但仅适用于无限行，如Aqib所说。因此，我添加了一些比较来了解线段是否接触到圆，因此我用Python编写了它。

def LineIntersectCircle(c, r, p1, p2):
    #p1 is the first line point
    #p2 is the second line point
    #c is the circle's center
    #r is the circle's radius

    p3 = [p1[0]-c[0], p1[1]-c[1]]
    p4 = [p2[0]-c[0], p2[1]-c[1]]

    m = (p4[1] - p3[1]) / (p4[0] - p3[0])
    b = p3[1] - m * p3[0]

    underRadical = math.pow(r,2)*math.pow(m,2) + math.pow(r,2) - math.pow(b,2)

    if (underRadical < 0):
        print("NOT")
    else:
        t1 = (-2*m*b+2*math.sqrt(underRadical)) / (2 * math.pow(m,2) + 2)
        t2 = (-2*m*b-2*math.sqrt(underRadical)) / (2 * math.pow(m,2) + 2)
        i1 = [t1+c[0], m * t1 + b + c[1]]
        i2 = [t2+c[0], m * t2 + b + c[1]]

        if p1[0] > p2[0]:                                           #Si el punto 1 es mayor al 2 en X
            if (i1[0] < p1[0]) and (i1[0] > p2[0]):                 #Si el punto iX esta entre 2 y 1 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i1[1] < p1[1]) and (i1[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i1[1] > p1[1]) and (i1[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

        if p1[0] < p2[0]:                                           #Si el punto 2 es mayor al 1 en X
            if (i1[0] > p1[0]) and (i1[0] < p2[0]):                 #Si el punto iX esta entre 1 y 2 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i1[1] < p1[1]) and (i1[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i1[1] > p1[1]) and (i1[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

        if p1[0] > p2[0]:                                           #Si el punto 1 es mayor al 2 en X
            if (i2[0] < p1[0]) and (i2[0] > p2[0]):                 #Si el punto iX esta entre 2 y 1 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i2[1] < p1[1]) and (i2[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i2[1] > p1[1]) and (i2[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

        if p1[0] < p2[0]:                                           #Si el punto 2 es mayor al 1 en X
            if (i2[0] > p1[0]) and (i2[0] < p2[0]):                 #Si el punto iX esta entre 1 y 2 en X
                if p1[1] > p2[1]:                                   #Si el punto 1 es mayor al 2 en Y
                    if (i2[1] < p1[1]) and (i2[1] > p2[1]):         #Si el punto iy esta entre 2 y 1
                        print("Intersection")
                if p1[1] < p2[1]:                                   #Si el punto 2 es mayo al 2 en Y
                    if (i2[1] > p1[1]) and (i2[1] < p2[1]):         #Si el punto iy esta entre 1 y 2
                        print("Intersection")

#21 楼

此Java函数返回DVec2对象。它需要DVec2作为圆的中心，圆的半径和直线。

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;
}

#22 楼

这是JavaScript的好解决方案（包含所有必需的数学和实时插图）
https://bl.ocks.org/milkbread/11000965

尽管该解决方案中的is_on函数需要修改：

 function is_on(a, b, c) {
    return Math.abs(distance(a,c) + distance(c,b) - distance(a,b))<0.000001;
} 

#23 楼

这是我在TypeScript中的解决方案，遵循@Mizipzor建议的想法（使用投影）：

 /**
 * Determines whether a line segment defined by a start and end point intersects with a sphere defined by a center point and a radius
 * @param a the start point of the line segment
 * @param b the end point of the line segment
 * @param c the center point of the sphere
 * @param r the radius of the sphere
 */
export function lineSphereIntersects(
  a: IPoint,
  b: IPoint,
  c: IPoint,
  r: number
): boolean {
  // find the three sides of the triangle formed by the three points
  const ab: number = distance(a, b);
  const ac: number = distance(a, c);
  const bc: number = distance(b, c);

  // check to see if either ends of the line segment are inside of the sphere
  if (ac < r || bc < r) {
    return true;
  }

  // find the angle between the line segment and the center of the sphere
  const numerator: number = Math.pow(ac, 2) + Math.pow(ab, 2) - Math.pow(bc, 2);
  const denominator: number = 2 * ac * ab;
  const cab: number = Math.acos(numerator / denominator);

  // find the distance from the center of the sphere and the line segment
  const cd: number = Math.sin(cab) * ac;

  // if the radius is at least as long as the distance between the center and the line
  if (r >= cd) {
    // find the distance between the line start and the point on the line closest to
    // the center of the sphere
    const ad: number = Math.cos(cab) * ac;
    // intersection occurs when the point on the line closest to the sphere center is
    // no further away than the end of the line
    return ad <= ab;
  }
  return false;
}

export function distance(a: IPoint, b: IPoint): number {
  return Math.sqrt(
    Math.pow(b.z - a.z, 2) + Math.pow(b.y - a.y, 2) + Math.pow(b.x - a.x, 2)
  );
}

export interface IPoint {
  x: number;
  y: number;
  z: number;
}
 

#24 楼

也许还有另一种方法可以使用坐标系的旋转来解决此问题。
通常，如果一个段是水平或垂直的，这意味着平行于x或y轴，则相交点很容易求解，因为我们已经知道相交的一个坐标（如果有）。其余的显然是使用圆的方程式找到另一个坐标。
受这个想法的启发，我们可以应用坐标系旋转以使一个轴的方向与线段的方向一致。
以圆x^2+y^2=1和线段为例在xy系统中具有P1（-1.5,0.5）和P2（-0.5，-0.5）的P1-P2。下面的方程式提醒您旋转的原理，其中theta是逆时针的角度，x'-y'是旋转后的系统：

x'= x * cos（θ）+ y * sin（theta）
y'=-x * sin（theta）+ y * cos（theta）

反之

x = x'* cos（ theta）-y'* sin（theta）
y = x'* sin（theta）+ y'* cos（theta）

考虑线段P1-P2方向（相对于45° -x），我们可以取theta=45°。在xy系统中将旋转的第二个等式转化为圆方程：x^2+y^2=1，经过简单的操作，我们在x'-y'系统中得到了“相同”方程：x'^2+y'^2=1。第一个旋转方程=> P1（-sqrt（2）/ 2，sqrt（2）），P2（-sqrt（2）/ 2，0）。
设交点为P。 '-y'Px = -sqrt（2）/ 2。使用新的圆方程，我们得到Py = + sqrt（2）/ 2。将P转换为原始的x-y系统，我们最终得到P（-1,0）。
要以数字方式实现此功能，我们首先要查看段的方向：水平，垂直或不垂直。如果它属于前两种情况，就像我说的那样简单。如果是最后一种情况，请应用上面的算法。
要判断是否有交点，我们可以将解与端点坐标进行比较，以查看它们之间是否有根。

我相信只要有方程式，该方法也可以应用于其他曲线。唯一的缺点是我们应该在x'-y'系统中为另一个坐标求解方程，这可能很困难。

#25 楼

这是用golang编写的解决方案。该方法与此处发布的其他一些答案类似，但并不完全相同。它易于实现，并且已经过测试。步骤如下：


平移坐标，使圆位于原点。
将线段表示为t的参数化函数，用于x和y坐标。如果t为0，则函数的值为端点的一个端点；如果t为1，则函数的值为另一个端点。生成x，y坐标，其距原点的距离等于圆的半径。
抛出t小于0或> 1（对于开放段为<= 0或> = 1的解）。这些点不包含在线段中。
转换回原始坐标。 （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
}

这里是测试的输出： >
最后，仅通过测试t> 0或t <1而不是两者都可以，该方法很容易扩展到射线从一个点开始穿过另一点并延伸到无穷远的情况。 >

#26 楼

我只需要那个，所以我想出了这个解决方案。语言是maxscript，但应轻松翻译成其他任何语言。
sideA，sideB和CircleRadius是标量，其余变量为[x，y，z]。我假设z = 0可以在XY平面上求解

fn projectPoint p1 p2 p3 = --project  p1 perpendicular to the line p2-p3
(
    local v= normalize (p3-p2)
    local p= (p1-p2)
    p2+((dot v p)*v)
)
fn findIntersectionLineCircle CircleCenter CircleRadius LineP1 LineP2=
(
    pp=projectPoint CircleCenter LineP1 LineP2
    sideA=distance pp CircleCenter
    --use pythagoras to solve the third side
    sideB=sqrt(CircleRadius^2-sideA^2) -- this will return NaN if they don't intersect
    IntersectV=normalize (pp-CircleCenter)
    perpV=[IntersectV.y,-IntersectV.x,IntersectV.z]
    --project the point to both sides to find the solutions
    solution1=pp+(sideB*perpV)
    solution2=pp-(sideB*perpV)
    return #(solution1,solution2)
)

#27 楼

基于@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)
    )

#28 楼

另一种解决方案，首先考虑您不关心碰撞位置的情况。请注意，此特定功能是在假设xB和yB为矢量输入的情况下构建的，但如果不是这种情况，则可以轻松进行修改。变量名称是在函数的开始处定义的。如果需要碰撞的位置，则可以使用此站点上详述的方法，并将其中一个代理的速度设置为零。这种方法也适用于矢量输入：http://twobitcoder.blogspot.com/2010/04/circle-collision-detection.html