程序代码：
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 }
运行结果：
