PS-2
Introduction
We've seen previously that Java provides a Point
class that has x and y instance variables, as well as getters and setters for them. Suppose we display a large number of Point
objects on a graphics window. Because each x,y location is a single pixel, to make Point
objects easier to see, let's draw a circle around each Point
with a radius of 5 pixels as shown below. How can we determine if the mouse was pressed on one of the points? How can we detect when two of them bump into each other (considering their 5 pixel radius)? An inefficient approach to determining which was clicked on — test each one. And we can imagine an inefficient approach to detecting collisions — look at all pairs. But we can do better, and would need to do better in some applications requiring speed. Especially if there were a large number of points to consider.
Just as a binary search enables faster look-up than linear search in one dimension (based on some notion of less than or greater than), a Point
object), and then has up to four children, each representing one of the four quadrants.

Here A is the root of the point quadtree, and it has children D (upper right), E (upper left), B (lower left), and K (lower right). D has three children G (upper right), F (upper left), and H (lower right). B has only one child C (lower right). K has one child L (upper left). Finally, H has one child I (upper right), which itself has one child J (upper left).
Here is the data above, shown as a tree
A[x=300,y=400]
├── D[x=450,y=200]
│ ├── G[x=500,y=125]
│ ├── F[x=350,y=175]
│ └── H[x=475,y=250]
│ └── I[x=525,y=225]
│ └── J[x=490,y=215]
├── E[x=200,y=250]
├── B[x=150,y=450]
│ └── C[x=250,y=550]
└── K[x=700,y=550]
└── L[x=310,y=410]
Note: there are several variations on the idea of a quadtree; we're following here an extension of the classic approach described by Finkel and Bentley in "Quad Trees: A Data Structure for Retrieval on Composite Keys", Acta Informatica 4, 1—9, 1974. See Fig. 1 for another example, also drawn as a tree. The paper is a good read, though I've translated some of the ALGOL-like description to pseudocode here, and used recursion rather than iteration. Be careful searching the web for further descriptions, as you might end up implementing an extra credit quadtree instead of the assigned one!
Data Structure
We want our quadtree to be generic to what "points" it holds, as long as they provide the ability to get x and y coordinates. Java provides an interface called Point2D
specifying getX
and getY
methods. Java's Point
class implements these methods. We will use it as a starting point for nodes in our quadtree.
The basic data structure that we'll use for each node in the PointQuadtree
includes:
- a point, of generic type
E
, as long as it implements thePoint2D
interface (so we can get x and y coordinates) - the two corners, upper-left (x1,y1) and lower-right (x2,y2), representing a rectangle portion of the graphics window that the node covers. (It isn't really necessary to store these, but it makes our life easier.)
- Four
PointQuadtree
children, one for each quadrant, numbered as in the figure below, named c1, c2, c3, and c4. Any quadrant may be empty, in which case the child isnull
.

The root of the tree covers the entire graphics window (x1,y1) to (x2,y2) with a Point
located at (x,y). The Point
divides the window into four quadrants. Each quadrant, however, may not be the same size as shown above. The upper-right quadrant #1 covers (x,y1) to (x2,y), and so forth. Make sure you agree with this. Each time we add a new point, we will add it to one of the four quadrants based on the new points x,y location. The new point will then divide that quadrant (not the whole graphics window) into four subquadrants. Note: I'm sticking with the graphics convention of the origin at the upper-left, and smaller y values higher up in the image. This makes computing these things with < and > feel a little strange compared to our math intuition, but such is Java's graphics.
Insertion
Inserting a point in a quadtree works much like it does with a binary tree (except with four children instead of two): at a given node, see which quadrant the new point lies in, and recursively insert in the appropriate child (quadrant). When there is no child for that quadrant, create a new leaf containing just the point, and store that leaf as that child.
To insert point p, which is at (x',y'), start at the root
If (x',y') is in quadrant 1
If child 1 exists, then recursively insert p in child 1
Else set child 1 to a new tree holding just p and with all children set to null
And similarly with the other quadrants / children
Finding
Quadtrees are particularly useful if we want to find all points that lie within a circle. For example, the mouse might not be pressed exactly on a point, but if it's close enough, we'll consider it a hit. Thus we search in a circle around the mouse location. Similarly, to detect collisions, we search in a circle around a given Point
to see if another Point
is too close. So the recursive call for find
considers all children whose rectangles overlap the region of interest.
Let's consider how to find all objects within a circle. We'll assume that we have methods to see if a point is inside a circle, and to see if a circle intersects a quadrant's rectangle.
To find all points within the circle (cx,cy,cr), stored in a tree covering rectangle (x1,y1)-(x2,y2)
If the circle intersects a quadrant's rectangle
If the tree's point is in the circle, then the point is a "hit"
For each non-null child quadrant
Recurse with that child
Here are some example search circles in the above picture; make sure you're comfortable with what rectangles get checked and what tree points get checked:
- Searching in a circle near B. Start at the root, A, and see that the circle intersects its rectangle. In this case the circle around the point we are searching does intersect the rectangle, because A's rectangle is the entire window. Test the point to see if A is inside the circle around the point we are searching — not a hit, the search point is too far away. Recurse to A's children D, E, B, and K. The circle only intersects B's rectangle. Check B's point; it is a hit, the search point is close to B. Also recurse with B's child C to see if more than B is in the search circle. The circle intersects C's rectangle. Check C's point; not a hit.
- Searching in a circle near G. Start at the root, A, and see that the circle intersects A's rectangle. Test its point, not a hit. Recurse to A's children D, E, B, and K. The circle only intersects D's rectangle. Check D's point; not a hit. Also recurse with its children G, F, and H. The circle only intersects G's rectangle. Check G's point; it is a hit.
- Searching in a circle near A (big enough to also contain L). Start at A, circle intersects A's rectangle, point is a hit. Recurse to children D, E, B, and K. Circle intersects all of their rectangles but doesn't contain any of their points. Further recursion from these tests G, F, H, C, and L. Only L's rectangle intersects. And its point is also a hit.
(Note: these are the first three test cases in test1 of the provided DotTreeGUI.)
Applications
This data structure and search mechanism then lets us solve the problem of quickly finding points near the mouse press — search in a circle around it. If the circle does not intersect a quadrant, there is no need to check for hits on any points in that quadrant. In this way, we only check quadrants that could hold points within the circle, and don't bother to check the rest. If there are many points in the window, this saves a lot of checking!
If we move from stationary points to moving points for collision detection, we have to account for the point's radius. Points intersect when their sides touch each other, not their centers. While in general, a point quadtree is only supposed to contain points (with variations developed to allow regions that have some extent in space), we can handle it here with a little trick. Let's deal only with points of a common, fixed radius. Then we can simply expand the circle we're looking for by that same amount and look for a point (e.g., point1 has radius r, point2 and all other points also have radius r, so by looking for other points within 2r of point1 we will detect any other nearby point).

Now we can efficiently solve collision detection. Insert all the points into a tree. For each point, find all other points within a circle of radius twice that of one point.
Implementation Notes
Several files are provided for you in ps2.zip. The big idea behind this problem set is to implement two applications. The first is DotTreeGUI
which allows you to add points on the window by clicking the mouse, or you may run several tests where points are placed at pre-determined locations on the window. Once points are added, you can press 'q' to highlight any points near the mouse. As you move the mouse, the code will draw a circle around its position. Click to see if any points that are within the circle. Use the '+' or '-' keys to expand or contract the radius of circle around the mouse. If multiple points are within the circle when it is clicked, they should all be highlighted.
The second application is CollisionGUI
. In this code you can add moving points to the window by clicking the mouse (or add many at a time in random locations by pressing 'r'). This code starts a timer ticking every 100 milliseconds (by default, can be adjusted), and at each tick, all points on the window will move. The code should then detect any collisions between points. Collisions are handled in two ways: if 'c' was pressed, points that collide should be lighted in red, if 'd' was pressed, points that collide should be removed from the window.
Here are more details about the files provided.
PointQuadtree
Stores points in a tree that enables fast detection if a point is within a circle around the mouse for DotTreeGUI
or if points collide for CollisionGUI
.
- The code is quite analogous to a binary tree, so familiarize yourself well with that first. It is recursive, with data structure recursion — from a node to its children.
- In order to build up a list over the course of recursion, a helper function is useful. Refer back to the fringe of a binary tree.
Geometry
Helper functions are provided for testing point-in-circle and circle-intersects-rectangle.
- Note that the functions increment static variables, which hold their values over all calls, and thus allow us to count the number of calls. Methods allow other classes to reset and access the counts. This is used in the
DotTreeGUI
to compare the number of calls your code makes to the ideal number.
InteractiveGUI
Extends our ImageGUI
from a prior lecture, but adds a timer (to drive animation for CollisionGUI
) and the following call back methods that you can override
handleMousePress
: provides the x,y location of the mouse when pressedhandleMouseMove
: provides the x,y location of the mouse as it moveshandleKeyPress
: provides the key that was pressedhandleTimer
: called each time the timer ticksrefresh
: erases the window and callsdraw
, passingdraw
a reference to the graphics windowdraw
: override to draw your points on the graphics window.
MovingPoint
Extends the Java-provided Point
class for CollisionGUI
. Provides the following additional instance variables:
r
: gives the point a radius of 5 pixels (by default)deltaX/deltaY
: the amount to move the point along the x or y axis if themove
method is calledxmax/ymax
: the width and height of the window
move
: addsdeltaX
tox
anddeltaY
toy
. IfdeltaX
is a positive number, each call tomove
addsdeltaX
tox
, causing the point to movedeltaX
pixels to the right (e.g.,x
gets bigger). IfdeltaX
is negative addingdeltaX
tox
causes the point to movedeltaX
pixels left (e.g.,x
gets smaller).deltaY
works similarly in the y axis. If that movement would cause the point to go off screen, thendeltaX = -deltaX
causes the point to change directions, moving left if it was previously moving right on each call tomove
, or moving right if it was previously moving left on each call tomove
.deltaY = -deltaY
has a similiar effect in the vertical in case points attempt to move off the top or below the bottom of the graphics window.draw
: causes the point to draw itself on the window centered at location x,y with radius r.
DotTreeGUI
Extends InteractiveGUI
.
- The GUI has two modes: 'a' for add to the tree and 'q' for query the tree to find all points near the mouse press. It also allows you to grow/shrink the size of the circle around the mouse, in which you're detecting points.
- There are some test cases that create pre-specified trees and perform searches on them, seeing how many nodes your tree search returns, and how many geometry tests it does along the way.
- The
drawTree
method is outside thePointQuadtree
class, so we explicitly pass around a tree object (and recurse with its children).
CollisionGUI
Extends InteractiveGUI
.
- This class allows you create
MovingPoints
and looks for collisions between points as they move. You can addMovingPoint
objects at a location by clicking the mouse, or you can add several points at random positions by pressing key 'r'. - There are two collision-handling modes: either just color the colliding blobs differently (key 'c', picture below from sample solution) or destroy them upon collision (key 'd'). The functionality is based on the
findColliders
method, which sets the colliders instance variable. Destruction takes advantage of theremoveAll
method of lists. - To build a tree with all the points, create a new
PointQuadTree
instance holding justMovingPoint
number 0 as the root, and then insertMovingPoints 1...n-1
into it. - As described above, to check collisions, do a
find
around a point. Note that this will find the point itself, since it's in the tree. That's okay, just handle it carefully.

Exercises
For this problem set, you are allowed to work with one partner. Note that you do not have to work with a partner, and if you do, you will both be given the same grade; there is no penalty (or bonus). You should weigh whether you will get more out of this assignment working alone or with someone else. If you choose to work with someone else, pick your partner carefully, and make sure it is someone you will be able to coordinate with, work well with, etc. Re-read the course policies.
- Implement the
PointQuadtree
methods.Insert
is of course first, butsize
and evenallPoints
should come along soon after, to help test. Note that you can (and should) do some testing of these even before tacklingfindInCircle
. - Implement the
DotTreeGUI
methods, to enable graphical construction and viewing of your trees. - Exercise your tree code by inserting points in different patterns (including the one illustrated above), checking that it displays correctly and that the mouse press picks up the points that it should (and doesn't pick up others). Note that you can expand/contract the mouse radius with +/- keys. Write a
test2
method that codifies some of your test cases. That is, it creates a tree and does some searches on the tree, comparing expected to actual results. You can use mytestFind
method if you like, or just do something simpler, e.g., comparing the points found to what you think should be found. In your write-up describe these test cases. - Implement the
CollisionGUI
methods. - Test your collision detection method by eye in an ad hoc fashion, as well as by devising careful test cases of things that should collide and things that should not. Take a screenshot of color-coded collisions (as above) and briefly describe your tests.
You may obtain extra credit for extending and enhancing the app. Only do this once you are completely finished with the specified version. Make a different file for the extra credit version, and document what you did and how it works. Some ideas:
- Extend the
DotTreeGUI
to show the nodes tested in trying to find the mouse press location. - Implement a find-in-rectangle method.
- Let the user drag out a circle (or rectangle) and show the points in it.
- Allow for
MovingPoints
with variable radii, correctly accounting for how they must be searched. - Implement a point-region quadtree, which uses a uniform spatial subdivision and keeps points within these quadrants.
Submission Instructions
Turn in your completed versions of the three classes. Turn in screenshots of your GUIs and a document with your discussion of tests.
Grading Rubric
Total of 100 points
Correctness (70 points)
10 | PointQuadtree insert |
---|---|
5 | PointQuadtree size |
5 | PointQuadtree allPoints |
10 | PointQuadtree findInCircle |
5 | DotTeeGUI mouse press invoking PointQuadtree to add, find |
10 | DotTreeGUI draw tree |
5 | CollisionGUI find colliders: build the tree |
10 | CollisionGUI find colliders: find all of them |
10 | CollisionGUI draw to show colliders |
Structure (10 points)
4 | Good decomposition of and within methods |
---|---|
3 | Proper used of instance and local variables |
3 | Proper use of parameters |
Style (10 points)
3 | Comments for new methods (purpose, parameters, what is returned) |
---|---|
4 | Good names for methods, variables, parameters |
3 | Layout (blank lines, indentation, no line wraps, etc.) |
Testing (10 points)
5 | Testing PointQuadtreeGUI |
---|---|
5 | Testing CollisionGUI |