Python - intersecting Numpy 2D arrays

Question

I am desperately looking for an effective way to check if two 2D numpy arrays intersect.

So, I have two arrays with an arbitrary number of 2D arrays, for example:

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

All I need is True, if there is at least one vector intersecting with another one from another array, otherwise false. Therefore, it should give such results:

f(A,B)  -> True
f(A,C)  -> False

I'm a little new to python, and first I wrote my program with Python lists, which works, but of course is very inefficient. The program takes several days to complete, so I'm working on a solution now numpy.array, but these arrays are really not that easy to use.

Here is some context about my program and Python list solution:

, , - 3 . http://en.wikipedia.org/wiki/Self-avoiding_walk. , , (, , 1000 ), , :

"" N:

X=[]
for i in range(0,N+1):
    X.append((i,0,0))

:

• ( "pivotelement" )
• ( , )
• 9 (3 * 3 90 °, 180 °, 270 °)
• ,
• → , else → .

1.-6. (, 1000, ~ 5000 ), . :

def PivotFold(chain):
randPiv=random.randint(1,N)  #Chooses a random pivotelement, N is the Chainlength
Pivot=chain[randPiv]  #get that pivotelement
C=[]  #C is going to be a shifted copy of the chain
intersect=False
for j in range (0,N+1):   # Here i shift the hole chain to get the pivotelement to the origin, so i can use simple rotations around the origin
    C.append((chain[j][0]-Pivot[0],chain[j][1]-Pivot[1],chain[j][2]-Pivot[2]))
rotRand=random.randint(1,18)  # rotRand is used to choose a direction and a Rotation (2 possible direction * 9 rotations = 18 possibilitys)
#Rotations around Z-Axis
if rotRand==1:
    for j in range (randPiv,N+1):
        C[j]=(-C[j][1],C[j][0],C[j][2])
        if C[0:randPiv].__contains__(C[j])==True:
            intersect=True
            break
elif rotRand==2:
    for j in range (randPiv,N+1):
        C[j]=(C[j][1],-C[j][0],C[j][2])
        if C[0:randPiv].__contains__(C[j])==True:
            intersect=True
            break
...etc
if intersect==False: # return C if there was no intersection in C
    Shizz=C
else:
    Shizz=chain
return Shizz

PivotFold () X . , , , ^^ , numpyarrays , , ...

Answer 1

:

In [11]:

def f(arrA, arrB):
    return not set(map(tuple, arrA)).isdisjoint(map(tuple, arrB))
In [12]:

f(A, B)
Out[12]:
True
In [13]:

f(A, C)
Out[13]:
False
In [14]:

f(B, C)
Out[14]:
False

? OK, set . numpy.array list ? , tuple. .

A numpy :

In [34]:

(A[...,np.newaxis]==B[...,np.newaxis].T).all(1)
Out[34]:
array([[False, False],
       [ True, False],
       [False, False]], dtype=bool)
In [36]:

(A[...,np.newaxis]==B[...,np.newaxis].T).all(1).any()
Out[36]:
True

:

In [38]:
#Dan method
%timeit set_comp(A,B)
10000 loops, best of 3: 34.1 µs per loop
In [39]:
#Avoiding lambda will speed things up
%timeit f(A,B)
10000 loops, best of 3: 23.8 µs per loop
In [40]:
#numpy way probably will be slow, unless the size of the array is very big (my guess)
%timeit (A[...,np.newaxis]==B[...,np.newaxis].T).all(1).any()
10000 loops, best of 3: 49.8 µs per loop

numpy RAM , A[...,np.newaxis]==B[...,np.newaxis].T 3D-.

Answer 2

, , :

def make_1d_view(a):
    a = np.ascontiguousarray(a)
    dt = np.dtype((np.void, a.dtype.itemsize * a.shape[1]))
    return a.view(dt).ravel()

def f(a, b):
    return len(np.intersect1d(make_1d_view(A), make_1d_view(b))) != 0

>>> f(A, B)
True
>>> f(A, C)
False

( +0.0 -0.0 ), np.intersect1d , , . , np.intersect1d , np.any .

Answer 3

np.tile np.swapaxes !

def intersect2d(X, Y):
        """
        Function to find intersection of two 2D arrays.
        Returns index of rows in X that are common to Y.
        """
        X = np.tile(X[:,:,None], (1, 1, Y.shape[0]) )
        Y = np.swapaxes(Y[:,:,None], 0, 2)
        Y = np.tile(Y, (X.shape[0], 1, 1))
        eq = np.all(np.equal(X, Y), axis = 1)
        eq = np.any(eq, axis = 1)
        return np.nonzero(eq)[0]

, , .

Answer 4

, O (n ^ 2), for-loop, numpythonic. , numpy

def set_comp(a, b):
   sets_a = set(map(lambda x: frozenset(tuple(x)), a))
   sets_b = set(map(lambda x: frozenset(tuple(x)), b))
   return not sets_a.isdisjoint(sets_b)

Answer 5

, , true, ! :

def(A,B):
 for i in A:
  for j in B:
   if i==j
   return True
 return False 

Answer 6

This problem can be effectively solved with the numpy_indexed package (disclaimer: I am the author):

import numpy_indexed as npi
len(npi.intersection(A, B)) > 0