Editing Quadtree (section)

===Image union / intersection===
One of the advantages of using quadtrees for image manipulation is that the set operations of union and intersection can be done simply and quickly.<ref name="Aluru2004" /><ref>{{Cite book|title=Efficient Computation and Data Structures for Graphics|last=Hunter|first=G. M.|publisher=Ph.D. dissertation, Department of Electrical Engineering and Computer Science, Princeton University|year=1978}}</ref><ref>{{Cite journal|last1=Hunter|first1=G. M.|last2=Steiglitz|first2=K.|year=1979|title=Operations on images using quad trees|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|volume=2|issue=2|pages=145–153|doi=10.1109/tpami.1979.4766900|pmid=21868843|s2cid=2544535}}</ref><ref>{{Cite journal|last=Schneier|first=M.|year=1981|title=Calculations of geometric properties using quadtrees|journal=Computer Graphics and Image Processing|volume=16 | issue = 3 |pages=296–302|doi=10.1016/0146-664X(81)90042-3}}</ref>
<ref>{{Cite book|title=Handbook of Data Structures and Applications|last=Mehta|first=Dinesh|publisher=Chapman and Hall/CRC Press|year=2007|pages=397}}</ref>
Given two binary images, the image union (also called ''overlay'') produces an image wherein a pixel is black if either of the input images has a black pixel in the same location. That is, a pixel in the output image is white only when the corresponding pixel in ''both'' input images is white, otherwise the output pixel is black. Rather than do the operation pixel by pixel, we can compute the union more efficiently by leveraging the quadtree's ability to represent multiple pixels with a single node. For the purposes of discussion below, if a subtree contains both black and white pixels we will say that the root of that subtree is coloured grey.

The algorithm works by traversing the two input quadtrees (<math>T_1</math> and <math>T_2</math>) while building the output quadtree <math>T</math>. Informally, the algorithm is as follows. Consider the nodes <math>v_1 \in T_1</math> and  <math>v_2 \in T_2</math> corresponding to the same region in the images.
* If <math>v_1</math> or <math>v_2</math> is black, the corresponding node is created in <math>T</math> and is colored black. If only one of them is black and the other is gray, the gray node will contain a subtree underneath. This subtree need not be traversed.
* If <math>v_1</math> (respectively, <math>v_2</math>) is white, <math>v_2</math> (respectively, <math>v_1</math>) and the subtree underneath it (if any) is copied to <math>T</math> .
* If both <math>v_1</math> and <math>v_2</math> are gray, then the corresponding children of <math>v_1</math> and <math>v_2</math> are considered.

While this algorithm works, it does not by itself guarantee a minimally sized quadtree. For example, consider the result if we were to union a checkerboard (where every tile is a pixel) of size  <math>2^{k} \times 2^{k}</math> with its complement. The result is a giant black square which should be represented by a quadtree with just the root node (coloured black), but instead the algorithm produces a full 4-ary tree of depth <math>k</math>. To fix this, we perform a bottom-up traversal of the resulting quadtree where we check if the four children nodes have the same colour, in which case we replace their  parent with a leaf of the same colour.<ref name="Aluru2004" />

The intersection of two images is almost the same algorithm. One way to think about the intersection of the two images is that we are doing a union with respect to the ''white'' pixels. As such, to  perform the intersection we swap the mentions of black and white in the union algorithm.