javascript - 局部最小值函数卡住而不是最小值

Question

总结
我对局部最小值执行二分搜索的简单函数通常会返回恰好与搜索的 ¼、½ 和 ¾ 相对应的虚假值。为什么会这样？

/**
 * 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
 * return: the `x` value that produces the smallest `y`
 */
function localMinimum(minX, maxX, ƒ, ε) {
    if (ε===undefined) ε=1e-15;
    let m=minX, n=maxX, k;
    while ((n-m)>ε) {
        k = (n+m)/2;
        if (ƒ(m)<ƒ(n)) n=k;
        else           m=k;
    }
    return k;
}

现场演示:http://phrogz.net/svg/closest-point-on-bezier_broken.html

该演示可让您调整三次贝塞尔曲线，四处移动鼠标，并尝试在曲线上找到离鼠标位置最近的点。在下面的屏幕截图中，您可以看到曲线(黑色)、鼠标的位置(以灰色圆圈为中心)、在曲线上找到的位置(红点)、从光标到曲线上的每个点(右下角)，以及计算为局部最小值的 t 参数(红色文本)。

这些屏幕截图代表了最坏的情况。在它们中，鼠标位置非常靠近直线，“局部最小值”函数返回的点不是局部最小值。如果您对演示进行试验，您会发现在许多情况下，局部最小值函数都按预期工作。只是……不接近一些早期的二分搜索边界。

准则指南
localMinimum() 函数(第 225 行)由 closestPoint() 函数(第 194 行)调用:

/**
 * out   : A vmath vector to modify with the point value
 * curve : Array of vectors as control points for a Bézier curve (any degree)
 * pt    : Object with .x/.y to find the point closest to
 * return: A parameter t representing the location of `out`
 */
function closestPoint(out, curve, pt, tmps) {
    let vec=vmath[ 'w' in curve[0] ? 'vec4' : 'z' in curve[0] ? 'vec3' : 'vec2' ];
    return localMinimum(0, 1,
      t => vec.squaredDistance(pt, bézierPoint(out, curve, t)));
}

bézierPoint() 函数(第 207 行)使用 De Casteljau 算法计算沿由 t 参数化的曲线的点。此函数按预期工作，独立于问题的其余部分进行测试。

squaredDistance() 函数是 vmath 库的一部分，如 simple as you would imagine .

我错过了什么？我的局部最小值函数是如何失败的？

Answer 1

我遇到了同样的问题，使用一组不同的函数来找到曲线上的最近点。

渐进式搜索

function localMinimum(minX, maxX, ƒ, ε) {
    if (ε===undefined) ε=1e-15;
    let m=minX, n=maxX, k;
    while ((n-m)>ε) {
        k = (n+m)/2;
        if (ƒ(m)<ƒ(n)) n=k;
        else           m=k;
    }
    return k;
}

是错误的，因为它会在错误的地方关闭。根据内存，曲线的导数(或二阶导数)是与将显示拐点的点的距离，您会得到错误的结果。换句话说，在曲线的那一部分，它越来越靠近你的点，然后开始移开。搜索功能假设这个拐点就是您正在寻找的点。

解决方案是系统搜索(以某种分辨率)，然后逐步搜索最终结果。