algorithm - 将此算法命名为 : Comparing and interpolating points?

Question

我的问题可能有点奇怪。我已经“开发”了一种算法，但不知道是否已经有类似的算法。

情况:我有一条由轨迹点 (2D) 定义的轨迹。例如，轨迹点代表转弯。轨道点之间只有直线。现在我在这个 2D 空间中得到了一组坐标。我计算从第一个轨迹点到新坐标的距离以及前两个轨迹点的间隔距离。如果到测量坐标的距离小于从第一个到第二个轨迹点的距离，我假设这个点位于这个间隔之间。然后我对其进行线性插值。如果它更大，我会在下一个时间间隔检查。

所以它基本上是采用间隔距离并尝试将它们放入其中。我正在尝试跟踪一个大致沿着这条轨道移动的物体。

这听起来很熟悉吗？有人可以提出一个类似的现有算法的建议吗？

编辑:根据我到目前为止所说的，我想澄清的是位置与跟踪点没有多重关联。考虑 Jonathan 制作的精美 ASCII 绘图:

发现 X 位置在段 1 和段 2 内 (S12)。现在下一个位置是 Y，它不能被认为足够接近 S12。我将转到 S23，并检查它是否在。

如果它在，我将不会检查 S12 的任何其他值，因为我已经在下一段中找到了一个。算法“不回头”。

但是如果它没有从那里找到正确的段，因为它恰好离第一个段很远，但无论如何仍然离任何其他段更远，我将放弃该值，下一个位置将再次在 S12 中寻找回来。

循环仍然是一个问题。假设我得到 S23 的 Y，然后跳过两个或三个位置(因为它们相差太远)，我可能会迷失方向。我可以确定 S34 中的一个位置，它已经在 S56 中了。

也许我可以想出一些平均速度来告诉它应该在哪个段。

似乎分割越大，做出正确决定的机会就越大。

Answer 1

关于您所描述的算法，我担心的是它是“贪婪的”并且可能会选择“错误的”轨道段(或者，至少，不是最接近点的轨道段)。

是时候将 ASCII 艺术推向极限了。考虑以下路径(数字代表轨迹点列表中的序列)和坐标 X(以及后来的 Y)。

    1-------------2
                  |
                  |    Y
                X |
            5-----+-----6
            |     |
            |     |
            4-----3

我们应该如何解读您的描述？

[C]alculate the distance from the first track point to the new coordinates and the distance for the interval for the first two track points. If the distance to the measured coordinates is shorter than the distance from the first to the second track point, [assume] that this point lies in between this interval; [...] [i]f it's bigger, [...] check with the next interval.

我认为第一句的意思是:

• 计算从 TP1(轨迹点 1)到 TP2 的距离 - 称之为 D12。
• 计算从 TP1 到 X(称为 D1X)和从 TP2 到 X(称为 D2X)的距离。

棘手的部分是条件句的解释。

我的印象是，如果 D1X 或 D2X 小于 D12，则 X 将被假定在(或最接近)轨道段 TP1 到 TP2(称为段 S12)上。

查看图中 X 的位置，很明显 D1X 和 D2X 都小于 D12，因此我对您的算法的解释会将 X 解释为与 S12 关联，但 X 显然更接近 S23 或S56 比 S12(但那些甚至没有被考虑就被丢弃)。

我是不是对你的算法有什么误解？

稍微考虑一下:我对您的算法的解释是，如果点 X 位于以 TP1 为中心的半径 D12 的圆或以 TP2 为中心的半径 D12 的圆内，则您将 X 与S12.但是，如果我们也考虑 Y 点，我建议您使用的算法也会将它与 S12 相关联。

如果算法细化说MAX(D1Y, D2Y) < D12 , 那么它不认为 Y 与 S12 相关。然而，X 可能仍被认为与 S12 有关，而不是与 S23 或 S56 有关。