程序代码：
四叉树：
1 using System; 2 using System.Drawing; 3 using System.Collections.Generic; 4 using System.Diagnostics; 5 6 namespace QuadTreeLib 7 { 8 /// 9 /// A Quadtree is a structure designed to partition space so10 /// that it's faster to find out what is inside or outside a given 11 /// area. See http://en.wikipedia.org/wiki/Quadtree12 /// 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 /// 17 public class QuadTree where T : IHasRect18 {19 /// 20 /// The root QuadTreeNode21 /// 根节点22 /// 23 QuadTreeNode m_root;24 25 /// 26 /// The bounds of this QuadTree27 /// 四叉树的包围盒，根节点的范围28 /// 29 RectangleF m_rectangle;30 31 /// 32 /// An delegate that performs an action on a QuadTreeNode33 /// 34 /// 35 public delegate void QTAction(QuadTreeNode obj);36 37 /// 38 /// 39 /// 40 /// 41 public QuadTree(RectangleF rectangle)42 {43 m_rectangle = rectangle;44 m_root = new QuadTreeNode (m_rectangle);//初始化根节点45 }46 47 /// 48 /// Get the count of items in the QuadTree49 /// 四叉树节点的数目50 /// 51 public int Count { get { return m_root.Count; } }52 53 /// 54 /// Insert the feature into the QuadTree55 /// 插入数据项56 /// 57 /// 58 public void Insert(T item)59 {60 m_root.Insert(item);//往四叉树插入数据项，其实是通过根节点插入数据项61 }62 63 /// 64 /// Query the QuadTree, returning the items that are in the given area65 /// 查询四叉树，返回给定区域的数据项66 /// 67 /// 68 /// Query(RectangleF area)70 {71 return m_root.Query(area);72 }73 74 /// 75 /// Do the specified action for each item in the quadtree76 /// 执行四叉树中特定的行为77 /// 78 /// 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 /// 9 /// The QuadTreeNode 10 /// 四叉树节点 11 /// 12 /// where T : IHasRect 14 { 15 /// 16 /// Construct a quadtree node with the given bounds 17 /// 根据给定的范围构建四叉树节点 18 /// 19 /// 20 public QuadTreeNode(RectangleF bounds) 21 { 22 m_bounds = bounds; 23 } 24 25 /// 26 /// The area of this node 27 /// 28 RectangleF m_bounds; 29 30 /// 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 /// 34 List m_contents = new List (); 35 36 /// 37 /// The child nodes of the QuadTree 38 /// 四叉树的子节点 39 /// 40 List > m_nodes = new List >(4); 41 42 /// 43 /// Is the node empty 44 /// 45 public bool IsEmpty { get { return m_bounds.IsEmpty || m_nodes.Count == 0; } } 46 47 /// 48 /// Area of the quadtree node 49 /// 四叉树节点的范围 50 /// 51 public RectangleF Bounds { get { return m_bounds; } } 52 53 /// 54 /// Total number of nodes in the this node and all SubNodes 55 /// 56 /// 57 public int Count 58 { 59 get 60 { 61 int count = 0; 62 63 foreach (QuadTreeNode node in m_nodes) 64 count += node.Count; 65 66 count += this.Contents.Count; 67 68 return count; 69 } 70 } 71 72 /// 73 /// Return the contents of this node and all subnodes in the true below this one. 74 /// 75 public List SubTreeContents 76 { 77 get 78 { 79 List results = new List (); 80 81 foreach (QuadTreeNode node in m_nodes) 82 results.AddRange(node.SubTreeContents); 83 84 results.AddRange(this.Contents); 85 return results; 86 } 87 } 88 89 public List Contents { get { return m_contents; } } 90 91 /// 92 /// Query the QuadTree for items that are in the given area 93 /// 查询给定范围的数据项 94 /// 95 /// 96 /// Query(RectangleF queryArea) 98 { 99 // create a list of the items that are found100 List results = new List ();101 102 // this quad contains items that are not entirely contained by103 // 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 node in m_nodes)112 {113 if (node.IsEmpty)114 continue;115 116 // Case 1: search area completely contained by sub-quad117 // if a node completely contains the query area, go down that branch118 // 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 quads130 if (queryArea.Contains(node.Bounds))131 {132 results.AddRange(node.SubTreeContents);133 continue;134 }135 136 // Case 3: search area intersects with sub-quad137 // traverse into this quad, continue the loop to search other138 // quads139 if (node.Bounds.IntersectsWith(queryArea))140 {141 results.AddRange(node.Query(queryArea));142 }143 }144 145 146 return results;147 }148 149 /// 150 /// Insert an item to this node151 /// 将数据项递归插入该四叉树节点152 /// 153 /// 154 public void Insert(T item)155 {156 // if the item is not contained in this quad, there's a problem157 //数据项不在当前四叉树节点范围内，返回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 below165 // we may be at the smallest allowed size in which case the subnodes will not be created166 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 return171 // this recurses into the node that is just large enough to fit this item172 foreach (QuadTreeNode 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, either182 // 1) none of the subnodes completely contained the item. or183 // 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 .QTAction action)190 {191 action(this);192 193 // draw the child quads194 foreach (QuadTreeNode node in this.m_nodes)195 node.ForEach(action);196 }197 198 /// 199 /// Internal method to create the subnodes (partitions space)200 /// 私有方法，创建子节点201 /// 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 (new RectangleF(m_bounds.Location, new SizeF(halfWidth, halfHeight))));212 m_nodes.Add(new QuadTreeNode (new RectangleF(new PointF(m_bounds.Left, m_bounds.Top + halfHeight), new SizeF(halfWidth, halfHeight))));213 m_nodes.Add(new QuadTreeNode (new RectangleF(new PointF(m_bounds.Left + halfWidth, m_bounds.Top), new SizeF(halfWidth, halfHeight))));214 m_nodes.Add(new QuadTreeNode (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 /// 4 /// An item with a position, a size and a random colour to test 5 /// the QuadTree structure. 6 /// 数据项 7 /// 8 class Item: IHasRect 9 {10 /// 11 /// Create an item at the given location with the given size.12 /// 数据项，在给定的位置构建特定大小的数据项13 /// 14 /// 15 /// 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 /// 24 /// Bounds of this item25 /// 数据项的范围26 /// 27 RectangleF m_rectangle;28 29 /// 30 ///默认大小31 /// 32 int m_size = 2;33 34 /// 35 /// 颜色36 /// 37 Color m_color;38 39 /// 40 /// Colour to draw the item for the QuadTree demo41 /// 42 public Color Color { get { return m_color; } }43 44 #region IHasRect Members45 46 /// 47 /// The rectangular bounds of this item48 /// 数据项的范围矩形49 /// 50 public RectangleF Rectangle { get { return m_rectangle; } }51 52 #endregion53 }54 } 包围盒接口：
1 namespace QuadTreeLib 2 { 3 /// 4 /// An interface that defines and object with a rectangle 5 /// 接口定义了对象的包围盒 6 /// 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 /// 10 /// Class draws a QuadTree11 /// 绘制四叉树类12 /// 13 class QuadTreeRenderer 14 {15 /// 16 /// Create the renderer, give the QuadTree to render.17 /// 渲染四叉树18 /// 19 /// 20 public QuadTreeRenderer(QuadTree - quadTree)21 {22 m_quadTree = quadTree;23 }24 25 QuadTree
- m_quadTree;26 27 ///
28 /// Hashtable contains a colour for every node in the quad tree so that they are29 /// rendered with a consistant colour.30 /// 31 Dictionary - , Color> m_dictionary = new Dictionary
- , Color>();32 33 ///
34 /// Get the colour for a QuadTreeNode from the hash table or else create a new colour35 /// 36 /// 37 /// - 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 ///
49 /// Render the QuadTree into the given Graphics context50 /// 在给定的图形设备渲染四叉树51 /// 52 /// 53 internal void Render(Graphics graphics)54 {55 //遍历节点触发委托方法56 m_quadTree.ForEach(delegate(QuadTreeNode - node)57 {58 59 // draw the contents of this quad60 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 quad70 71 // Draw the border72 //绘制包围盒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 colour77 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 - 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 ///
18 /// Resize the window re-initializes the QuadTree to the new size 19 /// 20 /// 21 /// 22 private void MainForm_Resize(object sender, EventArgs e) 23 { 24 Init(); 25 } 26 27 /// 28 /// Draw the QuadTree and the selection rectangle 29 /// Also highlight the selecte items. 30 /// 31 /// 32 /// 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 /// 60 /// Initialize the QuadTree to the size of the window. 61 /// Initialize the QuadTreeRenderer 62 /// 63 private void Init() 64 { 65 m_quadTree = new QuadTree - (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
- m_selectedItems; 75 76 ///
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 /// 84 /// 85 /// 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 /// 105 /// If the it's a right click, record the start point and start drag operation106 /// 107 /// 108 /// 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 /// 119 /// MouseMove: if we're dragging the update the area of the selection120 /// rectangle using the start point and the current point.121 /// Invalidate causes the form to redraw.122 /// 123 /// 124 /// 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 #endregion139 140 } 运行结果：
