PS-2

Starter code: PS-2.zip

Introduction

Goal: write a program that can detect collisions through quadtrees, which are useful as they quickly narrow down the collision checks to relevant regions making them ideal for applications like games, geographic information systems, and location-based services.

Context: 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.

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!

Task 1: Implement a point quadtree (30 pts)

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 the Point2D 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 is null.

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 c1 will always cover (x,y1) to (x2,y) as shown, and so forth. Each time we add a new point, we will add it to one of the four quadrants based on the new point's 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.

Task 1.1: Basics (10 pts)

Much of PointQuadtree is already provided for you. Familiarize yourself with it. Fill in size() and allPoints().

Task 1.2: Insertion (10 pts)

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

In PointQuadtree, fill in insert() following the outline above.

Task 1.3: Finding (10 pts)

This data structure 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!

Let's consider how to find all objects within a circle.

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

In PointQuadtree, fill in findInCircle() following the outline above. Note: the Geometry class provides helper functions pointInCircle() and circleIntersectsRectangle() for you.

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

Task 2: GUI (15 pts)

The class DotTreeGUI extends InteractiveGUI, which itself extends our ImageGUI from a prior lecture to add a timer (to drive animation for CollisionGUI in Task 3). The GUI has two modes: 'a' to add a point to the tree and 'q' to query the tree to find all points near the mouse press (and highlight them). It also allows you to grow or shrink the size of the detection circle by hitting the '+' or '-' keys.

Task 2.1: Add and find points (15 pts)

In DotTreeGUI, fill in handleMousePress(). If the mode is 'a', add a new point to the quadtree. If the mode is 'q', find all the points in the tree close to the mouse press (within mouseRadius). Once points are added, clicking the mouse while in 'q' mode should highlight all points near the mouse.

Testing

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). Expand/contract the mouse radius with +/- keys.

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. Run them by hitting the '0' or '1' keys while in the GUI (which call test0() and test1() respectively).

Write a test2() method that codifies some of your test cases. That is, create a tree and do 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.

Task 3: Collisions (25 pts)

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 circumferences 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.

Task 3.1: Find collisions (15 pts)

In CollisionGUI, fill in findColliders().

First, build a tree with all the points: create a new PointQuadTree instance holding just MovingPoint number 0 as the root, then insert MovingPoints 1...n-1 into it. To check collisions, findInCircle() around each point. Note that this will find the point itself, since it's in the tree. That's okay, just handle it carefully. Add all colliders to the colliders List.

Task 3.2: Draw (10 pts)

In CollisionGUI 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.

Fill in draw() accordingly.

Testing

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 in the write-up.

Extra credit

You may obtain extra credit for extending and enhancing the app. Only do this once you are completely finished with the specified version. In your write-up, explain what you did and how it works.

[10 pts] Extend the DotTreeGUI to show the nodes tested in trying to find the mouse press location.
[10 pts] Allow for MovingPoints with variable radii, correctly accounting for how they must be searched.
[10 pts] Let the user drag out a circle (or rectangle) and show the points in it.
[20 pts] Implement a point-region quadtree, which uses a uniform spatial subdivision and keeps points within these quadrants.

What to submit

Upload these files:

Completed versions of the three classes in a single zip file
Screenshots of your GUIs
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
15	DotTreeGUI mouse press invoking PointQuadtree to add, find
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 included within methods and for new methods
4	Consistent and informative names for variables, methods, parameters
3	Clean and consistent layout (blank lines, indentation, no line wraps, etc.)

Testing & discussion (10 points)

5	Testing DotTreeGUI
5	Testing CollisionGUI