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

Question

总结
我的简单函数对局部最小值执行二进制搜索，通常 returns 虚假值恰好对应于搜索的 ¼、½ 和 ¾。为什么会这样？

/**
 * 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 参数。

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

准则指南
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

就像经常发生的那样，当您花时间写下问题时，答案就显而易见了。我的 localMinimum() 功能有缺陷。

如果我们查看上面第三个示例的图表并从最大点画一条线，我们会看到它在右侧：

算法（如上图）的写法，立马丢掉图的右半边，关注左半边。从那一刻起，它就注定了。它一直以 0.5 的幅度向右移动左侧边界，但永远不允许再次向右移动。

这里是 localMinimum() 函数的固定版本，使用了一些 hack。给定任何边界，它会找到中间的点，然后向左和向右移动 "slightly"（由 ε 参数确定）并据此决定保留哪一半。

/**
 * 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-10;
    let m=minX, n=maxX, k;
    while ((n-m)>ε) {
        k = (n+m)/2;
        if (ƒ(k-ε)<ƒ(k+ε)) n=k;
        else               m=k;
    }
    return k;
}

我已将固定版本的演示上传到：http://phrogz.net/svg/closest-point-on-bezier.html

Answer 2

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

渐进搜索

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

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

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

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

Local minimum function getting stuck not at minimum

javascript

bezier