二次贝塞尔曲线的线交点在特定值上失败

Line intersection for quadratic bezier curve fails on specific values

提问人:Gaius Coffey 提问时间:10/19/2023 最后编辑:Gaius Coffey 更新时间:11/15/2023 访问量:35

问:

我有一种找到直线和二次贝塞尔曲线交点的方法(基于这里计算二次贝塞尔曲线交点的答案)粘贴在下面:

export type PointXY = {x:number,y:number};
const lerp = (a:number,b:number,t:number) => (a+t*(b-a));
export const quadraticIntersectsLine = (p1:PointXY, p2:PointXY, p3:PointXY, a1:PointXY, a2:PointXY)=>{
    let intersections:PointXY[] = [];
    // inverse line normal
    let normal={x: a1.y-a2.y, y: a2.x-a1.x}

    // Q-coefficients
    let c2={x: p1.x + p2.x*-2 + p3.x, y: p1.y + p2.y*-2 + p3.y}

    let c1={x: p1.x*-2 + p2.x*2, y: p1.y*-2 + p2.y*2}

    let c0={x: p1.x, y: p1.y}

    // Transform to line
    let coefficient = a1.x*a2.y-a2.x*a1.y;
    let a = normal.x*c2.x + normal.y*c2.y;
    let b = (normal.x*c1.x + normal.y*c1.y)/a;
    let c = (normal.x*c0.x + normal.y*c0.y + coefficient)/a;
    // solve the roots
    

/****
 * THE PROBLEM IS HERE! 
 * The "a" value is zero because perpendicular for this specific set of coordinates. 
 * WHAT IS THE BEST WAY TO RESOLVE IT?
 */

    let roots=[];
    let d = b*b-4*c;
    if(d>0){
        roots.push((-b+Math.sqrt(d))/2);
        roots.push((-b-Math.sqrt(d))/2);
    } else if(d===0){
        roots.push(-b/2);
    }
    let minX=Math.min(a1.x,a2.x);
    let minY=Math.min(a1.y,a2.y);
    let maxX=Math.max(a1.x,a2.x);
    let maxY=Math.max(a1.y,a2.y);
    // calc the solution points
    roots.forEach(t=>{
        if(t>=0 && t<=1) {
            // possible point -- pending bounds check
            let point={
                x:lerp(lerp(p1.x,p2.x,t),lerp(p2.x,p3.x,t),t),
                y:lerp(lerp(p1.y,p2.y,t),lerp(p2.y,p3.y,t),t)
            }
            let okY = point.y>=minY && point.y<=maxY,
                okX = point.x>=minX && point.x<=maxX;
            // bounds checks
            if(a1.x===a2.x && okY) {
                // vertical line
                intersections.push(point);
            } else if(a1.y===a2.y && okX) {
                // horizontal line
                intersections.push(point);
            } else if(okX && okY){
                // line passed bounds check
                intersections.push(point);
            }
        }
    })
    return intersections;
}

它有效...几乎完全...但是这里的具体值找不到交集,我无法弄清楚原因:

// Line (a1,a2) given by: [{"x":350,"y":350},{"x":608,"y":608}]
// Curve (p1,p2,p3) given by: [{"x":1024,"y":-40},{"x":569,"y":569},{"x":-40,"y":1024}]
let intersections = quadraticIntersectsLine({"x":1024,"y":-40},{"x":569,"y":569},{"x":-40,"y":1024},{"x":350,"y":350},{"x":608,"y":608});
// Intersections SHOULD be  [{"x":530.5,"y":530.5}] but IS []

在下图中,中线应停在曲线处,但未停在曲线处。

Middle line should stop at the curve, but doesn't.

我的数学技能真的无法弄清楚为什么存在这种边缘情况。寻找交叉点的解决方案非常普遍,几乎适用于其他所有实例。 有没有数学家可以解释为什么它在这种情况下会失败,以及(最好)我如何以编程方式检测和解决它?编辑添加我发现问题是“a”为零,因为线是垂直的。对于这组特定的坐标,这相当于中点 (t = 0.5),但我确信还有其他方法可以使 a = 0。谁能指出我处理 = 0 条件的正确方法?

JavaScript 数学 线 交集 次曲线

评论

1赞 Simon Goater 10/19/2023
您应该链接到您获取代码的位置。
0赞 Gaius Coffey 10/19/2023
我已经编辑了这篇文章,在这里包含了原文的链接:stackoverflow.com/questions/27664298/......

答:

0赞 Gaius Coffey 11/15/2023 #1

结果是一个舍入错误 - 我在 okX 和 okY 值中添加了一个公差值,以允许 Math.pow(10,-14) 输出的值。