这段用于确定圆和线段是否相交的代码正确吗？

显然很难找到一条线是否存在的答案segment和圆相交。例如，如果你用谷歌搜索，你会发现这个问题 https://stackoverflow.com/questions/1073336/circle-line-segment-collision-detection-algorithm甚至最上面的两个答案似乎也是错误的。

接受的答案有一条评论说：This seems to compute the intersection of a circle with a line, not a segment向下滚动到下一个答案，您会发现另一条评论说Isn't this answer in incomplete? It finds whether a circle and line intersect, not a line segment.

然后我尝试寻找一个函数来确定是否只是一个segment与圆相交，但无济于事。我能找到的最好的是伪代码解释在这里 https://stackoverflow.com/a/9053697/962155.

我尝试调整他的代码，虽然它似乎有效，但似乎过于冗长，我不确定我的实现是否正确。我想问这是否正确，如果正确，是否确实没有更好的方法来确定这一点？确定线段和圆是否相交的理想方法是什么？请注意，我只需要知道if它们相交，而不是相交的地方。

我在下面提供了完整的演示复制品，以便您也可以将其可视化。

function lineSegmentIntersectsCircle(x1, y1, x2, y2, cx, cy, r) {
  let deltaX = x2 - x1;
  let deltaY = y2 - y1;

  let mag = Math.sqrt(deltaX * deltaX + deltaY * deltaY);

  let unitX = deltaX / mag;
  let unitY = deltaY / mag;

  let d = (cx - x1) * unitY - (cy - y1) * unitX;

  if (d < -r || d > r) { return false; }

  let x1CXDelta = x1 - cx;
  let y1CYDelta = y1 - cy;

  let x2CXDelta = x2 - cx;
  let y2CYDelta = y2 - cy;

  let pointOneWithinCircle = x1CXDelta * x1CXDelta + y1CYDelta * y1CYDelta < r * r;
  if (pointOneWithinCircle) { return true; }

  let pointTwoWithinCircle = x2CXDelta * x2CXDelta + y2CYDelta * y2CYDelta < r * r;
  if (pointTwoWithinCircle) { return true; }

  let foo = unitX * x1 + unitY * y1;
  let bar = unitX * cx + unitY * cy;
  let baz = unitX * x2 + unitY * y2;

  return (foo < bar && bar < baz) || (baz < bar && bar < foo); 
}

let ctx = document.querySelector("canvas").getContext("2d");

function drawCircle(xCenter, yCenter, radius) {
  ctx.beginPath();
  ctx.arc(xCenter, yCenter, radius, 0, 2 * Math.PI);
  ctx.fill();
}

function drawLine(x1, y1, x2, y2) {
  ctx.beginPath();
  ctx.moveTo(x1, y1);
  ctx.lineTo(x2, y2);
  ctx.stroke();
}

let circleX = 340;
let circleY = 250;
let circleR = 60;

let lineX1 = 50;
let lineY1 = 350;
let lineX2 = 285;
let lineY2 = 250;

draw = () => {
  ctx.fillStyle = "#b2c7ef";
  ctx.fillRect(0, 0, 800, 800); 

  ctx.fillStyle = "#ffffff";

  drawCircle(circleX, circleY, circleR);
  drawLine(lineX1, lineY1, lineX2, lineY2);
}

console.log(lineSegmentIntersectsCircle(lineX1, lineY1, lineX2, lineY2, circleX, circleY, circleR))

draw();

canvas { display: flex; margin: 0 auto; }

<canvas width="400" height="400"></canvas>

我认为（1）计算线盘交点会更简单，它可以是空的、点或线段（2）测试交点是否与线段相交。

直线上的点是((1-t) x1 + t x2, (1-t) y1 + t y2)对于所有真实的t. Let x(t) = (1-t) x1 + t x2 - cx and y(t) = (1-t) y1 + t y2 - cy。线盘交点非空当且仅当多项式x(t)^2 + y(t)^2 - r^2 = 0有真正的根源t1 <= t2。在这种情况下，线盘交点全部为t in [t1, t2]。线段都是t in [0, 1]。两者相交当且仅当t1 <= 1 and t2 >= 0.

计算t1 and t2需要平方根，我们可以避免。让a, b, c是这样的x(t)^2 + y(t)^2 - r^2 = a t^2 + b t + c。我们有t1 + t2 = -b/a and t1 t2 = c/a.

• 根t1 and t2是真实的当且仅当b^2 - 4 a c >= 0.

• 条件t1 <= 1为假当且仅当t1 - 1 > 0 and t2 - 1 > 0，当且仅当(t1 - 1) + (t2 - 1) > 0 and (t1 - 1) (t2 - 1) > 0，这相当于-b/a - 2 > 0 and c/a + b/a + 1 > 0. Since a > 0，这简化为-b > 2 a and c + b + a > 0.

• 条件t2 >= 0为假当且仅当t1 < 0 and t2 < 0，当且仅当t1 + t2 = -b/a < 0 and t1 t2 = c/a > 0. Since a > 0，这简化为b > 0 and c > 0.

在 JavaScript 中实现。

function lineSegmentIntersectsCircleOptimized(x1, y1, x2, y2, cx, cy, r) {
  let x_linear = x2 - x1;
  let x_constant = x1 - cx;
  let y_linear = y2 - y1;
  let y_constant = y1 - cy;
  let a = x_linear * x_linear + y_linear * y_linear;
  let half_b = x_linear * x_constant + y_linear * y_constant;
  let c = x_constant * x_constant + y_constant * y_constant - r * r;
  return (
    half_b * half_b >= a * c &&
    (-half_b <= a || c + half_b + half_b + a <= 0) &&
    (half_b <= 0 || c <= 0)
  );
}

function lineSegmentIntersectsCircle(x1, y1, x2, y2, cx, cy, r) {
  let deltaX = x2 - x1;
  let deltaY = y2 - y1;

  let mag = Math.sqrt(deltaX * deltaX + deltaY * deltaY);

  let unitX = deltaX / mag;
  let unitY = deltaY / mag;

  let d = (cx - x1) * unitY - (cy - y1) * unitX;

  if (d < -r || d > r) {
    return false;
  }

  let x1CXDelta = x1 - cx;
  let y1CYDelta = y1 - cy;

  let x2CXDelta = x2 - cx;
  let y2CYDelta = y2 - cy;

  let pointOneWithinCircle =
    x1CXDelta * x1CXDelta + y1CYDelta * y1CYDelta < r * r;
  if (pointOneWithinCircle) {
    return true;
  }

  let pointTwoWithinCircle =
    x2CXDelta * x2CXDelta + y2CYDelta * y2CYDelta < r * r;
  if (pointTwoWithinCircle) {
    return true;
  }

  let foo = unitX * x1 + unitY * y1;
  let bar = unitX * cx + unitY * cy;
  let baz = unitX * x2 + unitY * y2;

  return (foo < bar && bar < baz) || (baz < bar && bar < foo);
}

function test() {
  for (let i = 0; i < 10000000; i++) {
    let x1 = Math.random();
    let y1 = Math.random();
    let x2 = Math.random();
    let y2 = Math.random();
    let cx = Math.random();
    let cy = Math.random();
    let r = Math.random();
    if (
      lineSegmentIntersectsCircle(x1, y1, x2, y2, cx, cy, r) !=
      lineSegmentIntersectsCircleOptimized(x1, y1, x2, y2, cx, cy, r)
    ) {
      console.log("bad");
      break;
    }
  }
}

test();