Construct a Quad-Tree [Netflix inspiration]
The other day I found a movie on Netflix about a patent infringement (The Billion Dollar Code), where the theme was a representation of a battle of David against Goliath.
However, something that called my attention was how a quad-tree was used as the solution to an image processing problem, and that really put me in a curious mode. How a data structure is applied to everyday life situations; that is, how an algorithm can be used to create an application that helps people.
The short story, a Quad-Tree is a data structure that has four leaves attached to a node, the values are stored in the leaf nodes of the tree. Without going into much detail, this data structure allows you to divide a space into multiple smaller quadrants; something like what was seen in the Netflix movie.
The data structure is used in real life, for example, in image compression, where each node contains the average color of each of its child nodes; as you go deeper into the tree (quadrant) more detail of the image is obtained.
Well, let’s see how the Quad-Tree can be constructed with a grid representation. Note that only the most basic definition of what a Quad-Tree is presented, so it’s recommended to review the lecture at the end of this story for further details.
As we work with a grid, it will be necessary to create variables for 4 nodes, a flag to know if it’s a leaf node and the variable to store the value of the unit (1, 0).
As we can see, we will build a Quad-Tree from grid. This 2D space is divided into 4 squares of equal size, if a square contains one or more cell then a child node is created; iterating each sub-square until no child nodes. The way we split the space is by dividing the length of the grid by two; starting at the top left, top right, bottom left and bottom right.
Starts from the top left
Starts from the middle of the horizontal axis
Starts from the middle of the vertical axis
Starts from the middle of vertical and middle of horizontal axis
After the recursion, it will be required to verify if all the nodes are or not a leaf, if all values are one or there are no ones at all means a leaf node. Well, here is the complete algorithm to build a simple Quad-Tree.
…by the way, I liked the movie.
Recommend lecture:
- Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT, Cambridge
