## What is a Quadtree?

A Quadtree is a data structure that allows two dimensional data, such as images or matrices, to be represented and traversed as a tree. The basic structure of a Quadtree is a node that has 4 children nodes, `upper left`

, `upper right`

, `bottom left`

, and `bottom right`

(it is also common to see the terms northeast, northwest, southeast, and southwest used for the children nodes.) Each of these child nodes references a region of the 2 dimensional data.

## Why use a Quadtree?

There are a number of benefits to representing 2 dimensional data as a tree. One example is when we need to search or traverse areas of a tree for updating and want to be able to do it in logarithmic time. Quadtrees are also a powerful structure that are commonly used in graphics programming and development.

## Implementing a Quadtree

To make our life easy, we will implement a helper matrix class:

from collections import namedtuple MatrixShape = namedtuple('MatrixShape', 'width height') class Matrix(object): # data is a list of lists def __init__(self, data): self.data = data def shape(self): if not self.data: return MatrixShape(width=0, height=0) return MatrixShape( len(self.data[0]), len(self.data) ) # getter for indexing like an array def __getitem__(self, key): return self.data[key] # return a sub matrix from x1,y1 to x2,y2 (not including x2,y2) def sub(self, x1, y1, x2, y2): if x1 < 0 or y1 < 0: raise ValueError("X1,Y1 must be positive") if x1 > x2 or y1 > y2: raise ValueError("X1,Y1 must be smaller than X2,Y2") mShape = self.shape(); max_x2 = x2 if x2 < mShape.width else mShape.width - 1 max_y2 = y2 if y2 < mShape.height else mShape.height - 1 return Matrix( [ [self.data[row][col] for col in range(x1, max_x2 + 1)] for row in range(y1, max_y2 + 1) ] ) def __str__(self): return "%s" % self.data

Using this matrix class, we can implement our QuadTree trivially. When implementing a Quadtree, in order for the tree to have the same depth for all leaf nodes, the matrix needs to have a number of cells equal to a power of 2 and have an equal width and height. It is possible to have a Quadtree of different depths, but for our implementation we will add some simple error handling and require a square matrix with an even number of rows and columns so that we can guarantee the tree is the same height at all leaf nodes.

class QuadTree(object): def __init__(self, matrix): if not matrix: raise ValueError("Matrix cannot be None or empty") self.leafNode = False self.value = None mShape = matrix.shape() if mShape.width == 1 and mShape.height == 1: self.leafNode = True self.value = matrix[0][0] return if mShape.width == 0 or (mShape.width & (mShape.width - 1)) != 0: raise ValueError("Matrix size must be a power of 2") if mShape.width != mShape.height: raise ValueError("Matrix must have same width and height") self.size = mShape.width quadSize = self.size / 2 self.upperLeft = QuadTree(matrix.sub(0,0,quadSize-1,quadSize-1)); self.bottomLeft = QuadTree(matrix.sub(0,quadSize,quadSize-1,(quadSize*2)-1)); self.upperRight = QuadTree(matrix.sub(quadSize,0,(quadSize*2)-1,quadSize-1)); self.bottomRight = QuadTree(matrix.sub(quadSize,quadSize,(quadSize*2)-1,(quadSize*2)-1)); def __str__(self, level=0): padding = " " * level if self.leafNode: return "%s+ %s" % (padding, self.value) else: s = [] s.append("%s+ ul\n%s" % (padding, self.upperLeft.__str__(level + 1))) s.append("%s+ ur\n%s" % (padding, self.upperRight.__str__(level + 1))) s.append("%s+ bl\n%s" % (padding, self.bottomLeft.__str__(level + 1))) s.append("%s+ br\n%s" % (padding, self.bottomRight.__str__(level + 1))) return "\n".join(s)

Using the above classes, if we were to instantiate a Quadtree and print it out, we would be able to see visually how a Quadtree would represent the matrix:

mat = Matrix([range(4) for x in range(4)]) tree = QuadTree(mat) print(tree)

The output for the above code would look like so:

+ ul + ul + 0 + ur + 1 + bl + 0 + br + 1 + ur + ul + 2 + ur + 3 + bl + 2 + br + 3 + bl + ul + 0 + ur + 1 + bl + 0 + br + 1 + br + ul + 2 + ur + 3 + bl + 2 + br + 3

## You may also want to read:

Write a function that takes a node and returns True if the node is part of a tree or False if it's part of a graph.

Read More >>Depth first search (sometimes referred to as DFS) is an algorithm for traversing a graph or tree.

Read More >>Given binary tree, write a function to print its values in column order, from the bottom to top. You can assume that there will be no collisions, in which 2 nodes would occupy the same row and column.

Read More >>