Editing Quadtree (section)

===Connected component labelling===
Consider two neighbouring black pixels in a binary image. They are ''adjacent'' if they share a bounding horizontal or vertical edge. In general, two black pixels are ''connected'' if one can be  reached from the other by moving only to adjacent pixels (i.e. there is a path of black pixels between them where each consecutive pair is adjacent). Each maximal set of connected black pixels  is a ''connected component''. Using the quadtree representation of images, [[Hanan Samet|Samet]]<ref>{{Cite journal|last=Samet|first=H.|year=1981|title=Connected component labeling using quadtrees|journal=Journal of the ACM|volume=28 | issue = 3 |pages=487–501|doi=10.1145/322261.322267|author-link=Hanan Samet|citeseerx=10.1.1.77.2573|s2cid=17485118}}</ref>  showed how we can find and label these connected components in time proportional to the size of the  quadtree.<ref name="Aluru2004" /><ref name=":1" /> This algorithm can also be used for polygon colouring.

The algorithm works in three steps: 
# establish the adjacency relationships between black pixels 
# process the equivalence relations from the first step to obtain one unique label for each  connected component 
# label the black pixels with the label associated with their connected component
To simplify the discussion, let us assume the children of a node in the quadtree follow the [[Z-order curve|''Z''-order]] (SW, NW, SE, NE). Since we can count on this structure, for any cell we know how to navigate the quadtree to find the adjacent cells in the different levels of the hierarchy.

Step one is accomplished with a [[Tree traversal#Post-order|post-order traversal]] of the quadtree. For each black leaf <math>v</math> we look at the node or nodes representing cells that are Northern neighbours and Eastern neighbours (i.e. the Northern and Eastern cells that share edges with the cell of <math>v</math>). Since the tree is organized in ''Z''-order, we have  the invariant that the Southern and Western neighbours have already been taken care of and accounted for. Let the Northern or Eastern neighbour currently under consideration be <math>u</math>. If <math>u</math> represents black pixels:
* If only one of <math>u</math> or <math>v</math> has a label, assign that label to the other cell
* If neither of them have labels, create one and assign it to both of them
* If <math>u</math> and <math>v</math> have different labels, record this label equivalence and move on
Step two can be accomplished using the [[disjoint-set data structure|union-find data structure]].<ref>{{Cite journal|last=Tarjan|first=R. E.|year=1975|title=Efficiency of a good but not linear set union algorithm|url=http://www.csd.uwo.ca/~eschost/Teaching/07-08/CS445a/p215-tarjan.pdf|journal=Journal of the ACM|volume=22 | issue = 2 |pages=215–225|doi=10.1145/321879.321884|hdl=1813/5942|s2cid=11105749|hdl-access=free}}</ref> We start with each unique label as a separate set. For every equivalence relation noted in the first step, we union the  corresponding sets. Afterwards, each distinct remaining set will be associated with a distinct connected component in the image.

Step three performs another post-order traversal. This time, for each black node <math>v</math> we use the union-find's ''find'' operation (with the old label of <math>v</math>) to find and assign <math>v</math> its new label (associated  with the connected component of which <math>v</math> is part).