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

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

vector<double> matrix;
auto index = 10;

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

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

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

2

Решение

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

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

Заданные баллы (x1,y1) а также (x2,y2)ответ будет max(|x1-x2|,|y1-y2|)

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]