提问人:Gaius Coffey 提问时间:10/19/2023 最后编辑:Gaius Coffey 更新时间:11/15/2023 访问量:35
二次贝塞尔曲线的线交点在特定值上失败
Line intersection for quadratic bezier curve fails on specific values
问:
我有一种找到直线和二次贝塞尔曲线交点的方法(基于这里计算二次贝塞尔曲线交点的答案)粘贴在下面:
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 []
在下图中,中线应停在曲线处,但未停在曲线处。
我的数学技能真的无法弄清楚为什么存在这种边缘情况。寻找交叉点的解决方案非常普遍,几乎适用于其他所有实例。 有没有数学家可以解释为什么它在这种情况下会失败,以及(最好)我如何以编程方式检测和解决它?编辑添加我发现问题是“a”为零,因为线是垂直的。对于这组特定的坐标,这相当于中点 (t = 0.5),但我确信还有其他方法可以使 a = 0。谁能指出我处理 = 0 条件的正确方法?
答:
0赞
Gaius Coffey
11/15/2023
#1
结果是一个舍入错误 - 我在 okX 和 okY 值中添加了一个公差值,以允许 Math.pow(10,-14) 输出的值。
评论