Quadtrees

Quadtrees allow segmentation of a large pixel area in subdivisions, so that groups of pixels can be efficiently compressed.

On figure 1 we have three pixels in an image that we want to compress. For this demonstration, we assume that we have only black and white pixels, so we don't compress color information. We just want to be able to reconstruct the position of the individual pixels later.

Quadree pixel compression
Figure 1: Compression of three pixels in three steps with the help of quadtree segmentation

Our canvas has 64 pixels in eight rows and eight columns. There are three black pixels near the middle of the image; all others are white. To be able to encode this information, we recursively use segmentation. First, we divide the 8x8 canvas in four 4x4 subdivisions and enumerate them clockwise from 0 to 4. We see that the pixels are in division 2, so we write this digit down. In the second step, we take the subdivison 2 and divide it again in four 2x2 subdivisions, again enumerating them from 0 to 4. This time the pixels are in segment 0, so we write it down as the second level of the tree. At last, we subdivide segment 0 again in four individual pixels and we see that they are on positions 1, 2 and 3. As they are part of the larger segment 0, we put them under it in our tree. This is how quadtree segmentation can be applied. If we had pixels in multiple main segments, we could have brought them under a common denominator (for example T for tree). This way we can encode them with T-0, T-1, T-2 and T-3. But the introduction of more hierarchy levels leads to slower algorithm execution.

Why is this method important?

Rendering algorithms work in a similar way, because processors work their way gradually through multiple segments in a clockwise manner. If you render a complex image and your processor slows down, you can see how it subdivides the larger image in smaller parts and then renders them. It's the divide and conquer strategy applied to computer graphics. This shows us that we can't tackle too challenging tasks at once—accomplishing individual ones is often easier.

We also subdivide our websites in multiple components and give them id-s in our code, which allows us to address their descendent elements easier. The DOM is also a tree and CSS gives us a nice way to encode which style we apply to which element. So to make our stylesheets faster, we need to minimize the nesting levels of our DOM elements.

bit.ly/11zo8wZ