Click here to Skip to main content
13,191,315 members (91,985 online)
Click here to Skip to main content
Add your own
alternative version


96 bookmarked
Posted 29 Oct 2008

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
Items in a QuadTree with nodes in random colours

User Selects a region and the QuadTree selects items

The Selected items


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.


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.


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.


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).


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.

    Case 1: Querying QuadTree

  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.

    Case 2: Querying QuadTree

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

    Case 3: Querying QuadTree

  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.


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.

Spatial drawing of shapes in a QuadTree

Tree representation of QuadTree

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;    
        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.


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.


  • 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


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


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


About the Author

Michael Coyle
Architect Blue Toque Software
Canada 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.

You may also be interested in...

Comments and Discussions

AnswerRe: File-based solution [modified] Pin
Michael Coyle13-Oct-10 12:19
memberMichael Coyle13-Oct-10 12:19 
GeneralMy vote of 2 Pin
chengiz526-Aug-10 5:40
memberchengiz526-Aug-10 5:40 
GeneralAccess C# dll from Pin
ralstogj9-Sep-09 11:10
memberralstogj9-Sep-09 11:10 
GeneralRe: Access C# dll from Pin
Michael Coyle9-Sep-09 12:50
memberMichael Coyle9-Sep-09 12:50 
GeneralRe: Access C# dll from Pin
ralstogj9-Sep-09 12:59
memberralstogj9-Sep-09 12:59 
GeneralRe: Access C# dll from Pin
ralstogj10-Sep-09 0:18
memberralstogj10-Sep-09 0:18 
GeneralRe: Access C# dll from Pin
Michael Coyle10-Sep-09 6:59
memberMichael Coyle10-Sep-09 6:59 
GeneralRe: Access C# dll from Pin
ralstogj14-Sep-09 0:12
memberralstogj14-Sep-09 0:12 

Thanks for your last bit of code I now have the the tree creating. But am having trouble inserting objects I have looked at your C# code for the item.cs class and translated to as follows :-

Imports System.Text
Imports QuadTreeLib
Imports System.Drawing

'To access the C# code that you want it be compiled as a DLL. Once that is done,
'simple add a reference to that project to your VB.Net project, import the namespace you need,
'and then you can use the C# code

Public Class Item
Implements IHasRect

Dim m_rect As RectangleF

Public ReadOnly Property Rectangle() As RectangleF Implements IHasRect.Rectangle
Return m_rect
End Get
End Property

Public Sub New(ByVal P As Point, ByVal Size As Integer)
Dim m_size As Integer
Dim m_rectangle As RectangleF

m_size = Size
m_rectangle = New RectangleF(P.X, P.Y, m_size, m_size)

End Sub

End Class

and have the following sub rountine to create the tree and try and insert and qurey objects:-

Public Class Textlap
<Autodesk.AutoCAD.Runtime.CommandMethod("TL")> _
Public Sub Find_Overlapping_Text()

'Create the quadtree using the C# .dll from the website
'to the extents of the points text

'To access the C# code that you want it be compiled as a DLL. Once that is done,
'simple add a reference to that project to your VB.Net project, import the namespace you need,
'and then you can use the C# code

Dim r As New Rectangle(100, 100, 100, 100) 'Me.ClientRectangle
' Rectangle(x upper lefthand corner ,y upper lefthand corner,width,height)

Dim m_quadTree As New QuadTree(Of Item)(r)
'Dim m_quadTree As New QuadTree(Of Item)(Me.ClientRectangle)

'add random points (text rectangles) into the quadtree for querying

'Random(rand = New Random(DateTime.Now.Millisecond))
'm_quadTree.Insert(new Item(e.Location, rand.Next(25) + 4));
Dim aa As Point

aa.X = 160
aa.Y = 85

'Dim jj As New Item(aa, 5)

m_quadTree.Insert(New Item(aa, 5))

'loop through all the text rectangles and
'Query the quadtree with a rectangle to find any other text objects under it
Dim m_selectionRect As New Rectangle(150, 90, 20, 20) 'query rectangle
Dim m_selectedItems As List(Of Item)
m_selectedItems = m_quadTree.Query(m_selectionRect)

End Sub

End Class

The code runs and gets pass the m_quadtree.insert line but when I look at the m_quadtree as a watch the tree item count is still zero. I guess the New constructor in vb is not what I have to use can you suggest what I should try.


Justin Ralston
GeneralRe: Access C# dll from Pin
Michael Coyle14-Sep-09 18:34
memberMichael Coyle14-Sep-09 18:34 
GeneralRe: Access C# dll from Pin
ralstogj16-Sep-09 0:17
memberralstogj16-Sep-09 0:17 
Questionremove node function? Pin
Member 17427019-Aug-09 13:22
memberMember 17427019-Aug-09 13:22 
AnswerRe: remove node function? Pin
Michael Coyle10-Aug-09 9:36
memberMichael Coyle10-Aug-09 9:36 
GeneralRe: remove node function? Pin
Member 174270110-Aug-09 11:54
memberMember 174270110-Aug-09 11:54 
GeneralRe: remove node function? Pin
Michael Coyle4-Apr-12 11:28
memberMichael Coyle4-Apr-12 11:28 
GeneralRe: remove node function? Pin
aubergine20104-Sep-13 2:26
memberaubergine20104-Sep-13 2:26 
GeneralRe: remove node function? Pin
Michael Coyle6-Sep-13 7:33
memberMichael Coyle6-Sep-13 7:33 
GeneralThe circle is not placed exactly under the mouse clicking location. Pin
danielmark9-Mar-09 5:31
memberdanielmark9-Mar-09 5:31 
GeneralRe: The circle is not placed exactly under the mouse clicking location. Pin
Michael Coyle9-Mar-09 6:33
memberMichael Coyle9-Mar-09 6:33 
GeneralRe: The circle is not placed exactly under the mouse clicking location. Pin
danielmark9-Mar-09 16:09
memberdanielmark9-Mar-09 16:09 
GeneralRe: The circle is not placed exactly under the mouse clicking location. Pin
DukeForge1-May-09 17:29
memberDukeForge1-May-09 17:29 
GeneralFound a bug Pin
rlukashuk15-Dec-08 12:46
memberrlukashuk15-Dec-08 12:46 
GeneralRe: Found a bug Pin
Michael Coyle15-Dec-08 12:51
memberMichael Coyle15-Dec-08 12:51 
GeneralSource Code Links Pin
Henry Minute29-Oct-08 23:49
memberHenry Minute29-Oct-08 23:49 
GeneralSource Code Links Pin
Henry Minute29-Oct-08 23:49
memberHenry Minute29-Oct-08 23:49 
GeneralRe: Source Code Links Pin
Michael Coyle30-Oct-08 7:56
memberMichael Coyle30-Oct-08 7:56 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

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

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.171017.1 | Last Updated 30 Oct 2008
Article Copyright 2008 by Michael Coyle
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid