source: trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/QuadTree/QuadTree.cs @ 1927

Last change on this file since 1927 was 1927, checked in by matkovic, 11 years ago

-added PowerCollection library
-added QuadTree
-improved path finding performance

File size: 2.4 KB
Line 
1using System;
2using System.Drawing;
3using System.Collections.Generic;
4using System.Diagnostics;
5
6namespace QuadTreeLib
7{
8    /// <summary>
9    /// A Quadtree is a structure designed to partition space so
10    /// that it's faster to find out what is inside or outside a given
11    /// area. See http://en.wikipedia.org/wiki/Quadtree
12    /// This QuadTree contains items that have an area (RectangleF)
13    /// it will store a reference to the item in the quad
14    /// that is just big enough to hold it. Each quad has a bucket that
15    /// contain multiple items.
16    /// </summary>
17    public class QuadTree<T> where T : IHasRect
18    {
19        /// <summary>
20        /// The root QuadTreeNode
21        /// </summary>
22        QuadTreeNode<T> m_root;
23
24        /// <summary>
25        /// The bounds of this QuadTree
26        /// </summary>
27        RectangleF m_rectangle;
28
29        /// <summary>
30        /// An delegate that performs an action on a QuadTreeNode
31        /// </summary>
32        /// <param name="obj"></param>
33        public delegate void QTAction(QuadTreeNode<T> obj);
34
35        /// <summary>
36        ///
37        /// </summary>
38        /// <param name="rectangle"></param>
39        public QuadTree(RectangleF rectangle)
40        {
41            m_rectangle = rectangle;
42            m_root = new QuadTreeNode<T>(m_rectangle);
43        }
44
45        /// <summary>
46        /// Get the count of items in the QuadTree
47        /// </summary>
48        public int Count { get { return m_root.Count; } }
49
50        /// <summary>
51        /// Insert the feature into the QuadTree
52        /// </summary>
53        /// <param name="item"></param>
54        public void Insert(T item)
55        {
56            m_root.Insert(item);
57        }
58
59        /// <summary>
60        /// Query the QuadTree, returning the items that are in the given area
61        /// </summary>
62        /// <param name="area"></param>
63        /// <returns></returns>
64        public List<T> Query(RectangleF area)
65        {
66            return m_root.Query(area);
67        }
68       
69        /// <summary>
70        /// Do the specified action for each item in the quadtree
71        /// </summary>
72        /// <param name="action"></param>
73        public void ForEach(QTAction action)
74        {
75            m_root.ForEach(action);
76        }
77
78
79        internal bool QueryAny(RectangleF queryRect)
80        {
81            return m_root.QueryAny(queryRect);
82        }
83    }
84
85}
Note: See TracBrowser for help on using the repository browser.