用于快速数组比较和替换具有最接近值的元素的算法。 （跟踪点）
Algorithm for fast array comparison and replacing elements with closest value. (Tracking Points)
我有两个数组 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}
那么最好的 algorithm/method 是什么？一定要快。
上下文：如果有帮助，我正在尝试研究一种跟踪算法，该算法从视频中的两个连续帧中获取点并尝试找出第一个中的哪些点帧对应于第二帧中的点。我希望通过这种方式跟踪对象并用 ID 标记它们。速度是至关重要的，因为处理是实时完成的。
您需要先对两个数组进行排序。但请记住 prevPoints 数组的原始方向，因为您需要在最后再次获取原始数组。
所以排序后：
prevPoints{2,5,10,13,22,84}
currPoints{1,9,15,99}
现在您基本上需要弄清楚 currPoints 中的哪些应该进入 prevPoints。该算法类似于 merge 2 sorted arrays 只是您不会合并，而是替换值。
最初两个指针都位于相应数组的开头。 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 数组重新排列为原始方向。
希望对您有所帮助！！！
我们按 x 位置对第一个列表进行排序，按 y 位置对第二个列表进行排序。所以每个点在每个列表中都有一个位置。现在，您为最近邻搜索执行此操作的方式（至少是我想到的）是通过二进制搜索找到每个列表中的点的位置。然后我们知道 4 个方向，+-1 x 或 +-y，基本上我们在这些方向中的每一个方向上移动，直到到目前为止的最佳长度大于仅那个坐标的距离。
所以我们在每个方向上搜索。假设最近点的距离为 25，那么如果我们在 +X 方向的下一个坐标仅在 +X 方向超过 25，我们就可以停止，因为即使 Y 的变化为 0，它也不能更近。
这使得一种高效快速的 n(log(n)) 最近点算法可以找到一个点。但是，同样由于我们只需要两个排序列表，一旦我们在 n(log(n)) 时间内得到它们，我们就可以在类似 log(n) 时间的东西中找到所有剩余点的最近点。在 x 排序列表中查找位置，在 y 排序列表中查找位置。然后螺旋出去，直到你截断并且肯定找到了最近的点。但是，由于脚手架在每种情况下都是相同的，所以最终应该很快。
尽管给定您的实际测试用例，您可能想提出一些非常有效的启发式方法。
简单地追踪这些点似乎很幼稚，如果我们逐帧追踪同一件事，那么 F2 中从 F0 到 F1 的点实际上应该等于它在 F0 中行进到F1。如果我们假设所有这些点都大致沿直线移动，那么我们可以比简单的最近点做得更好。我们可以大致找到这些点所走的曲线。如果我们通过插值 F0 和 F1 来猜测它们的位置应该是 F2 和低，并且看到一个点的位置真的非常接近。然后我们可以非常确定我们做到了。
同样，人们假设的物体的所有点都大致沿相同的方向运动。就像每个点从 F0 到 F1 移动 +5,+5，我们不仅可以猜测它们在 F2 的位置，而且我们可以知道这些对象相当有效地组成了同一个对象。
我有两个数组 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}
那么最好的 algorithm/method 是什么？一定要快。
上下文：如果有帮助，我正在尝试研究一种跟踪算法，该算法从视频中的两个连续帧中获取点并尝试找出第一个中的哪些点帧对应于第二帧中的点。我希望通过这种方式跟踪对象并用 ID 标记它们。速度是至关重要的，因为处理是实时完成的。
您需要先对两个数组进行排序。但请记住 prevPoints 数组的原始方向，因为您需要在最后再次获取原始数组。
所以排序后：
prevPoints{2,5,10,13,22,84}
currPoints{1,9,15,99}
现在您基本上需要弄清楚 currPoints 中的哪些应该进入 prevPoints。该算法类似于 merge 2 sorted arrays 只是您不会合并，而是替换值。
最初两个指针都位于相应数组的开头。 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 数组重新排列为原始方向。
希望对您有所帮助！！！
我们按 x 位置对第一个列表进行排序，按 y 位置对第二个列表进行排序。所以每个点在每个列表中都有一个位置。现在，您为最近邻搜索执行此操作的方式（至少是我想到的）是通过二进制搜索找到每个列表中的点的位置。然后我们知道 4 个方向，+-1 x 或 +-y，基本上我们在这些方向中的每一个方向上移动，直到到目前为止的最佳长度大于仅那个坐标的距离。
所以我们在每个方向上搜索。假设最近点的距离为 25，那么如果我们在 +X 方向的下一个坐标仅在 +X 方向超过 25，我们就可以停止，因为即使 Y 的变化为 0，它也不能更近。
这使得一种高效快速的 n(log(n)) 最近点算法可以找到一个点。但是，同样由于我们只需要两个排序列表，一旦我们在 n(log(n)) 时间内得到它们，我们就可以在类似 log(n) 时间的东西中找到所有剩余点的最近点。在 x 排序列表中查找位置，在 y 排序列表中查找位置。然后螺旋出去，直到你截断并且肯定找到了最近的点。但是，由于脚手架在每种情况下都是相同的，所以最终应该很快。
尽管给定您的实际测试用例，您可能想提出一些非常有效的启发式方法。
简单地追踪这些点似乎很幼稚，如果我们逐帧追踪同一件事，那么 F2 中从 F0 到 F1 的点实际上应该等于它在 F0 中行进到F1。如果我们假设所有这些点都大致沿直线移动，那么我们可以比简单的最近点做得更好。我们可以大致找到这些点所走的曲线。如果我们通过插值 F0 和 F1 来猜测它们的位置应该是 F2 和低，并且看到一个点的位置真的非常接近。然后我们可以非常确定我们做到了。
同样，人们假设的物体的所有点都大致沿相同的方向运动。就像每个点从 F0 到 F1 移动 +5,+5，我们不仅可以猜测它们在 F2 的位置，而且我们可以知道这些对象相当有效地组成了同一个对象。