About Schedule Software

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.

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 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 #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 pressed
• handleMouseMove: provides the x,y location of the mouse as it moves
• handleKeyPress: provides the key that was pressed
• handleTimer: called each time the timer ticks
• refresh: erases the window and calls draw, passing draw a reference to the graphics window
• draw: 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 the move method is called
• xmax/ymax: the width and height of the window

This class also provides the following methods:

• move: adds deltaX to x and deltaY to y. If deltaX is a positive number, each call to move adds deltaX to x, causing the point to move deltaX pixels to the right (e.g., x gets bigger). If deltaX is negative adding deltaX to x causes the point to move deltaX 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, then deltaX = -deltaX causes the point to change directions, moving left if it was previously moving right on each call to move, or moving right if it was previously moving left on each call to move. 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 the PointQuadtree 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 add MovingPoint 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 the removeAll method of lists.
• To build a tree with all the points, create a new PointQuadTree instance holding just MovingPoint number 0 as the root, and then insert MovingPoints 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.

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:

• 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