1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173 |
// *******************************************//
// *********Credits to Kyle Schouviller*******//
// *******for the original implementation*****//
// *******************************************//
using System;
using System.Collections.Generic;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
namespace Brains.Framework.QuadTree
{
public class QuadTree<T>
{
public static Rectangle GetRectangle(RectangleF rect)
{
return new Rectangle((int)rect.Left, (int)rect.Top, (int)rect.Width, (int)rect.Height);
}
/// <summary>
/// The head node of the QuadTree
/// </summary>
protected QuadTreeNode<T> headNode;
/// <summary>
/// Gets the world rectangle
/// </summary>
public RectangleF WorldRect
{
get { return headNode.Rect; }
}
/// <summary>
/// The maximum number of items in any node before partitioning
/// </summary>
protected int maxItems;
/// <summary>
/// QuadTree constructor
/// </summary>
/// <param name="worldRect">The world rectangle for this QuadTree (a rectangle containing all items at all times)</param>
/// <param name="maxItems">Maximum number of items in any cell of the QuadTree before partitioning</param>
public QuadTree(RectangleF worldRect, int maxItems)
{
this.headNode = new QuadTreeNode<T>(worldRect, maxItems, Resize);
this.maxItems = maxItems;
}
/// <summary>
/// QuadTree constructor
/// </summary>
/// <param name="size">The size of the QuadTree (i.e. the bottom-right with a top-left of (0,0))</param>
/// <param name="maxItems">Maximum number of items in any cell of the QuadTree before partitioning</param>
/// <remarks>This constructor is for ease of use</remarks>
public QuadTree(Vector2 size, int maxItems)
: this(new RectangleF(Vector2.Zero, size), maxItems)
{
// Nothing extra to initialize
}
/// <summary>
/// Inserts an item into the QuadTree
/// </summary>
/// <param name="item">The item to insert</param>
/// <remarks>Checks to see if the world needs resizing and does so if needed</remarks>
public void Insert(QuadTreePositionItem<T> item)
{
// check if the world needs resizing
if (!headNode.ContainsRect(item.Rect))
{
Resize(new RectangleF(
Vector2.Min(headNode.Rect.TopLeft, item.Rect.TopLeft) * 2,
Vector2.Max(headNode.Rect.BottomRight, item.Rect.BottomRight) * 2));
}
item.node = null;
item.quadTree = this;
headNode.Insert(item);
}
/// <summary>
/// Inserts an item into the QuadTree
/// </summary>
/// <param name="parent">The parent of the new position item</param>
/// <param name="position">The position of the new position item</param>
/// <param name="size">The size of the new position item</param>
/// <returns>A new position item</returns>
/// <remarks>Checks to see if the world needs resizing and does so if needed</remarks>
public QuadTreePositionItem<T> Insert(T parent, Vector2 position, Vector2 size)
{
QuadTreePositionItem<T> item = new QuadTreePositionItem<T>(parent, position, size);
// check if the world needs resizing
if (!headNode.ContainsRect(item.Rect))
{
Resize(new RectangleF(
Vector2.Min(headNode.Rect.TopLeft, item.Rect.TopLeft) * 2,
Vector2.Max(headNode.Rect.BottomRight, item.Rect.BottomRight) * 2));
}
item.node = null;
item.quadTree = this;
headNode.Insert(item);
return item;
}
/// <summary>
/// Resizes the Quadtree field
/// </summary>
/// <param name="newWorld">The new field</param>
/// <remarks>This is an expensive operation, so try to initialize the world to a big enough size</remarks>
public void Resize(RectangleF newWorld)
{
// Get all of the items in the tree
List<QuadTreePositionItem<T>> Components = new List<QuadTreePositionItem<T>>();
GetAllItems(ref Components);
// Destroy the head node
headNode.Destroy();
headNode = null;
// Create a new head
headNode = new QuadTreeNode<T>(newWorld, maxItems, Resize);
// Reinsert the items
foreach (QuadTreePositionItem<T> m in Components)
{
headNode.Insert(m);
}
}
/// <summary>
/// Gets a list of items containing a specified point
/// </summary>
/// <param name="Point">The point</param>
/// <param name="ItemsFound">The list to add found items to (list will not be cleared first)</param>
public void GetItems(Vector2 Point, ref List<QuadTreePositionItem<T>> ItemsList)
{
if (ItemsList != null)
{
headNode.GetItems(Point, ref ItemsList);
}
}
/// <summary>
/// Gets a list of items intersecting a specified rectangle
/// </summary>
/// <param name="Rect">The rectangle</param>
/// <param name="ItemsFound">The list to add found items to (list will not be cleared first)</param>
public void GetItems(RectangleF Rect, ref List<QuadTreePositionItem<T>> ItemsList)
{
if (ItemsList != null)
{
headNode.GetItems(Rect, ref ItemsList);
}
}
/// <summary>
/// Get a list of all items in the quadtree
/// </summary>
/// <param name="ItemsFound">The list to add found items to (list will not be cleared first)</param>
public void GetAllItems(ref List<QuadTreePositionItem<T>> ItemsList)
{
if (ItemsList != null)
{
headNode.GetAllItems(ref ItemsList);
}
}
}
} |
