计算网格上两点之间的距离
计算网格上两点之间的距离
提问于 2015-05-21 08:41:38
我需要计算网格上两点之间的距离。允许的移动是水平的和垂直的，以及对角的下一个邻居(所以45度旋转)。
所以曼哈顿的距离不是一种选择。此外，欧几里德距离不是一个选项，因为它没有沿着网格正确移动，这可能导致一个到低值(如在红线中)。
我在寻找距离，就像绿线，它从一个细胞移动到另一个细胞。
这个公式最好是快速的。
Stack Overflow用户
回答已采纳
发布于 2015-05-21 08:47:28
这很简单：
- 你朝着目标的对角线移动，直到你在同一排或同一目标上。这将是最小(dx，dy)步骤。 让我们称它为d(对于对角线步骤)
- 然后你沿着一条直线向目标移动。这将是最大的(dx，dy) -d步骤。 让我们称其为s(用于直线级)
- 距离为√2×d+ s。
代码：
double distance(int x1, int y1, int x2, int y2) {
int dx = abs(x2 - x1);
int dy = abs(y2 - y1);
int min = min(dx, dy);
int max = max(dx, dy);
int diagonalSteps = min;
int straightSteps = max - min;
return sqrt(2) * diagonalSteps + straightSteps;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/30368632
复制相关文章
相似问题
腾讯云开发者
