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

user_962155 0
Viewed 84

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.

collision-detection math algorithm javascript
2 Answers

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.

user_55673820

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

  1. 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);
  2. 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;
  3. 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>

user_14002790
Related