在C中聚类 [英] clustering in C
问题描述
有人可以帮助我进行C编程吗。
如果我有
x是一个0'和1'的2D数组
ex：x = array（[1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0]，
[1,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0]，
[1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0]，
[0， 0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0]）
我想要的是一个边界框在我们发现的区域中，我们发现了一堆的价值。所以例如在上面的列表中，前3个roes和colums有1'的
所以那个区域的那个盒子是3x3
所以我的最后一个阵列应该有一系列的群集
1'就像
coords = [（x1，y1 ，x2，y2），....]
其中x1，y1 - >左上角
x2，y2 - >那个矩形的右下角。
希望我对我的问题很清楚。
[0,0,0,0,0，
+ ----- +
0，| 1,1，| 0,0，
| |
0，| 0,1，| 0,0，
+ ----- +
0,0,0， 0,0]
如上所述。结果数组应该具有每个这样的框的
的面积。这就像洪水填充算法。
我希望算法返回所有矩形。不仅仅是
最小的。
qu*****@gmail.com 写道：有人可以帮我解决C编程问题。
< snip>
你好querypk ;，
google for Hoshen-Kopelman算法...
Jan
< qu ***** @ gmail.com>写了有人可以在这里帮助我进行C编程。
如果我有
x是一个0'和1'的2D数组
ex： x =数组（[1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0]，
[1,1 ，1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0]，
[1,1,1,0,1,1 ，1,0,1,1,0,1,1,1,0,0,0,0]，
[0,0,0,0,0,0,0,0,1,1 ，0,0,0,0,0,0,0,0]）
我想要的是在我们发现
1'的集群的区域上的边界框。例如，在上面的列表前3个roes和colums有1'的
所以那个盒子的面积是3x3
所以我的最后一个数组应该有一系列的
1'的集群像
coords = [（x1，y1，x2，y2），....]
其中x1，y1 - >左上角
x2，y2 - >那个矩形的右下角。
希望我对我的问题很清楚。
[0,0,0,0,0，
+ ----- +
0，| 1,1，| 0,0，
| |
0，| 0,1，| 0,0，
+ ----- +
0,0,0,0,0]
像上面的东西。结果阵列应该具有每个这样的盒子的区域。这就像洪水填充算法。
我希望算法返回所有矩形。不仅仅是
最小的。
首先要做的是分配一个临时的整数数组。将那些
设置为1，将零设置为零。
然后迭代数组。当你击中一个，做一个洪水填充，填充
与2,3,4等像这样
void floodfill（int * array，int x，int y，int width，int height，int fill）
{
if（x< 0 || x> = width）
返回;
如果（y <0 || y> =身高）
返回;
if（array [y * width + x] == fill）
return;
if（array [y * width + x] == 0）
return ;
数组[y * width + x] =填充;
floodfill（数组，x + 1，y，宽度，高度，填充）;
floodfill（数组，x - 1，y，宽度，高度，填充）;
floodfill（数组，x，y + 1，宽度，高度，填充）;
floodfill（数组，x，y -1，宽度，高度，填充）;
}
结果数组应为零列表，从2起集群。另外
记住你找到了多少个簇。
现在分配一个矩形结构数组和一个标志数组。设置
所有的falgs为零。
第二次迭代数组。当你达到非零值时，检查
标志。如果清楚，您就拥有了集群的顶点。如果数组相对较小并且时间不是很关键，那么从左上方的列向下找到左边的点来迭代
可能是最容易的。从底部向上搜索
以找到最低点，然后从右边向上列
找到正确的点。
（如果你有一个巨大的阵列和小群集，你可以再次使用洪水填充搜索群集
，并存储最大和最小点数。）
然后设置标志标记你已经找到了这个集群的矩形的事实，并继续直到你到达阵列的末尾。
hi jburgy ，
这种帮助我绑定修改代码，而不是
聚类1'它会集群0'只是为了更好地理解
算法..但我想我犯了一些错误，它确实没有做现在它所做的事情。
逆转。你能在这帮吗？基本上我正在努力
了解。我应该在C代码中改变什么才能使它适用于0
聚类而不是1'..
int hoshen_kopelman（int ** matrix ，int m，int n）{
uf_initialize（m * n / 2）;
/ *扫描矩阵* /
i i = 0; i< m; i ++）
for（int j = 0; j< n; j ++）
if（！matrix [i] [j]）{//如果被占用...
int up =（i == 0？0：matrix [i-1] [J]）; //查找
printf（"％d \ n"，up）;
int left =（j == 0？0：matrix [i] [ J-1]）; //向左看
开关（!!向上+ !!左）{
案例0：
matrix [i] [j] = uf_make_set（）; //一个新的集群
休息;
案例1：//现有集群的一部分
矩阵[i] [ j] = max（向上，向左）; //无论是非零是
标记
休息;
案例2：//此网站绑定两个集群
矩阵[i] [j] = uf_union（向上，向左）;
休息;
}
}
/ *将重新贴标签应用于矩阵* /
/ *这有点偷偷摸摸..我们创建一个映射来自
规范标签
由工会决定/找到一套新的规范标签，其中
是
保证顺序。 * /
int * new_labels = calloc（sizeof（int），n_labels）; //分配数组，
初始化为零
for（int i = 0; i< m; i ++）
for （int j = 0; j< n; j ++）
if（matrix [i] [j]）{
int x = uf_find（matrix [i] [j ]）;
if（new_labels [x] == 3）{
new_labels [0] ++;
new_labels [x] = new_labels [0];
}
矩阵[i] [j] = new_labels [x];
}
int total_clusters = new_labels [0];
免费（new_labels）;
uf_done（）;
返回total_clusters;
}
我将if（matrix [i] [j]）插入if（！matrix [i] [j]）但它没有更新其他集群。
http://splorg.org:8080/people/tobin/...nkopelman/hk.c
Can someone help me with C programming here.
If I have
x is a 2D array of 0''s and 1''s
ex: x = array([1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0],
[0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0])
what I want is a boundingbox over the region where we find clusters of
1''s.So for instance in the above list first 3 roes and colums have 1''s
so the area of that box is 3x3
so my final array should have an array of clusters of
1''s like
coords = [ (x1,y1,x2,y2), ....]
where x1,y1 -> top left point
x2,y2 -> bottom right point of that rectangle.
Hope I am clear with my question.
[0, 0, 0, 0, 0,
+-----+
0,|1, 1,|0, 0,
| |
0,|0, 1,|0, 0,
+-----+
0, 0, 0, 0, 0]
something like above. The resultant array should have the area of the
each such box. SOmething like a flood fill algorithm.
I would like the algorithm to return all the rectangles .Not just the
minimum ones.
qu*****@gmail.com wrote:Can someone help me with C programming here.
<snip>
Hi there "querypk",
google for Hoshen-Kopelman algorithm...
Jan
<qu*****@gmail.com> wroteCan someone help me with C programming here.
If I have
x is a 2D array of 0''s and 1''s
ex: x = array([1,1,1,0,0,0,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,0,0,0,0,0,1,1,1,1,0,0,0],
[1,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0],
[0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0])
what I want is a boundingbox over the region where we find clusters of
1''s.So for instance in the above list first 3 roes and colums have 1''s
so the area of that box is 3x3
so my final array should have an array of clusters of
1''s like
coords = [ (x1,y1,x2,y2), ....]
where x1,y1 -> top left point
x2,y2 -> bottom right point of that rectangle.
Hope I am clear with my question.
[0, 0, 0, 0, 0,
+-----+
0,|1, 1,|0, 0,
| |
0,|0, 1,|0, 0,
+-----+
0, 0, 0, 0, 0]
something like above. The resultant array should have the area of the
each such box. SOmething like a flood fill algorithm.
I would like the algorithm to return all the rectangles .Not just the
minimum ones.
First thing to do is to allocate a temporary array of integers. Set the ones
to one and the zeroes to zero.
Then iterate over the array. When you hit a one, do a flood fill, filling
with 2, 3, 4 etc, like this
void floodfill(int * array, int x, int y, int width, int height, int fill)
{
if(x < 0 || x >= width)
return;
if(y < 0 || y >= height)
return;
if(array[y * width + x] == fill)
return;
if(array[y * width + x] == 0)
return;
array[y * width + x] = fill;
floodfill(array, x + 1, y, width, height, fill);
floodfill(array, x - 1, y, width, height, fill);
floodfill(array, x, y + 1, width, height, fill);
floodfill(array, x, y -1, width, height, fill);
}
The resulting array should be a list of zeroes, and clusters from 2 up. Also
keep a count of how many clusters you have found.
Now allocate an array of rectangle structures, and an array of flags. Set
all the falgs to zero.
Iterate over the array a second time. When you hit a non-zero, check the
flag. If it is clear, you have the top point of the cluster. If the array is
relatively small and time isn''t critical, it is probably easiest to iterate
from the top left going down columns to find the left point, to iterate from
the bottom up to find the bottom point, and from the right going up columns
to find the right point.
(If you have a huge array with small clusters you can search the cluster
using the floodfill again, and store maximum and minimum points).
Then set the flag to mark the fact that you have found the rectnagle for
that cluster, and continue until you reach the end of the array.
hi jburgy,
that kind of helped I tied to modify the code so that instead of
clustering 1''s it would cluster 0''s just to better understand the
algorithm..But I guess I am making some mistake and it does''nt do the
revers of what it does now. Can you help here. basically I am trying to
understand. what should I change in the C code to make it work for 0
clustering instead of 1''s..
int hoshen_kopelman(int **matrix, int m, int n) {
uf_initialize(m * n / 2);
/* scan the matrix */
for (int i=0; i<m; i++)
for (int j=0; j<n; j++)
if (!matrix[i][j]) { // if occupied ...
int up = (i==0 ? 0 : matrix[i-1][j]); // look up
printf("%d\n",up);
int left = (j==0 ? 0 : matrix[i][j-1]); // look left
switch (!!up + !!left) {
case 0:
matrix[i][j] = uf_make_set(); // a new cluster
break;
case 1: // part of an existing cluster
matrix[i][j] = max(up,left); // whichever is nonzero is
labelled
break;
case 2: // this site binds two clusters
matrix[i][j] = uf_union(up, left);
break;
}
}
/* apply the relabeling to the matrix */
/* This is a little bit sneaky.. we create a mapping from the
canonical labels
determined by union/find into a new set of canonical labels, which
are
guaranteed to be sequential. */
int *new_labels = calloc(sizeof(int), n_labels); // allocate array,
initialized to zero
for (int i=0; i<m; i++)
for (int j=0; j<n; j++)
if (matrix[i][j]) {
int x = uf_find(matrix[i][j]);
if (new_labels[x] == 3) {
new_labels[0]++;
new_labels[x] = new_labels[0];
}
matrix[i][j] = new_labels[x];
}
int total_clusters = new_labels[0];
free(new_labels);
uf_done();
return total_clusters;
}
I canges the if(matrix[i][j]) to if(!matrix[i][j]) but it did not
update the other clusters.
http://splorg.org:8080/people/tobin/...nkopelman/hk.c
这篇关于在C中聚类的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
