Как вычислить расстояние между ячейками в 2D-сетке на Python - PullRequest
Новая
       7

Как вычислить расстояние между ячейками в 2D-сетке на Python

3 голосов
/ 06 мая 2020

Мой пример близок к примеру вопроса Python: как вычислить расстояние между ячейками? , но я хочу рассчитать расстояние между двумя ячейками с учетом того, что расстояние между соседние ячейки всегда равны 1 (включая диагонали). Позвольте мне объяснить:

Предположим, у меня есть следующая 2D-сетка: 

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

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

Я пробовал что-то вроде этого: 

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 ))

Однако это работает для некоторых ячеек, но не для других , например: 

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

Я имею в виду, я думаю, что линейные расстояния хорошо рассчитаны, но диагональные расстояния не все

1 Ответ

3 голосов
/ 06 мая 2020

Попробуйте: 

def distance(a, b, n=5):
    x1 = a%n;  x2 = b%n;
    y1 = a//n; y2 = 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

Пояснение:

Мы можем представить, что если мы хотим добраться от точки a до точки b на кратчайшем расстоянии возможно, мы хотим сначала исчерпать как можно больше диагональных ходов. Без диагоналей нам пришлось бы сделать dx + dy количество ходов, однако, поскольку мы можем двигаться по диагонали, мы можем эффективно двигаться в обоих направлениях за одно движение. Это означает, что меньший из двух (dx и dy) становится неактуальным, поскольку если dy = 10 и dx = 5, нам уже нужно переместить 10 в вертикальном направлении, поэтому мы можем зафиксировать 5 ходов за горизонтальное направление за счет покрытия 5 из этих вертикальных перемещается в диагональные движения. Таким образом, ответ будет max([dx, dy]).

...