如何使用p5.js计算圆上一条直线的交点

Question

我有一条线(se)，我知道它从圆内开始，到圆外结束。我试图找到线与圆相交的点l。

我正在使用p5.js库，并且可以访问其所有矢量函数。

我的想法是，如果我能在这条线上垂直于半径的方向上形成一个直角，那么我就可以开始解决一些问题了。

// Get the vector between s and c
let scVector = p5.Vector.sub(start, circleCenter);
// Get the angle between se and sc
let escAngle = this.v.angleBetween(scVector);
// Get the distance between t (where the right angle hits the center of the circle) and c
let tcDistance = Math.sin(escAngle) * scVector.mag();
// Get the distance between t and where the line intersects the circle
let tlDistance = Math.sqrt(Math.pow(hole.r, 2) - Math.pow(tcDistance, 2));
// Get the distance between the start point and t
let stDistance = Math.sqrt(Math.pow(scVector.mag(), 2) - Math.pow(tcDistance, 2));
// Add the two distances together, giving me the distance between s and l
let totalDistance = tcDistance + stDistance;
// Create a new Vector at this angle, at the totalDistance Magnitude, then add it to the current position
let point = p5.Vector.fromAngle(this.v.heading(), totalDistance).add(start);
// Mark a point (hopefully l) on the edge of the circle.
points.push({
  x: point.x,
  y: point.y,
  fill: '#ffffff'
})

遗憾的是，当我的物体穿过圆圈时，它们并没有留下点在边缘，而是离圆边更远。

小点是标记的位置，彩色点是物体（具有起点和终点）

这里有一个演示，可疑的部分是第42行及之后的代码: https://codepen.io/EightArmsHQ/pen/be0461014f9868e3462868776d9c8f1a

非常感谢您的任何帮助。

- Djave

---

如果您在离散时间间隔内增加每个球的位置，即使它穿过洞口，也不能保证在某个时间步长内球一定会在洞内（这取决于时间步长、洞半径和速度）。 - meowgoesthedog

我已经知道球是在洞内还是洞外。 - Djave

Answer 1

要找到点和直线的交点，我建议使用现有的算法，比如WolframMathWorld - Circle-Line Intersection中的算法。

该算法简短，解释清晰，并且可以用一个简短的函数来表达。输入参数p1、p2和cpt的类型为p5.Vector，r是一个标量。这些参数定义了从p1到p2的无限直线和以cpt为圆心、r为半径的圆。该函数返回一个交点列表，可能为空：

intersectLineCircle = function(p1, p2, cpt, r) {

    let sign = function(x) { return x < 0.0 ? -1 : 1; };

    let x1 = p1.copy().sub(cpt);
    let x2 = p2.copy().sub(cpt);

    let dv = x2.copy().sub(x1)
    let dr = dv.mag();
    let D = x1.x*x2.y - x2.x*x1.y;

    // evaluate if there is an intersection
    let di = r*r*dr*dr - D*D;
    if (di < 0.0)
        return [];
   
    let t = sqrt(di);

    ip = [];
    ip.push( new p5.Vector(D*dv.y + sign(dv.y)*dv.x * t, -D*dv.x + p.abs(dv.y) * t).div(dr*dr).add(cpt) );
    if (di > 0.0) {
        ip.push( new p5.Vector(D*dv.y - sign(dv.y)*dv.x * t, -D*dv.x - p.abs(dv.y) * t).div(dr*dr).add(cpt) ); 
    }
    return ip;
}

如果您想验证一个点是否在其他点之间，可以使用点积。如果您知道直线上的三个点，则仅需计算点之间的距离即可确定一个点是否在另外两个点之间。
p1、p2和px的类型为p5.Vector。这些点在同一条直线上。如果px在p1和p2之间，则函数返回true，否则返回false。

inBetween = function(p1, p2, px) {

    let v = p2.copy().sub(p1);
    let d = v.mag();
    v = v.normalize();

    let vx = px.copy().sub(p1);
    let dx = v.dot(vx);
    
    return dx >= 0 && dx <= d;
}

看一下我实现的用于测试该函数的示例。圆由鼠标跟踪，被一个随机移动的线段所相交：

var sketch = function( p ) {

p.setup = function() {
    let sketchCanvas = p.createCanvas(p.windowWidth, p.windowHeight);
    sketchCanvas.parent('p5js_canvas')
}

let points = [];
let move = []

// Circle-Line Intersection
// http://mathworld.wolfram.com/Circle-LineIntersection.html
p.intersectLineCircle = function(p1, p2, cpt, r) {

    let sign = function(x) { return x < 0.0 ? -1 : 1; };

    let x1 = p1.copy().sub(cpt);
    let x2 = p2.copy().sub(cpt);

    let dv = x2.copy().sub(x1)
    let dr = dv.mag();
    let D = x1.x*x2.y - x2.x*x1.y;

    // evaluate if there is an intersection
    let di = r*r*dr*dr - D*D;
    if (di < 0.0)
        return [];
   
    let t = p.sqrt(di);

    ip = [];
    ip.push( new p5.Vector(D*dv.y + sign(dv.y)*dv.x * t, -D*dv.x + p.abs(dv.y) * t).div(dr*dr).add(cpt) );
    if (di > 0.0) {
        ip.push( new p5.Vector(D*dv.y - sign(dv.y)*dv.x * t, -D*dv.x - p.abs(dv.y) * t).div(dr*dr).add(cpt) ); 
    }
    return ip;
}

p.inBetween = function(p1, p2, px) {

    let v = p2.copy().sub(p1);
    let d = v.mag();
    v = v.normalize();

    let vx = px.copy().sub(p1);
    let dx = v.dot(vx);
    
    return dx >= 0 && dx <= d;
}

p.endlessLine = function(x1, y1, x2, y2) {

    p1 = new p5.Vector(x1, y1);
    p2 = new p5.Vector(x2, y2);

    let dia_len = new p5.Vector(p.windowWidth, p.windowHeight).mag();
    let dir_v = p5.Vector.sub(p2, p1).setMag(dia_len);
    let lp1 = p5.Vector.add(p1, dir_v);
    let lp2 = p5.Vector.sub(p1, dir_v);

    p.line(lp1.x, lp1.y, lp2.x, lp2.y);
}

p.draw = function() {
        
    if (points.length == 0) {

        points = [];
        move = [];
        for (let i=0; i < 2; ++i ) {
            points.push( new p5.Vector(p.random(p.windowWidth-20)+10, p.random(p.windowHeight-20)+10));
            move.push( new p5.Vector(p.random(2)-1, p.random(2)-1) );
        }
        points.push( new p5.Vector(p.mouseX, p.mouseY));
    }
    else
    {
        for (let i=0; i < 2; ++i ) {
            points[i] = points[i].add(move[i]);
            if (points[i].x < 10 || points[i].x > p.windowWidth-10)
                move[i].x *= -1; 
            if (points[i].y < 10 || points[i].y > p.windowHeight-10)
                move[i].y *= -1;    
            move[i].x = Math.max(-1, Math.min(1, move[i].x+p.random(0.2)-0.1))
            move[i].y = Math.max(-1, Math.min(1, move[i].y+p.random(0.2)-0.1))
        }
        points[2].x = p.mouseX;
        points[2].y = p.mouseY;
    }
    let circle_diameter = p.min(p.windowWidth, p.windowHeight) / 2.0;

    let isectP = p.intersectLineCircle(...points, circle_diameter/2.0);

    // draw the scene

    p.background(192);
    
    p.stroke(0, 0, 255);
    p.fill(128, 128, 255);
    for (let i=0; i < points.length; ++i ) {
        p.ellipse(points[i].x, points[i].y, 10, 10);
    }

    for (let i=0; i < isectP.length; ++i ) {
        if (p.inBetween(points[0], points[1], isectP[i])) {
            p.stroke(255, 0, 0);
            p.fill(255, 128, 0);
        } else {
            p.stroke(255, 128, 0);
            p.fill(255, 255, 0);
        }

        p.ellipse(isectP[i].x, isectP[i].y, 10, 10);
    }

    p.stroke(0, 255, 0);
    p.noFill();
    p.endlessLine(points[0].x, points[0].y, points[1].x, points[1].y)
    p.ellipse(points[2].x, points[2].y, circle_diameter, circle_diameter);
}

p.windowResized = function() {
    p.resizeCanvas(p.windowWidth, p.windowHeight);
    points = [];
}

p.mouseClicked = function() {
    points = [];
}

p.keyPressed = function() {
    points = []
}

};

var circle_line = new p5(sketch);

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.3.1/p5.min.js"></script>
<div id="p5js_canvas"></div>

示例

- Rabbid76

---

谢谢，真是太巧妙了。数学从来不是我的强项，所以我找到了那篇Wolfram的文章，但就是无法“解码”它。再次非常感谢。 - Djave

非常好的演示！（+1） - George Profenza