Fastest computation of distances in rectangular array

Question

I'm looking for the fastest way to compute a lot of distances from some origin in a an image to every other point. Right now, what I have is something like this:

origin = [some_val,some_other_val]
y,x = np.mgrid[:image.shape[0],:image.shape[1]].astype(float)    
r = np.hypot(y-origin[0],x-origin[1])

Is there a faster way? I saw this answer, but I'm not sure how to apply it.

I meant to convey that I all the distances I want are within some rectangular space. — , Sep 14 '15 at 23:19

Divakar · Accepted Answer · 2015-09-14T17:34:15.303

Let's bring some broadcasting into play -

m,n= image.shape
r = np.sqrt((np.arange(m)[:,None]-origin[0])**2 + (np.arange(n)-origin[1])**2)

Runtime tests and verify results

Define functions -

In [115]: def broadcasting_based(origin,image_shape):
     ...:     m,n= image_shape
     ...:     return np.sqrt((np.arange(m)[:,None]-origin[0])**2 + (np.arange(n)-origin[1])**2)
     ...: 
     ...: 
     ...: def original_approach(origin,image_shape):
     ...:     y,x = np.mgrid[:image_shape[0],:image_shape[1]].astype(float)    
     ...:     return np.hypot(y-origin[0],x-origin[1])
     ...:

Case # 1:

In [116]: origin = np.array([100,200])

In [117]: np.allclose(broadcasting_based(origin,[500,500]),original_approach(origin,[500,500]))
Out[117]: True

In [118]: %timeit broadcasting_based(origin,[500,500])
100 loops, best of 3: 3.28 ms per loop

In [119]: %timeit original_approach(origin,[500,500])
10 loops, best of 3: 21.2 ms per loop

Case # 2:

In [123]: origin = np.array([1000,2000])

In [124]: np.allclose(broadcasting_based(origin,[5000,5000]),original_approach(origin,[5000,5000]))
Out[124]: True

In [125]: %timeit broadcasting_based(origin,[5000,5000])
1 loops, best of 3: 460 ms per loop

In [126]: %timeit original_approach(origin,[5000,5000])
1 loops, best of 3: 2.96 s per loop

score 1 · Answer 2 · answered Sep 14 '15 at 17:43

Apart from the other answers, you should definitely answer the question whether you need the distance, or if your problem can be solved with just the square of the distance. E.g. if you want to know the nearest one, this can be perfectly done with the square.

This would save you an expensive square root calculation for each point pair.

Fastest computation of distances in rectangular array

2 Answers2