Index, Spatial

Quadtrees

The quadtree is one of the most important spatial indices. The left-hand side of Figure 1 shows a simple spatial data set, which might represent the area covered by a lake. The data set is structured in raster format (made up of a regular square grid of cells), with cells that contain lake filled in gray and those that contain dry land filled in white. A quadtree indexes this data by recursively subdividing the area covered by the raster into quarters. At each step, those cells that [Page 228]contain different types of information (i.e., contain some lake and some land) are further subdivided. The right-hand side of Figure 1 illustrates the series of steps required to create the quadtree for the lake data set. By the fourth step in Figure 1, all the cells contain only one type of information (lake or land), so the recursive decomposition process stops at Level 4.

The advantage of using the quadtree structure becomes clear when we try to query the stored information. For example, suppose an application needs to test whether the point X in Figure 1 is in the lake or not. Without a spatial index of some kind (be it a simple row ordering of cells or a more sophisticated index like a quadtree), it would be necessary to search through the entire list of cells in the raster to answer this question. Each cell would need to be checked in turn to determine whether the point X is contained within that cell. In the worst case in Figure 1, this would mean searching the entire 16 × 16 raster, checking a total of 256 cells.

...