矩阵的簇（阵列）

所以。我在C工作，我需要一些帮助。我有一个矩阵（数组）（我现在不是如何翻译它的权利：D），它只有0和1。例如，您可能看起来像这样： 1 1 0 0 0 0 1 1 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1矩阵的簇（阵列）

现在。我需要从中提取包含1的簇。你能写一些关于如何处理这个问题的想法吗？我尝试了一个结构和一个指向它的指针，结构包含2个元素：x和y，x表示原始矩阵中的x坐标，y表示矩阵中的y坐标。然后，对于每个群集，它将如下所示： cluster[0][0].x = 0; cluster[0][0].y = 0; cluster[0][1].x = 1; cluster[0][1].y = 0; cluster[0][2].x = 0; cluster[0][2].y = 1; ..等等。但是我在迭代中遇到了一些问题（我有一个1000 * 1000的矩阵），我决定问你是否有其他想法。谢谢。

编辑：这些是在这个例子中，簇：

1： 1 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2： 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

3： 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0

4： 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1

EDIT2：所以。从1和0的矩阵中，我需要提取所有相邻的“1”的组。相邻意味着在其左上或右下与其位置相邻。至于第一个簇将是从矩阵开始的那些5“1”组成的那个簇。另一个群集应该是第2行第4列只包含一个“1”。我需要以某种方式将每个群集的x和y坐标存储在某处，因为我需要稍后使用它们。

来源

2015-01-09 Lazar Lucian-Ionut

什么是“集群”这里的信息来源？任何方向上都带有相邻的'1'的任何'1'？ – Evert

是的，但只能向左下方，不在对角线上。对于这个例子，有4个集群。 –

尽管如此，您仍然处于正确的轨道：您可以在双重循环中逐步浏览2D矩阵的元素，并且对于每个是1的元素，都可以上下左右（“+1” '，'-1'到行或列索引）以查看它是否包含'1'。有可能更聪明的方式，但这将是最直接的方式。您需要另一个矩阵来跟踪已属于某个集群的元素。 – Evert

对于字符串数据，只是一个数组

char map[1000][1000]

是将使用1兆字节的内存，这是不是有很多这些天。

，因为我看到它是

找到矩阵中的1，
做就可以了洪水填充（例如，改变1到2或0）
然后继续searhcing算法对于矩阵中的1。

返回转换所有1所需的填充数。

洪水填充是一个众所周知的算法，你应该能够找到一个合适的例子，或者可能使用图形库。

来源

2015-01-09 11:36:38 Jasen

一个简单的FPGA实现

使用回溯来获取所有集群，让我们从（0,0）开始作为一个例子，我们首先检查是否（0,0）为1，如果是这样，检查它的邻居一个一个。如果其中一个邻居是1，那么移动并按照相同的方式进行检查。这个过程不会停止，直到位置的四个方向邻居全部为0或被访问。

要记录我们访问的位置，我们需要一个与原点数组大小相同的标志图。另外，为了绘制每个簇，在回溯期间，我们同时记录每个位置，我选择一组列表来保存簇中的所有位置。

这里是所有的代码，包括您发表

#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 
#include <assert.h> 

#define MAX_COL  6 
#define MAX_ROW  5 
#define MAX_SIZE (MAX_COL * MAX_ROW) 

int a[5][6] = { 
    1, 1, 0, 0, 0, 0, 
    1, 1, 0, 1, 0, 0, 
    1, 0, 0, 0, 0, 1, 
    0, 0, 1, 1, 0, 1, 
    0, 0, 1, 0, 1, 1, 
}; 

int dir_x[4] = {0, 1, 0, -1}; 
int dir_y[4] = {1, 0, -1, 0}; 

struct point { 
    int x; 
    int y; 
}; 

struct node { 
    struct point pos; 
    struct node *next; 
}; 

struct node* cluster_set[MAX_SIZE]; 
int cluster_set_index = 0; 

int is_inside(int height, int width, int i, int j) 
{ 
    if (0 <= j && j < width && i >= 0 && i < height) 
     return 1; 
    return 0; 
} 

int cluster_check(int (*matrix)[MAX_COL], int height, int width, int row, int col, int (*flag_matrix)[MAX_COL], struct node* head) 
{ 
    int i, tmp_x, tmp_y; 
    flag_matrix[row][col] = 1; 

    for (i = 0; i < 4; i++) 
    { 
     tmp_x = row + dir_x[i]; 
     tmp_y = col + dir_y[i]; 
     if (is_inside(height, width, tmp_x, tmp_y) && matrix[tmp_x][tmp_y] && !flag_matrix[tmp_x][tmp_y]) { 
      flag_matrix[tmp_x][tmp_y] = 1; 
      struct node *new_node = (struct node*)malloc(sizeof(struct node)); 
      assert(new_node != NULL); 
      new_node -> pos.x = tmp_x; 
      new_node -> pos.y = tmp_y; 
      new_node -> next = NULL; 
      head -> next = new_node; 
      cluster_check(matrix, height, width, tmp_x, tmp_y, flag_matrix, new_node); 
     } 
    } 
} 

int cluster_count(int (*matrix)[MAX_COL], int height, int width) 
{ 
    int count = 0, i, j; 
    int flag_matrix[MAX_ROW][MAX_COL] = {0}; 

    for (i = 0; i < height; i++) 
     for (j = 0; j < width; j++) 
     { 
      if (matrix[i][j] && !flag_matrix[i][j]) { 
       count++; 
       struct node *new_node = (struct node*)malloc(sizeof(struct node)); 
       assert(new_node != NULL); 
       new_node -> pos.x = i; 
       new_node -> pos.y = j; 
       new_node -> next = NULL; 
       cluster_set[cluster_set_index++] = new_node; 
       cluster_check(matrix, height, width, i, j, flag_matrix, new_node); 
      } 
     } 
    return count; 
} 

void print_cluster(int (*map)[MAX_COL], int row, int col) 
{ 
    int i, j; 
    for (i = 0; i < row; i++) 
    { 
     for (j = 0; j < col; j++) 
      printf("%2d ", map[i][j]); 
     printf("\n"); 
    } 
    printf("\n"); 
} 


int main() 
{ 
    printf("total clusters: %d\n", cluster_count(a, 5, 6)); 
    int i, cluster_map[MAX_ROW][MAX_COL] = {0}; 
    struct node *tmp; 
    for (i = 0; i < cluster_set_index; i++) 
    { 
     tmp = cluster_set[i]; 
     while (tmp != NULL) { 
      printf("(%d, %d)", tmp->pos.x, tmp->pos.y); 
      cluster_map[tmp->pos.x][tmp->pos.y] = 1; 
      tmp = tmp -> next; 
     } 
     printf("\n"); 
     print_cluster(cluster_map, MAX_ROW, MAX_COL); 
     memset(cluster_map, 0x00, sizeof(int)*MAX_ROW*MAX_COL); 
    } 
}

这里测试用例的运行结果，只是忽略你不需要

total clusters: 4 
(0, 0)(0, 1)(1, 1)(1, 0)(2, 0) 
1 1 0 0 0 0 
1 1 0 0 0 0 
1 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

(1, 3) 
0 0 0 0 0 0 
0 0 0 1 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 

(2, 5)(3, 5)(4, 5)(4, 4) 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 1 
0 0 0 0 0 1 
0 0 0 0 1 1 

(3, 2)(4, 2) 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 0 0 0 0 
0 0 1 0 0 0 
0 0 1 0 0 0

来源

2015-01-09 16:31:15

矩阵的簇（阵列）

回答

相关问题