Removing Points From List If Distance Between 2 Points Is Below A Certain Threshold

I have a list of points and I want to keep the points of the list only if the distance between them is greater than a certain threshold. So, starting from the first point, if the t

Solution 1:

Not a fancy one-liner, but you can just iterate the values in the list and append them to some new list if the current value is greater than the last value in the new list, using [-1]:

lst = range(10)
diff = 3new = []
for n in lst:
    if not new or abs(n - new[-1]) >= diff:
        new.append(n)

Afterwards, new is [0, 3, 6, 9].

---

Concerning your comment "What if i had instead a list of coordinates (x,y)?": In this case you do exactly the same thing, except that instead of just comparing the numbers, you have to find the Euclidean distance between two points. So, assuming lst is a list of (x,y) pairs:

ifnotnewor((n[0]-new[-1][0])**2 + (n[1]-new[-1][1])**2)**.5 >= diff:

Alternatively, you can convert your (x,y) pairs into complex numbers. For those, basic operations such as addition, subtraction and absolute value are already defined, so you can just use the above code again.

lst = [complex(x,y) for x,y in lst]

new = []
for n in lst:
    if not new or abs(n - new[-1]) >= diff:  # same as in the first version
        new.append(n)
print(new)

Now, new is a list of complex numbers representing the points: [0j, (3+3j), (6+6j), (9+9j)]

Solution 2:

While the solution by tobias_k works, it is not the most efficient (in my opinion, but I may be overlooking something). It is based on list order and does not consider that the element which is close (within threshold) to the maximum number of other elements should be eliminated the last in the solution. The element that has the least number of such connections (or proximities) should be considered and checked first. The approach I suggest will likely allow retaining the maximum number of points that are outside the specified thresholds from other elements in the given list. This works very well for list of vectors and therefore x,y or x,y,z coordinates. If however you intend to use this solution with a list of scalars, you can simply include this line in the code orig_list=np.array(orig_list)[:,np.newaxis].tolist()

Please see the solution below:

import numpy as np

thresh = 2.0

orig_list=[[1,2], [5,6], ...]

nsamp = len(orig_list)
arr_matrix = np.array(orig_list)
distance_matrix = np.zeros([nsamp, nsamp], dtype=np.float)

for ii inrange(nsamp):
    distance_matrix[:, ii] = np.apply_along_axis(lambda x: np.linalg.norm(np.array(x)-np.array(arr_matrix[ii, :])),
                                                              1,
                                                              arr_matrix)


n_proxim = np.apply_along_axis(lambda x: np.count_nonzero(x < thresh),
                               0,
                               distance_matrix)

idx = np.argsort(n_proxim).tolist()
idx_out = list()

for ii in idx:
    for jj inrange(ii+1):
        if ii notin idx_out:
            if self.distance_matrix[ii, jj] < thresh:
                if ii != jj:
                    idx_out.append(jj)

pop_idx = sorted(np.unique(idx_out).tolist(),
                 reverse=True)

for pop_id in pop_idx:
    orig_list.pop(pop_id)

nsamp = len(orig_list)