Самый быстрый способ вычислить расстояния между последовательными векторами с помощью numpy / scipy

Question

У меня есть алгоритм роста линий, где мне нужно:

• вычислить (евклидово) расстояния между последовательными векторами в массиве
• вставить новый вектор, где расстояние большечем определенный порог

Я обычно делаю это очень наивно (см. код ниже) и хотел бы знать Как вычислить расстояния между последовательными векторами самым быстрым способом, используя numpy (и scipy, если необходимо).

import math


threshold = 10
vectorList = [(0, 10), (4, 8), (14, 14), (16, 19), (35, 16)]

for i in xrange(len(vectorList)):
    p1 = vectorList[i]
    p2 = vectorList[i+1]
    d = math.sqrt((p2[0] - p1[0])**2 + (p2[1] - p1[1])**2)
    if d >= threshold:
        pmid = ((p1[0] + p2[0]) * .5, (p1[1] + p2[1]) * .5)
        vectorList.insert(i+1, pmid)

РЕДАКТИРОВАТЬ: я нашел следующий обходной путь, но я все еще обеспокоенрасчет расстояния.

Мне нужно было бы вычислить расстояния между вектором и его следующим соседом в списке вместо вычисления всей матрицы расстояний (все векторы друг против друга), как я делаю здесь.

import numpy as np

vectorList = [(0, 10), (4, 8), (14, 14), (16, 19), (35, 16)]
arr = np.asarray(vectorList).astype(float)


dis = distance.cdist(arr, arr).diagonal(1)
idx = np.where(dis > 10)[0]
vec = (arr[idx] + arr[idx+1]) * .5
arr = np.insert(arr, idx+1, vec, 0)

# output
array([[ 0. , 10. ],[ 4. ,  8. ],[ 9. , 11. ],[14. , 14. ],[16. , 19. ],[25.5, 17.5],[35. , 16. ]])

Answer 1

In [209]: vectorList = [(0, 10), (4, 8), (14, 14), (16, 19), (35, 16), (39,50)] 
In [210]: vectorList                                                            
Out[210]: [(0, 10), (4, 8), (14, 14), (16, 19), (35, 16), (39, 50)]

Я добавил точку, сделав 3 возможных точки вставки.

In [212]: np.diff(vectorList, axis=0)                                           
Out[212]: 
array([[ 4, -2],
       [10,  6],
       [ 2,  5],
       [19, -3],
       [ 4, 34]])
In [213]: np.sum(np.diff(vectorList, axis=0)**2,1)                              
Out[213]: array([  20,  136,   29,  370, 1172])

расстояния:

In [214]: np.sqrt(np.sum(np.diff(vectorList, axis=0)**2,1))                     
Out[214]: array([ 4.47213595, 11.66190379,  5.38516481, 19.23538406, 34.23448554])

Средние значения:

In [216]: arr = np.array(vectorList)                                            
In [217]: arr                                                                   
Out[217]: 
array([[ 0, 10],
       [ 4,  8],
       [14, 14],
       [16, 19],
       [35, 16],
       [39, 50]])

In [218]: (arr[:-1]+arr[1:])/2                                                  
Out[218]: 
array([[ 2. ,  9. ],
       [ 9. , 11. ],
       [15. , 16.5],
       [25.5, 17.5],
       [37. , 33. ]])

Iможет сделать нечто подобное без diff:

d = np.sqrt(np.sum((arr[1:]-arr[:-1])**2,1)) 

Скачки, которые превышают порог:

In [224]: idx = np.nonzero(d>10)                                                
In [225]: idx                                                                   
Out[225]: (array([1, 3, 4]),)
In [227]: _218[idx]       # the mean values to insert                                                            
Out[227]: 
array([[ 9. , 11. ],
       [25.5, 17.5],
       [37. , 33. ]])

Используйте np.insert для вставки всех значений.

In [232]: np.insert(arr.astype(float), idx[0]+1, _227, axis=0)                  
Out[232]: 
array([[ 0. , 10. ],
       [ 4. ,  8. ],
       [ 9. , 11. ],
       [14. , 14. ],
       [16. , 19. ],
       [25.5, 17.5],
       [35. , 16. ],
       [37. , 33. ],
       [39. , 50. ]])

Answer 2

Вот подход с использованием sklearn NearestNeighbors

from sklearn.neighbors import NearestNeighbors
import numpy as np

def distance(p1,p2):
    return np.sqrt(np.sum(np.diff([p1,p2], axis=0)**2,1))

def find_shortest_distance(vectorList):
    nbrs = NearestNeighbors(n_neighbors=2, metric=distance).fit(vectorList)
    distances, indices = nbrs.kneighbors(vectorList)

    result = distances[:, 1]
    return result

vectorList = [(0, 10), (4, 8), (14, 14), (16, 19), (35, 16)]

, который возвращает:

result
Out[57]: array([ 4.47213595,  4.47213595,  5.38516481,  5.38516481, 19.23538406])

Это может быть излишним для вашей проблемы, но это решение не 't требует, чтобы точки были в последовательном порядке.

Время (медленнее, чем numpy):

%timeit find_shortest_distance(vectorList)
478 µs ± 2.68 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)