mcs/class/referencesource/System.Activities.Presentation/System.Activities.Presentation/System/Activities/Presentation/View/QuadTree.cs

   1 //----------------------------------------------------------------
   2 // Copyright (c) Microsoft Corporation.  All rights reserved.
   3 //----------------------------------------------------------------
   4 namespace System.Activities.Presentation.View
   5 {
   6     using System;
   7     using System.Collections.Generic;
   8     using System.Diagnostics;
   9     using System.IO;
  10     using System.Windows;
  11     using System.Runtime;
  12 #if DEBUG_DUMP
  13     using System.Windows.Controls;
  14     using System.Windows.Shapes;
  15     using System.Windows.Media;
  16     using System.Xml;
  17 #endif
  18
  19
  20     /// <summary>
  21     /// This class efficiently stores and retrieves arbitrarily sized and positioned
  22     /// objects in a quad-tree data structure.  This can be used to do efficient hit
  23     /// detection or visiblility checks on objects in a virtualized canvas.
  24     /// The object does not need to implement any special interface because the Rect Bounds
  25     /// of those objects is handled as a separate argument to Insert.
  26     /// </summary>
  27     class QuadTree<T> where T : class
  28     {
  29         Rect bounds; // overall bounds we are indexing.
  30         Quadrant root;
  31         IDictionary<T, Quadrant> table;
  32
  33
  34
  35         /// <summary>
  36         /// This determines the overall quad-tree indexing strategy, changing this bounds
  37         /// is expensive since it has to re-divide the entire thing - like a re-hash operation.
  38         /// </summary>
  39         public Rect Bounds
  40         {
  41             get { return this.bounds; }
  42             set { this.bounds = value; ReIndex(); }
  43         }
  44
  45         /// <summary>
  46         /// Insert a node with given bounds into this QuadTree.
  47         /// </summary>
  48         /// <param name="node">The node to insert</param>
  49         /// <param name="bounds">The bounds of this node</param>
  50         public void Insert(T node, Rect bounds)
  51         {
  52             if (this.bounds.Width == 0 || this.bounds.Height == 0)
  53             {
  54                 throw FxTrace.Exception.AsError(new ArgumentException(SR.BoundsMustBeNonZero));
  55             }
  56             if (bounds.Width == 0 || bounds.Height == 0)
  57             {
  58                 throw FxTrace.Exception.AsError(new ArgumentException(SR.BoundsMustBeNonZero));
  59             }
  60             if (this.root == null)
  61             {
  62                 this.root = new Quadrant(null, this.bounds);
  63             }
  64
  65             Quadrant parent = this.root.Insert(node, bounds);
  66
  67             if (this.table == null)
  68             {
  69                 this.table = new Dictionary<T, Quadrant>();
  70             }
  71             this.table[node] = parent;
  72
  73
  74         }
  75
  76         /// <summary>
  77         /// Get a list of the nodes that intersect the given bounds.
  78         /// </summary>
  79         /// <param name="bounds">The bounds to test</param>
  80         /// <returns>List of zero or mode nodes found inside the given bounds</returns>
  81         public IEnumerable<T> GetNodesInside(Rect bounds)
  82         {
  83             foreach (QuadNode n in GetNodes(bounds))
  84             {
  85                 yield return n.Node;
  86             }
  87         }
  88
  89         /// <summary>
  90         /// Get a list of the nodes that intersect the given bounds.
  91         /// </summary>
  92         /// <param name="bounds">The bounds to test</param>
  93         /// <returns>List of zero or mode nodes found inside the given bounds</returns>
  94         public bool HasNodesInside(Rect bounds)
  95         {
  96             if (this.root == null)
  97             {
  98                 return false;
  99             }
 100             return this.root.HasIntersectingNodes(bounds);
 101         }
 102
 103         /// <summary>
 104         /// Get list of nodes that intersect the given bounds.
 105         /// </summary>
 106         /// <param name="bounds">The bounds to test</param>
 107         /// <returns>The list of nodes intersecting the given bounds</returns>
 108         IEnumerable<QuadNode> GetNodes(Rect bounds)
 109         {
 110             List<QuadNode> result = new List<QuadNode>();
 111             if (this.root != null)
 112             {
 113                 this.root.GetIntersectingNodes(result, bounds);
 114             }
 115             return result;
 116         }
 117
 118         /// <summary>
 119         /// Remove the given node from this QuadTree.
 120         /// </summary>
 121         /// <param name="node">The node to remove</param>
 122         /// <returns>True if the node was found and removed.</returns>
 123         public bool Remove(T node)
 124         {
 125             if (this.table != null)
 126             {
 127                 Quadrant parent = null;
 128                 if (this.table.TryGetValue(node, out parent))
 129                 {
 130                     parent.RemoveNode(node);
 131                     this.table.Remove(node);
 132                     return true;
 133                 }
 134             }
 135             return false;
 136         }
 137
 138         /// <summary>
 139         /// Rebuild all the Quadrants according to the current QuadTree Bounds.
 140         /// </summary>
 141         void ReIndex()
 142         {
 143             this.root = null;
 144             foreach (QuadNode n in GetNodes(this.bounds))
 145             {
 146                 Insert(n.Node, n.Bounds);
 147             }
 148         }
 149
 150         /// <summary>
 151         /// Each node stored in the tree has a position, width & height.
 152         /// </summary>
 153         internal class QuadNode
 154         {
 155             Rect bounds;
 156             QuadNode next; // linked in a circular list.
 157             T node; // the actual visual object being stored here.
 158
 159             /// <summary>
 160             /// Construct new QuadNode to wrap the given node with given bounds
 161             /// </summary>
 162             /// <param name="node">The node</param>
 163             /// <param name="bounds">The bounds of that node</param>
 164             public QuadNode(T node, Rect bounds)
 165             {
 166                 this.node = node;
 167                 this.bounds = bounds;
 168             }
 169
 170             /// <summary>
 171             /// The node
 172             /// </summary>
 173             public T Node
 174             {
 175                 get { return this.node; }
 176                 set { this.node = value; }
 177             }
 178
 179             /// <summary>
 180             /// The Rect bounds of the node
 181             /// </summary>
 182             public Rect Bounds
 183             {
 184                 get { return this.bounds; }
 185             }
 186
 187             /// <summary>
 188             /// QuadNodes form a linked list in the Quadrant.
 189             /// </summary>
 190             public QuadNode Next
 191             {
 192                 get { return this.next; }
 193                 set { this.next = value; }
 194             }
 195         }
 196
 197
 198         /// <summary>
 199         /// The canvas is split up into four Quadrants and objects are stored in the quadrant that contains them
 200         /// and each quadrant is split up into four child Quadrants recurrsively.  Objects that overlap more than
 201         /// one quadrant are stored in the this.nodes list for this Quadrant.
 202         /// </summary>
 203         internal class Quadrant
 204         {
 205             Quadrant parent;
 206             Rect bounds; // quadrant bounds.
 207
 208             QuadNode nodes; // nodes that overlap the sub quadrant boundaries.
 209
 210             // The quadrant is subdivided when nodes are inserted that are
 211             // completely contained within those subdivisions.
 212             Quadrant topLeft;
 213             Quadrant topRight;
 214             Quadrant bottomLeft;
 215             Quadrant bottomRight;
 216
 217 #if DEBUG_DUMP
 218             public void ShowQuadTree(Canvas c)
 219             {
 220                 Rectangle r = new Rectangle();
 221                 r.Width = this.bounds.Width;
 222                 r.Height = this.bounds.Height;
 223                 Canvas.SetLeft(r, this.bounds.Left);
 224                 Canvas.SetTop(r, this.bounds.Top);
 225                 r.Stroke = Brushes.DarkRed;
 226                 r.StrokeThickness = 1;
 227                 r.StrokeDashArray = new DoubleCollection(new double[] { 2.0, 3.0 });
 228                 c.Children.Add(r);
 229
 230                 if (this.topLeft != null) this.topLeft.ShowQuadTree(c);
 231                 if (this.topRight != null) this.topRight.ShowQuadTree(c);
 232                 if (this.bottomLeft != null) this.bottomLeft.ShowQuadTree(c);
 233                 if (this.bottomRight != null) this.bottomRight.ShowQuadTree(c);
 234             }
 235
 236             public void Dump(LogWriter w)
 237             {
 238                 w.WriteAttribute("Bounds", this.bounds.ToString());
 239                 if (this.nodes != null)
 240                 {
 241                     QuadNode n = this.nodes;
 242                     do
 243                     {
 244                         n = n.Next; // first node.
 245                         w.Open("node");
 246                         w.WriteAttribute("Bounds", n.Bounds.ToString());
 247                         w.Close();
 248                     } while (n != this.nodes);
 249                 }
 250                 DumpQuadrant("TopLeft", this.topLeft, w);
 251                 DumpQuadrant("TopRight", this.topRight, w);
 252                 DumpQuadrant("BottomLeft", this.bottomLeft, w);
 253                 DumpQuadrant("BottomRight", this.bottomRight, w);
 254             }
 255
 256             public void DumpQuadrant(string label, Quadrant q, LogWriter w)
 257             {
 258                 if (q != null)
 259                 {
 260                     w.Open("Quadrant");
 261                     w.WriteAttribute("Name", label);
 262                     q.Dump(w);
 263                     w.Close();
 264                 }
 265             }
 266 #endif
 267
 268             /// <summary>
 269             /// Construct new Quadrant with a given bounds all nodes stored inside this quadrant
 270             /// will fit inside this bounds.
 271             /// </summary>
 272             /// <param name="parent">The parent quadrant (if any)</param>
 273             /// <param name="bounds">The bounds of this quadrant</param>
 274             public Quadrant(Quadrant parent, Rect bounds)
 275             {
 276                 this.parent = parent;
 277                 Fx.Assert(bounds.Width != 0 && bounds.Height != 0, "Cannot have empty bound");
 278                 if (bounds.Width == 0 || bounds.Height == 0)
 279                 {
 280                     throw FxTrace.Exception.AsError(new ArgumentException(SR.BoundsMustBeNonZero));
 281                 }
 282                 this.bounds = bounds;
 283             }
 284
 285             /// <summary>
 286             /// The parent Quadrant or null if this is the root
 287             /// </summary>
 288             internal Quadrant Parent
 289             {
 290                 get { return this.parent; }
 291             }
 292
 293             /// <summary>
 294             /// The bounds of this quadrant
 295             /// </summary>
 296             internal Rect Bounds
 297             {
 298                 get { return this.bounds; }
 299             }
 300
 301             /// <summary>
 302             /// Insert the given node
 303             /// </summary>
 304             /// <param name="node">The node </param>
 305             /// <param name="bounds">The bounds of that node</param>
 306             /// <returns></returns>
 307             internal Quadrant Insert(T node, Rect bounds)
 308             {
 309
 310                 Fx.Assert(bounds.Width != 0 && bounds.Height != 0, "Cannot have empty bound");
 311                 if (bounds.Width == 0 || bounds.Height == 0)
 312                 {
 313                     throw FxTrace.Exception.AsError(new ArgumentException(SR.BoundsMustBeNonZero));
 314                 }
 315
 316                 Quadrant toInsert = this;
 317                 while (true)
 318                 {
 319                     double w = toInsert.bounds.Width / 2;
 320                     if (w < 1)
 321                     {
 322                         w = 1;
 323                     }
 324                     double h = toInsert.bounds.Height / 2;
 325                     if (h < 1)
 326                     {
 327                         h = 1;
 328                     }
 329
 330                     // assumption that the Rect struct is almost as fast as doing the operations
 331                     // manually since Rect is a value type.
 332
 333                     Rect topLeft = new Rect(toInsert.bounds.Left, toInsert.bounds.Top, w, h);
 334                     Rect topRight = new Rect(toInsert.bounds.Left + w, toInsert.bounds.Top, w, h);
 335                     Rect bottomLeft = new Rect(toInsert.bounds.Left, toInsert.bounds.Top + h, w, h);
 336                     Rect bottomRight = new Rect(toInsert.bounds.Left + w, toInsert.bounds.Top + h, w, h);
 337
 338                     Quadrant child = null;
 339
 340                     // See if any child quadrants completely contain this node.
 341                     if (topLeft.Contains(bounds))
 342                     {
 343                         if (toInsert.topLeft == null)
 344                         {
 345                             toInsert.topLeft = new Quadrant(toInsert, topLeft);
 346                         }
 347                         child = toInsert.topLeft;
 348                     }
 349                     else if (topRight.Contains(bounds))
 350                     {
 351                         if (toInsert.topRight == null)
 352                         {
 353                             toInsert.topRight = new Quadrant(toInsert, topRight);
 354                         }
 355                         child = toInsert.topRight;
 356                     }
 357                     else if (bottomLeft.Contains(bounds))
 358                     {
 359                         if (toInsert.bottomLeft == null)
 360                         {
 361                             toInsert.bottomLeft = new Quadrant(toInsert, bottomLeft);
 362                         }
 363                         child = toInsert.bottomLeft;
 364                     }
 365                     else if (bottomRight.Contains(bounds))
 366                     {
 367                         if (toInsert.bottomRight == null)
 368                         {
 369                             toInsert.bottomRight = new Quadrant(toInsert, bottomRight);
 370                         }
 371                         child = toInsert.bottomRight;
 372                     }
 373
 374                     if (child != null)
 375                     {
 376                         toInsert = child;
 377                     }
 378                     else
 379                     {
 380                         QuadNode n = new QuadNode(node, bounds);
 381                         if (toInsert.nodes == null)
 382                         {
 383                             n.Next = n;
 384                         }
 385                         else
 386                         {
 387                             // link up in circular link list.
 388                             QuadNode x = toInsert.nodes;
 389                             n.Next = x.Next;
 390                             x.Next = n;
 391                         }
 392                         toInsert.nodes = n;
 393                         return toInsert;
 394                     }
 395                 }
 396             }
 397
 398             /// <summary>
 399             /// Returns all nodes in this quadrant that intersect the given bounds.
 400             /// The nodes are returned in pretty much random order as far as the caller is concerned.
 401             /// </summary>
 402             /// <param name="nodes">List of nodes found in the given bounds</param>
 403             /// <param name="bounds">The bounds that contains the nodes you want returned</param>
 404             internal void GetIntersectingNodes(List<QuadNode> nodes, Rect bounds)
 405             {
 406                 if (bounds.IsEmpty) return;
 407                 double w = this.bounds.Width / 2;
 408                 double h = this.bounds.Height / 2;
 409
 410                 // assumption that the Rect struct is almost as fast as doing the operations
 411                 // manually since Rect is a value type.
 412
 413                 Rect topLeft = new Rect(this.bounds.Left, this.bounds.Top, w, h);
 414                 Rect topRight = new Rect(this.bounds.Left + w, this.bounds.Top, w, h);
 415                 Rect bottomLeft = new Rect(this.bounds.Left, this.bounds.Top + h, w, h);
 416                 Rect bottomRight = new Rect(this.bounds.Left + w, this.bounds.Top + h, w, h);
 417
 418                 // See if any child quadrants completely contain this node.
 419                 if (topLeft.IntersectsWith(bounds) && this.topLeft != null)
 420                 {
 421                     this.topLeft.GetIntersectingNodes(nodes, bounds);
 422                 }
 423
 424                 if (topRight.IntersectsWith(bounds) && this.topRight != null)
 425                 {
 426                     this.topRight.GetIntersectingNodes(nodes, bounds);
 427                 }
 428
 429                 if (bottomLeft.IntersectsWith(bounds) && this.bottomLeft != null)
 430                 {
 431                     this.bottomLeft.GetIntersectingNodes(nodes, bounds);
 432                 }
 433
 434                 if (bottomRight.IntersectsWith(bounds) && this.bottomRight != null)
 435                 {
 436                     this.bottomRight.GetIntersectingNodes(nodes, bounds);
 437                 }
 438
 439                 GetIntersectingNodes(this.nodes, nodes, bounds);
 440             }
 441
 442             /// <summary>
 443             /// Walk the given linked list of QuadNodes and check them against the given bounds.
 444             /// Add all nodes that intersect the bounds in to the list.
 445             /// </summary>
 446             /// <param name="last">The last QuadNode in a circularly linked list</param>
 447             /// <param name="nodes">The resulting nodes are added to this list</param>
 448             /// <param name="bounds">The bounds to test against each node</param>
 449             static void GetIntersectingNodes(QuadNode last, List<QuadNode> nodes, Rect bounds)
 450             {
 451                 if (last != null)
 452                 {
 453                     QuadNode n = last;
 454                     do
 455                     {
 456                         n = n.Next; // first node.
 457                         if (n.Bounds.IntersectsWith(bounds))
 458                         {
 459                             nodes.Add(n);
 460                         }
 461                     } while (n != last);
 462                 }
 463             }
 464
 465             /// <summary>
 466             /// Return true if there are any nodes in this Quadrant that intersect the given bounds.
 467             /// </summary>
 468             /// <param name="bounds">The bounds to test</param>
 469             /// <returns>boolean</returns>
 470             internal bool HasIntersectingNodes(Rect bounds)
 471             {
 472                 if (bounds.IsEmpty) return false;
 473                 double w = this.bounds.Width / 2;
 474                 double h = this.bounds.Height / 2;
 475
 476                 // assumption that the Rect struct is almost as fast as doing the operations
 477                 // manually since Rect is a value type.
 478
 479                 Rect topLeft = new Rect(this.bounds.Left, this.bounds.Top, w, h);
 480                 Rect topRight = new Rect(this.bounds.Left + w, this.bounds.Top, w, h);
 481                 Rect bottomLeft = new Rect(this.bounds.Left, this.bounds.Top + h, w, h);
 482                 Rect bottomRight = new Rect(this.bounds.Left + w, this.bounds.Top + h, w, h);
 483
 484                 bool found = false;
 485
 486                 // See if any child quadrants completely contain this node.
 487                 if (topLeft.IntersectsWith(bounds) && this.topLeft != null)
 488                 {
 489                     found = this.topLeft.HasIntersectingNodes(bounds);
 490                 }
 491
 492                 if (!found && topRight.IntersectsWith(bounds) && this.topRight != null)
 493                 {
 494                     found = this.topRight.HasIntersectingNodes(bounds);
 495                 }
 496
 497                 if (!found && bottomLeft.IntersectsWith(bounds) && this.bottomLeft != null)
 498                 {
 499                     found = this.bottomLeft.HasIntersectingNodes(bounds);
 500                 }
 501
 502                 if (!found && bottomRight.IntersectsWith(bounds) && this.bottomRight != null)
 503                 {
 504                     found = this.bottomRight.HasIntersectingNodes(bounds);
 505                 }
 506                 if (!found)
 507                 {
 508                     found = HasIntersectingNodes(this.nodes, bounds);
 509                 }
 510                 return found;
 511             }
 512
 513             /// <summary>
 514             /// Walk the given linked list and test each node against the given bounds/
 515             /// </summary>
 516             /// <param name="last">The last node in the circularly linked list.</param>
 517             /// <param name="bounds">Bounds to test</param>
 518             /// <returns>Return true if a node in the list intersects the bounds</returns>
 519             static bool HasIntersectingNodes(QuadNode last, Rect bounds)
 520             {
 521                 if (last != null)
 522                 {
 523                     QuadNode n = last;
 524                     do
 525                     {
 526                         n = n.Next; // first node.
 527                         if (n.Bounds.IntersectsWith(bounds))
 528                         {
 529                             return true;
 530                         }
 531                     } while (n != last);
 532                 }
 533                 return false;
 534             }
 535
 536             /// <summary>
 537             /// Remove the given node from this Quadrant.
 538             /// </summary>
 539             /// <param name="node">The node to remove</param>
 540             /// <returns>Returns true if the node was found and removed.</returns>
 541             internal bool RemoveNode(T node)
 542             {
 543                 bool rc = false;
 544                 if (this.nodes != null)
 545                 {
 546                     QuadNode p = this.nodes;
 547                     while (p.Next.Node != node && p.Next != this.nodes)
 548                     {
 549                         p = p.Next;
 550                     }
 551                     if (p.Next.Node == node)
 552                     {
 553                         rc = true;
 554                         QuadNode n = p.Next;
 555                         if (p == n)
 556                         {
 557                             // list goes to empty
 558                             this.nodes = null;
 559                         }
 560                         else
 561                         {
 562                             if (this.nodes == n) this.nodes = p;
 563                             p.Next = n.Next;
 564                         }
 565                     }
 566                 }
 567                 return rc;
 568             }
 569
 570         }
 571 #if DEBUG_DUMP
 572         public void ShowQuadTree(Canvas container)
 573         {
 574             if (this.root != null)
 575             {
 576                 this.root.ShowQuadTree(container);
 577             }
 578         }
 579
 580         public void Dump(LogWriter w)
 581         {
 582             if (this.root != null)
 583             {
 584                 this.root.Dump(w);
 585             }
 586         }
 587 #endif
 588     }
 589
 590 #if DEBUG_DUMP
 591     public class LogWriter : IDisposable
 592     {
 593         XmlWriter xw;
 594         int indent;
 595         int maxdepth;
 596
 597         public LogWriter(TextWriter w)
 598         {
 599             XmlWriterSettings s = new XmlWriterSettings();
 600             s.Indent = true;
 601             this.xw = XmlWriter.Create(w, s);
 602         }
 603
 604         public int MaxDepth
 605         {
 606             get
 607             {
 608                 return this.maxdepth;
 609             }
 610         }
 611
 612         public void Open(string label)
 613         {
 614             this.xw.WriteStartElement(label);
 615             this.indent++;
 616             if (this.indent > this.maxdepth) this.maxdepth = this.indent;
 617
 618         }
 619         public void Close()
 620         {
 621             this.indent--;
 622             this.xw.WriteEndElement();
 623         }
 624         public void WriteAttribute(string name, string value)
 625         {
 626             this.xw.WriteAttributeString(name, value);
 627         }
 628
 629     #region IDisposable Members
 630
 631         public void Dispose()
 632         {
 633             Dispose(true);
 634             GC.SuppressFinalize(this);
 635         }
 636
 637         protected virtual void Dispose(bool disposing)
 638         {
 639             if (disposing && this.xw != null)
 640             {
 641                 using (this.xw)
 642                 {
 643                     this.xw.Flush();
 644                 }
 645                 this.xw = null;
 646             }
 647         }
 648
 649     #endregion
 650     }
 651 #endif
 652
 653 }