Hoshen–Kopelman algorithm: Difference between revisions

Revision as of 04:58, 12 September 2016

Revision as of 04:59, 12 September 2016

Line 20:

== Pseudo-Code ==

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.

=== <strong>Raster Scan and LabellingLabeling on the Grid ===</strong>

largest_label = 0;

for x in 0 to n_columns {

Line 39:

}

}

<strong>Union</strong>

=== Union ===

void union(int x, int y) {

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

}

<strong>Find</strong>

=== Find ===

int find(int x) {

int y = x;