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

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