Content deleted Content added
The description of the Union operation (from the Union-Find algorithm) was factually incorrect. Also, the characterization of Union-Find as computing equivalence classes was also incorrect. I corrected the description of Union-Find, which is now aligned with the (correct) information on the Union-Find Algorithm page. |
m Open access bot: url-access updated in citation with #oabot. |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 1:
{{short description|Algorithm for labeling clusters on a grid}}
{{Machine learning bar}}
The '''Hoshen–Kopelman algorithm''' is a simple and efficient [[algorithm]] for labeling [[Cluster analysis|clusters]] on a grid, where the grid is a regular [[Network theory|network]] of cells, with the cells being either occupied or unoccupied. This algorithm is based on a well-known [[Disjoint-set data structure|union-finding algorithm]].<ref>{{Cite web |title=Union-Find Algorithms |url=https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
== Percolation theory ==
Line 26:
On the other hand, if the current cell has no neighbors, it is assigned a new, previously unused, label. The entire grid is processed in this way.
Following [[pseudocode]] is referred from [https://www.ocf.berkeley.edu/~fricke/ Tobin Fricke's] implementation of the same algorithm.<ref name=":0">{{cite web|url=https://www.ocf.berkeley.edu/~fricke/projects/hoshenkopelman/hoshenkopelman.html |title=The Hoshen-Kopelman Algorithm for cluster identification|first=Tobin |last=Fricke |website=ocf.berkeley.edu |date=2004-04-21 |access-date=2016-09-17}}</ref> On completion, the cluster labels may be found in <code>labels</code>. Not shown is the second raster scan of the grid needed to produce the example output. In that scan, the value at <code>label[x,y]</code> is replaced by <code>find(label[x,y])</code>.
'''Raster Scan and Labeling on the Grid'''
largest_label = 0;
| |||