找到一点到曲线上点的最小距离的最快方法

Question

我正在寻找以下问题的快速解决方案:

我有一个固定的点(假设在白色测量线的右上角)并且需要找到由等间距点(下面的曲线)构成的曲线上的最近点.另外,我对上曲线上的每个点都这样做,以绘制不同颜色的曲线之间的距离(三个级别:低于最小值[红色],最小值和最大值[橙色]之间以及高于最大值[绿色]).

我目前的解决方案是权衡:我采用固定点,迭代任意间隔(例如固定点左右50个单位)并计算每对的距离.这节省了一些CPU功率,但它既不优雅也不准确,因为我可能会错过我选择的间隔之外的最小距离.

有关更快算法的任何建议吗？

编辑:等间距表示所有点在x轴上具有相同的距离,对于两条曲线都是如此.此外,我不需要在点之间进行插值,这将耗费太多时间.

Answer 1

我们可以标记顶部曲线 y=t(x) 和底部曲线 y=b(x)。标记最接近的函数 x_b=c(x_t)。我们知道，最接近的函数是弱单调非减的，因为两条最短路径永远不会相互交叉。

如果您知道距离函数 d(x_t,x_b) 对于每个固定的 x_t 只有一个局部最小值（如果曲线“足够平滑”就会发生这种情况），那么您可以通过“行走”曲线来节省时间：

- start with x_t=0, x_b=0
- while x_t <= x_max
-- find the closest x_b by local search
     (increment x_b while the distance is decreasing)
-- add {x_t, x_b} to the result set
-- increment x_t

如果您期望 x_b 足够平滑，但您不能假设这一点并且您想要精确的结果，

沿着两个方向走曲线。如果结果一致，则它们是正确的。如果他们不同意，请在两个结果（最左边和最右边的局部最大值）之间运行完整的搜索。以这样的顺序（二进制除法）对“模糊块”进行采样，以允许由于单调性而进行最多的修剪。

作为中间立场：

沿着两个方向走曲线。如果结果不一致，请在两者中进行选择。如果您可以保证每个固定 x_t 最多有两个局部最大值，则会产生最优解。仍然存在一些病态情况，其中未找到最佳解决方案，并且包含一个局部最小值，该局部最小值的两侧是另外两个局部最小值，这两个局部最小值都比这个局部最小值更差。我敢说，解决方案远非最优的情况并不常见（假设平滑 y=b(x)）。