Current Quadtree [Untested]

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Drawing;

namespace Aura.World.Util
{
	public class QuadTree
	{
		public const uint MAX_OBJECTS = 4;
		public const uint MAX_LEVELS = 8;

		private int _level = 0;
		private Rectangle _bounds;

		public List<Rectangle> Objects = new List<Rectangle>();
		public QuadTree[] Nodes;
		//Properties
		public int Level { get { return _level; } }
		public Rectangle Bounds { get { return _bounds; } }

		public QuadTree(int pLevel, Rectangle pBounds)
		{
			Nodes = new QuadTree[4];
			_bounds = pBounds;
		}

		/// <summary>
		/// Splits the quadtree into 4 quadrants.
		/// </summary>
		private void Split()
		{
			int newWidth = _bounds.Width / 2;
			int newHeight = _bounds.Height / 2;
			Nodes[0] = new QuadTree(this.Level + 1, new Rectangle(_bounds.X,_bounds.Y, newWidth,newHeight));
			Nodes[1] = new QuadTree(this.Level + 1, new Rectangle(_bounds.X + newWidth, _bounds.Y, newWidth, newHeight));
			Nodes[2] = new QuadTree(this.Level + 1, new Rectangle(_bounds.X + newWidth, _bounds.Y + newHeight, newWidth, newHeight));
			Nodes[3] = new QuadTree(this.Level + 1, new Rectangle(_bounds.X, _bounds.Y + newHeight, newWidth, newHeight));
		}

		/// <summary>
		/// Clears the Objects and all sub-objects
		/// </summary>
		public void Clear()
		{
			this.Objects.Clear();

			for (int i = 0; i < Nodes.Length; i++)
			{
				if (Nodes[i] != null)
				{
					Nodes[i].Clear();
					Nodes[i] = null;
				}
			}
		}

		/// <summary>
		/// Tries entering the object into the quadtree. If an object does not fully fit into a section it
		/// places it in the current object list
		/// </summary>
		/// <param name="pObject"></param>
		public void Insert(Rectangle pObject)
		{
			if (Nodes[0] != null)
			{
				var index = this.GetIndex(pObject);
				if (index != -1)
				{
					Nodes[index].Insert(pObject);
				}
			}

			Objects.Add(pObject);
			if (Objects.Count > MAX_OBJECTS && Level < MAX_LEVELS)
			{
				if (Nodes[0] == null)
					this.Split();

				List<Rectangle> toRemove = new List<Rectangle>();

				foreach(Rectangle obj in Objects){
					var index = this.GetIndex(obj);
					if (index != -1)
					{
						Nodes[index].Insert(obj);
						toRemove.Add(obj);
					}
				}

				foreach (var o in toRemove)
				{
					Objects.Remove(o);
				}
			}
		}

		/// <summary>
		/// Returns all objects and node objects
		/// </summary>
		/// <returns></returns>
		public List<Rectangle> GetChildObjects()
		{
			List<Rectangle> toReturn = this.Objects;
			if (Nodes[0] != null)
			{
				foreach (var obj in Nodes[0].GetChildObjects())
					toReturn.Add(obj);
			}

			return toReturn;
		}

		/// <summary>
		/// Returns all objects the given object may collide with
		/// </summary>
		/// <param name="pObject"></param>
		/// <returns></returns>
		public List<Rectangle> GetInRange(Rectangle pObject)
		{
			List<Rectangle> toReturn = new List<Rectangle>();
			var index = this.GetIndex(pObject);
			if (index != -1)
			{
				foreach (var i in Nodes[index].GetInRange(pObject))
					toReturn.Add(i);
			}

			foreach (var obj in Objects)
				toReturn.Add(obj);

			return toReturn;
		}

		/// <summary>
		/// Returns the index of the quadtree that the object fits into.
		/// If the object does not completely fit into a quadrant, it will return -1
		/// </summary>
		/// <param name="pObject"></param>
		/// <returns></returns>
		public int GetIndex(Rectangle pObject)
		{
			int index = -1;

			int vMidpoint = _bounds.X + (Bounds.Width / 2);
			int hMidpoint = _bounds.Y + (Bounds.Height / 2);

			var topHalf = (pObject.Y < hMidpoint && pObject.Y + pObject.Height < hMidpoint);
			var leftHalf = (pObject.X < vMidpoint && pObject.X + pObject.Width < vMidpoint);

			if (topHalf)
			{
				index = 0;
			}
			else
			{
				index = 2;
			}

			if (leftHalf)
				index += 1;

			return index;
		}
	}
}