QuadTree

Posted on

Introduction

A QuadTree is a spatial partitioning strategy used to make queries on relationships between 2D spatial data such as coordinates in a Geographic Information System (GIS), or the location of objects in a video game. For instance, you may need to know all the objects within a region on a map, test whether objects are visible by a camera, or optimize a collision detection algorithm.

The QuadTree is so named because it recursively partitions regions into four parts, with leaf nodes containing references to the spatial objects. Querying the QuadTree is a function of traversing the tree nodes that intersect the query area.

The OctTree is the analogous structure used for 3 dimensional problems.

For a masterful collection of demos and variations on the QuadTree and other spatial indexing methods see Frantisek Brabec and Hanan Samet’s site, or use the references at the end of this article.

Background

There are many spatial partitioning methods, each with the goal of providing an efficient way of determining the position of an item in a spatial domain. For example, a database query can be considered as a graphical problem. Consider a query on a database containing date of birth and income: a query against all people between 35 and 50 years of age and incomes between 30,000 and 60,000 per year . When plotted on a 2-dimensional chart, the points representing age and income are spatially distributed on the surface of the chart. In the same way, a map of all the restaurants in the city of Vancouver are spatially distributed. In the case of explicitly spatial data, the X and Y coordinates are Latitude and Longitude, but in all other ways the queries on the 2 dimensional data are same: they are 2 dimensional spatial queries.

Several spatial indexing methods are more efficient in time and space, and are easily generalizable to higher dimensions. However, the QuadTree is specialized to the 2D domain, and it is easy to implement.

Algorithm

The general strategy of the QuadTree is to build a tree structure that partitions a region recursively into four parts, or Quads. Each Quad can further partition itself as necessary. A pre-requisite is that you must know the bounds of the area to be encompassed; the basic algorithm does not lend itself to the addition or removal of areas under consideration without rebuilding the index.

Insertion

When an item is inserted into the tree, it is inserted into a Quad that encompasses the item’s position (or spatial index). Each Quad has a maximum capacity. When that capacity is exceeded, the Quad splits into four sub-quads that become child nodes of the parent Quad, and the items are redistributed into the new leaves of the QuadTree. Some variations set the maximum capacity to one, and subdivide until each leaf contains at most a single item (Adaptive QuadTree).

Querying

To query a QuadTree for items that are inside a particular rectangle, the tree is traversed. Each Quad is tested for intersection with the query area. In the diagrams below, the quads are blue and the query area is yellow.

 Quads that do not intersect are not traversed, allowing large regions of the spatial index to be rejected rapidly.
Quads that are wholly contained by the query area have their sub-trees added to the result set without further spatial tests: this allows large regions to be covered without further expensive operations.
Quads that intersect are traversed, with each sub-quad tested for intersection recursively.

When a Quad is found with no sub-Quads, its contents are individually tested for intersection with the query rectangle

Other Operations

Other operations on the QuadTree could include

  1. Deletion: an object is removed from the QuadTree, empty quads are removed
  2. Merge: two QuadTrees are merged, indexes are rebuilt
  3. Nearest Neighbour: common to more advanced spatial indexes, a Query could ask for the nearest neighbours to a given object. A simple implementation would be to take the object’s bounding rectangle and inflate it by an amount based on the the neighbour proximity. Objects in the result set would be sorted by increasing distance.

These operations are not demonstrated in this code.

Variation

This implementation of the QuadTree has the following variations:

The QuadTree has been changed to index items with rectangular bounds rather than points. This allows it to be used with lines, and polygons.

  • On insertion, new quads are created until there are no Quads able contain an item’s rectangle. IE: the item is inserted into the smallest quad that will contain it.
  • There is no maximum number of items in a Quad, there is a minimum Quad size (necessary to avoid massive tree growth if an item happens to have a very small area).
  • Because the Quad an item is stored in is related to the size of the item, both leaf nodes and parent nodes store items.
  • The QuadTree’s performance will be severely impacted if there are many large items.
  • The Quadtree’s performance will be best when the size of most items are close to the minimum quad size.

After writing this code I find that this particular variation bears a striking resemblance to the “MX-CIF QuadTree“.

Note: there are other operations on QuadTrees such as deleting a node, or find the nearest neighbour. These are not supported in this implementation

The following two diagrams show the spatial relationship of the QuadTree with the tree structure. The coloured regions represent objects in the spatial domain. Those that are entirely within a quad are shown in the tree structure in their smallest enclosing quad. You can see that the green shape, since it intersects two of the highest level Quads and does not fit into either is placed in the root quad. The red and purple shapes are placed in child nodes at level one since they are the largest enclosing Quads. The blue shape is at level three along with the orange shape. The Yellow shape is at level four. This tree is adaptive in that it does not create quads until insertion is requested.

figure 1: spatial objects partitioned using quads
figure 2: tree structure partitioning from figure 1

Using the Code

The QuadTree class is a generic class. The generic parameter has a restriction that it must inherit from the IHasRect interface which defines a property Rectangle. Creating a QuadTree requires an area, the demo application uses the main form’s ClientRectangle.

QuadTree<Item> m_quadTree = new QuadTree<Item>(this.ClientRectangle);

Inserting items into the QuadTree is done on a left mouse click, Querying items in a QuadTree is done with a right mouse drag

private void MainForm_MouseUp(object sender, MouseEventArgs e)
{
    if (m_dragging &amp;&amp; e.Button== MouseButtons.Right)
    {
        m_selectedItems = m_quadTree.Query(m_selectionRect);
        m_dragging = false;
    }
    else
    {
        Random rand = new Random(DateTime.Now.Millisecond);
        m_quadTree.Add(new Item(e.Location, rand.Next(25) + 4));
    }
    Invalidate();
}

Run the demo application, and left click anywhere in the client rectangle: an object is inserted at the click point with a random size. Right-click and drag: a selection rectangle is created. Release the mouse button: the QuadTree is queried with the selection rectangle. The QuadTree renderer draws the QuadTree nodes and the objects in the QuadTree in random colours. It also draws the selection region and highlights the selected nodes.

Performance:

There are two components of QuadTree performance: insertion and query. Insertion can be very expensive because it involves several intersection tests per item to be inserted. The number of tests depends on the size of the region (the root of the QuadTree) and on the minimum Quad size configured. These two numbers have to be tuned per application. Loading many items into the QuadTree (bulk load, or indexing) tends to be very CPU intensive. This overhead may not be acceptable; consider storing the QuadTree structure on disk (not covered in this article).

The QuadTree is designed to be faster at querying the spatial domain than iteration, but the performance of the index depends on the distribution of objects in the domain. If items are clustered together, the tree tends to have many items in one branch which defeats the strategy of being able to cull large regions, and reduce the number of intersection tests. The worst case performance happens when all objects are in one small cluster that is the same size as the smallest Quad; in this case the performance of the QuadTree will be slightly worse than just iterating through all objects.

If items are uniformly distributed across the spatial domain, performance is approximately O(n*log n)

Points of Interest

  • Generic implementation; allows you to used it with any class that implements IHasRect interface.
  • Colour used to draw the node is stored in a Hash Table; allows the colour of the Quad on screen to be constant over the life of the QuadTree
  • In the QuadTreeRenderer class, note the anonymous delegate used to draw the QuadTreeNodes; allows the QuadTree to be tested, and visualized, without adding specific code to the class to do so.

History

  • Initial version with regions and simple Insert and Query operations, demo application

References

  • H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley, Reading, MA, 1990. ISBN 0-201-50255-0
  • H. Samet, Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS, Addison-Wesley, Reading, MA, 1990. ISBN 0-201-50300-0.
  • Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf, Computational Geometry: Algorithms and Applications, 2nd Edition, Springer-Verlag 2000 ISBN: 3-540-65620-0
Posted in Articles, Blog and tagged , , , , , , , .