language-agnostic - 定位起点和终点之间的所有元素，由值(而非索引)给出

Question

问题如下，

我会得到一组长绳的 x 和 y 坐标(大约 30 到 4 万的坐标数组)。绳子躺在地上，可以是任何形状。

现在我会得到一个起点(基本上是 x 和 y 坐标)和一个终点。

根据上述位于起点和终点之间的坐标数组确定 x 和 y 坐标集的有效方法是什么。

穷举搜索即循环 40k 次不是可接受的解决方案(在试卷中提到)

可以接受一点误差

Answer 1

我们需要找到数组中的起点，然后是终点。对于每一个，我们都可以将绳子视为描述到该点的距离的函数，并且我们正在寻找该距离图上的最低点。如果一个点距离很远而另一个点很近，我们可以对下一步搜索的位置进行某种插值猜测。

distance
    |  /---\
    |--     \  /\       -
    |        --  ------- --   ------     ----------    -
    |                      \ /      \---/          \--/
    +-----------------------X--------------------------- array index

在上面的表示中，我们想要找到“X”……我们观察几个点的距离，了解距离曲线的斜率，甚至可能是该斜率的变化率，以便帮助指导我们的下一步探测....

要完善在已知距离值较低的区域进行二分搜索或插值搜索的基本方法，我们可以使用以下方法:

• 如果恰好给定了绳索长度并且知道坐标样本沿绳索等距，那么我们可以计算每个样本与目标点的距离的最大变化。
• 如果我们知道绳子的刚度确保它不会在非常小的直径内打圈，那么
  • 曲线斜率变化的速度有一个已知限制
  • 距离曲线在0点两侧收敛于垂直
• 您可以潜在地交叉引用/结合距离与目标的每个点的方向，或者改为使用:只有在目标处，方向才会立即改变约 180 度(数据点捕获的程度仍然取决于相邻样本之间的距离和绳索的任何刚度)。

否则，始终存在目标点可能奇怪地被两个非常远的点包围的风险，使我们的整个搜索算法受挫(这一定是他们所说的一些错误余量 - 时不时地这个搜索必须恢复到O(N) 暴力搜索，因为任何趋势分析都失败了)。