COS 226 Programming Assignment Checklist: Pattern Recognition

Frequently Asked Questions

Can the same point appear more than once in the input file? You may assume the data has been preprocessed so that this does not happen.

How do I sort a subarray? Arrays.sort(a, lo, hi) sorts the subarray from a[lo] to a[hi-1] according to the natural order of a[]. Use a Comparator as the fourth argument to sort according to an alternate order.

How much extra space can I use? Limit yourself to a constant amount of extra space for Brute.java and a linear amount of extra space for Fast.java. By extra space, we mean beyond the space needed to store the array of points.

Where can I see examples of Comparable and Comparator? See the lecture slides. We assume this is new Java material for most of you, so don't hesitate to ask if you are unsure of how to use it.

My program works except on (some) vertical line segments. What could be going wrong? Are you dividing by zero? With integers, this produces a runtime exception. With floating point numbers, 1.0/0.0 is positive infinity, whereas -1.0/0.0 is negative infinity.

I'm having trouble getting a minimal representation of the line segments in Fast.java when there are 5 or more points on a line segment. Any advice? Not handling the 5-or-more case will lead to only a minor deduction, so don't kill yourself over it.

Can I sort by slope instead of angle? Yes, the atan function is monotonic, so sorting by y/x and atan(y/x) leads to the same result.

Does (Math.atan(y/x) == Math.atan((c*y) / (c*x))) if x, y, and c are integer-valued doubles between 0 and 32,767 with c not equal to zero? Yes. In IEEE floating point, integer are represented exactly (assuming no overflow). Thus c*x and c*y are represented exactly. The result of an IEEE floating point operation is the nearest representable value. Thus, y/x and (c*x)/(c*y) will yield exactly the same value. Therefore, the two expression will be exactly equal. It's sometimes ok to compare floating point numbers for exact equality (but be sure that you know what you're doing!)

How do I access the mathematical constant π? It's Math.PI, but don't use it or you'll likely encounter floating point roundoff issues.

Why are most of the line segments in the input files horizontal and vertical? We generate most of the data sets at random. Since they have integer coordinates in a small range, there are more opportunities to form horizontal and vertical lines.

Testing

Input.   The directory collinear contains some sample input files. Thanks to Jesse Levinson '05 for the remarkable input file rs1423.txt.

Reference solutions.   Some of the input files have associated .png files that contain the desired output. You can use these for checking your work.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

1. Getting started. Download the directory collinear to your system. It contains a number of sample input files and some helper programs. To download all the files at once:

   • Safari. Click the ftp link above to mount the ftp site, then drag-and-drop the desired folder from the ftp mount to the desired location.

   • Internet Explorer. Click the ftp link above, then right click the desired folder, select Copy To Folder, and choose the desired location.

   • Firefox. Install the extension DownThemAll! and use that to download all links from a given page.

   The files Point.java and PointPlotter.java comprise a program that reads in a list of points and plots the results. To plot the points, type the following at the command line

   % javac PointPlotter.java
   % java PointPlotter < input56.txt
   

   This opens a graphical window where you will see the points plotted.

2. Brute force. Before writing any code, think carefully about the point data type operations that you will need to support. A minimalistic approach might involve creating a function

   public static double angle(Point a, Point b)
   

   that returns the tangent of the angle that b makes with a. You can use the Java function Math.atan() for this: it returns an angle between -pi/2 and pi/2. Then, use this helper function to create a function

   public static boolean areCollinear(Point a, Point b, Point c)
   

   that returns true if a, b, and c are collinear and false otherwise. Also consider a 4-argument version.

   public static boolean areCollinear(Point a, Point b, Point c, Point d)
   

   Now, iterate through all 4-tuples and check if the 4 points are collinear.

   It's also worth thinking about how to avoid printing out different representations of the same line segment (when there are exactly 4 points on the line) since you will need this insight for Fast.java. One approach is to only print out the line segment if the 4 points are in ascending order (say relative to y-coordinate, breaking ties by x-coordinate).

3. Sorting solution. Before writing any code, think carefully about the point data type operations that you will need to support. The complicating issue is that the function needed to compare the angles of two points q1 and q2 depends on a third point p, which changes from sort to sort. One solution is to include a public and final (but not static) instance variable BY_POLAR_ORDER in Point of type Comparator<Point>. This Comparator has a compare() method so that compare(q1, q2) compares the angle that q1 and q2 make with the invoking object p.

Enrichment

This problem belongs to a group of problems that are known as 3SUM-hard. It is conjectured that such problems have no subquadratic algorithms. Thus, the sorting algorithm presented above is about the best we can hope for (unless the conjecture is wrong). Under a restricted decision tree model of computation, Erickson proved that the conjecture is true.