Finding points that are almost the same in two lists in Python

Question

I have a bunch of sets of points (longitudes/latitudes), where each set represents part of a discrete global grid. For each grid point, I am trying to find all the other grid points that are adjacent to it and therefore share at least one vertex. Most of the time the grid points line up perfectly and so I can usually find all the adjacent grids with a command like any(i for i in point1 if i in point2) (see MWE below).

Unfortunately, there seem to be some floating point precision errors in my dataset so there are cases where two vertices are almost identical, but not quite.

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

Is there a computationally efficient way to solve this problem and find values that are almost the same, or the same within some tolerance?

Answer 1

You can try the following:

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()

This returns:

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

It means that point1[0] and point2[3] are close, and likewise for point1[5] and point2[4]

If you just want to know if there are some close values you can replace the last line with:

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

which gives:

True