root/src/BRAINSFramework/QuadTree/QuadTreeNode.cs

Show revision log
 
113
1
// *******************************************************************************//
1
// *******************************************//
2
// *******************************************************************************//
2
// *********Credits to Kyle Schouviller*******//
3
// *************************Credits to Kyle Schouviller***************************//
3
// *******for the original implementation*****//
4
// *************************for the original implementation***********************//
4
// *******************************************//
5
// *******************************************************************************//



6
// *******************************************************************************//



7
// *******************************************************************************//



8
// *******************************************************************************//



9
// *******************************************************************************//



10
5



11
6



7



12
using System;
8
using System;



13
using System.Collections.Generic;
9
using System.Collections.Generic;



14
using Microsoft.Xna.Framework;
10
using Microsoft.Xna.Framework;


...
...
16
12



17
13



18
14



19
namespace Brains.Framework
15
namespace Brains.Framework.QuadTree



20
{
16
{



21
    public class QuadTreeNode<T>
17
    public class QuadTreeNode<T>



22
    {
18
    {



23
        public static Rectangle GetRectangle(FRect rect)
19
        public static Rectangle GetRectangle(RectangleF rect)



24
        {
20
        {



25
            return new Rectangle((int)rect.Left, (int)rect.Top, (int)rect.Width, (int)rect.Height);
21
            return new Rectangle((int)rect.Left, (int)rect.Top, (int)rect.Width, (int)rect.Height);



26
        }
22
        }



27
23



28
        #region Delegates
24
        



29
25



30
        /// <summary>
26
        /// <summary>



31
        /// World resize delegate
27
        /// World resize delegate



32
        /// </summary>
28
        /// </summary>



33
        /// <param name="newSize">The new world size</param>
29
        /// <param name="newSize">The new world size</param>



34
        public delegate void ResizeDelegate(FRect newSize);
30
        public delegate void ResizeDelegate(RectangleF newSize);



35
31



36
        #endregion
32
        



37
33



38
        #region Properties
34
        



39
35



40
        /// <summary>
36
        /// <summary>



41
        /// The rectangle of this node
37
        /// The rectangle of this node



42
        /// </summary>
38
        /// </summary>



43
        protected FRect rect;
39
        protected RectangleF rect;



44
40



45
        /// <summary>
41
        /// <summary>



46
        /// Gets the rectangle of this node
42
        /// Gets the rectangle of this node



47
        /// </summary>
43
        /// </summary>



48
        public FRect Rect
44
        public RectangleF Rect



49
        {
45
        {



50
            get { return rect; }
46
            get { return rect; }



51
            protected set { rect = value; }
47
            protected set { rect = value; }


...
...
97
        /// <param name="newSize">The new world size</param>
93
        /// <param name="newSize">The new world size</param>



98
        protected ResizeDelegate WorldResize;
94
        protected ResizeDelegate WorldResize;



99
95



100
        #endregion
96
        



101
97



102
        #region Initialization
98
        



103
99



104
        /// <summary>
100
        /// <summary>



105
        /// QuadTreeNode constructor
101
        /// QuadTreeNode constructor


...
...
107
        /// <param name="parentNode">The parent node of this QuadTreeNode</param>
103
        /// <param name="parentNode">The parent node of this QuadTreeNode</param>



108
        /// <param name="rect">The rectangle of the QuadTreeNode</param>
104
        /// <param name="rect">The rectangle of the QuadTreeNode</param>



109
        /// <param name="maxItems">Maximum number of items in the QuadTreeNode before partitioning</param>
105
        /// <param name="maxItems">Maximum number of items in the QuadTreeNode before partitioning</param>



110
        public QuadTreeNode(QuadTreeNode<T> parentNode, FRect rect, int maxItems)
106
        public QuadTreeNode(QuadTreeNode<T> parentNode, RectangleF rect, int maxItems)



111
        {
107
        {



112
            ParentNode = parentNode;
108
            ParentNode = parentNode;



113
            Rect = rect;
109
            Rect = rect;


...
...
122
        /// <param name="rect">The rectangle of the QuadTreeNode</param>
118
        /// <param name="rect">The rectangle of the QuadTreeNode</param>



123
        /// <param name="maxItems">Maximum number of items in the QuadTreeNode before partitioning</param>
119
        /// <param name="maxItems">Maximum number of items in the QuadTreeNode before partitioning</param>



124
        /// <param name="worldResize">The function to return the size</param>
120
        /// <param name="worldResize">The function to return the size</param>



125
        public QuadTreeNode(FRect rect, int maxItems, ResizeDelegate worldResize)
121
        public QuadTreeNode(RectangleF rect, int maxItems, ResizeDelegate worldResize)



126
        {
122
        {



127
            ParentNode = null;
123
            ParentNode = null;



128
            Rect = rect;
124
            Rect = rect;


...
...
132
            Items = new List<QuadTreePositionItem<T>>();
128
            Items = new List<QuadTreePositionItem<T>>();



133
        }
129
        }



134
130



135
        #endregion
131
        



136
132



137
        #region Insertion methods
133
        



138
134



139
        /// <summary>
135
        /// <summary>



140
        /// Insert an item in this node
136
        /// Insert an item in this node


...
...
216
            // Create the nodes
212
            // Create the nodes



217
            Vector2 MidPoint = Vector2.Divide(Vector2.Add(Rect.TopLeft, Rect.BottomRight), 2.0f);
213
            Vector2 MidPoint = Vector2.Divide(Vector2.Add(Rect.TopLeft, Rect.BottomRight), 2.0f);



218
214



219
            TopLeftNode = new QuadTreeNode<T>(this, new FRect(Rect.TopLeft, MidPoint), MaxItems);
215
            TopLeftNode = new QuadTreeNode<T>(this, new RectangleF(Rect.TopLeft, MidPoint), MaxItems);



220
            TopRightNode = new QuadTreeNode<T>(this, new FRect(new Vector2(MidPoint.X, Rect.Top), new Vector2(Rect.Right, MidPoint.Y)), MaxItems);
216
            TopRightNode = new QuadTreeNode<T>(this, new RectangleF(new Vector2(MidPoint.X, Rect.Top), new Vector2(Rect.Right, MidPoint.Y)), MaxItems);



221
            BottomLeftNode = new QuadTreeNode<T>(this, new FRect(new Vector2(Rect.Left, MidPoint.Y), new Vector2(MidPoint.X, Rect.Bottom)), MaxItems);
217
            BottomLeftNode = new QuadTreeNode<T>(this, new RectangleF(new Vector2(Rect.Left, MidPoint.Y), new Vector2(MidPoint.X, Rect.Bottom)), MaxItems);



222
            BottomRightNode = new QuadTreeNode<T>(this, new FRect(MidPoint, Rect.BottomRight), MaxItems);
218
            BottomRightNode = new QuadTreeNode<T>(this, new RectangleF(MidPoint, Rect.BottomRight), MaxItems);



223
219



224
            IsPartitioned = true;
220
            IsPartitioned = true;



225
221


...
...
234
            }
230
            }



235
        }
231
        }



236
232



237
        #endregion
233
        



238
234



239
        #region Query methods
235
        



240
236



241
        /// <summary>
237
        /// <summary>



242
        /// Gets a list of items containing a specified point
238
        /// Gets a list of items containing a specified point


...
...
272
        /// <param name="Rect">The rectangle</param>
268
        /// <param name="Rect">The rectangle</param>



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



274
        /// <remarks>ItemsFound is assumed to be initialized, and will not be cleared</remarks>
270
        /// <remarks>ItemsFound is assumed to be initialized, and will not be cleared</remarks>



275
        public void GetItems(FRect Rect, ref List<QuadTreePositionItem<T>> ItemsFound)
271
        public void GetItems(RectangleF Rect, ref List<QuadTreePositionItem<T>> ItemsFound)



276
        {
272
        {



277
            
273
            



278
            // test the point against this node
274
            // test the point against this node


...
...
359
            else return null;
355
            else return null;



360
        }
356
        }



361
357



362
        #endregion
358
        



363
359



364
        #region Destruction
360
        



365
361



366
        /// <summary>
362
        /// <summary>



367
        /// Destroys this node
363
        /// Destroys this node


...
...
418
            }
414
            }



419
        }
415
        }



420
416



421
        #endregion
417
        



422
418



423
        #region Observer methods
419
        



424
420



425
        /// <summary>
421
        /// <summary>



426
        /// Handles item movement
422
        /// Handles item movement


...
...
444
                    }
440
                    }



445
                    else if (!ContainsRect(item.Rect))
441
                    else if (!ContainsRect(item.Rect))



446
                    {
442
                    {



447
                        WorldResize(new FRect(
443
                        WorldResize(new RectangleF(



448
                             Vector2.Min(Rect.TopLeft, item.Rect.TopLeft) * 2,
444
                             Vector2.Min(Rect.TopLeft, item.Rect.TopLeft) * 2,



449
                             Vector2.Max(Rect.BottomRight, item.Rect.BottomRight) * 2));
445
                             Vector2.Max(Rect.BottomRight, item.Rect.BottomRight) * 2));



450
                    }
446
                    }


...
...
468
            RemoveItem(item);
464
            RemoveItem(item);



469
        }
465
        }



470
466



471
        #endregion
467
        



472
468



473
        #region Helper methods
469
        



474
470



475
        /// <summary>
471
        /// <summary>



476
        /// Tests whether this node contains a rectangle
472
        /// Tests whether this node contains a rectangle



477
        /// </summary>
473
        /// </summary>



478
        /// <param name="rect">The rectangle to test</param>
474
        /// <param name="rect">The rectangle to test</param>



479
        /// <returns>Whether or not this node contains the specified rectangle</returns>
475
        /// <returns>Whether or not this node contains the specified rectangle</returns>



480
        public bool ContainsRect(FRect rect)
476
        public bool ContainsRect(RectangleF rect)



481
        {
477
        {



482
            return (rect.TopLeft.X >= Rect.TopLeft.X &&
478
            return (rect.TopLeft.X >= Rect.TopLeft.X &&



483
                    rect.TopLeft.Y >= Rect.TopLeft.Y &&
479
                    rect.TopLeft.Y >= Rect.TopLeft.Y &&


...
...
485
                    rect.BottomRight.Y <= Rect.BottomRight.Y);
481
                    rect.BottomRight.Y <= Rect.BottomRight.Y);



486
        }
482
        }



487
483



488
        #endregion
484
        



489
485



490
    }
486
    }



491
}
487
}