Кластеры матрицы (массива)
Так. Я работаю в 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
РЕДАКТИРОВАТЬ 2: Итак. Из этой матрицы 1 и 0 и мне нужно извлечь все группы смежных "1". Смежный означает соседний вверх или вниз, влево или вправо от своего положения. Что касается первого кластера, то он будет составлен из тех 5 "1", которые находятся в начале матрицы. Другим кластером будет тот, который содержит только одну "1" в строке 2 столбца 4. И мне нужно как-то хранить координаты x и y каждого кластера где-нибудь, так как мне нужно будет использовать их позже.
2 ответа
Простая реализация
Воспользуйтесь обратным отслеживанием, чтобы получить все кластеры, давайте начнем с (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
Для строки данных, просто массив
char map[1000][1000]
это будет использовать 1 мегабайт памяти, что не так много в наши дни.
Алгоритм, как я вижу это
- найти
1в матрице, - выполнить заливку (например, изменение
1в2или0) - затем продолжайте поиск для
1в матрице.
вернуть количество заливок, необходимое для преобразования всех 1s.
Flood fill - это хорошо известный алгоритм, вы должны найти подходящий пример или использовать графическую библиотеку.