QuadTree.cs source code in C# .NET

Source code for the .NET framework in C#

                        

Code:

/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / cdf / src / NetFx40 / Tools / System.Activities.Presentation / System / Activities / Presentation / View / QuadTree.cs / 1305376 / QuadTree.cs

                            //---------------------------------------------------------------- 
// Copyright (c) Microsoft Corporation.  All rights reserved.
//---------------------------------------------------------------
namespace System.Activities.Presentation.View
{ 
    using System;
    using System.Collections.Generic; 
    using System.Diagnostics; 
    using System.IO;
    using System.Windows; 
    using System.Runtime;
#if DEBUG_DUMP
    using System.Windows.Controls;
    using System.Windows.Shapes; 
    using System.Windows.Media;
    using System.Xml; 
#endif 

 
    /// 
    /// 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. 
    ///  
    class QuadTree where T : class
    { 
        Rect bounds; // overall bounds we are indexing.
        Quadrant root;
        IDictionary table;
 

 
        ///  
        /// 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. 
        /// 
        public Rect Bounds
        {
            get { return this.bounds; } 
            set { this.bounds = value; ReIndex(); }
        } 
 
        /// 
        /// Insert a node with given bounds into this QuadTree. 
        /// 
        /// The node to insert
        /// The bounds of this node
        public void Insert(T node, Rect bounds) 
        {
            if (this.bounds.Width == 0 || this.bounds.Height == 0) 
            { 
                throw FxTrace.Exception.AsError(new ArgumentException(SR.BoundsMustBeNonZero));
            } 
            if (bounds.Width == 0 || bounds.Height == 0)
            {
                throw FxTrace.Exception.AsError(new ArgumentException(SR.BoundsMustBeNonZero));
            } 
            if (this.root == null)
            { 
                this.root = new Quadrant(null, this.bounds); 
            }
 
            Quadrant parent = this.root.Insert(node, bounds);

            if (this.table == null)
            { 
                this.table = new Dictionary();
            } 
            this.table[node] = parent; 

 
        }

        /// 
        /// Get a list of the nodes that intersect the given bounds. 
        /// 
        /// The bounds to test 
        /// List of zero or mode nodes found inside the given bounds 
        public IEnumerable GetNodesInside(Rect bounds)
        { 
            foreach (QuadNode n in GetNodes(bounds))
            {
                yield return n.Node;
            } 
        }
 
        ///  
        /// Get a list of the nodes that intersect the given bounds.
        ///  
        /// The bounds to test
        /// List of zero or mode nodes found inside the given bounds
        public bool HasNodesInside(Rect bounds)
        { 
            if (this.root == null)
            { 
                return false; 
            }
            return this.root.HasIntersectingNodes(bounds); 
        }

        /// 
        /// Get list of nodes that intersect the given bounds. 
        /// 
        /// The bounds to test 
        /// The list of nodes intersecting the given bounds 
        IEnumerable GetNodes(Rect bounds)
        { 
            List result = new List();
            if (this.root != null)
            {
                this.root.GetIntersectingNodes(result, bounds); 
            }
            return result; 
        } 

        ///  
        /// Remove the given node from this QuadTree.
        /// 
        /// The node to remove
        /// True if the node was found and removed. 
        public bool Remove(T node)
        { 
            if (this.table != null) 
            {
                Quadrant parent = null; 
                if (this.table.TryGetValue(node, out parent))
                {
                    parent.RemoveNode(node);
                    this.table.Remove(node); 
                    return true;
                } 
            } 
            return false;
        } 

        /// 
        /// Rebuild all the Quadrants according to the current QuadTree Bounds.
        ///  
        void ReIndex()
        { 
            this.root = null; 
            foreach (QuadNode n in GetNodes(this.bounds))
            { 
                Insert(n.Node, n.Bounds);
            }
        }
 
        /// 
        /// Each node stored in the tree has a position, width & height. 
        ///  
        internal class QuadNode
        { 
            Rect bounds;
            QuadNode next; // linked in a circular list.
            T node; // the actual visual object being stored here.
 
            /// 
            /// Construct new QuadNode to wrap the given node with given bounds 
            ///  
            /// The node
            /// The bounds of that node 
            public QuadNode(T node, Rect bounds)
            {
                this.node = node;
                this.bounds = bounds; 
            }
 
            ///  
            /// The node
            ///  
            public T Node
            {
                get { return this.node; }
                set { this.node = value; } 
            }
 
            ///  
            /// The Rect bounds of the node
            ///  
            public Rect Bounds
            {
                get { return this.bounds; }
            } 

            ///  
            /// QuadNodes form a linked list in the Quadrant. 
            /// 
            public QuadNode Next 
            {
                get { return this.next; }
                set { this.next = value; }
            } 
        }
 
 
        /// 
        /// 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 this.nodes list for this Quadrant.
        /// 
        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 = this.bounds.Width; 
                r.Height = this.bounds.Height;
                Canvas.SetLeft(r, this.bounds.Left); 
                Canvas.SetTop(r, this.bounds.Top); 
                r.Stroke = Brushes.DarkRed;
                r.StrokeThickness = 1; 
                r.StrokeDashArray = new DoubleCollection(new double[] { 2.0, 3.0 });
                c.Children.Add(r);

                if (this.topLeft != null) this.topLeft.ShowQuadTree(c); 
                if (this.topRight != null) this.topRight.ShowQuadTree(c);
                if (this.bottomLeft != null) this.bottomLeft.ShowQuadTree(c); 
                if (this.bottomRight != null) this.bottomRight.ShowQuadTree(c); 
            }
 
            public void Dump(LogWriter w)
            {
                w.WriteAttribute("Bounds", this.bounds.ToString());
                if (this.nodes != null) 
                {
                    QuadNode n = this.nodes; 
                    do 
                    {
                        n = n.Next; // first node. 
                        w.Open("node");
                        w.WriteAttribute("Bounds", n.Bounds.ToString());
                        w.Close();
                    } while (n != this.nodes); 
                }
                DumpQuadrant("TopLeft", this.topLeft, w); 
                DumpQuadrant("TopRight", this.topRight, w); 
                DumpQuadrant("BottomLeft", this.bottomLeft, w);
                DumpQuadrant("BottomRight", this.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 

            ///  
            /// Construct new Quadrant with a given bounds all nodes stored inside this quadrant 
            /// will fit inside this bounds.
            ///  
            /// The parent quadrant (if any)
            /// The bounds of this quadrant
            public Quadrant(Quadrant parent, Rect bounds)
            { 
                this.parent = parent;
                Fx.Assert(bounds.Width != 0 && bounds.Height != 0, "Cannot have empty bound"); 
                if (bounds.Width == 0 || bounds.Height == 0) 
                {
                    throw FxTrace.Exception.AsError(new ArgumentException(SR.BoundsMustBeNonZero)); 
                }
                this.bounds = bounds;
            }
 
            /// 
            /// The parent Quadrant or null if this is the root 
            ///  
            internal Quadrant Parent
            { 
                get { return this.parent; }
            }

            ///  
            /// The bounds of this quadrant
            ///  
            internal Rect Bounds 
            {
                get { return this.bounds; } 
            }

            /// 
            /// Insert the given node 
            /// 
            /// The node  
            /// The bounds of that node 
            /// 
            internal Quadrant Insert(T node, Rect bounds) 
            {

                Fx.Assert(bounds.Width != 0 && bounds.Height != 0, "Cannot have empty bound");
                if (bounds.Width == 0 || bounds.Height == 0) 
                {
                    throw FxTrace.Exception.AsError(new ArgumentException(SR.BoundsMustBeNonZero)); 
                } 

                Quadrant toInsert = this; 
                while (true)
                {
                    double w = toInsert.bounds.Width / 2;
                    if (w < 1) 
                    {
                        w = 1; 
                    } 
                    double h = toInsert.bounds.Height / 2;
                    if (h < 1) 
                    {
                        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(toInsert.bounds.Left, toInsert.bounds.Top, w, h);
                    Rect topRight = new Rect(toInsert.bounds.Left + w, toInsert.bounds.Top, w, h); 
                    Rect bottomLeft = new Rect(toInsert.bounds.Left, toInsert.bounds.Top + h, w, h);
                    Rect bottomRight = new Rect(toInsert.bounds.Left + w, toInsert.bounds.Top + h, w, h);

                    Quadrant child = null; 

                    // See if any child quadrants completely contain this node. 
                    if (topLeft.Contains(bounds)) 
                    {
                        if (toInsert.topLeft == null) 
                        {
                            toInsert.topLeft = new Quadrant(toInsert, topLeft);
                        }
                        child = toInsert.topLeft; 
                    }
                    else if (topRight.Contains(bounds)) 
                    { 
                        if (toInsert.topRight == null)
                        { 
                            toInsert.topRight = new Quadrant(toInsert, topRight);
                        }
                        child = toInsert.topRight;
                    } 
                    else if (bottomLeft.Contains(bounds))
                    { 
                        if (toInsert.bottomLeft == null) 
                        {
                            toInsert.bottomLeft = new Quadrant(toInsert, bottomLeft); 
                        }
                        child = toInsert.bottomLeft;
                    }
                    else if (bottomRight.Contains(bounds)) 
                    {
                        if (toInsert.bottomRight == null) 
                        { 
                            toInsert.bottomRight = new Quadrant(toInsert, bottomRight);
                        } 
                        child = toInsert.bottomRight;
                    }

                    if (child != null) 
                    {
                        toInsert = child; 
                    } 
                    else
                    { 
                        QuadNode n = new QuadNode(node, bounds);
                        if (toInsert.nodes == null)
                        {
                            n.Next = n; 
                        }
                        else 
                        { 
                            // link up in circular link list.
                            QuadNode x = toInsert.nodes; 
                            n.Next = x.Next;
                            x.Next = n;
                        }
                        toInsert.nodes = n; 
                        return toInsert;
                    } 
                } 
            }
 
            /// 
            /// 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.
            ///  
            /// List of nodes found in the given bounds
            /// The bounds that contains the nodes you want returned 
            internal void GetIntersectingNodes(List nodes, Rect bounds) 
            {
                if (bounds.IsEmpty) return; 
                double w = this.bounds.Width / 2;
                double h = this.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(this.bounds.Left, this.bounds.Top, w, h); 
                Rect topRight = new Rect(this.bounds.Left + w, this.bounds.Top, w, h);
                Rect bottomLeft = new Rect(this.bounds.Left, this.bounds.Top + h, w, h); 
                Rect bottomRight = new Rect(this.bounds.Left + w, this.bounds.Top + h, w, h);

                // See if any child quadrants completely contain this node.
                if (topLeft.IntersectsWith(bounds) && this.topLeft != null) 
                {
                    this.topLeft.GetIntersectingNodes(nodes, bounds); 
                } 

                if (topRight.IntersectsWith(bounds) && this.topRight != null) 
                {
                    this.topRight.GetIntersectingNodes(nodes, bounds);
                }
 
                if (bottomLeft.IntersectsWith(bounds) && this.bottomLeft != null)
                { 
                    this.bottomLeft.GetIntersectingNodes(nodes, bounds); 
                }
 
                if (bottomRight.IntersectsWith(bounds) && this.bottomRight != null)
                {
                    this.bottomRight.GetIntersectingNodes(nodes, bounds);
                } 

                GetIntersectingNodes(this.nodes, nodes, bounds); 
            } 

            ///  
            /// 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.
            /// 
            /// The last QuadNode in a circularly linked list 
            /// The resulting nodes are added to this list
            /// The bounds to test against each node 
            static void GetIntersectingNodes(QuadNode last, List 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);
                }
            }
 
            /// 
            /// Return true if there are any nodes in this Quadrant that intersect the given bounds. 
            ///  
            /// The bounds to test
            /// boolean 
            internal bool HasIntersectingNodes(Rect bounds)
            {
                if (bounds.IsEmpty) return false;
                double w = this.bounds.Width / 2; 
                double h = this.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(this.bounds.Left, this.bounds.Top, w, h);
                Rect topRight = new Rect(this.bounds.Left + w, this.bounds.Top, w, h);
                Rect bottomLeft = new Rect(this.bounds.Left, this.bounds.Top + h, w, h);
                Rect bottomRight = new Rect(this.bounds.Left + w, this.bounds.Top + h, w, h); 

                bool found = false; 
 
                // See if any child quadrants completely contain this node.
                if (topLeft.IntersectsWith(bounds) && this.topLeft != null) 
                {
                    found = this.topLeft.HasIntersectingNodes(bounds);
                }
 
                if (!found && topRight.IntersectsWith(bounds) && this.topRight != null)
                { 
                    found = this.topRight.HasIntersectingNodes(bounds); 
                }
 
                if (!found && bottomLeft.IntersectsWith(bounds) && this.bottomLeft != null)
                {
                    found = this.bottomLeft.HasIntersectingNodes(bounds);
                } 

                if (!found && bottomRight.IntersectsWith(bounds) && this.bottomRight != null) 
                { 
                    found = this.bottomRight.HasIntersectingNodes(bounds);
                } 
                if (!found)
                {
                    found = HasIntersectingNodes(this.nodes, bounds);
                } 
                return found;
            } 
 
            /// 
            /// Walk the given linked list and test each node against the given bounds/ 
            /// 
            /// The last node in the circularly linked list.
            /// Bounds to test
            /// Return true if a node in the list intersects the bounds 
            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;
            }

            ///  
            /// Remove the given node from this Quadrant.
            ///  
            /// The node to remove 
            /// Returns true if the node was found and removed.
            internal bool RemoveNode(T node) 
            {
                bool rc = false;
                if (this.nodes != null)
                { 
                    QuadNode p = this.nodes;
                    while (p.Next.Node != node && p.Next != this.nodes) 
                    { 
                        p = p.Next;
                    } 
                    if (p.Next.Node == node)
                    {
                        rc = true;
                        QuadNode n = p.Next; 
                        if (p == n)
                        { 
                            // list goes to empty 
                            this.nodes = null;
                        } 
                        else
                        {
                            if (this.nodes == n) this.nodes = p;
                            p.Next = n.Next; 
                        }
                    } 
                } 
                return rc;
            } 

        }
#if DEBUG_DUMP
        public void ShowQuadTree(Canvas container) 
        {
            if (this.root != null) 
            { 
                this.root.ShowQuadTree(container);
            } 
        }

        public void Dump(LogWriter w)
        { 
            if (this.root != null)
            { 
                this.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;
            this.xw = XmlWriter.Create(w, s); 
        } 

        public int MaxDepth 
        {
            get
            {
                return this.maxdepth; 
            }
        } 
 
        public void Open(string label)
        { 
            this.xw.WriteStartElement(label);
            this.indent++;
            if (this.indent > this.maxdepth) this.maxdepth = this.indent;
 
        }
        public void Close() 
        { 
            this.indent--;
            this.xw.WriteEndElement(); 
        }
        public void WriteAttribute(string name, string value)
        {
            this.xw.WriteAttributeString(name, value); 
        }
 
    #region IDisposable Members 

        public void Dispose() 
        {
            Dispose(true);
            GC.SuppressFinalize(this);
        } 

        protected virtual void Dispose(bool disposing) 
        { 
            if (disposing && this.xw != null)
            { 
                using (this.xw)
                {
                    this.xw.Flush();
                } 
                this.xw = null;
            } 
        } 

    #endregion 
    }
#endif

} 

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.


                        

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK