c++ - 用于快速数组比较和替换具有最接近值的元素的算法。 (跟踪点)

Question

我有两个数组 currPoints 和 prevPoints。两者不一定大小相同。我想将 currPoints 中的每个元素与 prevPoints 进行比较，并替换 prevPoints 中最接近 currPoints 中值的值。

例子:

prevPoints{2,5,10,13,84,22}
currPoints{1,15,9,99}

应用算法后

prevPoints{1,5,9,15,99,22}

那么最好的算法/方法是什么？它需要快速。

上下文:如果有帮助，我正在尝试研究一种跟踪算法，该算法从视频中的两个连续帧中获取点，并试图找出第一帧中的哪些点对应于视频中的点第二帧。我希望通过这种方式跟踪对象并用 ID 标记它们。速度至关重要，因为处理是实时完成的。

Answer 1

您需要先对两个数组进行排序。但是请记住 prevPoints 数组的原始方向，因为您需要在最后再次获取原始数组。

排序后:

prevPoints{2,5,10,13,22,84}
currPoints{1,9,15,99}

现在您基本上需要弄清楚哪些 currPoints 应该进入 prevPoints。该算法类似于合并 2 个排序数组，只是您不会合并，而是替换值。

最初两个指针都位于相应数组的开头。 currpoints 中的 1 应该替换 prevPoints 中的 2，因为 currPoints 中的值小于 prevPoints 并且您知道 PrevPoints 中的下一个点只会高于 2(排序数组，记住)。替换并移动指针。

现在 currpointer 为 9，prevpointer 为 5。计算绝对差并存储到目前为止遇到的最小绝对差以及导致遇到最小绝对差的数字的值。(4在这种情况下)。当 currpointer 指向更高的值时，向前移动 prevpointer。

现在 10 处的 prevpointer 和 9 处的 currpointer。9 小于 10，因此必须进行替换。由于这个最小绝对差值小于之前的差值 ( 1 < 4 )，因此 10 将被 9 替换。

现在 prevpointer 位于 13，currpointer 位于 15。

以同样的方式进行。

将 prevPoints 数组重新排列到原来的方向。

希望这有帮助!!!