How to compute distance between cells in a 2D grid on Python

user_10557442 0
Viewed 834

My example is close to that of the question Python: how to compute the distance between cells?, but what I want is to calculate the distance between 2 cells taking into account that the distance between adjacent cells is always 1 (including diagonals). Let me explain:

Suppose I have the following 2D grid:

20  21  22  23  24
15  16  17  18  19
10  11  12  13  14
5   6   7   8   9
0   1   2   3   4

What I want is a function that as an argument has 2 cell indices and return the distance between them, so that the distance between adjacent cells is 1 (diagonal cells are adjacent too).

I've tried with something like this:

import numpy as np
import numba as nb

@nb.njit # to speed up the code with numba
def distance(a,b,n=5):
    x1 = a%n;  x2 = b%n;
    y1 = a//n; y2 = b//n
    return np.floor(np.sqrt( (x1-x2)**2 + (y1-y2)**2 ))

However, this works for some cells but not for others, for example:

>>> distance(2,7)
1.0 # works!
>>> distance(3,11)
2.0 # works!
>>> distance(0,24)
5.0 # wrong! it should be 4.0
>>> distance(0, 23)
5.0 # wrong! it should be also 4.0

I mean, I think linear distances are well calculated but diagonal distances aren't all

cell distance numpy python
1 Answers

Try:

def distance(a, b, n=5):
    x1, x2 = a%n, b%n
    y1, y2 = a//n, b//n
    dx = abs(x1 - x2)
    dy = abs(y1 - y2)
    return max([dx, dy])

>>> distance(2,7)
1
>>> distance(3,11)
2
>>> distance(0,24)
4
>>> distance(0, 23)
4

Explanation:

We can imagine that if we want to get from point a to point b in the shortest distance possible, we want to first exhaust as many diagonal moves as possible. Without diagonals, we would have had to make dx + dy number of moves, however since we can move in a diagonal direction, we can effectively move in both directions in a single move. This means the smaller of the two (dx and dy) become irrelevant since if dy = 10 and dx = 5, we already need to move 10 in the vertical direction, so we can capture 5 moves in the horizontal direction by coverting 5 of those vertical moves into diagonal moves. Thus, the answer is max([dx, dy]).

user_110704630
Related