Content deleted Content added
Line 12:
The Union-Find Algorithm is a simple method for computing equivalence classes. Calling the function union(x,y) specifies that items x and y are members of the same equivalence class. Because equivalence relations are transitive; all items equivalent to x are equivalent to all items equivalent to y. Thus for any item x, there is a set of items which are all equivalent to x are; this set is the equivalence class of which x is a member. A second function find(x) returns a representative member of the equivalence class to which x belongs.
==
In this algorithm we scan through a grid looking for occupied cells and labelling them with cluster labels. The algorithm begins with scanning the grid cell by cell and check if the cell is occupied, if the cell is occupied then this cell must be labelled with a cluster label. This cluster label is decided based on the neighbors of the cell which have been previously scanned and labelled, and if the cell doesn’t have any occupied neighbors then new label is assigned to the cell.
| |||