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

Question

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

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

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

任何关于更快算法的建议？

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

Answer 1

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

在您的示例中，假设您从直线右上角的上曲线上的点开始。然后垂直向下下降，你得到一个距离(我的眼睛)大约 200 微米。

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

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

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

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

由于您正在对下部曲线上的同一组点进行大量测试，因此您可以通过完全忽略这些点形成曲线这一事实来改进这一点。将它们全部放入 k-d 树或类似树中，然后反复搜索。它叫做 Nearest neighbor search .