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 wrong.
The accepted answer has a comment saying: This seems to compute the intersection of a circle with a line, not a segment Scroll down to the next answer and you'll find another comment saying Isn't this answer in incomplete? It finds whether a circle and line intersect, not a line segment.
I've then tried to search for a function for determining if just a segment intersects a circle, but to no avail. The best I could find is a pseudocode explanation here.
I've tried to adapt his code and while it seems to work, it seems overly verbose and I'm not sure if my implementation is correct. I'm asking whether or not this is correct and if it is, is there indeed no better way of determining this? What is the ideal way of determining if a line segment and circle intersects? Please note, I only need to know if they intersect, not where they intersect.
I've provided a full demo reproduction below so you can also visualize it.
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>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();