一种遍历相邻摩尔邻居(Moore Neighborhood)的方法

最后更新于:2022-11-08

摩尔邻居(Moore Neighborhood)定义在二维方格上,由一个中心单元和围绕它的八个单元组成。(摘自 Wikipedia)

moore-neighborhood-with-cardinal-directions

实现方法

  1. 首先找到左上角的坐标(NW)
  2. 横竖各循环3次

    • 当循环的x坐标与中心的x坐标相同循环的y坐标与中心的y坐标相同

      • 直接跳至下一次循环
    • 可能需要检查坐标是否合法(比如是否在边界内)


moore-neighborhood-illegal-example

▲ 中心点为1,红色区域超出区域非法,绿色区域合法

具体代码(C++)

这里的代码会搜索摩尔邻居围绕它的八个单元组成中的最小值,并返回。

// 检查坐标是否合法
bool validCoord(int indexX, int indexY, int gridWidth, int gridHeight) {
    if (indexX < 0 || indexY < 0) {
        return false;
    }
    if (indexX >= gridWidth || indexY >= gridHeight) {
        return false;
    }
    return true;
}

int findMooreMin(int** grid, int gridWidth, int gridHeight,  int cIndexX, int cIndexY) {
    // 找到NW的坐标
    int nIndexX = cIndexX - 1;
    int nIndexY = cIndexY - 1;
    // 将这个坐标对应的值作为目前找到的最小值
    int min = grid[nIndexX][nIndexY];
    // 循环9个格子
    for (int y = nIndexY; y < nIndexY + 3; ++y) {
        for (int x = nIndexX; x < nIndexX + 3; ++x) {
            // 检查当前的格子是否在中心
            if (y == cIndexY && x == cIndexX) {
                continue;
            }
            // 检查坐标是否合法
            if (validCoord(x, y, gridWidth, gridHeight)) {
                // 如果当前坐标对应的值小于min,更新min
                if (grid[y][x] < min) {
                    min = grid[y][x];
                }
            }
        }
    }
    // 返回min
    return min;
}

完整测试代码如下:

#include <iostream>


int findMooreMin(int** grid, int gridWidth, int gridHeight,  int cIndexX, int cIndexY);

int main(int argc, char** argv) {
    // Create a new 3*3 array
    int** array = new int*[3];
    for (int i = 0; i < 3; ++i) {
        array[i] = new int[3];
    }

    // set all values to y*x
    for (int y = 0; y < 3; ++y) {
        for (int x = 0; x < 3; ++x) {
            array[y][x] = y*x;
        }
    }
    // set [y][x] to -10
    array[1][0] = -10;
    int min = findMooreMin(array, 3, 3, 1, 1);

    std::cout << min << std::endl;


    // Remove a 3*3 array
    for (int i = 0; i < 3; ++i) {
        delete[] array[i];
    }
    delete [] array;

    return 0;
}


// 检查坐标是否合法
bool validCoord(int indexX, int indexY, int gridWidth, int gridHeight) {
    if (indexX < 0 || indexY < 0) {
        return false;
    }
    if (indexX >= gridWidth || indexY >= gridHeight) {
        return false;
    }
    return true;
}

int findMooreMin(int** grid, int gridWidth, int gridHeight,  int cIndexX, int cIndexY) {
    // 找到NW的坐标
    int nIndexX = cIndexX - 1;
    int nIndexY = cIndexY - 1;
    // 将这个坐标对应的值作为目前找到的最小值
    int min = grid[nIndexY][nIndexX];
    // 循环9个格子
    for (int y = nIndexY; y < nIndexY + 3; ++y) {
        for (int x = nIndexX; x < nIndexX + 3; ++x) {
            // 检查当前的格子是否在中心
            if (y == cIndexY && x == cIndexX) {
                continue;
            }
            // 检查坐标是否合法
            if (validCoord(x, y, gridWidth, gridHeight)) {
                // 如果当前坐标对应的值小于min,更新min
                if (grid[y][x] < min) {
                    min = grid[y][x];
                }
            }
        }
    }
    // 返回min
    return min;
}

返回值为-10

文章目录

标签: 原创, C++

评论已关闭。 了解详情