Go to top

A Simple QuadTree Implementation in C#

, 29 Oct 2008
 Rate this:
Please Sign up or sign in to vote.
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_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 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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

Architect Blue Toque Software
Canada
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.
Follow on

Comments and Discussions

 First Prev Next
 delete a item Member 10665902 23-Mar-14 21:37
 My vote of 5 Lowrenz 1-Mar-14 5:22
 Count Member 10357716 4-Nov-13 4:24
 Re: Count Michael Coyle 4-Nov-13 6:04
 Re: Count Member 10357716 4-Nov-13 7:25
 Traversing through all the nodes present in a QuadTree sleekFish 10-Aug-13 22:42
 Point variant? Thomas Schmidt 2-Apr-12 21:15
 Re: Point variant? Michael Coyle 4-Apr-12 11:12
 Re: Point variant? Thomas Schmidt 4-Apr-12 11:20
 Re: Point variant? Michael Coyle 4-Apr-12 11:21
 How could I use this with geocoordinates? Clinton Sanchez 29-Feb-12 19:09
 Re: How could I use this with geocoordinates? Michael Coyle 1-Mar-12 10:47
 My vote of 5 manoj kumar choubey 19-Feb-12 21:36
 Great article Harvey Green 25-Sep-11 20:45
 thanks michael Kiraya 8-Sep-11 22:21
 Thank you for this great contribution George Mamaladze 10-Jul-11 9:47
 Re: Thank you for this great contribution Michael Coyle 10-Jul-11 10:21
 Re: Thank you for this great contribution George Mamaladze 11-Jul-11 11:49
 File-based solution walterman 13-Oct-10 11:38
 Re: File-based solution [modified] Michael Coyle 13-Oct-10 12:19
 My vote of 2 chengiz5 26-Aug-10 5:40
 Access C# dll from vb.net ralstogj 9-Sep-09 11:10
 Re: Access C# dll from vb.net Michael Coyle 9-Sep-09 12:50
 Re: Access C# dll from vb.net ralstogj 9-Sep-09 12:59
 Re: Access C# dll from vb.net ralstogj 10-Sep-09 0:18
 Hi   Have had a go but am getting the following errors. Not sure what to do as this is at the limits of my current knowledge of vb.net I have explain wants happening below with screen captures showing the errors in vb.net editor   http://screencast.com/t/p1RRmDpr[^]   http://screencast.com/t/NTpWfAakYU[^]   http://screencast.com/t/p00DT4k8WZ[^]   Regards   Justin Ralston
 Re: Access C# dll from vb.net Michael Coyle 10-Sep-09 6:59
 Re: Access C# dll from vb.net ralstogj 14-Sep-09 0:12
 Re: Access C# dll from vb.net Michael Coyle 14-Sep-09 18:34
 Re: Access C# dll from vb.net ralstogj 16-Sep-09 0:17
 remove node function? Member 1742701 9-Aug-09 13:22
 Re: remove node function? Michael Coyle 10-Aug-09 9:36
 Re: remove node function? Member 1742701 10-Aug-09 11:54
 Re: remove node function? Michael Coyle 4-Apr-12 11:28
 Re: remove node function? aubergine2010 4-Sep-13 2:26
 Re: remove node function? Michael Coyle 6-Sep-13 7:33
 Found a bug rlukashuk 15-Dec-08 12:46
 Re: Found a bug Michael Coyle 15-Dec-08 12:51
 Source Code Links Henry Minute 29-Oct-08 23:49
 Source Code Links Henry Minute 29-Oct-08 23:49
 Re: Source Code Links Michael Coyle 30-Oct-08 7:56
 Last Visit: 31-Dec-99 18:00     Last Update: 14-Sep-14 21:22 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web01 | 2.8.140905.1 | Last Updated 30 Oct 2008
Article Copyright 2008 by Michael Coyle
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid