二维矩阵中两个单元格之间的距离

Question

我有一个表示为值向量的二维矩阵，一个索引表示第一个单元格，一对坐标表示第二个单元格。

vector<double> matrix;
auto index = 10;

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

我需要找出这两个单元格之间的距离，其中 8 个相邻单元格的第一个 "ring" 距离等于 1，第二个环单元格的距离等于 2，依此类推。

有没有比欧氏距离更快的方法？

Answer 1

您需要的是修改后的 Manhattan Distance。我认为您的用例可能有一个特定的名称，但我不知道。不管怎样，我就是这样做的。

假设这两个点相距 x 行和 y 列。那么x+y就是曼哈顿距离。但在你的情况下，对角线移动也是允许的。因此，如果您最初沿对角线移动到该点，您将覆盖 x 和 y 中较小的一个，而另一个则剩余一些。然后您可以移动 horizontally/vertically 以完成剩余的距离。因此，您的度量距离为 max(x,y).

给定点 (x1,y1) 和 (x2,y2)，答案是 max(|x1-x2|,|y1-y2|)

二维矩阵中两个单元格之间的距离

Distance between two cells in a 2D matrix

c++

matrix

euclidean-distance