Each patch of same-colored pixels on the map is a connected component. One scan over the image with a union-find structure, plus a quick second pass, finds them all, and the picture on the right gives each one its own color.
New map Size 100 × 100 200 × 200 500 × 500 1000 × 1000 Help: how it works
Components are numbered in the raster order of their roots, and shown with their sizes in pixels.
On the map, two overlapping circles of the same color merge into one blob, and a circle cut in two by another one drawn across it leaves two separate blobs. Each blob is a connected component: a set of same-colored pixels you can walk between by steps up, down, left and right, taken as large as it can be. Diagonal steps don't count, so two same-colored blobs that touch only at a corner are two components. (This is called 4-connectivity; allowing diagonal steps as well gives 8-connectivity.)
The pixels are numbered in raster order, the order you read text in. In an image w pixels wide, pixel i is in column i mod w of row ⌊i / w⌋, its left neighbor is pixel i − 1, and the one above it is pixel i − w.
Suppose pixels 7, 8, 9 and 10 have turned out to be in one component, and the program has recorded that by making each one point at another: 10 → 9 → 7, 8 → 7, and 7 → 7. Following the pointers from any of the four ends at pixel 7, which points at itself. Pixel 7 is the root, and serves as the name of the set: two pixels are known to be in the same set exactly when following the pointers from each of them leads to the same root.
That is a union-find structure, also called a disjoint-set forest: a forest of trees stored as a single array of parent pointers, parent[i], with one entry per pixel. It has two operations: find the root of a node's tree, and union two trees into one by pointing one's root at the other's. If pixel 3 is the root of some other tree, and the program learns that pixels 3 and 10 are in the same component, setting parent[7] = 3 merges the two sets in one step, however big they are.
parent[i]
parent[7] = 3
Both the image and the union-find array are wrapped in a CountedArray, and the algorithm reaches their elements only through get and set, so the counts on the page are exact. items is the bare array inside, which is used only to hand it to another counter or to the drawing code. Asking for the length isn't counted, since it touches no element.
CountedArray
get
set
items
length
get and set also check each index. A JavaScript array or typed array quietly answers undefined for a read outside it, and ignores a write; the algorithm itself checks every index it computes before using it, and check makes sure that a mistake there would stop the program instead of quietly producing wrong answers.
check
undefined
Here is findRoot on the path 12 → 11 → 10 → 9 → 8, where 8 is the root. The call for 12 reads its parent, 11, and calls itself for 11, which calls itself for 10, which calls itself for 9, which calls itself for 8. Pixel 8 is its own parent, so that innermost call returns 8. Each of the other calls, as it returns, points its pixel straight at 8: first 9, which already pointed there, then 10, 11 and 12.
findRoot
Afterwards every pixel on the path is one step from the root, so later finds starting anywhere on it are quick. This is path compression. On a path of m pixels below the root, a find makes m + 1 reads, one for each pixel including the root, and m writes, one for each pixel except the root; so every find reads exactly once more than it writes. Skipping the write when a pixel already points at the root would save some writes, at the cost of another test.
The recursion costs stack space, one frame for each pixel on the path, and with the linking rule below nothing guarantees that paths stay short. Path halving, which repoints every other pixel on the path at its grandparent in a single loop, needs no stack, but it's harder to follow. On maps like these the paths stay short anyway: in tests, no find went more than three steps.
union finds both roots and, unless they are the same, hangs one under the other. Which one goes under matters. This version always hangs the later root, the one with the higher pixel number, under the earlier one. The rest of the program relies on two consequences of that:
union
The textbook choice is instead union by rank (or by size): hang the shallower (or smaller) tree under the deeper (or larger) one. Together with path compression, that guarantees an amortized cost per operation that grows only as the inverse of Ackermann's function, which is at most 4 for any number of pixels that could fit in a computer (Tarjan 1975; Tarjan and van Leeuwen 1984). In general, linking by number carries no such guarantee: an adversarial sequence of unions can make operations cost on the order of log n steps each, amortized (Tarjan and van Leeuwen 1984). But it needs no second array for the ranks, it makes every root its component's first pixel, and the counts on the page show that on images it costs little. Wu, Otoo and Suzuki (2009) use the same smaller-number-wins rule, also with path compression, and argue that labeling an image this way takes time linear in its number of pixels.
At each pixel the scan looks only left and up. It doesn't need to look right or down: pixel i and its right neighbor i + 1 are the same pair as i + 1 and its left neighbor, which gets compared when the scan reaches i + 1, and likewise for the pixel below. So every pair of orthogonal neighbors is compared exactly once, and joined if they are the same color.
The scan is a single loop over pixel numbers, and it checks each neighbor's number before using it. The left neighbor of pixel i is i − 1, unless i starts a row; then i − 1 is the last pixel of the row above, which isn't a neighbor at all (or, for pixel 0, doesn't exist). So the test i % width !== 0, meaning that i's column isn't the first, comes first. The upper neighbor is i − w, which is negative in the top row, so its test is above >= 0. Since && doesn't evaluate its right side when its left side is false, neither neighbor is read unless it exists.
i % width !== 0
above >= 0
&&
Each pixel becomes a tree of its own, parent[i] = i, when the scan reaches it, and not before. It isn't needed sooner, because everything the scan does at pixel i involves only i and earlier pixels, and following parent pointers leads only to still earlier pixels. So no entry is read before it's written, setting up the array costs no separate pass, and the whole of pass 1 is a single scan.
parent[i] = i
Why trees, rather than just copying a label from a neighbor? Think of a blob shaped like a U. The scan meets the tops of the two arms separately, with nothing yet to say they're connected, so they become two different trees. Only in the bar at the bottom of the U does a pixel find its own color both to its left and above it, in different trees, and union merges them, hanging the right arm's root under the left arm's. Every pixel of the right arm is now in the left arm's set, without being visited again. Union-find lets the scan say “these two are the same” cheaply, however many pixels are already on each side.
After pass 1, each tree holds exactly one component. Pass 2 finds the root of every pixel; a pixel is a root exactly when it is its own root. Listing the roots as they turn up gives one per component, in the raster order of the components' first pixels.
Path compression has a useful side effect here: finding a pixel's root also points the pixel straight at it. So when pass 2 finishes, parent[i] is the root of pixel i's component for every i: a complete labeling, with each component named by its first pixel.
These finds are short, thanks to the backward-pointer rule. Pixel i's parent p comes before i, so pass 2 has already found p's root and pointed p straight at it, and the find from i takes at most two steps: to p, then to the root.
findComponents wraps the image and a new union-find array in counters and runs the two passes. For pass 2 it wraps the same union-find array in a second CountedArray, so that the page can show the two passes' counts separately.
findComponents
The page then numbers the components 0, 1, 2… in the order of their roots, gives each one a color, and draws the pictures. None of that is counted.
For an image of n = w × h pixels in k components (the page's sizes are multiples of 100, so dividing by n just moves the decimal point):
The per-pixel figures change little from one size to the next, even though the largest size has a hundred times as many pixels as the smallest: the work grows in proportion to the number of pixels. They creep up a little with size, because in a coarser image a larger share of neighboring pixels lie on opposite sides of a circle's edge, where there's nothing to join. A map's circles are the same at every size, so its components are nearly the same too; only some slivers along the circles' edges merge or split.
The map is 400 random circles in 8 colors, drawn over a light blue sea, later circles covering earlier ones; the same circles are redrawn at each size. The selected component pulses between its colors and their negatives.
The components' colors are spread over a sphere in the OKLab color space, so that they differ in lightness as well as hue. Lightness is the height on the sphere, and chroma shrinks toward the poles, where colors are too light or too dark to show much hue anyway. Successive components take successive points of the R2 sequence, a two-dimensional relative of the golden angle that spreads any run of consecutive points evenly over a square, and Archimedes's equal-area map carries the square onto the sphere. So components with nearby numbers get very different colors. A Fibonacci lattice would space the points a little more evenly, but it needs their number in advance, and it puts consecutive points at nearly the same height; components numbered close together, whose roots are in nearby rows, would get nearly the same lightness.