如何计算2D矩阵中2个点之间的距离

Question

我是这个网站的新手,也是C的新手.我需要一个程序来找到所有点的平均"跳跃".

这个想法是这样的:找到从1到2,1到3,1到4 ... 1到9的"跳跃"距离,或找到2到1,2到3,2到4到5等.

在第一行执行这些操作非常简单,只需(2-1)或(3-1)即可获得正确的数字.但如果我想找到1到4或1到8之间的距离,那么我完全不知道.矩阵的尺寸应该可以改变.但我只想要一个3x3矩阵的帮助.

任何人都可以告诉我如何找到它？

跳跃意味着从一个点到另一个点的垂直或水平移动.从1到2 = 1,从1到9 = 4(仅限最短路径)

Answer 1

_{让我们定义“跳跃”距离：“从 A 点 [A x} ,A _y ] 到达 B 点 [B _x ,B _y ]所需的跳跃数”。

现在可以通过两种方式允许跃点：

1. 水平/垂直
   在这种情况下，您可以向上/向下或向左/向右移动。由于您必须独立移动 X 轴和 Y 轴，因此您的答案是：
   jumpDistance = abs(Bx - Ax) + abs(By - Ay);

2. 水平/垂直以及对角线
   在这种情况下，您可以向上/向下或向左/向右以及对角线移动。不同之处在于Case 1，现在您只需跳跃一次即可同时更改 X 轴和 Y 轴。现在你的答案是：
   jumpDistance = Max(abs(Bx - Ax),abs(By - Ay));

Answer 2

对这类问题的"距离"定义总是很棘手.

想象一下,这些点是场上的标记,你可以自由地遍布它.然后,您可以从一个点到另一个点采取任何路径.那么最短的路线就是一条直线; 它的长度是连接点的向量的长度,恰好是两个点位置之间的差异向量.这个长度可以在毕达哥拉定理的帮助下计算出来:dist = sqrt((x2-x1)^2 + (y2-y1)^2).这被称为点之间的欧几里德距离.

现在假设你在一个城市,每个点都是一座建筑.你不能走过建筑物,所以唯一的选择是向上/向下或向左/向右.然后,最短距离由差矢量的分量之和给出; 这是一种数学方式,说"向下走2个街区然后向左走一个街区"意味着走3个街区的距离:dist = abs(x2-x1) + abs(y2-y1).这被称为点之间的曼哈顿距离.

然而,在您的问题中,看起来唯一可能的移动是跳转到相邻点,只需一步,允许对角线.然后问题变得有点棘手,因为路径非常不规则.这里需要一些图论,在对链接元素或"节点"的问题进行建模时非常有用.每个点都是一个节点,连接到它们的邻居,问题是找到到另一个给定点的最短路径.如果跳跃有不同的权重(例如,在对角线上跳跃更难),解决这个问题的一个简单方法就是使用Dijkstra算法; 关于维基百科实施的更多细节.

如果成本始终相同,则问题将减少到计算从源到目标点的广度优先搜索中的跳转次数.