У меня есть 2D-матрица, представленная в виде вектора значений, индекса, представляющего первую ячейку, и пары координат, представляющей вторую ячейку.
vector<double> matrix;
auto index = 10;
auto x1 = index % width;
auto y1 = index / width;
auto x2 = ...
auto y2 = ...
Мне нужно найти расстояние между этими двумя ячейками, где расстояние равно 1 для первого «кольца» из 8 соседних ячеек, 2 для второго кольца и так далее.
Есть ли способ быстрее, чем евклидово расстояние?
Вам нужно что-то вроде модифицированного Манхэттенское расстояние. Я думаю, что для вашего варианта использования может быть конкретное имя, но я его не знаю. Во всяком случае, я бы так поступил.
Предположим, что две точки находятся на расстоянии x строки и y столбца. Тогда x+y — это Манхэттенское расстояние. Но в вашем случае допустимы и диагональные движения. Таким образом, если вы изначально двигались по диагонали к точке, вы бы покрыли меньшее из x и y, а некоторое количество осталось в другом. Затем вы можете двигаться по горизонтали/вертикали, чтобы покрыть оставшееся расстояние. Следовательно, расстояние по вашей метрике будет max(x,y).
Учитывая точки (x1,y1) и (x2,y2), ответ будет max(|x1-x2|,|y1-y2|)
