Content deleted Content added
Added linkrot template. |
Meatsgains (talk | contribs) Filled in 2 bare reference(s) with reFill () |
||
Line 4:
{{Machine learning bar}}
<div align="justify">
The '''Hoshen–Kopelman algorithm''' is simple and efficient [[algorithm]] for labeling [[Cluster analysis|clusters]] on a grid. Where the grid is a regular network of cells,with the cells being either occupied or <strong>unoccupied</strong>. This algorithm is based on well-known [[Disjoint-set data structure|union-finding algorithm]]. The algorithm was originally described in [http://journals.aps.org/prb/abstract/10.1103/PhysRevB.14.3438 Percolation and Cluster Distribution. I. Cluster Multiple Labeling Technique and Critical Concentration Algorithm] by J. Hoshen and R. Kopelman.<ref>{{cite journal|url=http://
</div>
Line 35:
<div align="justify">
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 <code>union</code> operation is performed, to specify that these neighboring cells are in fact members of the same equivalence class. Then a <code>find</code> 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 <code>find</code> operations at each cell, to re-label the cells with their final assignment of a representative element.
Following pseudo-code is referred from one of the University of California Berkeley's projects.<ref>{{cite web|url=https://www.ocf.berkeley.edu/~fricke/projects/hoshenkopelman/hoshenkopelman.html|title=The Hoshen-Kopelman Algorithm|publisher=}}</ref>
</div>
<strong>Raster Scan and Labeling on the Grid</strong>
| |||