For loop on two arrays of points

Question

I have two arrays of points: list1 with list1.shape = [N, 3] and list2 with list2.shape = [M, 3]. Within N, M: the total number of point, (x, y, z) are 3 coordinates in 3D.

Now I want to check if each point of list1 is within a distance r with each point of list2. A nature way to do this is a for loop:

for i in range(N):
    for j in range(M):
        if (list1[i, 0] - list2[j, 0])**2 + (list1[i, 1] - list2[j, 1])**2 + (list1[i, 2] - list2[j, 2])**2 < r**2:
        ''' Return 1 if list1[i] is within list2[j] '''
            return True
        else:
        ''' Return 0 if list1[i] is not within list2[j] '''
            return False

But it's horribly slow. Could I do the more efficient way?

May be k-d tree is the solution? http://en.wikipedia.org/wiki/K-d_tree — Dmitry Bychenko, Mar 11 '14 at 14:33
The nicest solution for a euclidean distance matrix is in this **question** : http://stackoverflow.com/questions/3518574/why-does-looping-beat-indexing-here . Replace one 'Data' with list1 and the other with list2 — jarondl, Mar 11 '14 at 14:38
Your code would overwrite `a[i]` multiple times, and only the value `j==M-1` would matter. How do you actually need it to behave? — interjay, Mar 11 '14 at 14:38

score 1 · Answer 1 · answered Mar 11 '14 at 14:49

1

You can use the outer operations to calculate the distance matrix without the for loops:

s = np.subtract.outer

d_matrix = s(list1[:,0], list2[:,0])**2
d_matrix += s(list1[:,1], list2[:,1])**2
d_matrix += s(list1[:,2], list2[:,2])**2

Where each line is the distance of point i about all points. To find out if point i is close to any point using your criterion:

a = np.zeros_like(list1[:,0])
a[np.any(d_matrix < r**2, axis=1)] = 1

answered Mar 11 '14 at 14:49

Saullo G. P. Castro

56,802
26
179
234

@user2863620 but you should give a try in K-d Tree, since it calculates only the upper triangle of the `d_matrix` and therefore is more efficient (if you need) – Saullo G. P. Castro Mar 11 '14 at 14:54
With M, N is small. Kd-Tree seems not be faster than the brute force way. – user2863620 Mar 11 '14 at 14:58

For loop on two arrays of points

1 Answers1