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.
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?
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).