source: trunk/CrypPlugins/WorkspaceManager/View/VisualComponents/CryptoLineView/QuadTree/QuadTreeNode.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: 9.0 KB
RevLine 
[1927]1using System;
2using System.Collections.Generic;
3using System.Drawing;
4using System.Diagnostics;
5
6namespace QuadTreeLib
7{
8    /// <summary>
9    /// The QuadTreeNode
10    /// </summary>
11    /// <typeparam name="T"></typeparam>
12    public class QuadTreeNode<T> where T : IHasRect
13    {
14        /// <summary>
15        /// Construct a quadtree node with the given bounds
16        /// </summary>
17        /// <param name="area"></param>
18        public QuadTreeNode(RectangleF bounds)
19        {
20            m_bounds = bounds;
21        }
22
23        /// <summary>
24        /// The area of this node
25        /// </summary>
26        RectangleF m_bounds;
27
28        /// <summary>
29        /// The contents of this node.
30        /// Note that the contents have no limit: this is not the standard way to impement a QuadTree
31        /// </summary>
32        List<T> m_contents = new List<T>();
33
34        /// <summary>
35        /// The child nodes of the QuadTree
36        /// </summary>
37        List<QuadTreeNode<T>> m_nodes = new List<QuadTreeNode<T>>(4);
38
39        /// <summary>
40        /// Is the node empty
41        /// </summary>
42        public bool IsEmpty { get { return m_bounds.IsEmpty || m_nodes.Count == 0; } }
43
44        /// <summary>
45        /// Area of the quadtree node
46        /// </summary>
47        public RectangleF Bounds { get { return m_bounds; } }
48
49        /// <summary>
50        /// Total number of nodes in the this node and all SubNodes
51        /// </summary>
52        public int Count
53        {
54            get
55            {
56                int count = 0;
57
58                foreach (QuadTreeNode<T> node in m_nodes)
59                    count += node.Count;
60
61                count += this.Contents.Count;
62
63                return count;
64            }
65        }
66
67        /// <summary>
68        /// Return the contents of this node and all subnodes in the true below this one.
69        /// </summary>
70        public List<T> SubTreeContents
71        {
72            get
73            {
74                List<T> results = new List<T>();
75
76                foreach (QuadTreeNode<T> node in m_nodes)
77                    results.AddRange(node.SubTreeContents);
78
79                results.AddRange(this.Contents);
80                return results;
81            }
82        }
83
84        public List<T> Contents { get { return m_contents; } }
85
86        public bool QueryAny(RectangleF queryArea)
87        {
88
89            // this quad contains items that are not entirely contained by
90            // it's four sub-quads. Iterate through the items in this quad
91            // to see if they intersect.
92            foreach (T item in this.Contents)
93            {
94                if (queryArea.IntersectsWith(item.Rectangle))
95                    return true;
96            }
97
98            foreach (QuadTreeNode<T> node in m_nodes)
99            {
100                if (node.IsEmpty)
101                    continue;
102
103                // Case 1: search area completely contained by sub-quad
104                // if a node completely contains the query area, go down that branch
105                // and skip the remaining nodes (break this loop)
106                if (node.Bounds.Contains(queryArea))
107                {
108                    return node.QueryAny(queryArea);
109                }
110
111                // Case 2: Sub-quad completely contained by search area
112                // if the query area completely contains a sub-quad,
113                // just add all the contents of that quad and it's children
114                // to the result set. You need to continue the loop to test
115                // the other quads
116                if (queryArea.Contains(node.Bounds))
117                {
118                    if (node.SubTreeContents.Count != 0)
119                        return true;
120                    continue;
121                }
122
123                // Case 3: search area intersects with sub-quad
124                // traverse into this quad, continue the loop to search other
125                // quads
126                if (node.Bounds.IntersectsWith(queryArea))
127                {
128                    if (node.QueryAny(queryArea))
129                        return true;
130                }
131            }
132            return false;
133        }
134        /// <summary>
135        /// Query the QuadTree for items that are in the given area
136        /// </summary>
137        /// <param name="queryArea"></pasram>
138        /// <returns></returns>
139        public List<T> Query(RectangleF queryArea)
140        {
141            // create a list of the items that are found
142            List<T> results = new List<T>();
143
144            // this quad contains items that are not entirely contained by
145            // it's four sub-quads. Iterate through the items in this quad
146            // to see if they intersect.
147            foreach (T item in this.Contents)
148            {
149                if (queryArea.IntersectsWith(item.Rectangle))
150                    results.Add(item);
151            }
152
153            foreach (QuadTreeNode<T> node in m_nodes)
154            {
155                if (node.IsEmpty)
156                    continue;
157
158                // Case 1: search area completely contained by sub-quad
159                // if a node completely contains the query area, go down that branch
160                // and skip the remaining nodes (break this loop)
161                if (node.Bounds.Contains(queryArea))
162                {
163                    results.AddRange(node.Query(queryArea));
164                    break;
165                }
166
167                // Case 2: Sub-quad completely contained by search area
168                // if the query area completely contains a sub-quad,
169                // just add all the contents of that quad and it's children
170                // to the result set. You need to continue the loop to test
171                // the other quads
172                if (queryArea.Contains(node.Bounds))
173                {
174                    results.AddRange(node.SubTreeContents);
175                    continue;
176                }
177
178                // Case 3: search area intersects with sub-quad
179                // traverse into this quad, continue the loop to search other
180                // quads
181                if (node.Bounds.IntersectsWith(queryArea))
182                {
183                    results.AddRange(node.Query(queryArea));
184                }
185            }
186
187
188            return results;
189        }
190
191        /// <summary>
192        /// Insert an item to this node
193        /// </summary>
194        /// <param name="item"></param>
195        public void Insert(T item)
196        {
197            // if the item is not contained in this quad, there's a problem
198            if (!m_bounds.Contains(item.Rectangle))
199            {
200                Trace.TraceWarning("feature is out of the bounds of this quadtree node");
201                return;
202            }
203
204            // if the subnodes are null create them. may not be sucessfull: see below
205            // we may be at the smallest allowed size in which case the subnodes will not be created
206            if (m_nodes.Count == 0)
207                CreateSubNodes();
208
209            // for each subnode:
210            // if the node contains the item, add the item to that node and return
211            // this recurses into the node that is just large enough to fit this item
212            foreach (QuadTreeNode<T> node in m_nodes)
213            {
214                if (node.Bounds.Contains(item.Rectangle))
215                {
216                    node.Insert(item);
217                    return;
218                }
219            }
220
221            // if we make it to here, either
222            // 1) none of the subnodes completely contained the item. or
223            // 2) we're at the smallest subnode size allowed
224            // add the item to this node's contents.
225            this.Contents.Add(item);
226        }
227
228        public void ForEach(QuadTree<T>.QTAction action)
229        {
230            action(this);
231
232            // draw the child quads
233            foreach (QuadTreeNode<T> node in this.m_nodes)
234                node.ForEach(action);
235        }
236
237        /// <summary>
238        /// Internal method to create the subnodes (partitions space)
239        /// </summary>
240        private void CreateSubNodes()
241        {
242            // the smallest subnode has an area
243            if ((m_bounds.Height * m_bounds.Width) <= 10)
244                return;
245
246            float halfWidth = (m_bounds.Width / 2f);
247            float halfHeight = (m_bounds.Height / 2f);
248
249            m_nodes.Add(new QuadTreeNode<T>(new RectangleF(m_bounds.Location, new SizeF(halfWidth, halfHeight))));
250            m_nodes.Add(new QuadTreeNode<T>(new RectangleF(new PointF(m_bounds.Left, m_bounds.Top + halfHeight), new SizeF(halfWidth, halfHeight))));
251            m_nodes.Add(new QuadTreeNode<T>(new RectangleF(new PointF(m_bounds.Left + halfWidth, m_bounds.Top), new SizeF(halfWidth, halfHeight))));
252            m_nodes.Add(new QuadTreeNode<T>(new RectangleF(new PointF(m_bounds.Left + halfWidth, m_bounds.Top + halfHeight), new SizeF(halfWidth, halfHeight))));
253        }
254
255    }
256}
Note: See TracBrowser for help on using the repository browser.