Duplicate removal within a certain distance in Python

Question

I have two numpy.arrays of points (shapes (m,2) and (n,2)) like this:

A = numpy.array([[1,2],[3,4]])
B = numpy.array([[5,6],[7,8],[9,2]])

I need to merge them into an array with the next condition:

If there are two points with distance less or equal to epsilon, just leave one

I have this code, but it's so slow:

import numpy as np

eps = 0.1
A = np.array([[1,2],[3,4]])
B = np.array([[5,6],[7,8],[9,2]])

for point in B:
    if not (np.amin(np.linalg.norm(A-point)) <= eps):
        A = np.append(  A ,  [point], axis=0)

What is the best way to do that using numpy?

Thanks a lot!

Answer 1

You could calculate a Delaunay triangulation first, from which a list of neighboring points can easily be extracted:

import numpy as np
from itertools import product
from scipy.spatial import Delaunay

eps = 3.  # choose value, which filters out some points
A = np.array([[1,2],[3,4]])
B = np.array([[5,6],[7,8],[9,2]])

# triangulate points:
pts = np.vstack([A, B])
tri = Delaunay(pts)

# extract all edges:
si_idx = [[0, 1], [0, 2], [1, 2]]  # edge indeces in tri.simplices
edges = [si[i] for si, i in product(tri.simplices, si_idx)]
dist_edges = [np.linalg.norm(tri.points[ii[0]] - tri.points[ii[1]])
              for ii in edges]  # calculate distances

# list points which are closer than eps:
for ee, d in zip(edges, dist_edges):
    if d < eps:
        print("|p[{}] - p[{}]| = {}".format(ee[0], ee[1], d))

As @David Wolever already noted, it is not clear from your question, how to exactly remove the points from the merged list.