Hoshen–Kopelman algorithm: Difference between revisions

Revision as of 05:32, 11 September 2016

Revision as of 05:34, 11 September 2016

Line 18:

So in the raster scan of the grid in question, each time an occupied cell is encountered, a check is done to see whether this cell has any neighboring cells who have already been scanned. If so, first a '''''union''''' operation is performed, to specify that these neighboring cells are in fact members of the same equivalence class. Then a '''''find''''' operation is performed to find a representative member of that equivalence class with which to label the current cell. If, on the other hand, the current cell has no neighbors, it is assigned a new, previously unused, label. The entire grid is processed in this way. The grid can be raster-scanned a second time, performing only '''''find''''' operations at each cell, to re-label the cells with their final assignment of a representative element.

=== Raster Scan and Labelling on the grid ===

largest_label = 0;

for x in 0 to n_columns {

Line 38:

}

=== Union ===

void union(int x, int y) {

labels[findvoid union(int x)], =int find(y); {

labels[find(x)] = find(y);

}

int find(int x) {

int y = x;

while (labels[y] != y)

y = labels[y];

while (labels[x] != x) {

int z = labels[x];

labels[x] = y;

x = z;

}

=== Find ===

int find(int x) {

int y = x;

while (labels[y] != y)

y = labels[y];

while (labels[x] != x) {

int z = labels[x];

labels[x] = y;

x = z;

}

return y;

}

}

</div>

==== '''Example''' ====