python - 如何确保元组列表中的最小欧氏距离

Question

我有一个元组列表形式的非常大的坐标列表。

data = [(1,1),(1,11),(1,21),(11,1),(21,1),(11,11),(11,21),(21,11),(21,21),(1,2),(2,1)]

元组列表实际上是由 for 循环和附加命令组成的，如下所示:

data = []
    for i in source: # where i a tuple of form (x,y)
        data.append(i)

是否有一种方法可以确保所有元组之间的欧几里得距离高于某个阈值？在此示例中，(1,1)、(1,2)、(2,1) 之间的距离非常小。在这种情况下，我只想保留 3 个元组中的一个。导致这些新的元组列表之一:

data = [(1,1),(1,11),(1,21),(11,1),(21,1),(11,11),(11,21),(21,11),(21,21)]
data = [(2,1),(1,11),(1,21),(11,1),(21,1),(11,11),(11,21),(21,11),(21,21)]
data = [(1,2),(1,11),(1,21),(11,1),(21,1),(11,11),(11,21),(21,11),(21,21)]

我有一个遍历列表的蛮力算法，但应该有更优雅或更快捷的方法来做到这一点？或者有没有其他方法可以加快这个操作？我期待 ~70k 到 500k 元组的列表。

我的方法:

from scipy.spatial.distance import euclidean
data = [(1,1),(1,11),(1,21),(11,1),(21,1),(11,11),(11,21),(21,11),(21,21),(1,2),(2,1)]
new_data = []
while len(data) >0:
    
    check = data.pop()
    flag = True
    for i in data:
         if euclidean(check,i) < 5:
              flag = False
              break
         else:
              pass
    if flag == True:
        new_data.append(check)
    else:
        flag = True
    
         

补充要点:尽管元组列表来自某个迭代函数，但元组的顺序是不确定的。在 for 循环结束之前，元组的实际数量是未知的。在这种情况下，我宁愿避免使用多处理/多线程来加快速度。如有必要，我可以安排一些时间，但我认为没有必要。我现在的解决方案是时间 O(n(n-1)/2) 和 O(n) 的空间复杂度，我认为任何改进都会更好。

Answer 1

您可以使用 Quadtree 组织您的 2D 数据/元组.

Quadtrees are the two-dimensional analog of octrees and are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.