Tutorial¶
This guide seeks to help you learn how to use quads
. We’ll be covering:
- what a Quadtree is,
- why you might want to use one,
- how to create your first tree,
- how to store extra data within the tree,
- how to search within the tree,
- …and how to see what your tree looks like.
Let’s begin with the basics.
What Is a Quadtree?¶
A Quadtree is a type of data structure, a form of a Tree. It has a number of interesting properties, such as:
- A built-in hierarchy
- Sparse structure
- Fast inserts
- Fast lookups
- Ideal for storing spatial or image data
The sparse nature & quick spatial lookups offer a significant improvement
over other structures, such as plain list
objects or the like.
Why You Might Use a Quadtree¶
The ideal case is when you’re dealing with a 2D chunk of data. This includes things like images, maps, & storing spreadsheet data.
Quadtrees come in several forms. The two we’ll discuss here are in storing point data (for instance, X/Y coordinates) or region data (where an entire portion of the 2D data is homogeneous).
For instance, the author uses them in a GIS application as an indexing structure, allowing for fast proximity-based lookups.
There are many more uses you can find online & in other sources.
“Great! I Need a Quadtree. What Now?”¶
There are many libraries out there (in all types of languages) for quadtrees.
But since you’re here, you’re probably using the Python programming
language. And you could totally use quads
!
If you already have Python, you can go to a shell & run:
$ pip install quads
This will install quads
globally, which may not always be desirable.
Options like virtualenv
, poetry
& others allow for isolated installs.
See their documentation for usage.
Making a Quadtree¶
Making a new quadtree is easy. Fire up a Python shell & enter the following:
>>> import quads
>>> tree = quads.QuadTree((0, 0), 20, 20)
The first statement (import quads
) imports the library for your use.
The second statement is the more interesting one. We’re using the
quads.QuadTree
class to make a new quadtree instance. We’re setting a center
point of (0, 0)
& providing a width/height of 20
.
This gives us a tree with Cartesian coordinates, from -10
to 10
on
both the X & Y axis.
But the tree is empty & doesn’t do a whole lot without some data. Let’s add some points that we care about to it…:
>>> tree.insert((3, 5))
This inserts a new point at the coordinates (3, 5)
.
We can verify the point is now in the tree with:
>>> (3, 5) in tree
True
>>> (-2, -2) in tree
False
We also see that a different point (2, 2)
, while within the coordinate
space of our quadtree, is NOT present in the data. Let’s fix that &
add a bunch more points as well:
>>> tree.insert((-2, -2))
>>> (-2, -2) in tree
True
>>> tree.insert((0, 1))
>>> tree.insert((-3, 3))
>>> tree.insert((-2, 4))
>>> tree.insert((11, 12))
ValueError: Point <Point: (11, 12)> is not within this node
(<Point: (0, 0)> - <BoundingBox: (-10.0, -10.0) to (10.0, 10.0)>).
Whoops. We tried to insert a point that didn’t fit within the bounds we’d
set when creating the :py:quads.QuadTree
. When that happens, you
get a ValueError
exception warning you of the problem.
Storing Extra Data on Points¶
Sometimes, just the coordinate values aren’t enough to represent what’s being stored. For instance, let’s say you’re plotting out the board state of a game of Checkers.
Our board might look like:
>>> import quads
# Center is at 4x4 of the 8 by 8 board.
>>> board = quads.QuadTree((4, 4), 8, 8)
We can store the location of the pieces by setting points. But with what we’ve learned so far, we’d have no way to know if a given piece is red or black.
Enter the data=...
argument:
# Zero-based offsets, so everything
>>> board.insert((1, 1), data="red")
>>> board.insert((0, 0), data="black")
>>> board.insert((3, 5), data="red")
>>> board.insert((7, 7), data="black")
>>> board.insert((4, 4), data="black")
Now we know whose pieces are where. And if it’s black’s turn, red is in trouble!
Searching the Quadtree¶
Data’s no use to anyone if there isn’t a way to find that data. There are
several useful methods for searching a quads.QuadTree
.
As we’ve already seen, if we just want to detect if a point is present
within the data, we use the in
operator:
>>> (-2, -2) in tree
True
If we want the full point back, data
included, we use
quads.QuadTree.find()
:
>>> board.find((1, 1))
Point(1, 1, data="red")
If we want all the points within a bounding box, the
quads.QuadTree.within_bb()
method allows you to look up all points
in the provided area:
>>> bb = quads.BoundingBox(min_x=0, min_y=0, max_x=6, max_y=6)
>>> tree.within_bb(bb)
[
Point(3, 5),
Point(0, 1),
]
Warning
Note: The data coming out of the within_bb
query isn’t
necessarily in any (obvious) order.
You’ll need to manually sort the points to suit your needs.
The order is actually a result of a combination of the insertion order & the way nodes within the tree are traversed.
And finally, we come to “Nearest Neighbors”. The
quads.QuadTree.nearest_neighbors()
method allows you to pick a
location (even if it doesn’t exist within the data itself) & pick out the
quads.Point
objects nearest to it. For example:
# Repeated from above as a reminder; no need to do this if you still
# have the same instance around.
# >>> tree = quads.QuadTree((0, 0), 20, 20)
# >>> tree.insert((3, 5))
# >>> tree.insert((-2, -2))
# >>> tree.insert((0, 1))
# >>> tree.insert((-3, 3))
# >>> tree.insert((-2, 4))
>>> found = tree.nearest_neighbors((2, 2), count=4)
>>> found
[
Point(0, 1),
Point(3, 5),
Point(-2, 4),
Point(-3, 3),
]
These points come out in-order, from closest to furthest from the
provided point. Note that because we limited the count=4
, we only got
four out of the five points back.
No distances are included in the results, but you can calculate them if you
need via quads.euclidean_distance()
:
>>> quads.euclidean_distance(
... quads.Point(2, 2),
... quads.Point(-2, 4),
... )
4.47213595499958
Note that once you leave the bounds of the QuadTree
API, you’ll need to
use quads.Point
to represent locations.
Visualizing Your Quadtree¶
quads
itself only requires the Python standard library, meaning you
don’t have to install anything else to use it.
However, if we want to visualize what our QuadTree
looks like, we’ll
need to install another library.:
$ pip install matplotlib
Once you have a tree
built up, you can call quads.visualize()
to draw what the tree’s nodes & points look like.:
>>> quads.visualize(tree)
The tree we’ve built in this tutorial isn’t exceptionally interesting, but large tree can be quite complex & kinda beautiful:
Where to Go From Here¶
This guide has covered the bulk of the typical interactions with quads
.
However, if you have slightly different needs, all the objects within it are able to be extended/overridden to solve other problems.
For instance, quads.QuadTree
is normally a point quadtree, but
by setting the capacity=...
parameter to 1
, you can now represent
region quadtrees.
Or supplying a different QuadNode
with extra methods. Or extending the
Point
class to handle more/different data.
Enjoy!