root/src/BRAINSFramework/QuadTree/QuadTree.cs

Show revision log
 
113
1
// *******************************************//



2
// *********Credits to Kyle Schouviller*******//



3
// *******for the original implementation*****//



4
// *******************************************//



1
using System;
5
using System;



2
using System.Collections.Generic;
6
using System.Collections.Generic;



3
using System.Text;
7
using System.Text;


...
...
5
using Microsoft.Xna.Framework.Graphics;
9
using Microsoft.Xna.Framework.Graphics;



6
10



7
11



8
namespace Brains.Framework
12
namespace Brains.Framework.QuadTree



9
{
13
{



10
    public class QuadTree<T>
14
    public class QuadTree<T>



11
    {
15
    {



12
       
16



13
        public static Rectangle GetRectangle(FRect rect)
17
        public static Rectangle GetRectangle(RectangleF rect)



14
        {
18
        {



15
            return new Rectangle((int)rect.Left, (int)rect.Top, (int)rect.Width, (int)rect.Height);
19
            return new Rectangle((int)rect.Left, (int)rect.Top, (int)rect.Width, (int)rect.Height);



16
        }
20
        }



17
        public void Count()
21
        



18
        {



19
            



20
        }



21



22
        #region Properties



23



24
        /// <summary>
22
        /// <summary>



25
        /// The head node of the QuadTree
23
        /// The head node of the QuadTree



26
        /// </summary>
24
        /// </summary>


...
...
29
        /// <summary>
27
        /// <summary>



30
        /// Gets the world rectangle
28
        /// Gets the world rectangle



31
        /// </summary>
29
        /// </summary>



32
        public FRect WorldRect
30
        public RectangleF WorldRect



33
        {
31
        {



34
            get { return headNode.Rect; }
32
            get { return headNode.Rect; }



35
        }
33
        }


...
...
39
        /// </summary>
37
        /// </summary>



40
        protected int maxItems;
38
        protected int maxItems;



41
39



42
        #endregion



43



44
        #region Initialization



45



46
        /// <summary>
40
        /// <summary>



47
        /// QuadTree constructor
41
        /// QuadTree constructor



48
        /// </summary>
42
        /// </summary>



49
        /// <param name="worldRect">The world rectangle for this QuadTree (a rectangle containing all items at all times)</param>
43
        /// <param name="worldRect">The world rectangle for this QuadTree (a rectangle containing all items at all times)</param>



50
        /// <param name="maxItems">Maximum number of items in any cell of the QuadTree before partitioning</param>
44
        /// <param name="maxItems">Maximum number of items in any cell of the QuadTree before partitioning</param>



51
        public QuadTree(FRect worldRect, int maxItems)
45
        public QuadTree(RectangleF worldRect, int maxItems)



52
        {
46
        {



53
            this.headNode = new QuadTreeNode<T>(worldRect, maxItems, Resize);
47
            this.headNode = new QuadTreeNode<T>(worldRect, maxItems, Resize);



54
            this.maxItems = maxItems;
48
            this.maxItems = maxItems;


...
...
61
        /// <param name="maxItems">Maximum number of items in any cell of the QuadTree before partitioning</param>
55
        /// <param name="maxItems">Maximum number of items in any cell of the QuadTree before partitioning</param>



62
        /// <remarks>This constructor is for ease of use</remarks>
56
        /// <remarks>This constructor is for ease of use</remarks>



63
        public QuadTree(Vector2 size, int maxItems)
57
        public QuadTree(Vector2 size, int maxItems)



64
            : this(new FRect(Vector2.Zero, size), maxItems)
58
            : this(new RectangleF(Vector2.Zero, size), maxItems)



65
        {
59
        {



66
            // Nothing extra to initialize
60
            // Nothing extra to initialize



67
        }
61
        }



68
62
      



69
        #endregion



70



71
        #region Methods



72



73
        /// <summary>
63
        /// <summary>



74
        /// Inserts an item into the QuadTree
64
        /// Inserts an item into the QuadTree



75
        /// </summary>
65
        /// </summary>


...
...
80
            // check if the world needs resizing
70
            // check if the world needs resizing



81
            if (!headNode.ContainsRect(item.Rect))
71
            if (!headNode.ContainsRect(item.Rect))



82
            {
72
            {



83
                Resize(new FRect(
73
                Resize(new RectangleF(



84
                    Vector2.Min(headNode.Rect.TopLeft, item.Rect.TopLeft) * 2,
74
                    Vector2.Min(headNode.Rect.TopLeft, item.Rect.TopLeft) * 2,



85
                    Vector2.Max(headNode.Rect.BottomRight, item.Rect.BottomRight) * 2));
75
                    Vector2.Max(headNode.Rect.BottomRight, item.Rect.BottomRight) * 2));



86
            }
76
            }


...
...
104
            // check if the world needs resizing
94
            // check if the world needs resizing



105
            if (!headNode.ContainsRect(item.Rect))
95
            if (!headNode.ContainsRect(item.Rect))



106
            {
96
            {



107
                Resize(new FRect(
97
                Resize(new RectangleF(



108
                    Vector2.Min(headNode.Rect.TopLeft, item.Rect.TopLeft) * 2,
98
                    Vector2.Min(headNode.Rect.TopLeft, item.Rect.TopLeft) * 2,



109
                    Vector2.Max(headNode.Rect.BottomRight, item.Rect.BottomRight) * 2));
99
                    Vector2.Max(headNode.Rect.BottomRight, item.Rect.BottomRight) * 2));



110
            }
100
            }


...
...
120
        /// </summary>
110
        /// </summary>



121
        /// <param name="newWorld">The new field</param>
111
        /// <param name="newWorld">The new field</param>



122
        /// <remarks>This is an expensive operation, so try to initialize the world to a big enough size</remarks>
112
        /// <remarks>This is an expensive operation, so try to initialize the world to a big enough size</remarks>



123
        public void Resize(FRect newWorld)
113
        public void Resize(RectangleF newWorld)



124
        {
114
        {



125
            // Get all of the items in the tree
115
            // Get all of the items in the tree



126
            List<QuadTreePositionItem<T>> Components = new List<QuadTreePositionItem<T>>();
116
            List<QuadTreePositionItem<T>> Components = new List<QuadTreePositionItem<T>>();


...
...
140
            }
130
            }



141
        }
131
        }



142
132



143
        #endregion



144



145
        #region Query methods



146



147
        /// <summary>
133
        /// <summary>



148
        /// Gets a list of items containing a specified point
134
        /// Gets a list of items containing a specified point



149
        /// </summary>
135
        /// </summary>


...
...
162
        /// </summary>
148
        /// </summary>



163
        /// <param name="Rect">The rectangle</param>
149
        /// <param name="Rect">The rectangle</param>



164
        /// <param name="ItemsFound">The list to add found items to (list will not be cleared first)</param>
150
        /// <param name="ItemsFound">The list to add found items to (list will not be cleared first)</param>



165
        public void GetItems(FRect Rect, ref List<QuadTreePositionItem<T>> ItemsList)
151
        public void GetItems(RectangleF Rect, ref List<QuadTreePositionItem<T>> ItemsList)



166
        {
152
        {



167
            if (ItemsList != null)
153
            if (ItemsList != null)



168
            {
154
            {


...
...
181
                headNode.GetAllItems(ref ItemsList);
167
                headNode.GetAllItems(ref ItemsList);



182
            }
168
            }



183
        }
169
        }



184



185
        #endregion



186



187
      



188
    }
170
    }



189
171



190
172