Поиск ближайших трех x, y точек в трех массивах

Question

В Python у меня есть три списка, содержащие координаты x и y. Каждый список содержит 128 баллов. Как я могу найти наиболее близкие три точки эффективным способом?

Это мой рабочий код питона, но не достаточно эффективно:

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 

If your arrays are very big, findclosest может быть лучше, чем findclosest2, как он использует меньше памяти. (И если ваши массивы огромны, векторизовать только один внутренний цикл.)

Вы можете Google для «Numpy вещания», чтобы узнать больше, что делает np.newaxis

Answer 2

Давайте попробуем синхронизацию несколько различных решений, чтобы увидеть.

Я собираюсь инициализировать три массива, используя случайные функции numpy. Если у вас есть существующие переменные, которые являются списками кортежей или списков списков, просто позвоните на них np.array.

import numpy as np 

c1 = np.random.normal(size=(128, 2)) 
c2 = np.random.normal(size=(128, 2)) 
c3 = np.random.normal(size=(128, 2)) 

---

время начала давайте свой код так, мы имеем отправную точку.

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 
    return mina 

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 

%timeit findclosest(c1, c2, c3) 
# 1 loops, best of 3: 23.3 s per loop 

---

Одна из функций, которые могут быть полезны в scipy.spatial.distance.cdist, который вычисляет все попарные расстояния между двумя массивами точек. Поэтому мы можем использовать это, чтобы заранее вычислить и сохранить все расстояния, а затем просто получить и добавить расстояния от этих массивов. Я также собираюсь использовать itertools.product, чтобы упростить цикл, хотя он не будет работать с ускорением.

from scipy.spatial.distance import cdist 
from itertools import product 

def findclosest_usingcdist(c1, c2, c3): 
    dists_12 = cdist(c1, c2) 
    dists_23 = cdist(c2, c3) 
    dists_13 = cdist(c1, c3) 

    min_dist = np.inf 
    ind_gen = product(range(len(c1)), range(len(c2)), range(len(c3))) 
    for i1, i2, i3 in ind_gen: 
     dist = dists_12[i1, i2] + dists_23[i2, i3] + dists_13[i1, i3] 
     if dist < min_dist: 
      min_dist = dist 
      min_points = (c1[i1], c2[i2], c3[i3]) 

    return min_dist, min_points 

%timeit findclosest_usingcdist(c1, c2, c3) 
# 1 loops, best of 3: 2.02 s per loop 

Таким образом, используя cdist покупает нам порядок величины ускорения.

---

Это, однако, даже не сравнимо с ответом @ pv. Реализация его с некоторыми материалами ушла, чтобы лучше сравнивать предыдущие решения (см. Ответ @ pv для реализации, который возвращает точки).

def findclosest2(c1, c2, 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] 
    i1, i2, i3 = np.unravel_index(k, d.shape) 
    min_points = (c1[i1], c2[i2], c3[i3]) 
    return min_val, min_points 

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 

%timeit findclosest_usingbroadcasting(c1, c2, c3) 
# 100 loops, best of 3: 19.1 ms per loop 

Так что это массовое ускорение и, безусловно, правильный ответ.