"Generic" QuadTree implementation

[GaryTexmo]

For a project I'm working on I had need of a QuadTree to give me quick and easy access to objects within a given bounds. I learned quite a bit working on it and thought it might be a good idea to share the code with the Bytes community.

To use it, create a new QuadTree and tell it what area it's going to cover. Then simply insert objects into it using the Insert method. You can use the Remove method to take objects out. On a removal, if a quad's children are empty, the children will be removed.

Some notes, in no particular order...

* This QuadTree holds any type, so long as that type inherits from IHasRectangle and implements the property the interface defines. This is so the QuadTree knows what the bounds of an object are.

* In this implementation, a quad will subdivide when it holds more than two objects. That said, a quad will only contain an object that it completely contains. If a quad's children cannot contain an object, it will live in the quad itself.

* The code is built using an XNA rectangle. It should be easy to modify the code to work with System.Drawing, or even a custom Rectangle object if desired. So long as the object provides the appropriate methods (Contains and Intersects), minimal work should be required to port.

* This code is offered freely, enjoy!

* In light of the above, note that it's not guaranteed to be bug free. I've tested it fairly extensively but it's quite possible I missed something. I'm definitely open to feedback, but please keep it constructive.

* I'm still doing a bit of work on this, but it's going to make it a little more XNA specific. This is the generic version of the object. I may post an update later.

Enough rambling... here's the code.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
 
namespace QuadTree
{
    /// <summary>
    /// Interface to define Rect, so that QuadTree knows how to store the object.
    /// </summary>
    public interface IHasRectangle
    {
        /// <summary>
        /// The rectangle that defines the object's boundaries.
        /// </summary>
        Rectangle Rect { get; }
    }
 
    /// <summary>
    /// A QuadTree Object that provides fast and efficient storage of objects in a world space.
    /// </summary>
    /// <typeparam name="T">Any object iheriting from IHasRect.</typeparam>
    public class QuadTree<T> where T : IHasRectangle
    {
        #region Constants
        // How many objects can exist in a QuadTree before it sub divides itself
        private const int MAX_OBJECTS_PER_NODE = 2;
        #endregion
 
        #region Private Members
        private List<T> m_objects = null;       // The objects in this QuadTree
        private Rectangle m_rect;               // The area this QuadTree represents
 
        private QuadTree<T> m_childTL = null;   // Top Left Child
        private QuadTree<T> m_childTR = null;   // Top Right Child
        private QuadTree<T> m_childBL = null;   // Bottom Left Child
        private QuadTree<T> m_childBR = null;   // Bottom Right Child
        #endregion
 
        #region Public Properties
        /// <summary>
        /// The area this QuadTree represents.
        /// </summary>
        public Rectangle QuadRect { get { return m_rect; } }
 
        /// <summary>
        /// The top left child for this QuadTree
        /// </summary>
        public QuadTree<T> TopLeftChild { get { return m_childTL; } }
 
        /// <summary>
        /// The top right child for this QuadTree
        /// </summary>
        public QuadTree<T> TopRightChild { get { return m_childTR; } }
 
        /// <summary>
        /// The bottom left child for this QuadTree
        /// </summary>
        public QuadTree<T> BottomLeftChild { get { return m_childBL; } }
 
        /// <summary>
        /// The bottom right child for this QuadTree
        /// </summary>
        public QuadTree<T> BottomRightChild { get { return m_childBR; } }
 
        /// <summary>
        /// The objects contained in this QuadTree at it's level (ie, excludes children)
        /// </summary>
        public List<T> Objects { get { return m_objects; } }
 
        /// <summary>
        /// How many total objects are contained within this QuadTree (ie, includes children)
        /// </summary>
        public int Count { get { return this.ObjectCount(); } }
        #endregion
 
        #region Constructor
        /// <summary>
        /// Creates a QuadTree for the specified area.
        /// </summary>
        /// <param name="rect">The area this QuadTree object will encompass.</param>
        public QuadTree(Rectangle rect)
        {
            m_rect = rect;
        }
 
        /// <summary>
        /// Creates a QuadTree for the specified area.
        /// </summary>
        /// <param name="x">The top-left position of the area rectangle.</param>
        /// <param name="y">The top-right position of the area reactangle.</param>
        /// <param name="width">The width of the area rectangle.</param>
        /// <param name="height">The height of the area rectangle.</param>
        public QuadTree(int x, int y, int width, int height)
        {
            m_rect = new Rectangle(x, y, width, height);
        }
        #endregion
 
        #region Private Members
        /// <summary>
        /// Add an item to the object list.
        /// </summary>
        /// <param name="item">The item to add.</param>
        private void Add(T item)
        {
            if (m_objects == null)
                m_objects = new List<T>();
 
            m_objects.Add(item);
        }
 
        /// <summary>
        /// Remove an item from the object list.
        /// </summary>
        /// <param name="item">The object to remove.</param>
        private void Remove(T item)
        {
            if (m_objects != null && m_objects.Contains(item))
                m_objects.Remove(item);
        }
 
        /// <summary>
        /// Get the total for all objects in this QuadTree, including children.
        /// </summary>
        /// <returns>The number of objects contained within this QuadTree and its children.</returns>
        private int ObjectCount()
        {
            int count = 0;
 
            // Add the objects at this level
            if (m_objects != null) count += m_objects.Count;
 
            // Add the objects that are contained in the children
            if (m_childTL != null)
            {
                count += m_childTL.ObjectCount();
                count += m_childTR.ObjectCount();
                count += m_childBL.ObjectCount();
                count += m_childBR.ObjectCount();
            }
 
            return count;
        }
 
        /// <summary>
        /// Subdivide this QuadTree and move it's children into the appropriate Quads where applicable.
        /// </summary>
        private void Subdivide()
        {
            // We've reached capacity, subdivide...
            Point size = new Point(m_rect.Width / 2, m_rect.Height / 2);
            Point mid = new Point(m_rect.X + size.X, m_rect.Y + size.Y);
 
            m_childTL = new QuadTree<T>(new Rectangle(m_rect.Left, m_rect.Top, size.X, size.Y));
            m_childTR = new QuadTree<T>(new Rectangle(mid.X, m_rect.Top, size.X, size.Y));
            m_childBL = new QuadTree<T>(new Rectangle(m_rect.Left, mid.Y, size.X, size.Y));
            m_childBR = new QuadTree<T>(new Rectangle(mid.X, mid.Y, size.X, size.Y));
 
            // If they're completely contained by the quad, bump objects down
            for (int i = 0; i < m_objects.Count; i++)
            {
                QuadTree<T> destTree = GetDestinationTree(m_objects[i]);
 
                if (destTree != this)
                {
                    // Insert to the appropriate tree, remove the object, and back up one in the loop
                    destTree.Insert(m_objects[i]);
                    Remove(m_objects[i]);
                    i--;
                }
            }
        }
 
        /// <summary>
        /// Get the child Quad that would contain an object.
        /// </summary>
        /// <param name="item">The object to get a child for.</param>
        /// <returns></returns>
        private QuadTree<T> GetDestinationTree(T item)
        {
            // If a child can't contain an object, it will live in this Quad
            QuadTree<T> destTree = this;
 
            if (m_childTL.QuadRect.Contains(item.Rect))
            {
                destTree = m_childTL;
            }
            else if (m_childTR.QuadRect.Contains(item.Rect))
            {
                destTree = m_childTR;
            }
            else if (m_childBL.QuadRect.Contains(item.Rect))
            {
                destTree = m_childBL;
            }
            else if (m_childBR.QuadRect.Contains(item.Rect))
            {
                destTree = m_childBR;
            }
 
            return destTree;
        }
        #endregion
 
        #region Public Methods
        /// <summary>
        /// Clears the QuadTree of all objects, including any objects living in its children.
        /// </summary>
        public void Clear()
        {
            // Clear out the children, if we have any
            if (m_childTL != null)
            {
                m_childTL.Clear();
                m_childTR.Clear();
                m_childBL.Clear();
                m_childBR.Clear();
            }
 
            // Clear any objects at this level
            if (m_objects != null)
            {
                m_objects.Clear();
                m_objects = null;
            }
 
            // Set the children to null
            m_childTL = null;
            m_childTR = null;
            m_childBL = null;
            m_childBR = null;
        }
 
        /// <summary>
        /// Deletes an item from this QuadTree. If the object is removed causes this Quad to have no objects in its children, it's children will be removed as well.
        /// </summary>
        /// <param name="item">The item to remove.</param>
        public void Delete(T item)
        {
            // If this level contains the object, remove it
            bool objectRemoved = false;
            if (m_objects != null && m_objects.Contains(item))
            {
                Remove(item);
                objectRemoved = true;
            }
 
            // If we didn't find the object in this tree, try to delete from its children
            if (m_childTL != null && !objectRemoved)
            {
                m_childTL.Delete(item);
                m_childTR.Delete(item);
                m_childBL.Delete(item);
                m_childBR.Delete(item);
            }
 
            if (m_childTL != null)
            {
                // If all the children are empty, delete all the children
                if (m_childTL.Count == 0 &&
                    m_childTR.Count == 0 &&
                    m_childBL.Count == 0 &&
                    m_childBR.Count == 0)
                {
                    m_childTL = null;
                    m_childTR = null;
                    m_childBL = null;
                    m_childBR = null;
                }
            }
        }
 
        /// <summary>
        /// Insert an item into this QuadTree object.
        /// </summary>
        /// <param name="item">The item to insert.</param>
        public void Insert(T item)
        {
            // If this quad doesn't intersect the items rectangle, do nothing
            if (!m_rect.Intersects(item.Rect))
                return;
 
            if (m_objects == null || 
                (m_childTL == null && m_objects.Count + 1 <= MAX_OBJECTS_PER_NODE))
            {
                // If there's room to add the object, just add it
                Add(item);
            }
            else
            {
                // No quads, create them and bump objects down where appropriate
                if (m_childTL == null)
                {
                    Subdivide();
                }
 
                // Find out which tree this object should go in and add it there
                QuadTree<T> destTree = GetDestinationTree(item);
                if (destTree == this)
                {
                    Add(item);
                }
                else
                {
                    destTree.Insert(item);
                }
            }
        }
 
        /// <summary>
        /// Get the objects in this tree that intersect with the specified rectangle.
        /// </summary>
        /// <param name="rect">The rectangle to find objects in.</param>
        /// <param name="results">A reference to a list that will be populated with the results.</param>
        public void GetObjects(Rectangle rect, ref List<T> results)
        {
            // We can't do anything if the results list doesn't exist
            if (results != null)
            {
                if (rect.Contains(m_rect))
                {
                    // If the search area completely contains this quad, just get every object this quad and all it's children have
                    GetAllObjects(ref results);
                }
                else if (rect.Intersects(m_rect))
                {
                    // Otherwise, if the quad isn't fully contained, only add objects that intersect with the search rectangle
                    if (m_objects != null)
                    {
                        for (int i = 0; i < m_objects.Count; i++)
                        {
                            if (rect.Intersects(m_objects[i].Rect))
                            {
                                results.Add(m_objects[i]);
                            }
                        }
                    }
 
                    // Get the objects for the search rectangle from the children
                    if (m_childTL != null)
                    {
                        m_childTL.GetObjects(rect, ref results);
                        m_childTR.GetObjects(rect, ref results);
                        m_childBL.GetObjects(rect, ref results);
                        m_childBR.GetObjects(rect, ref results);
                    }
                }
            }
        }
 
        /// <summary>
        /// Get all objects in this Quad, and it's children.
        /// </summary>
        /// <param name="results">A reference to a list in which to store the objects.</param>
        public void GetAllObjects(ref List<T> results)
        {
            // If this Quad has objects, add them
            if (m_objects != null)
                results.AddRange(m_objects);
 
            // If we have children, get their objects too
            if (m_childTL != null)
            {
                m_childTL.GetAllObjects(ref results);
                m_childTR.GetAllObjects(ref results);
                m_childBL.GetAllObjects(ref results);
                m_childBR.GetAllObjects(ref results);
            }
        }
        #endregion
    }
}
 

[GaryTexmo]

Update

This project is still being developed. When we have time to work on it, a friend and I are enhancing this to support moving objects in a more efficient manner. The project can be tracked at SourceForge at the following URL: https://sourceforge.net/projects/quadtree/.

The above still provides a good, basic implementation, but if your project is going to have many moving objects, you may want to keep track of the updates.

Thanks!

[TravisM]

Thank you sir, I've implemented your code with my own interface and used a few foreach loops in an array of children, using null for no children. Thanks again for the start on this. I see using this for terrain and game objects that exist therein. :)