四叉の木を勉強します.
80670 ワード
プログラムコード:
http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C
四叉木:
四叉ツリーノード:
データ項目は、Tとして伝えられます.
包囲箱インターフェース:
レンダリングツリー:
メインフォームの呼び出し:
実行結果:
http://www.codeproject.com/Articles/30535/A-Simple-QuadTree-Implementation-in-C
四叉木:
1 using System; 2 using System.Drawing; 3 using System.Collections.Generic; 4 using System.Diagnostics; 5
6 namespace 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 /// 22 /// </summary>
23 QuadTreeNode<T> m_root; 24
25 /// <summary>
26 /// The bounds of this QuadTree 27 /// ， 28 /// </summary>
29 RectangleF m_rectangle; 30
31 /// <summary>
32 /// An delegate that performs an action on a QuadTreeNode 33 /// </summary>
34 /// <param name="obj"></param>
35 public delegate void QTAction(QuadTreeNode<T> obj); 36
37 /// <summary>
38 ///
39 /// </summary>
40 /// <param name="rectangle"></param>
41 public QuadTree(RectangleF rectangle) 42 { 43 m_rectangle = rectangle; 44 m_root = new QuadTreeNode<T>(m_rectangle);//
45 } 46
47 /// <summary>
48 /// Get the count of items in the QuadTree 49 /// 50 /// </summary>
51 public int Count { get { return m_root.Count; } } 52
53 /// <summary>
54 /// Insert the feature into the QuadTree 55 /// 56 /// </summary>
57 /// <param name="item"></param>
58 public void Insert(T item) 59 { 60 m_root.Insert(item);// ，
61 } 62
63 /// <summary>
64 /// Query the QuadTree, returning the items that are in the given area 65 /// ， 66 /// </summary>
67 /// <param name="area"></param>
68 /// <returns></returns>
69 public List<T> Query(RectangleF area) 70 { 71 return m_root.Query(area); 72 } 73
74 /// <summary>
75 /// Do the specified action for each item in the quadtree 76 /// 77 /// </summary>
78 /// <param name="action"></param>
79 public void ForEach(QTAction action) 80 { 81 m_root.ForEach(action); 82 } 83
84 } 85
86 }四叉ツリーノード:
1 using System; 2 using System.Collections.Generic; 3 using System.Drawing; 4 using System.Diagnostics; 5
6 namespace QuadTreeLib 7 { 8 /// <summary>
9 /// The QuadTreeNode 10 /// 11 /// </summary>
12 /// <typeparam name="T"></typeparam>
13 public class QuadTreeNode<T> where T : IHasRect 14 { 15 /// <summary>
16 /// Construct a quadtree node with the given bounds 17 /// 18 /// </summary>
19 /// <param name="area"></param>
20 public QuadTreeNode(RectangleF bounds) 21 { 22 m_bounds = bounds; 23 } 24
25 /// <summary>
26 /// The area of this node 27 /// </summary>
28 RectangleF m_bounds; 29
30 /// <summary>
31 /// The contents of this node. 32 /// Note that the contents have no limit: this is not the standard way to impement a QuadTree 33 /// </summary>
34 List<T> m_contents = new List<T>(); 35
36 /// <summary>
37 /// The child nodes of the QuadTree 38 /// 39 /// </summary>
40 List<QuadTreeNode<T>> m_nodes = new List<QuadTreeNode<T>>(4); 41
42 /// <summary>
43 /// Is the node empty 44 /// </summary>
45 public bool IsEmpty { get { return m_bounds.IsEmpty || m_nodes.Count == 0; } } 46
47 /// <summary>
48 /// Area of the quadtree node 49 /// 50 /// </summary>
51 public RectangleF Bounds { get { return m_bounds; } } 52
53 /// <summary>
54 /// Total number of nodes in the this node and all SubNodes 55 ///
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 /// <summary>
92 /// Query the QuadTree for items that are in the given area 93 /// 94 /// </summary>
95 /// <param name="queryArea"></pasram>
96 /// <returns></returns>
97 public List<T> Query(RectangleF queryArea) 98 { 99 // create a list of the items that are found
100 List<T> results = new List<T>(); 101
102 // this quad contains items that are not entirely contained by 103 // it's four sub-quads. Iterate through the items in this quad 104 // to see if they intersect.
105 foreach (T item in this.Contents) 106 { 107 if (queryArea.IntersectsWith(item.Rectangle)) 108 results.Add(item); 109 } 110
111 foreach (QuadTreeNode<T> node in m_nodes) 112 { 113 if (node.IsEmpty) 114 continue; 115
116 // Case 1: search area completely contained by sub-quad 117 // if a node completely contains the query area, go down that branch 118 // and skip the remaining nodes (break this loop)
119 if (node.Bounds.Contains(queryArea)) 120 { 121 results.AddRange(node.Query(queryArea)); 122 break; 123 } 124
125 // Case 2: Sub-quad completely contained by search area 126 // if the query area completely contains a sub-quad, 127 // just add all the contents of that quad and it's children 128 // to the result set. You need to continue the loop to test 129 // the other quads
130 if (queryArea.Contains(node.Bounds)) 131 { 132 results.AddRange(node.SubTreeContents); 133 continue; 134 } 135
136 // Case 3: search area intersects with sub-quad 137 // traverse into this quad, continue the loop to search other 138 // quads
139 if (node.Bounds.IntersectsWith(queryArea)) 140 { 141 results.AddRange(node.Query(queryArea)); 142 } 143 } 144
145
146 return results; 147 } 148
149 /// <summary>
150 /// Insert an item to this node 151 /// 152 /// </summary>
153 /// <param name="item"></param>
154 public void Insert(T item) 155 { 156 // if the item is not contained in this quad, there's a problem 157 // ，
158 if (!m_bounds.Contains(item.Rectangle)) 159 { 160 Trace.TraceWarning("feature is out of the bounds of this quadtree node"); 161 return; 162 } 163
164 // if the subnodes are null create them. may not be sucessfull: see below 165 // we may be at the smallest allowed size in which case the subnodes will not be created
166 if (m_nodes.Count == 0) 167 CreateSubNodes();// ， 168
169 // for each subnode: 170 // if the node contains the item, add the item to that node and return 171 // this recurses into the node that is just large enough to fit this item
172 foreach (QuadTreeNode<T> node in m_nodes) 173 { 174 if (node.Bounds.Contains(item.Rectangle))// ，
175 { 176 node.Insert(item); 177 return; 178 } 179 } 180
181 // if we make it to here, either 182 // 1) none of the subnodes completely contained the item. or 183 // 2) we're at the smallest subnode size allowed 184 // add the item to this node's contents. 185 // ， ， ，
186 this.Contents.Add(item); 187 } 188 //
189 public void ForEach(QuadTree<T>.QTAction action) 190 { 191 action(this); 192
193 // draw the child quads
194 foreach (QuadTreeNode<T> node in this.m_nodes) 195 node.ForEach(action); 196 } 197
198 /// <summary>
199 /// Internal method to create the subnodes (partitions space) 200 /// ， 201 /// </summary>
202 private void CreateSubNodes() 203 { 204 // the smallest subnode has an area
205 if ((m_bounds.Height * m_bounds.Width) <= 10) 206 return; 207
208 float halfWidth = (m_bounds.Width / 2f); 209 float halfHeight = (m_bounds.Height / 2f); 210
211 m_nodes.Add(new QuadTreeNode<T>(new RectangleF(m_bounds.Location, new SizeF(halfWidth, halfHeight)))); 212 m_nodes.Add(new QuadTreeNode<T>(new RectangleF(new PointF(m_bounds.Left, m_bounds.Top + halfHeight), new SizeF(halfWidth, halfHeight)))); 213 m_nodes.Add(new QuadTreeNode<T>(new RectangleF(new PointF(m_bounds.Left + halfWidth, m_bounds.Top), new SizeF(halfWidth, halfHeight)))); 214 m_nodes.Add(new QuadTreeNode<T>(new RectangleF(new PointF(m_bounds.Left + halfWidth, m_bounds.Top + halfHeight), new SizeF(halfWidth, halfHeight)))); 215 } 216
217 } 218 }データ項目は、Tとして伝えられます.
1 namespace QuadTreeDemoApp 2 { 3 /// <summary>
4 /// An item with a position, a size and a random colour to test 5 /// the QuadTree structure. 6 /// 7 /// </summary>
8 class Item: IHasRect 9 { 10 /// <summary>
11 /// Create an item at the given location with the given size. 12 /// ， 13 /// </summary>
14 /// <param name="p"></param>
15 /// <param name="size"></param>
16 public Item(Point p, int size) 17 { 18 m_size = size; 19 m_rectangle = new RectangleF(p.X, p.Y, m_size, m_size); 20 m_color = Utility.RandomColor; 21 } 22
23 /// <summary>
24 /// Bounds of this item 25 /// 26 /// </summary>
27 RectangleF m_rectangle; 28
29 /// <summary>
30 /// 31 /// </summary>
32 int m_size = 2; 33
34 /// <summary>
35 /// 36 /// </summary>
37 Color m_color; 38
39 /// <summary>
40 /// Colour to draw the item for the QuadTree demo 41 /// </summary>
42 public Color Color { get { return m_color; } } 43
44 #region IHasRect Members
45
46 /// <summary>
47 /// The rectangular bounds of this item 48 /// 49 /// </summary>
50 public RectangleF Rectangle { get { return m_rectangle; } } 51
52 #endregion
53 } 54 }包囲箱インターフェース:
1 namespace QuadTreeLib 2 { 3 /// <summary>
4 /// An interface that defines and object with a rectangle 5 /// 6 /// </summary>
7 public interface IHasRect 8 { 9 RectangleF Rectangle { get; } 10 } 11 }レンダリングツリー:
1 using System; 2 using System.Collections.Generic; 3 using System.Drawing; 4
5 using QuadTreeLib; 6
7 namespace QuadTreeDemoApp 8 { 9 /// <summary>
10 /// Class draws a QuadTree 11 /// 12 /// </summary>
13 class QuadTreeRenderer 14 { 15 /// <summary>
16 /// Create the renderer, give the QuadTree to render. 17 /// 18 /// </summary>
19 /// <param name="quadTree"></param>
20 public QuadTreeRenderer(QuadTree<Item> quadTree) 21 { 22 m_quadTree = quadTree; 23 } 24
25 QuadTree<Item> m_quadTree; 26
27 /// <summary>
28 /// Hashtable contains a colour for every node in the quad tree so that they are 29 /// rendered with a consistant colour. 30 /// </summary>
31 Dictionary<QuadTreeNode<Item>, Color> m_dictionary = new Dictionary<QuadTreeNode<Item>, Color>(); 32
33 /// <summary>
34 /// Get the colour for a QuadTreeNode from the hash table or else create a new colour 35 /// </summary>
36 /// <param name="node"></param>
37 /// <returns></returns>
38 Color GetColor(QuadTreeNode<Item> node) 39 { 40 if (m_dictionary.ContainsKey(node)) 41 return m_dictionary[node]; 42
43 Color color = Utility.RandomColor; 44 m_dictionary.Add(node, color); 45 return color; 46 } 47
48 /// <summary>
49 /// Render the QuadTree into the given Graphics context 50 /// 51 /// </summary>
52 /// <param name="graphics"></param>
53 internal void Render(Graphics graphics) 54 { 55 //
56 m_quadTree.ForEach(delegate(QuadTreeNode<Item> node) 57 { 58
59 // draw the contents of this quad
60 if (node.Contents != null) 61 { 62 foreach (Item item in node.Contents) 63 { 64 using (Brush b = new SolidBrush(item.Color)) 65 graphics.FillEllipse(b, Rectangle.Round(item.Rectangle)); 66 } 67 } 68
69 // draw this quad 70
71 // Draw the border 72 //
73 Color color = GetColor(node); 74 graphics.DrawRectangle(Pens.Black, Rectangle.Round(node.Bounds)); 75
76 // draw the inside of the border in a distinct colour
77 using (Pen p = new Pen(color)) 78 { 79 Rectangle inside = Rectangle.Round(node.Bounds); 80 inside.Inflate(-1, -1); 81 graphics.DrawRectangle(p, inside); 82 } 83
84 }); 85
86 } 87 } 88 }メインフォームの呼び出し:
1 public partial class MainForm : Form 2 { 3 QuadTree<Item> m_quadTree; 4
5 QuadTreeRenderer m_renderer; 6
7 public MainForm() 8 { 9 InitializeComponent(); 10 } 11
12 private void MainForm_Load(object sender, EventArgs e) 13 { 14 Init(); 15 } 16
17 /// <summary>
18 /// Resize the window re-initializes the QuadTree to the new size 19 /// </summary>
20 /// <param name="sender"></param>
21 /// <param name="e"></param>
22 private void MainForm_Resize(object sender, EventArgs e) 23 { 24 Init(); 25 } 26
27 /// <summary>
28 /// Draw the QuadTree and the selection rectangle 29 /// Also highlight the selecte items. 30 /// </summary>
31 /// <param name="sender"></param>
32 /// <param name="e"></param>
33 private void MainForm_Paint(object sender, PaintEventArgs e) 34 { 35 // draw the QuadTree
36 m_renderer.Render(e.Graphics); 37
38 // draw the selection rectangle
39 if (!m_selectionRect.IsEmpty) 40 { 41 // draw the selection rect in semi-transparent yellow
42 using (Brush b = new SolidBrush(Color.FromArgb(128, Color.Yellow))) 43 e.Graphics.FillRectangle(b, Rectangle.Round(m_selectionRect)); 44 } 45
46 // draw the selected items with a red ring around them
47 if (m_selectedItems != null) 48 { 49 foreach (Item obj in m_selectedItems) 50 { 51 Rectangle selectedRect = Rectangle.Round(obj.Rectangle); 52 selectedRect.Inflate(1, 1); 53 using (Pen p = new Pen(Color.Red, 2)) 54 e.Graphics.DrawEllipse(p, selectedRect); 55 } 56 } 57 } 58
59 /// <summary>
60 /// Initialize the QuadTree to the size of the window. 61 /// Initialize the QuadTreeRenderer 62 /// </summary>
63 private void Init() 64 { 65 m_quadTree = new QuadTree<Item>(this.ClientRectangle);//
66 m_renderer = new QuadTreeRenderer(m_quadTree); 67 } 68
69 #region mouse interaction code
70
71 bool m_dragging = false; 72 RectangleF m_selectionRect; 73 Point m_startPoint; 74 List<Item> m_selectedItems; 75
76 /// <summary>
77 /// MouseUp: 78 /// - if you're using the left mouse button insert a new item into 79 /// the QuadTree at the click point 80 /// - if you're dragging with the right mouse button, query the 81 /// QuadTree with the selection rectangle defined by the current 82 /// point and the point when the mouseDown event happened. 83 /// </summary>
84 /// <param name="sender"></param>
85 /// <param name="e"></param>
86 private void MainForm_MouseUp(object sender, MouseEventArgs e) 87 { 88 if (m_dragging && e.Button== MouseButtons.Right) 89 { 90 m_selectedItems = m_quadTree.Query(m_selectionRect); 91 m_dragging = false; 92 } 93 else
94 { 95 Random rand = new Random(DateTime.Now.Millisecond); 96
97 m_quadTree.Insert(new Item(e.Location, rand.Next(25) + 4)); 98 } 99
100 Invalidate(); 101
102 } 103
104 /// <summary>
105 /// If the it's a right click, record the start point and start drag operation 106 /// </summary>
107 /// <param name="sender"></param>
108 /// <param name="e"></param>
109 private void MainForm_MouseDown(object sender, MouseEventArgs e) 110 { 111 if (e.Button == MouseButtons.Right) 112 { 113 m_dragging = true; 114 m_startPoint = e.Location; 115 } 116 } 117
118 /// <summary>
119 /// MouseMove: if we're dragging the update the area of the selection 120 /// rectangle using the start point and the current point. 121 /// Invalidate causes the form to redraw. 122 /// </summary>
123 /// <param name="sender"></param>
124 /// <param name="e"></param>
125 private void MainForm_MouseMove(object sender, MouseEventArgs e) 126 { 127 if (m_dragging) 128 { 129 m_selectionRect = RectangleF.FromLTRB( 130 Math.Min(e.Location.X, m_startPoint.X), 131 Math.Min(e.Location.Y, m_startPoint.Y), 132 Math.Max(e.Location.X, m_startPoint.X), 133 Math.Max(e.Location.Y, m_startPoint.Y)); 134
135 Invalidate(); 136 } 137 } 138 #endregion
139
140 }実行結果: