Расстояние между двумя ячейками в 2D-матрице

Question

У меня есть 2D-матрица, представленная как вектор значений, индекс, представляющий первую ячейку, и пару координат, представляющих вторую ячейку.

vector<double> matrix; 
auto index = 10; 

auto x1 = index % width; 
auto y1 = index/width; 
auto x2 = ... 
auto y2 = ... 

мне нужно найти расстояние между этими двумя ячейками, где расстояние равно 1 для первого «кольца» из 8 соседних ячеек, 2 для второго кольца, и так далее.

Есть ли способ быстрее, чем евклидово расстояние?

Answer 1

Что вам нужно, это что-то вроде модифицированного Manhattan Distance. Я думаю, что может быть определенное имя для вашего случая использования, но я этого не знаю. Во всяком случае, так я и сделал бы это.

Предположим, что две точки: x ряды и y колонок. Затем x+y - расстояние Манхэттен. Но в вашем случае также разрешены диагональные движения. Итак, если вы перенесли по диагонали к точке вначале, вы покроете меньшую из x и y, а оставшаяся часть останется в другой. Затем вы можете перемещаться горизонтально/вертикально, чтобы покрыть оставшееся расстояние. Следовательно, расстояние по вашей метрике будет max(x,y).

заданных точек (x1,y1) и (x2,y2), ответ будет max(|x1-x2|,|y1-y2|)