Content deleted Content added
No edit summary |
No edit summary |
||
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 {
for y in 0 to n_rows {
if occupied[x,y] then
left = occupied[x-1,y];
above = occupied[x,y-1];
if (left == 0) and (above == 0) then /* Neither a label above nor to the left. */
largest_label = largest_label + 1; /* Make a new, as-yet-unused cluster label. */
label[x,y] = largest_label;
else if (left != 0) and (above == 0) then /* One neighbor, to the left. */
label[x,y] = find(left);▼
else if (left == 0) and (above != 0) then /* One neighbor, above. */▼
label[x,y] = find(above);▼
else /* Neighbors BOTH to the left and above. */▼
union(left,above); /* Link the left and above clusters. */▼
label[x,y] = find(left);
}
▲ else if (left == 0) and (above != 0) then /* One neighbor, above. */
▲ label[x,y] = find(above);
▲ else /* Neighbors BOTH to the left and above. */
▲ union(left,above); /* Link the left and above clusters. */
▲ label[x,y] = find(left);
}
void union(int x, int y) {
| |||