python - 在 Python 的两个列表中查找几乎相同的点

Question

我有一组点(经度/纬度)，其中每组代表离散全局网格的一部分。对于每个网格点，我试图找到与其相邻的所有其他网格点，因此至少共享一个顶点。大多数情况下，网格点完美对齐，因此我通常可以使用 any(i for i in point1 if i in point2) 之类的命令找到所有相邻的网格(参见下面的 MWE)。

不幸的是，我的数据集中似乎存在一些浮点精度错误，因此在某些情况下两个顶点几乎相同，但又不完全相同。

point1 = [(177.4150316259643, 80.06868164738896),
          (162.04772459076872, 80.29781125179436),
          (153.403148072541, 82.32650976966762),
          (165.2980351177718, 84.62501223785691),
          (-168.7499999978935, 83.98251402600364),
          (-168.74999999845744, 81.58268534624698)]

# point2[3] and point2[4] should match point1[0] and point1[5]
point2 = [(-157.50739908371222, 77.7317781763434),
          (-168.75000000105112, 76.80636446168572),
          (-179.99260091805525, 77.73177817832965),
          (177.41503162596428, 80.06868164738897),
          (-168.7500000015425, 81.58268534399583),
          (-154.91503162867107, 80.06868164543069)]

print(any([i for i in point1 if i in point2]))
# False

# adjust point2[3] so that it matches point1[0]
point2[3] = (177.4150316259643, 80.06868164738896)

print(any([i for i in point1 if i in point2]))
# True

是否有计算效率高的方法来解决此问题并找到几乎相同或在一定公差范围内相同的值？

Answer 1

您可以尝试以下方法:

point1 = [(177.4150316259643, 80.06868164738896),
          (162.04772459076872, 80.29781125179436),
          (153.403148072541, 82.32650976966762),
          (165.2980351177718, 84.62501223785691),
          (-168.7499999978935, 83.98251402600364),
          (-168.74999999845744, 81.58268534624698)]

point2 = [(-157.50739908371222, 77.7317781763434),
          (-168.75000000105112, 76.80636446168572),
          (-179.99260091805525, 77.73177817832965),
          (177.41503162596428, 80.06868164738897),
          (-168.7500000015425, 81.58268534399583),
          (-154.91503162867107, 80.06868164543069)]


import numpy as np

# set tolerance to control how close values need to be 
# to be considered the same
tolerance = 10**(-6) 

p1 = np.array(point1)[:, np.newaxis, :]
p2 = np.array(point2)[np.newaxis, :, :]
(np.linalg.norm(p1 - p2, axis=2) < tolerance).nonzero()

返回:

(array([0, 5]), array([3, 4]))

这意味着point1[0]和point2[3]很接近，同样对于 point1[5] 和 point2[4]

如果您只想知道是否有一些接近的值，您可以将最后一行替换为:

(np.linalg.norm(p1 - p2, axis=2) < tolerance).any()

给出:

True