python - 在三个数组中找到最近的三个 x,y 点

Question

在 Python 中，我有三个包含 x 和 y 坐标的列表。每个列表包含 128 个点。如何高效地找到最近的三个点？

这是我的工作 python 代码，但它不够高效:

   def findclosest(c1, c2, c3):
       mina = 999999999
       for i in c1:
          for j in c2:
             for k in c3:
                # calculate sum of distances between points
                d = xy3dist(i,j,k)
                if d < mina:
                   mina = d

    def xy3dist(a, b, c):
       l1 = math.sqrt((a[0]-b[0]) ** 2 + (a[1]-b[1]) ** 2 )   
       l2 = math.sqrt((b[0]-c[0]) ** 2 + (b[1]-c[1]) ** 2 )   
       l3 = math.sqrt((a[0]-c[0]) ** 2 + (a[1]-c[1]) ** 2 )       
       return l1+l2+l3

知道如何使用 numpy 完成此操作吗？

Answer 1

您可以使用 Numpy 的广播功能来矢量化两个内部循环:

import numpy as np

def findclosest(c1, c2, c3):
   c1 = np.asarray(c1)
   c2 = np.asarray(c2)
   c3 = np.asarray(c3)

   for arr in (c1, c2, c3):
       if not (arr.ndim == 2 and arr.shape[1] == 2):
           raise ValueError("expected arrays of 2D coordinates")

   min_val = np.inf
   min_pos = None

   for a, i in enumerate(c1):
       d = xy3dist(i, c2.T[:,:,np.newaxis], c3.T[:,np.newaxis,:])
       k = np.argmin(d)

       if d.flat[k] < min_val:
           min_val = d.flat[k]
           b, c = np.unravel_index(k, d.shape)
           min_pos = (a, b, c)

       print a, min_val, d.min()

   return min_val, min_pos

def xy3dist(a, b, c):
   l1 = np.sqrt((a[0]-b[0]) ** 2 + (a[1]-b[1]) ** 2 )   
   l2 = np.sqrt((b[0]-c[0]) ** 2 + (b[1]-c[1]) ** 2 )   
   l3 = np.sqrt((a[0]-c[0]) ** 2 + (a[1]-c[1]) ** 2 )       
   return l1+l2+l3

np.random.seed(1234)
c1 = np.random.rand(5, 2)
c2 = np.random.rand(9, 2)
c3 = np.random.rand(7, 2)

val, pos = findclosest(c1, c2, c3)

a, b, c = pos
print val, xy3dist(c1[a], c2[b], c3[c])

也可以向量化所有 3 个循环

def findclosest2(c1, c2, c3):
    c1 = np.asarray(c1)
    c2 = np.asarray(c2)
    c3 = np.asarray(c3)
    d = xy3dist(c1.T[:,:,np.newaxis,np.newaxis], c2.T[:,np.newaxis,:,np.newaxis], c3.T[:,np.newaxis,np.newaxis,:])
    k = np.argmin(d)
    min_val = d.flat[k]
    a, b, c = np.unravel_index(k, d.shape)
    min_pos = (a, b, c)
    return min_val, min_pos

如果您的数组非常大，findclosest 可能比 findclosest2 更好，因为它使用的内存更少。 (如果你的数组很大，只向量化最里面的一个循环。)

你可以在谷歌上搜索“numpy broadcasting”来了解更多 np.newaxis 的作用