如何有效地确定一组点是否包含两个接近的点

Question

我需要确定一组点(每个由浮点元组给出,每个都在[0,1]中)包含两个在彼此的某个阈值(例如0.01)内的点.我还要提一下,在我感兴趣的问题版本中,这些"点"由长度为〜30的元组给出,即它们是[0,1] ^ 30中的点.

我可以使用以下内容测试是否有任何两个在此阈值内:

def is_near(p1, p2):
    return sqrt(sum((x1 - x2)**2 for x1, x2 in zip(p1, p2))) < 0.01  # Threshold.

使用这个我可以使用以下内容检查每一对:

def contains_near(points):
     from itertools import combinations
     return any(is_near(p1, p2) for p1, p2 in combinations(points, r=2))

然而,这在列表的长度上是二次的,这对于我所拥有的长点列表来说太慢了.

有没有解决这个问题的方法？

我尝试过将这些点捕捉到网格中,这样我就可以使用字典/哈希映射来存储它们:

def contains_near_hash(points):
     seen = dict()
     for point in points:
         # The rescaling constant should be 1 / threshold.
         grid_point = tuple([round(x * 100, 0) for x in point])  
         if grid_point in seen:
             for other in seen[grid_point]:
                 if is_near(point, other):
                      return True
             seen[grid_point].append(point)
         else:
             seen[grid_point] = [point]
    return False

但是,这不起作用

points = [(0.1149999,), (0.1150001,)]

由于这些轮到两个不同的网格点.我还尝试了一个版本,其中点被附加到所有相邻网格点,但是我想要做的示例有~30个坐标,每个网格点有2 ^ 30个邻居,这使得这完全不切实际.

Answer 1

如果一对点在至少一个维度上的距离小于阈值,则它们只能彼此"接近".这可以被利用来通过一个接一个地过滤一个维度来减少候选对的数量.

我建议:
- 在一个维度上对点进行排序(比如:x)
- 找到与排序列表中下一个点足够接近的所有点,并将它们的索引放入set候选者中
- 不要使用sqrt()二次距离(x1 - x2)**2,甚至abs(x1 - x2)是效率
- 对第二维也这样做
- 确定两组的相交,这些是彼此靠近的点

这样,您可以避免代价高昂的is_near()呼叫,以较小的集合进行操作,仅使用唯一的点,并且设置查找非常有效.

该方案可以很容易地扩展到包括2个以上的维度.