PriorityQuadTree
Chris Lovett has a written a cool Virtualized WPF Canvas that lets you pan and zoom around a huge canvas full of shapes, and it only creates those shapes which can be seen on your screen at the time (i.e. within your viewbox of the canvas). As you pan around, it destroys the shapes that are no longer in view, and it creates new shapes as they come into view. In order to quickly determine which shapes are within the viewbox as you pan back and forth around the canvas, he has written a quad tree that builds a spatial index of all of the bounding boxes of the shapes. The QuadTree can then be queried to almost instantly return all of the items whose bounding boxes intersect a given Rect (which represents the viewbox in this case).
The QuadTree works great to limit the number of instantiated elements when you’re zoomed in and panning around with a small viewbox, but what about when you zoom way out? The QuadTree of course returns all of the items since your viewbox is huge! But the problem is that WPF just can’t handle that many elements at once while maintaining responsiveness. So if we can’t create elements for all of the items within our viewbox, then how do we decide which ones to show and which ones to leave out? Well, if you know that some items are more important to show than others, then you can simply assign a priority to each item and show the ones with highest priority first.
When implementing this solution, my first approach was to take the items returned by the query to the QuadTree, sort them by priority, and then create elements for only the first N, where N was the upper limit on how many elements could be created without bringing WPF to its knees. The problem was that I had to sort all of the items returned by the query (which might have been millions), even though I was only going to use the first N (which was only in the hundreds), and the huge sorting operation was causing a noticeable delay since it had to be done every time you moved the viewbox even one pixel.
The fact that I had millions of items but I only needed to extract the first N in order reminded me of the PriorityQueue I had written several years ago. What if the QuadTree could do the same thing? If it always returned items in order of priority, and if it only had to do the lookup for the first N items, it would be perfect!
The PriorityQuadTree solves both of these problems. It lets you associate a priority (a double) for each item, and it returns a lazy IEnumerable instead of a List so that it only has to process as many items as you enumerate. I could have written it to take N as an argument, and return a List with exactly N items, but in my particular application I didn’t always need all N items. This was because the user could pan or zoom again while in the middle of this process, which causes old viewbox to be invalid so you want the process to start over. By implementing it as a LINQ-style lazy enumeration, I only do exactly as much work as required, and the CPU cycles are distributed evenly throughout the enumeration instead of doing a bunch of work up front that might have caused a delay in the UI.
Internally, for each Quadrant I keep track of the maximum priority of all the items that are underneath that Quadrant. I call this the potential for the Quadrant, since that’s the best possible priority you could get when you query it. You’re not guaranteed to get an item what that priority though, since you might query it with a Rect that doesn’t wind up intersecting the item with that priority. But having that potential is the key to avoiding a linear search through the tree when doing a query.
Doing a query starts at the root Quadrant and recursively calls down to each of the sub-Quadrants, just like in the original QuadTree, but this time each sub-Quadrant returns a Tuple<QuadNode, double> instead of just a QuadNode, and this extra double represents the remaining potential of the Quadrant. The parent Quadrant uses a PriorityQueue with the remaining potentials of its sub-Quadrants, and it simply Dequeues the Quadrants in a loop until the PriorityQueue is empty. This is all done lazily and recursively, so you can imagine it at any given time like a huge chain of partially-enumerated method calls, and each time you extract the next node in the query then it sets the chains in motion like a giant game of Plinko.
The code is too big to post here, so I’m attaching the full source file for PriorityQuadTree instead. It relies on code from other sections of my blog, namely RectExtensions, MathExtensions, and PriorityQueue, so please be sure to download those files as well. Enjoy!