CODEWITHSUNDEEP
python
ramzeek
ramzeek

Reputation: 2315

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

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?

Upvotes: 3

Views: 881

Answers (2)

bb1
bb1

Reputation: 7863

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

Upvotes: 1

SequenceToSequence
SequenceToSequence

Reputation: 514

Since you're dealing with coordinates, you could just use a radius. You can set a threshold so that if another point falls within a certain radius, it will be considered similar.

def similar(point1, point2, threshold):
  return threshold^2 - (point1[0]-point2[0])^2 + (point1[1]-point2[1])^2 > 0

If true, they are almost the same, if false, they are not.

Upvotes: 1

Related Questions