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) {
  letx_linear= x2 - x1;
  letx_constant= x1 - cx;
  lety_linear= y2 - y1;
  lety_constant= y1 - cy;
  leta= x_linear * x_linear + y_linear * y_linear;
  lethalf_b= x_linear * x_constant + y_linear * y_constant;
  letc= 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) {
  letdeltaX= x2 - x1;
  letdeltaY= y2 - y1;

  letmag= Math.sqrt(deltaX * deltaX + deltaY * deltaY);

  letunitX= deltaX / mag;
  letunitY= deltaY / mag;

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

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

  letx1CXDelta= x1 - cx;
  lety1CYDelta= y1 - cy;

  letx2CXDelta= x2 - cx;
  lety2CYDelta= y2 - cy;

  letpointOneWithinCircle=
    x1CXDelta * x1CXDelta + y1CYDelta * y1CYDelta < r * r;
  if (pointOneWithinCircle) {
    returntrue;
  }

  letpointTwoWithinCircle=
    x2CXDelta * x2CXDelta + y2CYDelta * y2CYDelta < r * r;
  if (pointTwoWithinCircle) {
    returntrue;
  }

  letfoo= unitX * x1 + unitY * y1;
  letbar= unitX * cx + unitY * cy;
  letbaz= unitX * x2 + unitY * y2;

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

function test() {
  for (leti=0; i < 10000000; i++) {
    letx1= Math.random();
    lety1= Math.random();
    letx2= Math.random();
    lety2= Math.random();
    letcx= Math.random();
    letcy= Math.random();
    letr= Math.random();
    if (
      lineSegmentIntersectsCircle(x1, y1, x2, y2, cx, cy, r) !=
      lineSegmentIntersectsCircleOptimized(x1, y1, x2, y2, cx, cy, r)
    ) {
      console.log("bad");
      break;
    }
  }
}

test();