python-3.x - 找到最近点集的最快方法

Question

我有三个点数组:

A=[[5,2],[1,0],[5,1]]

B=[[3,3],[5,3],[1,1]]

C=[[4,2],[9,0],[0,0]]

我需要最有效的方法来找到彼此最接近(每个轴的一个像素内)的三个点(每个阵列一个)。

我现在做的是引用一个点，比方说A[0] ，并循环所有其他 B 点和 C 点以寻找解决方案。如果A[0]没有给我任何结果我将引用移动到 A[1]等等。这种方法是一个巨大的问题，因为如果我增加每个数组的点数和/或数组的数量，它有时需要太多时间才能收敛，特别是如果解决方案位于数组的最后一个成员中。所以我想知道是否有任何方法可以在不使用引用的情况下执行此操作，或者是否有比循环遍历所有元素更快的方法。

我必须遵守的规则如下:

• 最终的解决方案只能由每个数组中的一个元素组成，例如:S=[A[n],B[m],C[j]]
• 每个选定的元素必须在 X 和 Y 中与解决方案的所有其他成员的 1 个像素以内(因此解决方案的每个成员的 Xi-Xj<=1 和 Yi-Yj<=1)。

例如，在这个简化的案例中，解决方案是:S=[A[1],B[2],C[1]]

为了进一步澄清问题:我上面写的只是一个简单的例子来解释我的需要。在我的真实情况下，我事先不知道列表的长度，也不知道我必须处理的列表的数量，可能是 A、B、C 或 A、B、C、D、E...(每个一个具有不同点数的)等。所以我还需要找到一种方法使其尽可能通用。

Answer 1

这个要求:

each selected element has to be within 1 pixel in X and Y from ALL the other members of the solution (so Xi-Xj<=1 and Yi-Yj<=1 for each member of the solution).

大大简化了问题，因为这意味着对于任何给定的 (x_i, y_i) , 只有九种可能的选择 (x_j, y_j).

所以我认为最好的方法如下:

• 复制B和C到sets的 tuples .
• 遍历 A。对于每个点 (x_i, y_i):
  • 从 x_i−1 到 x_{i 遍历 x 的值}+1 和 y 的值从 y_i−1 到 yi +1。对于每个结果点 (x_j, y_j):
    • 检查 (x_j, y_j) 是否在B .如果是这样:
      • 从 max 迭代 x 的值(x_i, x_j)−1 到 min (x_i, x_j)+1 和 y 的值来自max(y_i, y_j)−1 到 min(y< sub>i, y_j)+1。对于每个结果点 (x_k, y_k):
        • 检查 (x_k, y_k) 是否在C .如果是这样，我们就完成了!
• 如果我们走到最后还没有找到匹配项，那就意味着没有匹配项。

这大约需要 O(len(A) + len(B) + len(C) ) 时间和 O(len(B) + len(C) 额外空间。

---

编辑添加(由于评论中的后续问题):如果您有 N 个列表而不是只有 3 个，则不要嵌套 N 循环深度(这使得时间在 N 中呈指数增长)，你会想要做更多像这样的事情:

• 将 B、C 等复制到元组集中，如上所述。
• 遍历 A。对于每个点 (x_i, y_i):
  • 创建一个包含 (x_i, y_i) 及其八个邻居的集合。
  • 对于列表 B、C 等中的每一个:
    • 对于九点集合中的每个元素，查看它是否在当前列表中。
    • 更新集合以删除不在当前列表中的所有点并且在当前列表中没有任何邻居。
  • 如果集合仍然至少有一个元素，那么 — 很好，每个列表都包含一个在该元素的一个像素内的点(所有这些点也都在彼此的一个像素内)。所以，我们完成了!
• 如果我们走到最后还没有找到匹配项，那就意味着没有匹配项。

实现起来要复杂得多，但在 N 中是线性的，而不是在 N 中呈指数。