7

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

最小距离问题图解

我有一个固定点（比如说白色测量线上的右上角），需要在由等距点（下曲线）组成的曲线上找到最近的点。此外，我对上曲线上的每个点执行此操作，以绘制具有不同颜色的曲线之间的距离（三个级别：低于最小值 [红色]、最小值和最大值之间 [橙色] 以及高于最大值 [绿色]）。

我目前的解决方案是权衡：我取固定点，遍历任意间隔（例如，固定点左右各 50 个单位）并计算每对的距离。这节省了一些 CPU 功率，但它既不优雅也不准确，因为我可能会错过我选择的间隔之外的最小距离。

有更快算法的建议吗？

编辑：等间距意味着所有点在 x 轴上的距离相同，这对于两条曲线都是如此。我也不需要在点之间进行插值，这太耗时了。

4

3 回答 3

3

您可以迭代直到“超出范围”，而不是任意距离。

在您的示例中，假设您从直线右上角的上曲线上的点开始。然后垂直向下下降，你会得到（在我看来）大约 200 微米的距离。

现在您可以从这里测试点向右移动，直到水平距离为 200um。除此之外，不可能达到小于 200 微米的距离。

向左移动，距离下降，直到找到 150 微米的最小值，然后再次开始上升。一旦你在你的上点左侧 150 微米，再一次，你不可能超过你找到的最小值。

如果您先向左走，则不必向右走那么远，因此优化要么遵循距离下降的方向，要么同时从中间向两个方向进行计算。

我不知道 um 50 单位是多少，所以这可能比你所拥有的要慢或快。不过，它确实避免了丢失较低值的风险。

由于您正在对较低曲线上的同一组点进行大量测试，因此您可以通过忽略这些点完全形成曲线的事实来改进这一点。将它们全部粘贴在 kd 树或类似树中，然后反复搜索。这称为最近邻搜索。

于 2012-10-08T10:29:43.173 回答
3

将这个问题识别为最近邻搜索问题可能会有所帮助。该链接包含有关用于此的各种算法的很好的讨论。如果您可以使用 C++ 而不是直接使用 C，那么ANN看起来是一个很好的库。

看起来这个问题以前也有人问过。

于 2012-10-08T11:29:59.733 回答
2

我们可以标记顶部曲线 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)）。

于 2012-10-08T10:45:39.177 回答