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,
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), 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 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 >>