c++ - 如何迭代栅格网格中的环？

Question

我们处于二维空间中的任何给定位置。该空间被划分为二次单元。我想遍历给定距离内的所有单元格，按照它们与我们的距离顺序。例如，这可能发生在尺寸增加的环中。距离几乎相等的单元格的顺序无关紧要。

如何按到给定位置的距离顺序遍历这些单元格？

score 2 · Accepted Answer

如果简化为整数网格坐标是可以的（正如您对“几乎相等距离”的评论所暗示的那样），您可以使用下面的代码随着距离的增加逐个遍历单元格。如果您的起点与 (0,0) 不同，则只需将其添加到每个生成的点。关键思想是：

从我们开始，我们以逆时针方向(d,0)迭代地寻找具有“相似”距离（整数部分 = ）的相邻点，直到我们到达起点。d(0,0)
每个点（除了我们来自的邻居）最多有一个具有“相似”距离的直接邻居（通过边缘）。如果没有直接邻居，则恰好有一个具有“相似”距离的对角邻居（同样除了前一个邻居）。
到下一个邻居的向量“几乎”正交于到原点的向量。

这是代码：

#include <cmath>
#include <vector>

template <typename T> int sgn(T val) {
    return (T(0) < val) - (val < T(0));
}

int dist(double dx, double dy)
{
    return (int)sqrt(dx*dx + dy*dy);
}

typedef std::pair<int,int> TPoint;
typedef std::vector<TPoint> TPoints;

void generateNeighbourRing(int d, TPoints& ring)
{
    int dx = d;
    int dy = 0;
    do
    {
        ring.push_back(TPoint(dx,dy));
        int nx = -sgn(dy);
        int ny = sgn(dx);
        if (nx != 0 && dist(dx+nx, dy) == d)
            dx += nx;
        else if (ny != 0 && dist(dx, dy+ny) == d)
            dy += ny;
        else
        {
            dx += nx;
            dy += ny;
        }
    } while (dx != d || dy != 0);
}

int main()
{
    TPoints points;
    const int d_max = 4;
    for (int d = 0; d <= d_max; ++d)
        generateNeighbourRing(d, points);
    printf("spiral for dmax=%d (%d points):\n", d_max, points.size());
    for (unsigned int i=0; i<points.size(); ++i)
        printf(" (%d,%d),", points[i].first, points[i].second);
    printf("\n");
}