Line intersection for quadratic bezier curve fails on specific values

41 views Asked by At

I have a method for finding the intersection of a line and a quadratic bezier curve (based on the answer here calculating intersection point of quadratic bezier curve ) pasted below:

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;
}

It works... almost entirely... but the specific values here fail to find the intersection and I cannot work out why:

// 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 []

In the image below, the middle line should stop at the curve but doesn't.

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

My maths skills are really not up to working out why this edge-case exists. The solution for finding intersections is quite common and works in almost every other instance. Are there any mathematicians out there who can explain why it fails in this one situation and (preferably) how I can programmatically detect and resolve it? EDITED TO ADD I have found that the problem is that "a" is zero as the line is perpendicular. For this specific set of coordinates, that equates to mid-point (t = 0.5) but I am sure there are other ways to make a = 0. Can anybody point me to the correct way to handle a = 0 condition?

1

There are 1 answers

0
Gaius Coffey On

Turned out to be a rounding error - I have added a tolerance value to the okX and okY values to allow for values that are out by Math.pow(10,-14).