检查相邻网格的最有效方法

Question

假设我有一个由大小为 NxN 的二维数组 A 表示的大方形网格，并且通过其坐标将一个点分配给其中一个网格。每个网格都被八个相邻的网格包围（想想键盘上的数字键盘，5 号被 1、2、3、4、6、7、8、9 包围）。

现在我会为每个相邻的网格做一些事情，但是数组中的一些元素可能没有八个相邻的网格。如果它在寄宿生之一，那么它只有五个邻居（比如 2 号只被 1、3、4、5、6 包围），如果它在四个角之一，那么它只被包围三个邻居。给定数组 A 的一个元素，如何以最有效的方式检查它的邻居？我可以设置很多if语句来查看它的数组索引是否大于0或小于N-1，但是如何对这些if语句进行分组（嵌套）以便需要最少的步骤？

谢谢

Answer 1

如果您不希望每个元素检查几个条件，您可以对 "safe" 个元素使用 for 循环 i=1,j=1; i<N-1 && j<N-1; i++,j++。

然后使用循环遍历每一行，就像这样 j=1;j<N-1;j++ {check array[0][j] and array[N-1][j] 和 i.

一样

现在，您只需要检查边角即可。

通过这种方式，没有元素会检查比它必须检查的更多的条件。

Answer 2

pt: (i,j )
if(i>0 &&j>0&& i<n-1&&j<n-1){
//not a border element.
}
else{
  if(i+j == 0|| i+j == n-1 || i+j == 2(n-1)){
     //four corner points ie #neighbour = 3
  }
  else{
     //boundary points with #neighbour = 5
  }
}

Answer 3

我认为您将不得不对不同的方法进行计时。这是直接从一个简单的 "Game of Life" 程序中截取的，它计算周围 white 细胞的数量。

无论你用哪种方式切分，你最终都会得到很多 ifs 和 buts。所以我决定采用这种非常明显的方法，我首先修改循环的开始和结束变量：

unsigned count_neighbours(const sf::Image& img, unsigned x, unsigned y)
{
    unsigned c = 0;

    auto Nx = img.getSize().x;
    auto Ny = img.getSize().y;

    unsigned xb = x ? x - 1 : x;
    unsigned yb = y ? y - 1 : y;
    unsigned xe = (x == Nx - 1) ? Nx : x + 2;
    unsigned ye = (y == Ny - 1) ? Ny : y + 2;

    for(auto xi = xb; xi < xe; ++xi)
        for(auto yi = yb; yi < ye; ++yi)
            if(xi != x || yi != y)
                if(img.getPixel(xi, yi) == sf::Color::White)
                    ++c;
    return c;
}

Answer 4

@ClsForCookies 的解决方案非常出色，因为绝大多数节点都是内部节点，不需要任何测试。

无论如何，这只有在您可以自由强加访问顺序并且您同意复制代码时才有用。

所以现在我假设您事先不知道节点索引。

一种选择是使用在网格周围有额外边距的位数组。位告诉你是否出格。

另一种是使用与原始网格相同大小的代码数组（或向节点添加属性）。该代码将告诉您节点配置（左上角、上边缘...）。有九种情况。对于每九个可能的值，您可以预先存储现有邻居的可能位移列表（3 到 8 种可能性）。

无需存储整个 9 码数组，您可以使用公式

计算它们

Code = (0 < i + 2 * (i >= N)) + 3 * (0 < j + 2 * (j >= N))

要限制存储，您还可以将代码的 i 和 j 部分预存储在两个一维数组中。

最后，您可以使用以下方案扫描(i, j)：

if i > 0:
    i--
    if j > 0:
        j--; Process; j++
    Process
    if j < N-1:
        j++; Process; j--
    i++
if j > 0:
    j--; Process; j++
if j < N-1:
    j++; Process; j--
if i < N-1:
    i++
    if j > 0:
        j--; Process; j++
    Process
    if j < N-1:
        j++; Process; j--
    i--

不幸的是，内部节点的成本最高（8 次测试）。

检查相邻网格的最有效方法

most efficient way to check neighbouring grid

c++

arrays

algorithm

grid