此代码是否用于确定圆和线 SEGMENT 相交是否正确？

Question

直线线段和圆是否相交，显然很难找到答案。例如，如果你 google 你会发现 this question 甚至前两个答案似乎都是错误的。

已接受的答案有一条评论说：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。

然后我尝试搜索一个函数来确定线段是否与圆相交，但无济于事。我能找到的最好的是 pseudocode explanation here.

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

我在下面提供了完整的演示复制品，因此您也可以对其进行可视化。

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>

Answer 1

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

直线的点数是((1-t) x1 + t x2, (1-t) y1 + t y2)，所有实数t。让x(t) = (1-t) x1 + t x2 - cx和y(t) = (1-t) y1 + t y2 - cy。当且仅当多项式 x(t)^2 + y(t)^2 - r^2 = 0 具有实根 t1 <= t2 时，线-盘交点为非空。在这种情况下，线盘交集是[t1, t2]中的所有t。线段是[0, 1]中的全部t。两者相交当且仅当 t1 <= 1 和 t2 >= 0.

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

根 t1 和 t2 是真实的当且仅当 b^2 - 4 a c >= 0.
当且仅当 t1 - 1 > 0 和 t2 - 1 > 0 条件 t1 <= 1 为假，当且仅当 (t1 - 1) + (t2 - 1) > 0 和(t1 - 1) (t2 - 1) > 0，相当于-b/a - 2 > 0和c/a + b/a + 1 > 0。由于 a > 0，这简化为 -b > 2 a 和 c + b + a > 0。
当且仅当 t1 < 0 和 t2 < 0 条件 t2 >= 0 为假，而当且仅当 t1 + t2 = -b/a < 0 且t1 t2 = c/a > 0。由于 a > 0，这简化为 b > 0 和 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();

此代码是否用于确定圆和线 SEGMENT 相交是否正确？

Is this code for determining if a circle and line SEGMENT intersects correct?

javascript

math

geometry

collision-detection