Is This Code For Determining If A Circle And Line SEGMENT Intersects Correct?

It's apparently very hard to find the answer to whether a line segment and circle intersect. For example, if you google you'll find this question and even the top two answers seem

Solution 1:

I think it would be a simpler to (1) compute the line-disk intersection, which is either empty, a point, or a line segment (2) test whether the intersection intersects the line segment.

The points of the line are ((1-t) x1 + t x2, (1-t) y1 + t y2) for all real t. Let x(t) = (1-t) x1 + t x2 - cx and y(t) = (1-t) y1 + t y2 - cy. The line-disk intersection is nonempty if and only if the polynomial x(t)^2 + y(t)^2 - r^2 = 0 has real roots t1 <= t2. In this case, the line-disk intersection is all t in [t1, t2]. The line segment is all t in [0, 1]. The two intersect if and only if t1 <= 1 and t2 >= 0.

Computing t1 and t2 requires a square root, which we can avoid. Let a, b, c be such that x(t)^2 + y(t)^2 - r^2 = a t^2 + b t + c. We have t1 + t2 = -b/a and t1 t2 = c/a.

• The roots t1 and t2 are real if and only if b^2 - 4 a c >= 0.

• The condition t1 <= 1 is false if and only if t1 - 1 > 0 and t2 - 1 > 0, which in turn is true if and only if (t1 - 1) + (t2 - 1) > 0 and (t1 - 1) (t2 - 1) > 0, which is equivalent to -b/a - 2 > 0 and c/a + b/a + 1 > 0. Since a > 0, this simplifies to -b > 2 a and c + b + a > 0.

• The condition t2 >= 0 is false if and only if t1 < 0 and t2 < 0, which in turn is true if and only if t1 + t2 = -b/a < 0 and t1 t2 = c/a > 0. Since a > 0, this simplifies to b > 0 and c > 0.

Implementation in 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();