我编写了一些快速而简单的代码来估计任意阶贝塞尔曲线的这一点。(注意:这是伪暴力,而不是封闭式解决方案。)
Demo: http://phrogz.net/svg/closest-point-on-bezier.html
/** Find the ~closest point on a Bézier curve to a point you supply.
* out : A vector to modify to be the point on the curve
* curve : Array of vectors representing control points for a Bézier curve
* pt : The point (vector) you want to find out to be near
* tmps : Array of temporary vectors (reduces memory allocations)
* returns: The parameter t representing the location of `out`
*/
function closestPoint(out, curve, pt, tmps) {
let mindex, scans=25; // More scans -> better chance of being correct
const vec=vmath['w' in curve[0]?'vec4':'z' in curve[0]?'vec3':'vec2'];
for (let min=Infinity, i=scans+1;i--;) {
let d2 = vec.squaredDistance(pt, bézierPoint(out, curve, i/scans, tmps));
if (d2<min) { min=d2; mindex=i }
}
let t0 = Math.max((mindex-1)/scans,0);
let t1 = Math.min((mindex+1)/scans,1);
let d2ForT = t => vec.squaredDistance(pt, bézierPoint(out,curve,t,tmps));
return localMinimum(t0, t1, d2ForT, 1e-4);
}
/** Find a minimum point for a bounded function. May be a local minimum.
* minX : the smallest input value
* maxX : the largest input value
* ƒ : a function that returns a value `y` given an `x`
* ε : how close in `x` the bounds must be before returning
* returns: the `x` value that produces the smallest `y`
*/
function localMinimum(minX, maxX, ƒ, ε) {
if (ε===undefined) ε=1e-10;
let m=minX, n=maxX, k;
while ((n-m)>ε) {
k = (n+m)/2;
if (ƒ(k-ε)<ƒ(k+ε)) n=k;
else m=k;
}
return k;
}
/** Calculate a point along a Bézier segment for a given parameter.
* out : A vector to modify to be the point on the curve
* curve : Array of vectors representing control points for a Bézier curve
* t : Parameter [0,1] for how far along the curve the point should be
* tmps : Array of temporary vectors (reduces memory allocations)
* returns: out (the vector that was modified)
*/
function bézierPoint(out, curve, t, tmps) {
if (curve.length<2) console.error('At least 2 control points are required');
const vec=vmath['w' in curve[0]?'vec4':'z' in curve[0]?'vec3':'vec2'];
if (!tmps) tmps = curve.map( pt=>vec.clone(pt) );
else tmps.forEach( (pt,i)=>{ vec.copy(pt,curve[i]) } );
for (var degree=curve.length-1;degree--;) {
for (var i=0;i<=degree;++i) vec.lerp(tmps[i],tmps[i],tmps[i+1],t);
}
return vec.copy(out,tmps[0]);
}
上面的代码使用了vmath库有效地在向量(2D、3D 或 4D)之间进行 lerp,但是替换lerp()
打电话进来bézierPoint()
用你自己的代码。
调整算法
The closestPoint()
函数分两个阶段工作:
- 首先,计算沿曲线的所有点(均匀间隔的值)t范围)。记录哪个值t到该点的距离最小。
- 然后,使用
localMinimum()
函数寻找最小距离周围的区域,使用二分搜索来找到t以及产生真实最小距离的点。
的价值scans
in closestPoint()
确定在第一遍中使用多少个样本。扫描次数越少速度越快,但会增加错过真正最小点的机会。
The ε
限制传递给localMinimum()
函数控制它继续寻找最佳值的时间。值为1e-2
将曲线量化为约 100 个点,因此您可以看到从closestPoint()
沿着线弹出。每增加一个小数点精度——1e-3
, 1e-4
, …—花费大约 6-8 次额外调用bézierPoint()
.