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 quadtree enables faster look-up in two dimensions. The structure is like a binary tree: each node stores an element (in this case a Point object), and then has up to four children, each representing one of the four quadrants.

a quadtree

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:

quadrants

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:

(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).

point-circle.png

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.

Geometry

Helper functions are provided for testing point-in-circle and circle-intersects-rectangle.

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

MovingPoint

Extends the Java-provided Point class for CollisionGUI. Provides the following additional instance variables:

This class also provides the following methods:

DotTreeGUI

Extends InteractiveGUI.

CollisionGUI

Extends InteractiveGUI.

collisions.png

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.

  1. Implement the PointQuadtree methods. Insert is of course first, but size and even allPoints should come along soon after, to help test. Note that you can (and should) do some testing of these even before tackling findInCircle.
  2. Implement the DotTreeGUI methods, to enable graphical construction and viewing of your trees.
  3. 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 my testFind 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.
  4. Implement the CollisionGUI methods.
  5. 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:

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)

10PointQuadtree insert
5PointQuadtree size
5PointQuadtree allPoints
10PointQuadtree findInCircle
5DotTeeGUI mouse press invoking PointQuadtree to add, find
10DotTreeGUI draw tree
5CollisionGUI find colliders: build the tree
10CollisionGUI find colliders: find all of them
10CollisionGUI draw to show colliders

Structure (10 points)

4Good decomposition of and within methods
3Proper used of instance and local variables
3Proper use of parameters

Style (10 points)

3Comments for new methods (purpose, parameters, what is returned)
4Good names for methods, variables, parameters
3Layout (blank lines, indentation, no line wraps, etc.)

Testing (10 points)

5Testing PointQuadtreeGUI
5Testing CollisionGUI