快速数组比较和替换最接近的元素的算法。 （Tracking Points）

Question

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

例子：

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中的值小于prevPoints的事实，并且您知道PrevPoints中的下一个点只会高于2（请记住已排序的arry），则currpoints中的1应取代prevPoints中的2。替换并移动指针。

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

现在prevpointer在10和currpointer在9. 9小于10，因此必须进行替换。作为该最小绝对差小于较早的一（1 < 4），因此将10将由9.

代替现在prevpointer是在13和currpointer是在15

继续以相同的方式。

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

希望这有助于！

Answer 2

我们按x位置排序第一个列表，第二个列表按y位置排序。所以每个点在每个列表中都有一个位置。现在，您对最近邻居搜索（至少是我想出的）的做法是通过二分搜索找到每个列表中的点的位置。然后我们知道4个方向，+ 1 x或+ -y，基本上我们在每个方向上移动，直到到目前为止的最佳长度大于只有一个坐标的距离。

所以我们在每个方向搜索。并且说最近的点在25的距离处，那么如果我们的下一个坐标在+ X方向上在+ X方向上超过25，我们可以停止，因为即使Y的变化为0，它也不能接近。

这使得一个高效且快速的n（log（n））最近点算法可以找到一个点。但是，由于我们只需要两个排序列表，只要我们有n（log（n））时间，我们就可以找到所有剩余点的最近点，如log（n）时间。在x排序列表中查找位置，找到y排序列表中的位置。然后旋出，直到你截断，并确定找到最近的点。但是，由于脚手架在每种情况下都是相同的，它应该只是相当快速。

虽然给出了你的实际测试用例，但你可能想提出一些非常有效的启发式方法。

---

简单的跟踪点似乎真的天真，如果我们从框架跟踪同样的事情帧应该是从F0在F2点到F1实际上应该等于它在行驶的距离的情况下F0到F1。如果我们假设所有这些点都以大致的直线行进，那么我们可以做得比仅仅最接近的点好得多。我们通常可以找到这些点正在采取的曲线。如果我们猜测他们的位置应该是F2，通过插入F0和F1并且低，并且看到一个点的位置，那么真的非常接近。那么我们可以肯定我们已经确定了这一点。

同样，人们会假设的所有对象都沿大致相同的方向行进。就像每个点从F0到F1移动+5，+5一样，我们不仅可以猜测它们的F2位置，而且我们可以相当有效地知道这些对象组成了同一个对象。