logo标签列表

圆与线段相交检测算法？

algorithmmathlinecollision-detectiongeometry
225

我有一条从A到B的线段，以及一个位于C处、半径为R的圆。

图像

如何使用良好的算法检查该线段是否与圆相交？并且在圆的边缘上发生交点的坐标是什么？

5
问题：你在谈论经过A和B的无限直线还是从A到B的有限线段？ - Jason S
2
在这种情况下，它是有限线段。根据线的长度是有限还是无限，"line" 的叫法会不同吗？ - Mizipzor
1
有性能要求吗？它需要是一个快速的方法吗？ - chmike
目前为止，所有我尝试过的算法都没有明显地减慢应用程序的速度。 - Mizipzor
19
@Mizipzor 是的，它们被称为另一个词：线段。如果你只说“线”，那么它暗示着无限长。 - MestreLion
如果你正在进行2D游戏中的碰撞检测，那么你会喜欢看到我的答案。 - xakepp35
29个回答
231

给定：

  1. E 是光线的起点，
  2. L 是光线的终点，
  3. C 是要测试的球体的中心，
  4. 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) = 圆的中心。

注意：这里我们简化了问题为二维，得到的解也适用于三维。

得到：

  1. 展开： x2 - 2xh + h2 + y2 - 2yk + k2 - r2 = 0
  2. 代入： x = ex + tdx
    y = ey + tdy
    ( ex + tdx )2 - 2( ex + tdx )h + h2 + ( ey + tdy )2 - 2( ey + tdy )k + k2 - r2 = 0
  3. 展开并整理： ex2 + 2extdx + t2dx2 - 2exh - 2tdxh + h2 + ey2 + 2eytdy + t2dy2 - 2eyk - 2tdyk + k2 - r2 = 0
  4. 分组： t2( dx2 + dy2 ) + 2t( exdx + eydy - dxh - dyk ) + ex2 + ey2 - 2exh - 2eyk + h2 + k2 - r2 = 0
  5. 最终式子为： t2( d · d ) + 2t( e · d - d · c ) + e · e - 2( e · c ) + c · c - r2 = 0
    其中：d表示向量d，·表示点积。
  6. 化简得： t2( d · d ) + 2t( d · ( e - c ) ) + ( e - c ) · ( e - c ) - r2 = 0
  7. 令 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 ;
}
3
h和k是你相交的圆的中心点。t是线性方程的参数。在代码中，t1和t2是方程的解。t1和t2告诉你“相交发生在射线上的哪个位置”。 - bobobobo
29
t是一个数值，可以通过使用公式 P = E + t * d 中已知的其他变量和值来计算。 - Derek 朕會功夫
3
不确定为什么，但代码似乎不能处理穿刺的情况。当我将if t1 <= 0 && t1 >= -1 && t2 <= 0 && t2 >= -1添加为真条件时，它可以正常工作，但是在有限线的一侧（即圆在“无限”部分时），它也会产生假阳性。我还不理解数学，但是复制/粘贴者要小心。 - Nicolas Mommaerts
1
我刚想到了一种更好的理解最终公式的方法。(P-C)^2等于r^2，因为P在圆上；C+f等于E的定义；E+td等于P的定义；所以C+f+td等于P；所以(f+td)^2等于r^2；所以t^2d^2+t2f*d等于r^2；所以我们得到了二次公式。 - Rialgar
1
@NicolasMommaerts 这是一个非常老的问题，但如果有人遇到了像Nicolas一样的问题，那么问题出在你做的是 f = C - E 而不是 f = E - C。 - Minestrone-Soup
显示剩余14条评论
160

似乎没有人考虑投影，我是不是完全错了？

将向量AC投影到AB上。投影向量AD给出新点D。
如果D和C之间的距离小于等于R，那么它们相交。

就像这样:
Image by SchoolBoy

社区编辑:

对于后来找到此帖子并想知道如何实现此算法的任何人，以下是使用常见的向量操作函数编写的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};
}
10
有许多细节需要考虑：D 是否在 AB 之间？C 垂直距离是否大于半径？所有这些都涉及向量的大小，即平方根。 - ADB
20
好主意，但是你如何计算这两个交点呢？ - Ben
5
@Spider 没关系。一般来说，由于这是球线相交问题的一种变体，Mizipzor的策略完全有效。CD是一个投影，根据定义它是垂直的。 - user719662
3
这是一个老问题，但在这个网站上有一些很好的资源，涉及到这个问题和相关的算法：http://paulbourke.net/geometry/pointlineplane/ - Andrew
5
这个答案不完整吗？它只能判断圆和直线是否相交，而不能判断线段。我认为正确的检查方式应该是像这样子的：(projectionPointInCircle and projectionPointOnLine) or endPointsInCircle 最后一项检查很必要，因为线段可能会穿过圆并在中心之前结束。endPoints指的是线段的起始和结束点。 - unlut
显示剩余5条评论
53
我会使用算法计算点（圆心）与线（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
1
你需要测试 t-dt 和 t+dt。如果 t-dt < 0，则 p1 在圆内。如果 t+dt > 1，则 p2 在圆内。当然，这是在 LEC < R 的情况下成立的。 - chmike
谢谢。我喜欢这个程序的注释，因为没有使用“点积”这个词，因为我的数学有点生疏。然而，t和dt不在0..1之间，所以在将其转换为Python时，我将t除以了LAB**2。我的理解是，第一次除以LAB是将圆的中心投影到线AB上，第二次除以LAB是将其归一化到范围0..1内。此外，dt需要除以LAB，以便它也被归一化。因此，“if (t-dt >=0.0)”表示第一个交点存在，“if (t+dt <= 1.0)”表示第二个交点存在。经过测试，这个方法可行。 - punchcard
2
因为与圆相交的交点在直线上的“距离”t+dt和t-dt处。 t是直线上最靠近圆心的点。 与圆相交的交点与t对称距离。 交点位于“距离”t-dt和t+dt处。 我引用了距离，因为它不是欧几里得距离。 要从t = 0处的A获取欧几里得距离，必须将该值乘以LAB。 - chmike
这段代码计算了线的向量上的交点。你如何确定交点是否发生在端点之间而不是线的外部？ - Matt W
1
@Matt W 你是说“如何确定交点是否发生在线段AB的端点之外”？将t视为沿线的距离度量即可。点A位于t=0，点B位于t=LAB。当两个交点（t1=t-td和t2=t+td）的值都为负数时，交点在该段之外（从该点侧面望去在A点后面）。当t1和t2大于LAB时，它们也在该段之外（这次是在B点后面）。当t1（或t2）在0到LAB之间时，交点t1（或t2）仅在A和B之间发生。 - Marconius
显示剩余9条评论
21

好的，我不会给你提供代码，但既然你已经打上了标签，我想这对你来说并不重要。

首先，你需要得到一条垂直于线的向量。

在 y = ax + c 方程中将会有一个未知变量 (即 c 是未知数)。
为了求解它，需要计算此线通过圆心时的值。

也就是说，
将圆心的位置代入线性方程中，并求解 c 的值。
然后计算原始线和其法线的交点。

这将给出离圆最近的线上点。
计算此点与圆心之间的距离（使用向量的大小）。
如果小于圆的半径，则表示有交点！

2
那其实就是我想要的。我想要理论，而在我看来，谷歌搜索线圆碰撞算法只会出现代码。 - Mizipzor
1
哦，抱歉 - 我正在使用具有梯度和偏移量的直线简单方程（笛卡尔方程）。我假设您将该行存储为这样的方程式 - 在这种情况下，您可以使用梯度的负数作为k。如果您没有像这样存储该行，则可以将k计算为（y2-y1）/（x2-x1）。 - a_m0d
1
我们不假设m为零；我们首先计算梯度（这样线的方程就像y=2x+m一样），然后一旦我们有了梯度，我们可以通过将圆的中心插入y和x来解决m。 - a_m0d
我建议以下另一种方法（带有代码），使用三角形面积来计算圆心到直线的距离。 - chmike
1
+1 非常好的解释！但我认为这假设了一条直线，而不是一条线段。因此，如果该直线上距离圆心最近的点不在点A和点B之间，它仍将被计算在内。 - user377628
显示剩余2条评论
15
另一种方法使用三角形ABC面积公式。交点测试比投影方法更简单、更高效，但要找到交点的坐标需要更多的工作。至少会被推迟到需要它的时候。
计算三角形面积的公式为：面积 = 底边长 × 高 / 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 不同，并且该线段长度不为零，如果在您的应用程序中可能会发生这种情况。
2
我喜欢这种方法的简单性。也许我可以调整一些周围的代码，使其不需要实际的碰撞点本身，我会看看如果我使用A或B而不是计算出来的中间点会发生什么。 - Mizipzor
1
t = Dx*(Cx-Ax) + Dy*(Cy-Ax) 应该改为 t = Dx*(Cx-Ax) + Dy*(Cy-Ay)。 - Stonetip
刚刚编辑过，第一行使用“叉积”计算三角形面积，而不是点积。在此链接的代码证实了这一点：https://dev59.com/tUzSa4cB1Zd3GeqPqNgI - ericsoco
5
注意，这个回答的前半部分是测试与一条直线的相交性，而不是测试与一条线段的相交性（正如问题所问）。 - ericsoco
附上一张图片会更有助于理解。 - WDUK
9
我编写了一个小脚本来测试通过将圆的中心点投影到线条上来进行相交测试。
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
我找到的这个解决方案似乎比其他一些解决方案更容易理解。
以下是需要翻译的内容：

Taking:

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 的位置。

p3 = p1 - c
p4 = p2 - c

顺便提一下，每当我将点之间的分数相减时，我先将x值相减，再将y值相减，然后将它们放入一个新点中，以防有人不知道。
无论如何，现在我要解出由p3和p4确定的直线方程：
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。

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

然后我将它们设为相等：

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

解二次方程（0 = ax^2 + bx + 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，b 和 c。
a = m^2 + 1
b = 2mb
c = b^2 - r^2

因此，我将其代入二次公式：

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

并将值代入，然后尽可能简化：

(-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

这是它将会简化的最远程。最后，将其分离成带有±的方程式:

(-2mb + 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2 or     
(-2mb - 2 * sqrt(r^2 * (m^2 + 1) - b^2))/ 2m^2 + 2

然后将这两个方程的结果直接插入到 mx + b 中的 x 变量中。为了清晰，我写了一些JavaScript代码来展示如何使用：

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((Math.pow(r,2)*(Math.pow(m,2)+1)),2)-Math.pow(b,2)); //the value under the square root sign 

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

我希望这可以帮到你！

附言：如果有人发现任何错误或有任何建议，请留言。我很新，欢迎所有的帮助/建议。

如果可能的话，请附上一些示例值，以便我们可以快速掌握流程。 - Prabindh
2
带有 underRadical 的额外 ')' - byJeevan
这看起来很不错，但我认为你需要将c添加回由interceptOnCircle返回的点。类似于[i1 + c，i2 + c]以撤消第7和第8行上的转换。 - Real John Connor
6
以下是Javascript的实现方法。我的方法是先将线段转换成无限线，然后找到交点。然后检查找到的点是否在线段上。代码有很好的注释，您应该能够跟随代码进行理解。
您可以在此演示页面上尝试运行代码。这段代码来自于我的算法库。 enter image description here 
// 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 [];

}
4

通过将向量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
  }
}

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

你错过了一个情况，因为我们正在讨论一条线段：当线段结束于圆时。 - ADB
@ADB 实际上，我的算法只适用于无限直线，而不是线段。有许多情况它不能处理线段。 - Juozas Kontvainis
原始问题是关于线段，而不是圆线相交，这是一个更容易的问题。 - msumme
4

在这个帖子中，我想补充一些内容... 以下是由pahlevan发布的代码版本，适用于C#/XNA，并进行了一些整理：

    /// <summary>
    /// Intersects a line and a circle.
    /// </summary>
    /// <param name="location">the location of the circle</param>
    /// <param name="radius">the radius of the circle</param>
    /// <param name="lineFrom">the starting point of the line</param>
    /// <param name="lineTo">the ending point of the line</param>
    /// <returns>true if the line and circle intersect each other</returns>
    public static bool IntersectLineCircle(Vector2 location, float radius, Vector2 lineFrom, Vector2 lineTo)
    {
        float ab2, acab, h2;
        Vector2 ac = location - lineFrom;
        Vector2 ab = lineTo - lineFrom;
        Vector2.Dot(ref ab, ref ab, out ab2);
        Vector2.Dot(ref ac, ref ab, out acab);
        float t = acab / ab2;

        if (t < 0)
            t = 0;
        else if (t > 1)
            t = 1;

        Vector2 h = ((ab * t) + lineFrom) - location;
        Vector2.Dot(ref h, ref h, out h2);

        return (h2 <= (radius * radius));
    }
在 C#/XNA 中，您可以使用 Ray.Intersects(BoundingSphere)。 - bobobobo
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接