Part 1 of this series is here.
According to Wikipedia:
“A quadtree is a tree data structure in which each internal node has exactly four children. Quadtrees are most often used to partition a two-dimensional space by recursively subdividing it into four quadrants or regions.”
Building a quadtree from data points is simple.
1. Divide the entire area into 4 equal quadrants. Each quadrant can hold up to a predefined number of points.
2. Start adding points until you have reached the maximum for that quadrant.
3. Split the quadrant into 4 equal quadrants and continue adding points.
Eventually you end up with something like this:
Basic quadtree implementation in C# using System.Drawing.Point as containing data type
// start actual usable code
namespace CDNASDK
{
/// <summary>
/// Simple Quadtree class in C# - based on the wikipedia article @
/// http://en.wikipedia.org/wiki/Quadtree
//
// - kj 2014
/// </summary>
public partial class QuadTree
{
// Arbitrary constant to indicate how many elements can be stored in this quad tree node
// one place to tune performance is by tuning the node capacity
const int QT_NODE_CAPACITY = 5;
// Axis-aligned bounding box stored as a center with half-dimensions or a rectangle in 2D ;P
// to represent the boundaries of this quad tree
public Rectangle BoundingBox;
// Any class with a Point type property can be used here
List<Point> points = new List<Point>();
// Children
public QuadTree northWest;
public QuadTree northEast;
public QuadTree southWest;
public QuadTree southEast;
// Methods
public QuadTree(Rectangle _boundingBox )
{
BoundingBox = _boundingBox;
northWest = null;
northEast = null;
southWest = null;
southEast = null;
}
// Insert a point into the QuadTree
public bool insert(Point p)
{
// Ignore objects which do not belong in this quad tree
if (!BoundingBox.Contains(p))
return false; // object cannot be added
if (points == null) points = new List<Point>();
// If there is space in this quad tree, add the object here
if (points.Count < QT_NODE_CAPACITY)
{
points.Add(p);
return true;
}
// Otherwise, we need to subdivide then add the point to whichever node will accept it
if (northWest == null)
subdivide();
//looks like the order here matters...
if (northWest.insert(p)) return true;
if (southWest.insert(p)) return true;
if (southEast.insert(p)) return true;
if (northEast.insert(p)) return true;
// Otherwise, the point cannot be inserted for some unknown reason (which should never happen)
return false;
}
private void subdivide()
{
// create four children which fully divide this quad into four quads of equal area
Rectangle BBNW = new Rectangle(BoundingBox.X, BoundingBox.Y, BoundingBox.Width / 2, BoundingBox.Height / 2);
Rectangle BBNE = new Rectangle(BoundingBox.X + BoundingBox.Width / 2,
BoundingBox.Y, BoundingBox.Width / 2, BoundingBox.Height / 2);
Rectangle BBSW = new Rectangle(BoundingBox.X,
BoundingBox.Y + BoundingBox.Height /2, BoundingBox.Width / 2, BoundingBox.Height / 2);
Rectangle BBSE = new Rectangle(BoundingBox.X + BoundingBox.Width / 2,
BoundingBox.Y + BoundingBox.Height /2, BoundingBox.Width / 2, BoundingBox.Height / 2);
// create the new quad trees
northWest = new QuadTree(BBNW);
northEast = new QuadTree(BBNE);
southWest = new QuadTree(BBSW);
southEast = new QuadTree(BBSE);
// insert points contained in northwest bounding box
foreach(Point p in queryRange(BBNW))
{
northWest.insert(p);
}
// insert points contained in southwest bounding box
foreach (Point p in queryRange(BBSW))
{
southWest.insert(p);
}
// insert points contained in southeast bounding box
foreach (Point p in queryRange(BBSE))
{
southEast.insert(p);
}
// insert points contained in northeast bounding box
foreach (Point p in queryRange(BBNE))
{
northEast.insert(p);
}
//since the points are now in children quads
//clear the list
points.Clear();
}
public Point[] queryRange(Rectangle range)
{
// Prepare an array of results
List<Point> pointsInRange = new List<Point>();
// Automatically abort if the range does not collide with this quad
if (!BoundingBox.IntersectsWith(range))
return pointsInRange.ToArray(); // empty list
if (points == null) points = new List<Point>();
// Check objects at this quad level
for (int p = 0; p < points.Count ; p++)
{
if (range.Contains(points[p]))
pointsInRange.Add(points[p]);
}
// Terminate here, if there are no children
if (northWest == null)
return pointsInRange.ToArray();
// Otherwise, add the points from the children
pointsInRange.AddRange(northWest.queryRange(range));
pointsInRange.AddRange(northEast.queryRange(range));
pointsInRange.AddRange(southWest.queryRange(range));
pointsInRange.AddRange(southEast.queryRange(range));
return pointsInRange.ToArray();
}
}
}
Creating a quadtree
//build quad tree
QuadTree myQuadTree = new QuadTree(
new Rectangle(0, 0, width, height));
And adding points to the quadtree is straightforward.
//insert a point
myQuadTree.insert(ll);
Querying against the quadtree is easy. To find all the visible points, all we need is to send the bounding rectangle of the viewport to the .queryRange(rect) method.
myQuadTree.queryRange(vpBoundingBox)
OK. We finally made it to the good stuff. All source code is included in the archive here.
Extract the archive to a folder somewhere and open the solution in Visual Studio 2012 or later.
Verify the reference to System.Drawing.
I have made a couple of changes to the quadtree example class from above:
QuadTree.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Drawing;
namespace CDNASDK
{
/// <summary>
/// Simple Quadtree class in C# - based on the wikipedia article @
/// http://en.wikipedia.org/wiki/Quadtree
//
// - kj 2014
/// </summary>
#region Test Data Model
public class TestData
{
public enum SomeData
{
AA,
AB,
AC,
AD,
AE,
AF,
BA,
BB,
BC,
BD,
BE,
BF
};
public Point xy { get; set; }
public SomeData somedata { get; set; }
}
#endregion
public partial class QuadTree
{
// Arbitrary constant to indicate how many elements can be stored in this quad tree node
// one place to tune performance is by tuning the node capacity
const int QT_NODE_CAPACITY = 25;
// Axis-aligned bounding box stored as a center with half-dimensions or a rectangle in 2D ;P
// to represent the boundaries of this quad tree
public Rectangle BoundingBox;
// Any class with a Point type property can be used here
List<TestData> points = new List<TestData>();
// Children
public QuadTree northWest;
public QuadTree northEast;
public QuadTree southWest;
public QuadTree southEast;
// Methods
public QuadTree(Rectangle _boundingBox )
{
BoundingBox = _boundingBox;
northWest = null;
northEast = null;
southWest = null;
southEast = null;
}
// Insert a point into the QuadTree
public bool insert(TestData p)
{
// Ignore objects which do not belong in this quad tree
if (!BoundingBox.Contains(p.xy))
return false; // object cannot be added
if (points == null) points = new List<TestData>();
// If there is space in this quad tree, add the object here
if (points.Count < QT_NODE_CAPACITY)
{
points.Add(p);
return true;
}
// Otherwise, we need to subdivide then add the point to whichever node will accept it
if (northWest == null)
subdivide();
//looks like the order here matters...
if (northWest.insert(p)) return true;
if (southWest.insert(p)) return true;
if (southEast.insert(p)) return true;
if (northEast.insert(p)) return true;
// Otherwise, the point cannot be inserted for some unknown reason (which should never happen)
return false;
}
private void subdivide()
{
// create four children which fully divide this quad into four quads of equal area
Rectangle BBNW = new Rectangle(BoundingBox.X, BoundingBox.Y, BoundingBox.Width / 2, BoundingBox.Height / 2);
Rectangle BBNE = new Rectangle(BoundingBox.X + BoundingBox.Width / 2,
BoundingBox.Y, BoundingBox.Width / 2, BoundingBox.Height / 2);
Rectangle BBSW = new Rectangle(BoundingBox.X,
BoundingBox.Y + BoundingBox.Height /2, BoundingBox.Width / 2, BoundingBox.Height / 2);
Rectangle BBSE = new Rectangle(BoundingBox.X + BoundingBox.Width / 2,
BoundingBox.Y + BoundingBox.Height /2, BoundingBox.Width / 2, BoundingBox.Height / 2);
// create the new quad trees
northWest = new QuadTree(BBNW);
northEast = new QuadTree(BBNE);
southWest = new QuadTree(BBSW);
southEast = new QuadTree(BBSE);
// insert points contained in northwest bounding box
foreach(TestData p in queryRange(BBNW))
{
northWest.insert(p);
}
// insert points contained in southwest bounding box
foreach (TestData p in queryRange(BBSW))
{
southWest.insert(p);
}
// insert points contained in southeast bounding box
foreach (TestData p in queryRange(BBSE))
{
southEast.insert(p);
}
// insert points contained in northeast bounding box
foreach (TestData p in queryRange(BBNE))
{
northEast.insert(p);
}
//since the points are now in children quads
//clear the list
points.Clear();
}
public TestData[] queryRange(Rectangle range)
{
// Prepare an array of results
List<TestData> pointsInRange = new List<TestData>();
// Automatically abort if the range does not collide with this quad
if (!BoundingBox.IntersectsWith(range))
return pointsInRange.ToArray(); // empty list
if (points == null) points = new List<TestData>();
// Check objects at this quad level
for (int p = 0; p < points.Count ; p++)
{
if (range.Contains(points[p].xy))
pointsInRange.Add(points[p]);
}
// Terminate here, if there are no children
if (northWest == null)
return pointsInRange.ToArray();
// Otherwise, add the points from the children
pointsInRange.AddRange(northWest.queryRange(range));
pointsInRange.AddRange(southWest.queryRange(range));
pointsInRange.AddRange(southEast.queryRange(range));
pointsInRange.AddRange(northEast.queryRange(range));
return pointsInRange.ToArray();
}
}
}
Opening up Program.cs for a closer look…
We create an instance of the quadtree class.
QuadTree qt = new QuadTree(new Rectangle(0, 0, QuadTreeSize, QuadTreeSize));
Next we add 1 million random locations with some random data:
Random random = new Random();
for (s=0; s < 1000000; s++)
{
//create a new object of type Testdata
TestData td = new TestData();
//create a random point
int X = random.Next(0, QuadTreeSize);
int Y = random.Next(0, QuadTreeSize);
Array values = Enum.GetValues(typeof(TestData.SomeData));
//add some meaningful data
td.somedata = (TestData.SomeData)values.GetValue(random.Next(values.Length));
td.xy = new Point(X, Y);
...
//insert the object into the quadtree
qt.insert(td);
}
Next we have three test cases:
Brute force array parsing: In this case we visit every array node, checking to see if we meet the selection criteria.
Brute Force Method:
foreach( TestData td in tdl)
{
//add in some random computational logic (ToString() is suppose to be slow so i use it as an example)
if ((td.somedata.ToString().Equals("BA") || td.somedata.ToString().Equals("BD")
|| td.somedata.ToString().Equals("AA")
|| td.somedata.ToString().Equals("BB"))
&& Viewport.Contains(td.xy)) recordcount++;
}
Brute force with viewport clipping: Here we move our early out test to the beginning of the loop, using string comparison only on points falling inside the viewport.
foreach (TestData td in tdl)
{
//early out test - clip to the viewport
if (Viewport.Contains(td.xy))
//add in some random computational logic (ToString() is suppose to be slow so i use it as an example)
if (td.somedata.ToString().Equals("BA") || td.somedata.ToString().Equals("BD")
|| td.somedata.ToString().Equals("AA")
|| td.somedata.ToString().Equals("BB")) recordcount++;
}
Using quadtrees: Finally, we use a quadtree to test recursively using the viewport’s bounding box as our range value.
foreach( TestData td in qt.queryRange(Viewport))
{
//add in some random computational logic (ToString() is suppose to be slow so i use it as an example)
if (td.somedata.ToString().Equals("BA") || td.somedata.ToString().Equals("BD")
|| td.somedata.ToString().Equals("AA")
|| td.somedata.ToString().Equals("BB")) recordcount++;
}
Executing the program will yield the following test results:
Conclusion: We can see from the test results that brute force array parsing (i.e., visiting/testing every node) is extremely slow. We manage to get almost seven times better performance using an early out test (viewport clipping). The most interesting result, however, is using the quadtree. In this case, we more than double the performance of clipping alone, and squeeze a whopping 15 times better performance over brute force alone!
Stay tuned for the next installment of this series, where I will show specifics on how using a quadtree helped our pipeline map demo meet its functional requirement.
alinesfnc
courtneyhumphries
dnemesek
fncprince
jdhanco1
jerrylilly
jmarsalis
Jason Verlangieri
kayladsween
kconwayfnc
kevinjatfnc
kmkemp11
melakin93
michaelenej
raju1971
rsmasonwp
softwareunwound
usmmmm
vpirkle