如何在 JavaScript 中检查直线是否与圆相交？

Question

我正在创建一个库，这样我可以更轻松地创建 HTML5 canvas 游戏。我目前正在研究碰撞检测。这是我为线/圆碰撞编写的代码如下。

object1

是包含圆的 x、y 和半径的对象。

object2

是包含线段两个点的对象。

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;

这里是

object1

和

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
}

我测试了这段代码，它没有检测到正确点的交叉点。有什么帮助吗？

Answer 1

我建议为基本向量运算编写单独的函数，例如添加它们、获取它们的大小、执行点积等。

您可以使用 Vector formulation 如何获得给定线上最接近另一点（圆心）的点。

这也可以让我们知道那个点离线段的一端有多远，以及那个点是在线段上还是在线段外。

有了这些信息，您就可以确定线段和圆是否发生碰撞。它们在以下任一情况下发生碰撞：

• 线段的一个端点在圆内；
• 线段上的最近点确实在线段上并且在圆内。

这里是一个交互式OOP实现：移动鼠标改变线段的一个端点；圆圈的内部颜色将反映是否有碰撞：

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>

Answer 2

给出的答案可以改进

避免平方根

在下面的示例中，函数

rayInterceptsCircle

返回

true

或

false

取决于线段（射线）和圆的截距，使用线段到圆心的距离。

这与现有答案类似，但它避免了计算昂贵的平方根

在圆周长上

函数

rayDist2Circle

返回沿直线到它与圆相交的点的距离，如果没有截距，则距离返回为Infinity。它确实需要最多 2 个平方根。

如果你有很多圆，你必须根据这个函数测试线可以通过找到最小距离找到线截取的第一个圆

演示

用鼠标移动线段端点。如果线截取圆，则在截取点处以红色呈现。

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>