我有一个包含 2 个点的 NxN 网格,即源点和目标点。我需要一步一步地从源头移动到目的地(它也在移动)。我如何确定下一个要移动到的点?
一种方法是评估所有 8 个点,并使用欧几里德距离查看哪个点产生的距离最短。但是,我希望有一个很酷的(数学)技巧可以产生更优雅的结果。
最佳答案
你的问题陈述允许沿对角线移动,这更快(因为它在一个步骤中同时水平移动和垂直):这个解决方案将始终这样做,除非它具有与以下相同的 x 或 y 坐标目标。
using Position = pair<int,int>;
Position move(Position const ¤t, Position const &target) {
// horizontal and vertical distances
const int dx = target.first - current.first;
const int dy = target.second - current.second;
// horizontal and vertical steps [-1,+1]
const int sx = dx ? dx/abs(dx) : 0;
const int sy = dy ? dy/abs(dy) : 0;
return { current.first + sx, current.second + sy };
}
虽然我不确定这是否算作一个很酷的数学技巧,但它只取决于知道:
dx = target.x-current.x
如果您应该朝正 x 方向移动则为正,如果您应该朝负方向移动则为负,如果您应该直线向上则为零/向下dx/abs(dx)
保留符号并删除大小,因此它始终是-1,0,+1
之一(但要避免被零除)
关于c++ - 从源开始,在 C++ 中找到最接近网格上目标的下一个点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/42249118/