13,046,562 members (70,278 online)
alternative version

#### Stats

184.3K views
96 bookmarked
Posted 29 Oct 2008

# A Simple QuadTree Implementation in C#

, 29 Oct 2008
 Rate this:
A QuadTree is a spatial indexing method well suited to 2 dimensional spatial problems

## 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 of 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 is the same as a query for all restaurants in the city of Vancouver: 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.

1. Quads that do not intersect are not traversed, allowing large regions of the spatial index to be rejected rapidly.

2. Quads that are wholly contained by the query region have their sub-trees added to the result set without further spatial tests: this allows large regions to be covered without further expensive operations.

3. Quads that intersect are traversed, with each sub-Quad tested for intersection recursively.

4. 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 rect and inflate it by an amount based on the neighbor 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 to 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.

## 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 && e.Button== MouseButtons.Right)
{
m_dragging = false;
}
else
{
Random rand = new Random(DateTime.Now.Millisecond);
}
}```

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 use it with any class that implements `IHasRect` interface.
• Colour used to draw the node is stored in an hashtable; 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.

## 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

## History

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

## Share

I've been lead architect in several software companies. I've worked in the Justice and Public Safety area for the last 7 years, writing facial recognition, arrest and booking software and emergency management/GIS software. Prior to that I worked in the games industry with 3D animation.

Currently I'm working on some GIS/mapping software for outdoor enthusiasts. I intend to spin off portions of this into the open source community as time permits.

## You may also be interested in...

 FirstPrev Next
 Access C# dll from vb.net ralstogj9-Sep-09 11:10 ralstogj 9-Sep-09 11:10
 Re: Access C# dll from vb.net Michael Coyle9-Sep-09 12:50 Michael Coyle 9-Sep-09 12:50
 Re: Access C# dll from vb.net ralstogj9-Sep-09 12:59 ralstogj 9-Sep-09 12:59
 Re: Access C# dll from vb.net ralstogj10-Sep-09 0:18 ralstogj 10-Sep-09 0:18
 Re: Access C# dll from vb.net Michael Coyle10-Sep-09 6:59 Michael Coyle 10-Sep-09 6:59
 Re: Access C# dll from vb.net ralstogj14-Sep-09 0:12 ralstogj 14-Sep-09 0:12
 Re: Access C# dll from vb.net Michael Coyle14-Sep-09 18:34 Michael Coyle 14-Sep-09 18:34
 Re: Access C# dll from vb.net ralstogj16-Sep-09 0:17 ralstogj 16-Sep-09 0:17
 Oops I was visualising the box going down as the Rectangle method said the x was for the upper left corner in the vb IDE I have changed the code as you suggested and it runs no problem. I have started putting it together with the autocad code and objects. At the moment the quadtree takes integers could it be upgraded to take Doubles floating points? or would it be best to times everything by say 100 to scale it up to give me more accuracy and upgrade the code to take longs? Its just the raw point data I often have of the sea floor can be spread over a responible area of say 1 km by 1 km. I guess i could break the area down into a grid of 32,767 units /100 squares the maximum storage value of an integer. Regards Justin Ralston
 remove node function? Member 17427019-Aug-09 13:22 Member 1742701 9-Aug-09 13:22
 Re: remove node function? Michael Coyle10-Aug-09 9:36 Michael Coyle 10-Aug-09 9:36
 Re: remove node function? Member 174270110-Aug-09 11:54 Member 1742701 10-Aug-09 11:54
 Re: remove node function? Michael Coyle4-Apr-12 11:28 Michael Coyle 4-Apr-12 11:28
 Re: remove node function? aubergine20104-Sep-13 2:26 aubergine2010 4-Sep-13 2:26
 Re: remove node function? Michael Coyle6-Sep-13 7:33 Michael Coyle 6-Sep-13 7:33
 The circle is not placed exactly under the mouse clicking location. danielmark9-Mar-09 5:31 danielmark 9-Mar-09 5:31
 Re: The circle is not placed exactly under the mouse clicking location. Michael Coyle9-Mar-09 6:33 Michael Coyle 9-Mar-09 6:33
 Re: The circle is not placed exactly under the mouse clicking location. danielmark9-Mar-09 16:09 danielmark 9-Mar-09 16:09
 Re: The circle is not placed exactly under the mouse clicking location. DukeForge1-May-09 17:29 DukeForge 1-May-09 17:29
 Found a bug rlukashuk15-Dec-08 12:46 rlukashuk 15-Dec-08 12:46
 Re: Found a bug Michael Coyle15-Dec-08 12:51 Michael Coyle 15-Dec-08 12:51
 Source Code Links Henry Minute29-Oct-08 23:49 Henry Minute 29-Oct-08 23:49
 Source Code Links Henry Minute29-Oct-08 23:49 Henry Minute 29-Oct-08 23:49
 Re: Source Code Links Michael Coyle30-Oct-08 7:56 Michael Coyle 30-Oct-08 7:56
 Last Visit: 31-Dec-99 18:00     Last Update: 23-Jul-17 17:02 Refresh « Prev12