How to check if a line is intersecting with a circle in JavaScript?

CharlesMasgalas
May 14, 2023
227 views
1 vote
2 Answers

I’m creating a library so it’s easier for me to create HTML5 canvas games. I’m currently working on the collision detection. This is the code I wrote for line/circle collisions is below. object1 is an object containing the circle’s x, y, and radius. object2 is an object containing both points of a line segment.

const point1 = object2.point1;
const point2 = object2.point2;
        
let newPoint1X = point1.x - object1.x;
let newPoint1Y = point1.y - object1.y;
let newPoint2X = point2.x - object1.x;
let newPoint2Y = point2.y - object1.y;

let lineSlope = (newPoint2Y - newPoint1Y) / (newPoint2X - newPoint1X);
let circleSlope;
        
if (lineSlope != 0) circleSlope = lineSlope / -1;
else circleSlope = 65535;
        
let closestX = (newPoint1Y - lineSlope * newPoint1X) / (circleSlope - lineSlope);  
let closestY = closestX * circleSlope;

if ((closestX - newPoint1X) * (closestX - newPoint2X) >= 0 && (closestY - newPoint1Y) * (closestY - newPoint2Y) >= 0) {
    if ((closestX - newPoint1X) * (closestX - newPoint2X) > 0) { 
        if (Math.abs(closestX - newPoint1X) > Math.abs(closestX - newPoint2X)) {
            closestX = newPoint2X;
            closestY = newPoint2Y;
        }
        else {
            closestX = newPoint1X;
            closestY = newPoint1Y;
        }
    }
    else {
        if (Math.abs(closestY - newPoint1Y) > Math.abs(closestY - newPoint2Y)) {
            closestX = newPoint2X;
            closestY = newPoint2Y;
        }
        else {
            closestX = newPoint1X;
            closestY = newPoint1Y;
        }
    }
}

return closestX * closestX + closestY * closestY < object1.radius * object1.radius;

Here is an example of object1 and object2:

let object1 = {
    type: "circle",
    x: 100,
    y: 100,
    radius: 50,
    color: "#90fcff"
}
let object2 = {
    type: "line",
    point1: {
        x: 30,
        y: 20
    },
    point2: {
        x: 360,
        y: 310
    },
    color: "#000000",
    lineWidth: 1
}

I tested this code, and it doesn’t detect intersections at the right points. Any help with this?

Answers

I would suggest writing separate functions for the basic vector operations, like adding them, getting their size, performing a dot product, …etc.

You could use the Vector formulation of how to get the point on a given line that is closest to another point (the center of your circle).

This also allows to know how far that point is from one end of the line segment and whether that point is on the segment or outside of it.

With that information you can then determine whether the segment and the circle collide. They collide when either:

One of the segment’s endpoints is within the circle;
The closest point on the segment is really ON the segment and is within the circle.

Here is an interactive OOP implementation: move the mouse to change one endpoint of a segment; the circle’s interior color will reflect whether there is a collision or not:

class Vector {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }
    // Basic methods for vectors:
    sub(other)  { return new Vector(this.x - other.x, this.y - other.y) }
    add(other)  { return new Vector(this.x + other.x, this.y + other.y) }
    mul(scalar) { return new Vector(this.x * scalar,  this.y * scalar)  }
    norm()      { return this.mul(1/this.size())   }
    size()      { return Math.sqrt(this.dot(this)) }
    dot(other)  { return this.x * other.x + this.y * other.y }
}

class Segment {
    constructor(a, b) {
        this.a = a;
        this.b = b;
    }
    sub(vector) {
        return new Segment(this.a.sub(vector), this.b.sub(vector));
    }
    closestPointToOrigin() {
        const vector = this.b.sub(this.a);
        const size = vector.size();
        const n = vector.norm();
        const distanceClosestFromA = -this.a.dot(n);
        // Check if closest point lies ON the segment
        if (distanceClosestFromA < 0 || distanceClosestFromA > size) return null; 
        return this.a.add(n.mul(distanceClosestFromA));
    }
    closestPointTo(point) {
        return this.sub(point).closestPointToOrigin()?.add(point);
    }
}

class Circle {
    constructor(center, radius) {
        this.center = center;
        this.radius = radius;
    }
    contains(point) {
        return point && this.center.sub(point).size() <= this.radius;
    }
    // Main algorithm:
    collidesWithSegment(segment) {
        return (this.contains(segment.a) 
             || this.contains(segment.b)
             || this.contains(segment.closestPointTo(this.center)));
    }
}

// I/O

class Output {
    constructor(canvas, onMove) {
        this.ctx = canvas.getContext("2d");
        this.ctx.fillStyle = "yellow";
        canvas.addEventListener("mousemove", e => {
            const current = new Vector(e.clientX - canvas.offsetLeft,
                                       e.clientY - canvas.offsetTop);
            onMove(this, current);
        });
    }
    
    drawCircle(circle, fillIt) {
        this.ctx.beginPath();
        this.ctx.arc(circle.center.x, circle.center.y, circle.radius, 0, 2 * Math.PI);
        if (fillIt) this.ctx.fill();
        this.ctx.stroke();
    } 

    drawSegment(segment) {
        this.ctx.beginPath();
        this.ctx.moveTo(segment.a.x, segment.a.y);
        this.ctx.lineTo(segment.b.x, segment.b.y);
        this.ctx.stroke();
    }

    clear() {
        this.ctx.clearRect(0, 0, this.ctx.canvas.width, this.ctx.canvas.height); 
    }

    draw(circle, segment, isColliding) {
        this.clear();
        this.drawCircle(circle, isColliding);
        this.drawSegment(segment);
    }
}

// Refresh is called on each mouse move on the canvas:
function refresh(output, current) {
    const circle = new Circle(new Vector(100, 50), 30);
    const fixed = new Vector(160, 70);
    const segment = new Segment(fixed, current ?? fixed);
    // Determine whether circle collides with segment:
    const isColliding = circle.collidesWithSegment(segment);
    output.draw(circle, segment, isColliding);
}

const output = new Output(document.querySelector("canvas"), refresh);
refresh(output);

<canvas width=600 height=170></canvas>

The given answer can be improved.

Avoid the square root

In the example below the function rayInterceptsCircle returns true or false depending on the intercept of a line segment (ray) and circle by using the distance from the line segment to the circle center.

This is similar to the existing answer however it avoids the need to calculate a expensive square root

On circle perimeter

The function rayDist2Circle returns the distance along the line to the point where it intersects the circle, if there is no intercept then the distance is returned as Infinity. It does require up to 2 square roots.

If you have many circles that you must test the line against this function can find the first circle the line intercepts by finding the minimum distance

Demo

Use mouse to move line segment endpoint. If line intercepts circle it is rendered in red to the point of intercept.

const ctx = canvas.getContext("2d");
const TAU = Math.PI * 2;
requestAnimationFrame(renderLoop);
var W = canvas.width, H = canvas.height;


const Point = (x, y) => ({x, y}); 
const Ray = (p1, p2) => ({p1, p2}); 
const Circle = (p, radius) => ({x: p.x, y: p.y, radius});

function drawRayLeng(ray, len) {
  ctx.beginPath();
  ctx.lineTo(ray.p1.x, ray.p1.y);
  if (len < Infinity) {
    const dx = ray.p2.x - ray.p1.x;
    const dy = ray.p2.y - ray.p1.y;
    const scale = len / Math.hypot(dx, dy);
    ctx.lineTo(ray.p1.x + dx * scale , ray.p1.y + dy  * scale);
  } else {
    ctx.lineTo(ray.p2.x, ray.p2.y);
  }
  ctx.stroke();
}
function drawRay(ray) {
  ctx.beginPath();
  ctx.lineTo(ray.p1.x, ray.p1.y);
  ctx.lineTo(ray.p2.x, ray.p2.y);
  ctx.stroke();
}
function drawCircle(circle) {
  ctx.beginPath();
  ctx.arc(circle.x, circle.y, circle.radius, 0, TAU);
  ctx.stroke();
}
function rayInterceptsCircle(ray, circle) {    
    const dx = ray.p2.x - ray.p1.x;
    const dy = ray.p2.y - ray.p1.y;
    const u = Math.min(1, Math.max(0, ((circle.x - ray.p1.x) * dx + (circle.y - ray.p1.y) * dy) / (dy * dy + dx * dx)));
    const nx = ray.p1.x + dx * u - circle.x;
    const ny = ray.p1.y + dy * u - circle.y;    
    return nx * nx + ny * ny < circle.radius * circle.radius;
}
function rayDist2Circle(ray, circle) {
    const dx = ray.p2.x - ray.p1.x;
    const dy = ray.p2.y - ray.p1.y;
    const vcx = ray.p1.x - circle.x; 
    const vcy = ray.p1.y - circle.y;
    var v =  (vcx * dx +  vcy * dy) * (-2 / Math.hypot(dx, dy));
    const dd = v * v - 4 * (vcx * vcx + vcy * vcy - circle.radius * circle.radius);
    if (dd <= 0) { return Infinity; }
    return  (v - Math.sqrt(dd)) / 2;
}
const mouse  = {x : 0, y : 0}
function mouseEvents(e){
    mouse.x = e.pageX;
    mouse.y = e.pageY;
}
document.addEventListener("mousemove", mouseEvents);

const c1 = Circle(Point(150, 120), 60);
const r1 = Ray(Point(0, 50), Point(300, 50));


function renderLoop(time) {
   ctx.clearRect(0, 0, W, H);
   r1.p1.x = c1.x + Math.cos(time / 5000) * 100;
   r1.p1.y = c1.y + Math.sin(time / 5000) * 100;
   r1.p2.x = mouse.x;
   r1.p2.y = mouse.y;
   
   ctx.lineWidth = 0.5;
   drawCircle(c1);
   drawRay(r1);
   ctx.lineWidth = 5;
   if (rayInterceptsCircle(r1, c1)) {
     ctx.strokeStyle = "red";
     drawRayLeng(r1, rayDist2Circle(r1, c1));
   } else {
     drawRay(r1);
   }
   
   ctx.strokeStyle = "black";
   requestAnimationFrame(renderLoop);
}

canvas {
  position: absolute;
  top: 0px;
  left: 0px;
}

<canvas id="canvas" width="300" height="250"></canvas>

Please signup or login to give your own answer.

Click here to cancel reply.