Minimum distance between two points of multiple arrays-CodePudding

I have multiple arrays of shape (12,3). Suppose they are Q, V, R, S. These arrays are actually xyz coordinates (atomic symbols omitted) For a sample, I am trying to calculate the smallest distance between a particle in Q and a particle in V array. Apart from that, I want the xyz component of the smallest distance. For a output distance and xyz component, I create two arrays and append distance and xyz components values to them. Here is my code,

import numpy as np
xyz_QV=[]; r_QV=[]

def min_distance(A,B):
        diff=10**20
        for i in A:
            for j in B:
                k=np.linalg.norm(i-j)
                if  k < diff:
                    diff = k
                    #xyz_QV.append(i-j)
        xyz_QV.append(i-j)
        return diff
    print('r_min=',min_distance(V,Q))
    r_QV.append(min_distance(V,Q))
xyz_QV=np.array(xyz_QV)
print(xyz_QV)
print(r_QV)

I have checked manually that distance array is okay, but the xyz component I am getting is wrong and instead of one row of xyz, I am getting two rows. Any help please.

Additionally, If I want to find the same for QS and RS, what do I need to modify in the function?

Thanks in Advance..

Edit 1: providing sample arrays

Q= [[ 0.71264532  1.1209957   0.06054078]
 [ 1.35784165  1.98639917  0.12773717]
 [ 1.25823573 -0.1592519   0.12423352]
 [ 2.32495428 -0.28709988  0.24674303]
 [ 0.42688496 -1.27452666  0.04265043]
 [ 0.85044465 -2.26843268  0.09474995]]
R=[[ 0.42688496 -1.27452666  0.04265043]
 [ 0.85044465 -2.26843268  0.09474995]
 [-0.94957784 -1.11007406 -0.1003136 ]
 [-1.5944557  -1.9762737  -0.16371348]
 [-1.49552564  0.17105056 -0.16154602]
 [-2.56378279  0.29922115 -0.27370311]]
V=[[ 1.82750755  1.11126079  3.25188149]
 [ 2.47235268  1.97744454  3.31563221]
 [ 2.37346068 -0.16989031  3.31340122]
 [ 3.44166756 -0.29803736  3.42614544]
 [ 1.5418112  -1.28549041  3.23475079]
 [ 1.9648929  -2.27984284  3.28440446]]

The output I am getting is

r_min= 3.069280599179459
[[ 1.11444826 -0.01141016  3.18965451]
 [ 1.11444826 -0.01141016  3.18965451]]
[3.069280599179459]

CodePudding user response：

Note: this answer relies on scipy.

You can get all pairwise distances between two arrays using scipy's spatial.distance module:

from scipy.spatial.distance import cdist


QV_dist = cdist(Q, V)
q_idx, v_idx = np.unravel_index(QV_dist.argmin(), QV_dist.shape)
min_QV_dist = QV_dist[q_idx, v_idx]
xyz = Q[q_idx] - V[v_idx]

Wrapping this up in a function (note the np.abs() on the xyz components, which you may or may not want):

from typing import Tuple
from itertools import combinations as combs
from scipy.spatial.distance import cdist


def min_dist_and_xyz(A: np.ndarray, B: np.ndarray) -> dict:
    AB_dist = cdist(A, B)
    A_i, B_i = np.unravel_index(AB_dist.argmin(), AB_dist.shape)
    return {"dist": AB_dist[A_i, B_i], "xyz": np.abs(A[A_i] - B[B_i])}


def all_min_dists(arrs: Tuple[np.ndarray], labels: str) -> dict:
    distances = {}
    # Cycle through all pair-wise combinations of arrays
    for (x_lbl, x), (y_lbl, y) in combs(dict(zip(labels, arrs)).items(), 2):
        distances[f"{x_lbl}{y_lbl}"] = min_dist_and_xyz(x, y)
    return distances

Usage (I rounded the output separately for the sake of displaying the data):

>>> Q, V, R, S = np.random.random((4, 12, 3))
>>> all_min_dists(arrs=(Q, V, R, S), labels="QVRS")
{'QV': {'dist': 0.14817, 'xyz': array([0.13026, 0.04566, 0.05387])},
 'QR': {'dist': 0.06003, 'xyz': array([0.01459, 0.05818, 0.00255])},
 'QS': {'dist': 0.04912, 'xyz': array([0.03048, 0.02257, 0.03121])},
 'VR': {'dist': 0.18245, 'xyz': array([0.12439, 0.06326, 0.11754])},
 'VS': {'dist': 0.14755, 'xyz': array([0.02883, 0.12283, 0.0765 ])},
 'RS': {'dist': 0.13614, 'xyz': array([0.12737, 0.04761, 0.00664])}}

CodePudding user response：

IIUC, you are trying to find the minimum distance between every particle in Q and every particle in V. On top of that, you want to get those particles as well.

Here is a completely vectorized way of what you are trying to do.

You can use the same method np.linalg.norm(particle1-particle2)
You can create 2 addition axis in the Q and V matrix such that you have a way of broadcasting the operation you want to get a cross product between particles in Q and V.

Q    -> 12  , None , 3
V    -> None, 12   , 3
---------------------
Q-V  -> 12  , 12   , 3
---------------------
norm -> 12  , 12
---------------------
min  -> 1

Which results in 12, 12, 3 matrix which can be reduced with np.linalg.norm with axis=-1 to a 12, 12 matrix. This is the distance between every 12 particles in Q vs every 12 ones in V.
Now, it's just a matter of finding the minimum in this matrix
To get the index in Q and index in V for particles that result in this minimum distance, you can use np.unravel_index to get them and then index Q and V post that.

#Creating 2 dummy lists of particles
Q = np.random.random((12,3))
V = np.random.random((12,3))

#distance between every particle in Q vs V (resuting in 12,12 matrix)
distances = np.linalg.norm(Q[:,None,:]-V[None,:,:], axis=-1) 

#Get index position for Q and V particles with min dist
idx = np.unravel_index(distances.argmin(), distances.shape)

#Find particle Q and particle V which result in min distance
particleQ, particleV = Q[idx[0]], V[idx[1]]

print(particleQ)
print(particleV)

[0.60751186 0.93177959 0.23249369]
[0.64406579 0.91601754 0.27724177]

To prove that these particles have the minimum distance between them.

print('Minimum distance between Q and V particles:', distances.min())
print('Distance between the above calculated particleQ & particleV', np.linalg.norm(particleQ-particleV))

Minimum distance between Q and V particles: 0.11540521863305497
Distance between the above calculated particleQ & particleV 0.11540521863305497

As a function

def find_dist(Q, V):
    #distance between every particle in Q vs V (resuting in 12,12 matrix)
    distances = np.linalg.norm(Q[:,None,:]-V[None,:,:], axis=-1) 
    idx = np.unravel_index(distances.argmin(), distances.shape)
    particleQ, particleV = Q[idx[0]], V[idx[1]]
    
    return distances.min(), (particleQ, particleV), distances

QR_min, QR_particles, _ = find_dist(Q,R)
QV_min, QV_particles, _ = find_dist(Q,V)
RV_min, RV_particles, _ = find_dist(R,V)

print('Arrays Q, R')
print('Min distance:', QR_min)
print('Particle with min distance Q', QR_particles[0])
print('Particle with min distance R', QR_particles[1])
print('')
print('Arrays Q, V')
print('Min distance:', QV_min)
print('Particle with min distance Q', QV_particles[0])
print('Particle with min distance V', QV_particles[1])
print('')
print('Arrays R, V')
print('Min distance:', RV_min)
print('Particle with min distance R', RV_particles[0])
print('Particle with min distance V', RV_particles[1])
print('')

Arrays Q, R
Min distance: 0.0
Particle with min distance Q [ 0.42688496 -1.27452666  0.04265043]
Particle with min distance R [ 0.42688496 -1.27452666  0.04265043]

Arrays Q, V
Min distance: 3.0692806011237583
Particle with min distance Q [ 2.32495428 -0.28709988  0.24674303]
Particle with min distance V [ 2.37346068 -0.16989031  3.31340122]

Arrays R, V
Min distance: 3.3621077448250167
Particle with min distance R [ 0.85044465 -2.26843268  0.09474995]
Particle with min distance V [ 1.5418112  -1.28549041  3.23475079]