Chapter 1: Quadtrees and Octrees

In this chapter, we introduce the quadtree and octree structures. Their definition and complexity, the recursive construction scheme, and a standard application are presented. Quadtrees and octrees have applications in mesh generation, as shown in Sections 1.3, 1.4, and 1.5.

1.1. Definition

A quadtree is a tree rooted so that every internal node has four children. Every node in the tree corresponds to a square. If a node v has children, their corresponding squares are the four quadrants, as shown in Figure 1.1.

Figure 1.1: An example of a quadtree.

Quadtrees can store many kinds of data. We will describe the variant that stores a set of points and suggest a recursive definition. A simple recursive splitting of squares is continued until there is only one point in a square. Let P be a set of points.

The definition of a quadtree for a set of points in a square Q = [ x 1 _Q : x 2 _Q ] — [ y 1 _Q : y 2 _Q ] is as follows :

• If P ‰ 1, then the quadtree is a single leaf where Q and P are stored.

• Otherwise, let Q _NE , Q _NW , Q _SW , and Q _SE denote the four quadrants. Let x _mid := ( x 1 _Q + x 2 _Q ) / 2 and y _mid := ( y 1 _Q + y 2 _Q ) / 2, and define

  

  The quadtree consists of a root node v , and Q is stored at v . In the following, let Q ( v ) denote the square stored at v . Furthermore, v has four children: the X -child is the root of the quadtree of the set P _X , where X is an element of the set { NE, NW, SW, SE }.