What is a quad tree?
A quad tree will recursively decompose space. It serves a similar purpose to a binary search tree, but for 2D information. It is able to remove entire parts of a search, simplifying the problem.
Applications:
Image Compression
3D Rendering
Objecet Collision
Nearest Neighbor Finding
Quadtrees:
The best way to explain a quad tree is with the region quadtree. Originally, there was a 2D array that was made up of 1’s and 0’s. In a quadtree, each non-leaf node has exactly four children. Each of these children represents splitting the current subplane into four different parts.
Constructing a Quadtrees:
For the most basic way of constructing region quadtrees the algorithim will run in O(n^2) time. There does exist a lot complex algorithims which are able to do this faster. The entire algorithim works by going bottom up. It starts with a single value in the matrix. If that value is a 1 then it checks to see if its 3 neighbors also have 1’s. If the 3 neighbors are also have values of 1 then, that region starts searching the neighboring three 2×2 regions to see if they are also all ones. This process will continue until there is no more new nodes to explore and the root is placed.
Image Compression Example:
The algorithim used to compress the image on the left is very similar to the region quadtree. Instead of storing a strict 1 or 0 value it most likely stores a more specific color value. If the values in one of the subquadrants is close enough they just become one giant blob of that color. Which is why in the water where it is mostly blue the biggest sections are there. When more precision is colors is needed the quadrants become super small. Explaining why the cells become so small when around the eagle.
I do not own the following image. It was taken from https://demonstrations.wolfram.com/QuadTreeImageDecomposition/
