Why does this function that checks if a line intersects a circle sometimes gives false positives?

Question

I found this function on Stackoverflow some time ago and only now am I realizing that it sometimes seems to give false-positives. Here it is:

function lineIntersectsCircle(p1X, p1Y, p2X, p2Y, cX, cY, r) {
  let xDelta = p1X - p2X;
  let yDelta = p1Y - p2Y;

  let distance = Math.sqrt(xDelta * xDelta + yDelta * yDelta)

  let a = (cY - p1Y) * (p2X - p1X);
  let b = (cX - p1X) * (p2Y - p1Y);

  return Math.abs(a - b) / distance <= r;
}

Here's a full code demo reproduction showing the issue here:

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();
}

function lineIntersectsCircle(p1X, p1Y, p2X, p2Y, cX, cY, r) {
  let xDelta = p1X - p2X;
  let yDelta = p1Y - p2Y;

  let distance = Math.sqrt(xDelta * xDelta + yDelta * yDelta)

  let a = (cY - p1Y) * (p2X - p1X);
  let b = (cX - p1X) * (p2Y - p1Y);

  return Math.abs(a - b) / distance <= r;
}

let circleX = 250;
let circleY = 250;
let circleR = 50;

let lineX1 = 50;
let lineY1 = 350;
let lineX2 = 185;
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(lineIntersectsCircle(lineX1, lineY1, lineX2, lineY2, circleX, circleY, circleR))

draw();

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

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

As you can see, the line doesn't intersect the circle, yet it console logs a true statement. Does anyone know why this would be? If this function is incorrect, what is the proper function for only determining if a line and circle intersect? I do not need the intersection points, only whether or not they intersect at all.

Looks like the canvas Y axis is reversed from the expected Y axis of the function. — pilchard, Apr 15 '21 at 20:40
could you explain your intended logic in words perhaps? Perhaps I'm in a stupid mood but I'm struggling to understand what `a` and `b` are supposed to represent, and therefore why the final inequality is supposed to determine if there's an intersection or not. — Robin Zigmond, Apr 15 '21 at 20:40

Thomas Jager · Answer 1 · 2021-04-15T20:48:42.143

1

Mathematically, a line is different from a line segment; a line is infinitely long.

You use the formula for finding the distance between a point (centre of the circle) and a line. While the formula uses a line defined by two points, it is not terminated by those points, so that doesn't apply to a line segment.

If you extend that line segment out, you can see that it intersects with the circle.

edited Apr 15 '21 at 20:48

answered Apr 15 '21 at 20:42

Thomas Jager

4,836
2
16
30

Ah, okay. So I need to find the formula for determining if a line _segment_ intersects with a circle, not just a line. Okay, I'll google around for that I suppose. – Ryan Peschel Apr 15 '21 at 20:43
You may find [this](https://math.stackexchange.com/questions/103556/circle-and-line-segment-intersection) to be of help. (I haven't included it in the main answer because it's just a link.) – Thomas Jager Apr 15 '21 at 20:45
Oh okay so this equation is much easier! That's good. Thanks! – Ryan Peschel Apr 15 '21 at 20:46
There's also an algorithm question with an answer: https://stackoverflow.com/questions/1073336/circle-line-segment-collision-detection-algorithm – Herohtar Apr 15 '21 at 20:53
@Herohtar That question refers to finding the points. I only need to know if there is an intersection at all. Also I'm having a bit of trouble converting Thomas' link answer to actual code. It's more complex than I thought. – Ryan Peschel Apr 15 '21 at 21:04
Huh, I'm looking all over for an answer that works for line _segments_ and I cannot find any. Every code example listed that I've seen so far is riddled with comments saying "this only works for lines, not segments." Okay, then where is the one that works with _segments_? – Ryan Peschel Apr 15 '21 at 21:10
@Herohtar Read one of the latest comments in the accepted answer. It says: `This seems to compute the intersection of a circle with a line, not a segment` The second answer also has a comment saying: `Isn't this answer in incomplete? It finds whether a circle and line intersect, not a line segment` – Ryan Peschel Apr 15 '21 at 21:23
I'm just going to post a separate question – Ryan Peschel Apr 15 '21 at 21:25
The comment on the accepted answer is outdated. The second answer is indeed incomplete. – Herohtar Apr 15 '21 at 21:32
@RyanPeschel I could post one in Python – mikuszefski Apr 16 '21 at 05:59
@mikuszefski don't worry about it there's a solution here https://stackoverflow.com/questions/67116296/is-this-code-for-determining-if-a-circle-and-line-segment-intersects-correct – Ryan Peschel Apr 16 '21 at 06:01

coderLMN · Answer 2 · 2021-04-16T09:32:10.880

Three steps to determine whether a line segment intersects with a circle:

transform the coordinates to make (xCenter, yCenter) of the circle as the zero point, and switch the X,Y coordinates (because the Y axis of the canvas points downward, which makes linear functions incorrect);
find the point nearest to the circle in the (infinite) line, if the point is not inside the line segment, get one of the end points which is closer to the point;
if the point is inside the circle, and the 2 end points are not both inside the circle, there is at least one intersection.

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();
}

function lineIntersectsCircle(p1X, p1Y, p2X, p2Y, cX, cY, r) {
// to calculate the new position based on the new zero point at the circle center, 
//where X, Y coordinates have to be switched because in Canvas Y coordinate increases downwards
  let newp1y = p1X - cX, newp1x = p1Y - cY, newp2y = p2X - cX, newp2x = p2Y - cY; 
// when the 2 end points are all inside the circle, there is no intersection
if((newp1x*newp1x + newp1y*newp1y < r*r) && (newp2x*newp2x + newp2y*newp2y < r*r)) {
    return false;
}
// slope of the line and the slope of the perpendicular line from the circle center
  let slopeL = (newp2y - newp1y) / (newp2x - newp1x), slopeC;   
  if(slopeL != 0){
    slopeC = -1/slopeL;
  }
  else{
    slopeC = 65535;    // for a vertical line, this slope number is big enough
  }
// calculate the nearest point at the straight line from the circle center
  let closeX = (newp1y - slopeL*newp1x)/(slopeC - slopeL);  
  let closeY = closeX * slopeC;

// in this condition, the nearest point is not inside the line segment, so the end point
// which is closer to this point will be picked as the real nearest point to the circle center
  if((closeX - newp1x)*(closeX - newp2x) >=0 && (closeY - newp1y)*(closeY - newp2y) >=0){
    if((closeX - newp1x)*(closeX - newp2x) > 0){ 
        if(Math.abs(closeX - newp1x) > Math.abs(closeX - newp2x)){
              closeX = newp2x;
              closeY = newp2y;
          }
          else{
              closeX = newp1x;
              closeY = newp1y;
          }
       }
       else {
          if(Math.abs(closeY - newp1y) > Math.abs(closeY - newp2y)){
              closeX = newp2x;
              closeY = newp2y;
          }
          else{
              closeX = newp1x;
              closeY = newp1y;
          }
       }
  }
  //check if the picked nearest point is inside the circle
  return (closeX*closeX + closeY*closeY) < r*r;
}

let circleX = 250;
let circleY = 250;
let circleR = 50;

let lineX1 = 50;
let lineY1 = 350;
let lineX2 = 185;
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(lineIntersectsCircle(lineX1, lineY1, lineX2, lineY2, circleX, circleY, circleR))

draw();

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

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

Why does this function that checks if a line intersects a circle sometimes gives false positives?

2 Answers2