c - 如何将二维数组重复 segmentation 或分割成更小的象限？

Question

我正在尝试将 2^n x 2^n 二维数组拆分为 4 个象限。然后我想在这些象限中搜索信息。如果所有象限数组元素 = 1 或 0，则可以保留该象限。如果象限混合有 1 和 0，那么我想继续拆分数组，直到只剩下 1 或 0 的象限(即使这是单个数组元素)。我知道我必须实现一个递归函数，但我似乎不知道如何......这是我到目前为止所拥有的。非常感谢任何帮助!

node* split(int **image_array, int width){
 node* root = NULL;
 int i, j;
 int black_pixel_NW = 0, black_pixel_NE = 0, black_pixel_SE = 0, black_pixel_SW = 0;


 if (width >= 2){


     for (i = 0; i < width/2; i++)   {
         for (j = 0; j < width/2; j++){
             printf("(%d,%d) = %d\n", i, j, image_array[i][j]);
             if (image_array[i][j] == 0){
                 black_pixel_NW = ++black_pixel_NW;
             }
         }
     }
     printf("\nBlack pixels NW = %d\n", black_pixel_NW);


     for (i = width/2; i < width; i++)   {
         for (j = 0; j < width/2; j++){
             printf("(%d,%d) = %d\n", i, j, image_array[i][j]);
             if (image_array[i][j] == 0){
                 black_pixel_NE = ++black_pixel_NE;
             }
         }
     }
     printf("\nBlack pixels NE = %d\n", black_pixel_NE);


             for (i = width/2; i < width; i++)   {
         for (j = width/2; j < width; j++){
             printf("(%d,%d) = %d\n", i, j, image_array[i][j]);
             if (image_array[i][j] == 0){
                 black_pixel_SE = ++black_pixel_SE;
             }
         }
     }
    printf("\nBlack pixels SE = %d\n", black_pixel_SE);


     for (i = 0; i < width/2; i++)   {
         for (j = width/2; j < width; j++){
             printf("(%d,%d) = %d\n", i, j, image_array[i][j]);
             if (image_array[i][j] == 0){
                 black_pixel_SW = ++black_pixel_SW;
             }
         }
     }
     printf("\nBlack pixels SW = %d\n", black_pixel_SW);

     width = width / 2;

 }

 return root;}

该代码将用于读取二进制图像文件，因此包含 black_pixel 变量。 black_pixel_NW 表示左上象限中黑色像素的数量。我在函数中有指针的东西，因为这些信息最终将存储在四叉树中。

Answer 1

当将函数分解为绝对原始状态时，递归是最容易理解的。您实际上将逻辑编写了 4 次。

最明显的解决方案(对我来说!)是稍微扩展函数参数。像这样的东西:

split(int **img, int x, int y, int width, int height);

仅将逻辑放入单个象限，然后递归遍历四个象限中的每一个。喜欢:

if (all_pixels_same_color) return; // or do something
else {
 split(img, x, y, width/2, height/2); // Top left Quadrant
 split(img, x + width/2, y, width/2, height/2); // Top right Q.
 split(img, x, y + height/2, width/2, height/2); // Bottom left Q.
 split(img, x + width/2, y + height/2, width/2, height/2); // Bottom right Q.
}

现在要查看图像的每个像素，只需从图像的完整尺寸开始

split(img, 0, 0, 256, 256);

该函数会将其视为一个象限，并且很可能会分成另外四个象限(使用四个新的起始象限位置调用自身四次)。

编辑: 检查象限中所有像素是否具有相同值的示例:

if (width == 1 || height == 1)
 return; // or something else

int i, j;
int cmp = img[x][y]; // top-left pixel

for (j = y; j < height; j++)
 for (i = x; i < width; i++)
   if (img[i][j * IMG_WIDTH] != cmp)
    goto split_to_quads; // or whatever