namespace GMap.NET.WindowsPresentation{
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Windows;
#if DEBUG_DUMP
using System.Windows.Controls;
using System.Windows.Shapes;
using System.Windows.Media;
using System.Xml;
#endif
/// <summary>
/// This class efficiently stores and retrieves arbitrarily sized and positioned
/// objects in a quad-tree data structure. This can be used to do efficient hit
/// detection or visiblility checks on objects in a virtualized canvas.
/// The object does not need to implement any special interface because the Rect Bounds
/// of those objects is handled as a separate argument to Insert.
/// </summary>
public class QuadTree<T> where T : class
{
Rect _bounds; // overall bounds we are indexing.
Quadrant _root;
IDictionary<T, Quadrant> _table;
/// <summary>
/// Each node stored in the tree has a position, width & height.
/// </summary>
internal class QuadNode
{
Rect _bounds;
QuadNode _next; // linked in a circular list.
T _node; // the actual visual object being stored here.
/// <summary>
/// Construct new QuadNode to wrap the given node with given bounds
/// </summary>
/// <param name="node">The node</param>
/// <param name="bounds">The bounds of that node</param>
public QuadNode(T node, Rect bounds)
{
_node = node;
_bounds = bounds;
}
/// <summary>
/// The node
/// </summary>
public T Node
{
get
{
return _node;
}
set
{
_node = value;
}
}
/// <summary>
/// The Rect bounds of the node
/// </summary>
public Rect Bounds
{
get
{
return _bounds;
}
}
/// <summary>
/// QuadNodes form a linked list in the Quadrant.
/// </summary>
public QuadNode Next
{
get
{
return _next;
}
set
{
_next = value;
}
}
}
/// <summary>
/// The canvas is split up into four Quadrants and objects are stored in the quadrant that contains them
/// and each quadrant is split up into four child Quadrants recurrsively. Objects that overlap more than
/// one quadrant are stored in the _nodes list for this Quadrant.
/// </summary>
internal class Quadrant
{
Quadrant _parent;
Rect _bounds; // quadrant bounds.
QuadNode _nodes; // nodes that overlap the sub quadrant boundaries.
// The quadrant is subdivided when nodes are inserted that are
// completely contained within those subdivisions.
Quadrant _topLeft;
Quadrant _topRight;
Quadrant _bottomLeft;
Quadrant _bottomRight;
#if DEBUG_DUMP
public void ShowQuadTree(Canvas c)
{
Rectangle r = new Rectangle();
r.Width = _bounds.Width;
r.Height = _bounds.Height;
Canvas.SetLeft(r, _bounds.Left);
Canvas.SetTop(r, _bounds.Top);
r.Stroke = Brushes.DarkRed;
r.StrokeThickness = 1;
r.StrokeDashArray = new DoubleCollection(new double[] { 2.0, 3.0 });
c.Children.Add(r);
if (_topLeft != null) _topLeft.ShowQuadTree(c);
if (_topRight != null) _topRight.ShowQuadTree(c);
if (_bottomLeft != null) _bottomLeft.ShowQuadTree(c);
if (_bottomRight != null) _bottomRight.ShowQuadTree(c);
}
public void Dump(LogWriter w)
{
w.WriteAttribute("Bounds", _bounds.ToString());
if (_nodes != null)
{
QuadNode n = _nodes;
do
{
n = n.Next; // first node.
w.Open("node");
w.WriteAttribute("Bounds", n.Bounds.ToString());
w.Close();
} while (n != _nodes);
}
DumpQuadrant("TopLeft", _topLeft, w);
DumpQuadrant("TopRight", _topRight, w);
DumpQuadrant("BottomLeft", _bottomLeft, w);
DumpQuadrant("BottomRight", _bottomRight, w);
}
public void DumpQuadrant(string label, Quadrant q, LogWriter w)
{
if (q != null)
{
w.Open("Quadrant");
w.WriteAttribute("Name", label);
q.Dump(w);
w.Close();
}
}
#endif
/// <summary>
/// Construct new Quadrant with a given bounds all nodes stored inside this quadrant
/// will fit inside this bounds.
/// </summary>
/// <param name="parent">The parent quadrant (if any)</param>
/// <param name="bounds">The bounds of this quadrant</param>
public Quadrant(Quadrant parent, Rect bounds)
{
_parent = parent;
Debug.Assert(bounds.Width != 0 && bounds.Height != 0);
if(bounds.Width == 0 || bounds.Height == 0)
{
// todo: localize
throw new ArgumentException("Bounds of quadrant cannot be zero width or height");
}
_bounds = bounds;
}
/// <summary>
/// The parent Quadrant or null if this is the root
/// </summary>
internal Quadrant Parent
{
get
{
return _parent;
}
}
/// <summary>
/// The bounds of this quadrant
/// </summary>
internal Rect Bounds
{
get
{
return _bounds;
}
}
/// <summary>
/// Insert the given node
/// </summary>
/// <param name="node">The node </param>
/// <param name="bounds">The bounds of that node</param>
/// <returns></returns>
internal Quadrant Insert(T node, Rect bounds)
{
Debug.Assert(bounds.Width != 0 && bounds.Height != 0);
if(bounds.Width == 0 || bounds.Height == 0)
{
// todo: localize
throw new ArgumentException("Bounds of quadrant cannot be zero width or height");
}
double w = _bounds.Width / 2;
if(w == 0)
{
w = 1;
}
double h = _bounds.Height / 2;
if(h == 0)
{
h = 1;
}
// assumption that the Rect struct is almost as fast as doing the operations
// manually since Rect is a value type.
Rect topLeft = new Rect(_bounds.Left, _bounds.Top, w, h);
Rect topRight = new Rect(_bounds.Left + w, _bounds.Top, w, h);
Rect bottomLeft = new Rect(_bounds.Left, _bounds.Top + h, w, h);
Rect bottomRight = new Rect(_bounds.Left + w, _bounds.Top + h, w, h);
Quadrant child = null;
// See if any child quadrants completely contain this node.
if(topLeft.Contains(bounds))
{
if(_topLeft == null)
{
_topLeft = new Quadrant(this, topLeft);
}
child = _topLeft;
}
else if(topRight.Contains(bounds))
{
if(_topRight == null)
{
_topRight = new Quadrant(this, topRight);
}
child = _topRight;
}
else if(bottomLeft.Contains(bounds))
{
if(_bottomLeft == null)
{
_bottomLeft = new Quadrant(this, bottomLeft);
}
child = _bottomLeft;
}
else if(bottomRight.Contains(bounds))
{
if(_bottomRight == null)
{
_bottomRight = new Quadrant(this, bottomRight);
}
child = _bottomRight;
}
if(child != null)
{
return child.Insert(node, bounds);
}
else
{
QuadNode n = new QuadNode(node, bounds);
if(_nodes == null)
{
n.Next = n;
}
else
{
// link up in circular link list.
QuadNode x = _nodes;
n.Next = x.Next;
x.Next = n;
}
_nodes = n;
return this;
}
}
/// <summary>
/// Returns all nodes in this quadrant that intersect the given bounds.
/// The nodes are returned in pretty much random order as far as the caller is concerned.
/// </summary>
/// <param name="nodes">List of nodes found in the given bounds</param>
/// <param name="bounds">The bounds that contains the nodes you want returned</param>
internal void GetIntersectingNodes(List<QuadNode> nodes, Rect bounds)
{
if(bounds.IsEmpty)
return;
double w = _bounds.Width / 2;
double h = _bounds.Height / 2;
// assumption that the Rect struct is almost as fast as doing the operations
// manually since Rect is a value type.
Rect topLeft = new Rect(_bounds.Left, _bounds.Top, w, h);
Rect topRight = new Rect(_bounds.Left + w, _bounds.Top, w, h);
Rect bottomLeft = new Rect(_bounds.Left, _bounds.Top + h, w, h);
Rect bottomRight = new Rect(_bounds.Left + w, _bounds.Top + h, w, h);
// See if any child quadrants completely contain this node.
if(topLeft.IntersectsWith(bounds) && _topLeft != null)
{
_topLeft.GetIntersectingNodes(nodes, bounds);
}
if(topRight.IntersectsWith(bounds) && _topRight != null)
{
_topRight.GetIntersectingNodes(nodes, bounds);
}
if(bottomLeft.IntersectsWith(bounds) && _bottomLeft != null)
{
_bottomLeft.GetIntersectingNodes(nodes, bounds);
}
if(bottomRight.IntersectsWith(bounds) && _bottomRight != null)
{
_bottomRight.GetIntersectingNodes(nodes, bounds);
}
GetIntersectingNodes(_nodes, nodes, bounds);
}
/// <summary>
/// Walk the given linked list of QuadNodes and check them against the given bounds.
/// Add all nodes that intersect the bounds in to the list.
/// </summary>
/// <param name="last">The last QuadNode in a circularly linked list</param>
/// <param name="nodes">The resulting nodes are added to this list</param>
/// <param name="bounds">The bounds to test against each node</param>
static void GetIntersectingNodes(QuadNode last, List<QuadNode> nodes, Rect bounds)
{
if(last != null)
{
QuadNode n = last;
do
{
n = n.Next; // first node.
if(n.Bounds.IntersectsWith(bounds))
{
nodes.Add(n);
}
} while(n != last);
}
}
/// <summary>
/// Return true if there are any nodes in this Quadrant that intersect the given bounds.
/// </summary>
/// <param name="bounds">The bounds to test</param>
/// <returns>boolean</returns>
internal bool HasIntersectingNodes(Rect bounds)
{
if(bounds.IsEmpty)
return false;
double w = _bounds.Width / 2;
double h = _bounds.Height / 2;
// assumption that the Rect struct is almost as fast as doing the operations
// manually since Rect is a value type.
Rect topLeft = new Rect(_bounds.Left, _bounds.Top, w, h);
Rect topRight = new Rect(_bounds.Left + w, _bounds.Top, w, h);
Rect bottomLeft = new Rect(_bounds.Left, _bounds.Top + h, w, h);
Rect bottomRight = new Rect(_bounds.Left + w, _bounds.Top + h, w, h);
bool found = false;
// See if any child quadrants completely contain this node.
if(topLeft.IntersectsWith(bounds) && _topLeft != null)
{
found = _topLeft.HasIntersectingNodes(bounds);
}
if(!found && topRight.IntersectsWith(bounds) && _topRight != null)
{
found = _topRight.HasIntersectingNodes(bounds);
}
if(!found && bottomLeft.IntersectsWith(bounds) && _bottomLeft != null)
{
found = _bottomLeft.HasIntersectingNodes(bounds);
}
if(!found && bottomRight.IntersectsWith(bounds) && _bottomRight != null)
{
found = _bottomRight.HasIntersectingNodes(bounds);
}
if(!found)
{
found = HasIntersectingNodes(_nodes, bounds);
}
return found;
}
/// <summary>
/// Walk the given linked list and test each node against the given bounds/
/// </summary>
/// <param name="last">The last node in the circularly linked list.</param>
/// <param name="bounds">Bounds to test</param>
/// <returns>Return true if a node in the list intersects the bounds</returns>
static bool HasIntersectingNodes(QuadNode last, Rect bounds)
{
if(last != null)
{
QuadNode n = last;
do
{
n = n.Next; // first node.
if(n.Bounds.IntersectsWith(bounds))
{
return true;
}
} while(n != last);
}
return false;
}
/// <summary>
/// Remove the given node from this Quadrant.
/// </summary>
/// <param name="node">The node to remove</param>
/// <returns>Returns true if the node was found and removed.</returns>
internal bool RemoveNode(T node)
{
bool rc = false;
if(_nodes != null)
{
QuadNode p = _nodes;
while(p.Next.Node != node && p.Next != _nodes)
{
p = p.Next;
}
if(p.Next.Node == node)
{
rc = true;
QuadNode n = p.Next;
if(p == n)
{
// list goes to empty
_nodes = null;
}
else
{
if(_nodes == n)
_nodes = p;
p.Next = n.Next;
}
}
}
return rc;
}
}
/// <summary>
/// This determines the overall quad-tree indexing strategy, changing this bounds
/// is expensive since it has to re-divide the entire thing - like a re-hash operation.
/// </summary>
public Rect Bounds
{
get
{
return _bounds;
}
set
{
_bounds = value;
ReIndex();
}
}
/// <summary>
/// Insert a node with given bounds into this QuadTree.
/// </summary>
/// <param name="node">The node to insert</param>
/// <param name="bounds">The bounds of this node</param>
public void Insert(T node, Rect bounds)
{
if(_bounds.Width == 0 || _bounds.Height == 0)
{
// todo: localize.
throw new InvalidOperationException("You must set a non-zero bounds on the QuadTree first");
}
if(bounds.Width == 0 || bounds.Height == 0)
{
// todo: localize.
throw new InvalidOperationException("Inserted node must have a non-zero width and height");
}
if(_root == null)
{
_root = new Quadrant(null, _bounds);
}
Quadrant parent = _root.Insert(node, bounds);
if(_table == null)
{
_table = new Dictionary<T, Quadrant>();
}
_table[node] = parent;
}
/// <summary>
/// Get a list of the nodes that intersect the given bounds.
/// </summary>
/// <param name="bounds">The bounds to test</param>
/// <returns>List of zero or mode nodes found inside the given bounds</returns>
public IEnumerable<T> GetNodesInside(Rect bounds)
{
foreach(QuadNode n in GetNodes(bounds))
{
yield return n.Node;
}
}
/// <summary>
/// Get a list of the nodes that intersect the given bounds.
/// </summary>
/// <param name="bounds">The bounds to test</param>
/// <returns>List of zero or mode nodes found inside the given bounds</returns>
public bool HasNodesInside(Rect bounds)
{
if(_root != null)
{
_root.HasIntersectingNodes(bounds);
}
return false;
}
/// <summary>
/// Get list of nodes that intersect the given bounds.
/// </summary>
/// <param name="bounds">The bounds to test</param>
/// <returns>The list of nodes intersecting the given bounds</returns>
IEnumerable<QuadNode> GetNodes(Rect bounds)
{
List<QuadNode> result = new List<QuadNode>();
if(_root != null)
{
_root.GetIntersectingNodes(result, bounds);
}
return result;
}
/// <summary>
/// Remove the given node from this QuadTree.
/// </summary>
/// <param name="node">The node to remove</param>
/// <returns>True if the node was found and removed.</returns>
public bool Remove(T node)
{
if(_table != null)
{
Quadrant parent = null;
if(_table.TryGetValue(node, out parent))
{
parent.RemoveNode(node);
_table.Remove(node);
return true;
}
}
return false;
}
/// <summary>
/// Rebuild all the Quadrants according to the current QuadTree Bounds.
/// </summary>
void ReIndex()
{
_root = null;
foreach(QuadNode n in GetNodes(_bounds))
{
// todo: it would be more efficient if we added a code path that allowed
// reuse of the QuadNode wrappers.
Insert(n.Node, n.Bounds);
}
}
#if DEBUG_DUMP
public void ShowQuadTree(Canvas container)
{
if (_root != null)
{
_root.ShowQuadTree(container);
}
}
public void Dump(LogWriter w)
{
if (_root != null)
{
_root.Dump(w);
}
}
#endif
}
#if DEBUG_DUMP
public class LogWriter : IDisposable
{
XmlWriter _xw;
int _indent;
int _maxdepth;
public LogWriter(TextWriter w)
{
XmlWriterSettings s = new XmlWriterSettings();
s.Indent = true;
_xw = XmlWriter.Create(w, s);
}
public int MaxDepth
{
get
{
return _maxdepth;
}
}
public void Open(string label)
{
_xw.WriteStartElement(label);
_indent++;
if (_indent > _maxdepth) _maxdepth = _indent;
}
public void Close()
{
_indent--;
_xw.WriteEndElement();
}
public void WriteAttribute(string name, string value)
{
_xw.WriteAttributeString(name, value);
}
#region IDisposable Members
public void Dispose()
{
Dispose(true);
GC.SuppressFinalize(this);
}
protected virtual void Dispose(bool disposing)
{
if (disposing && _xw != null)
{
using (_xw)
{
_xw.Flush();
}
_xw = null;
}
}
#endregion
}
#endif
}
|