COS 226 Pattern Recognition Assignment

COS 226 Programming Assignment

Pattern Recognition

Write a program to recognize line patterns in a given set of points.

Computer vision involves analyzing patterns in visual images and reconstructing the real-world objects that produced them. The process in often broken up into two phases: feature detection and pattern recognition. Feature detection involves selecting important features of the image; pattern recognition involves discovering patterns in the features. We will investigate a particularly clean pattern recognition problem involving points and line segments. This kind of pattern recognition arises in many other applications, for example statistical data analysis.

The problem. Given a set of N distinct points in the plane, draw every line segment that connects a subset of 4 or more of the points.

Point data type. Create an immutable data type Point that represents a point in the plane by implementing the following API:

public class Point implements Comparable<Point> {
   public final Comparator<Point> SLOPE_ORDER;                             // compare points by slope to this point

   public static boolean areCollinear(Point p, Point q, Point r)           // are the three points p, q, and r collinear?
   public static boolean areCollinear(Point p, Point q, Point r, Point s)  // are the four points p, q, r, and s collinear?

   public Point(int x, int y)                                              // construct the point (x, y)
   public void draw()                                                      // draw this point
   public void drawTo(Point that)                                          // draw the line segment from this point to that point
   public String toString()                                                // string representation

   public int compareTo(Point that)                                        // is this point lexicographically smaller than that point?
}

To get started, use the data type Point.java, which implements the constructor and the draw(), drawTo(), and toString() methods. Your job is to add the following components.

The areCollinear() methods should take three or four points and return true if they are collinear, false otherwise. These methods should work even if two or more argument points are equal.
The compareTo() method should compare points by their y-coordinates, breaking ties by their x-coordinates. The invoking point (x₀, y₀) is less than the argument point (x₁, y₁) if and only if either y₀ < y₁ or if y₀ = y₁ and x₀ < x₁.
The SLOPE_ORDER comparator should compare points by the slopes they make with the invoking point (x₀, y₀). The point (x₁, y₁) is less than the point (x₂, y₂) if and only if the slope (y₁ − y₀) / (x₁ − x₀) is less than the slope (y₂ − y₀) / (x₂ − x₀). Treat the slope of a vertical line segment as positive infinity; treat the slope of a degenerate line segment (between a point and itself) as negative infinity.

Brute force. Write a program Brute.java that examines 4 points at a time and checks whether they all lie on the same line segment, printing out any such line segments to standard output and plotting them to standard drawing.

A faster, sorting-based solution. Remarkably, it is possible to solve the problem much faster than the brute-force solution described above. Given a point p, the following method determines whether p participates in a set of 4 or more collinear points.

Think of p as the origin.
For each other point q, determine the slope it makes with p.
Sort the points according to the slopes they makes with p.
Check if any 3 (or more) adjacent points in the sorted order have equal slopes with respect to p. If so, these points, together with p, are collinear.

Applying this method for each of the N points in turn yields an efficient algorithm to the problem. The algorithm solves the problem because points that have equal slopes with respect to p are collinear, and sorting brings such points together. The algorithm is fast because the bottleneck operation is sorting.

Write a program Fast.java that efficiently implements this algorithm. Your program should use space proportional to N.

Input format. Read the points from standard input. The input consists of an integer N, followed by N pairs of integers (x, y), each between 0 and 32,767.

% more input6.txt       % more input8.txt
6                       8
19000  10000             10000      0
18000  10000                 0  10000
32000  10000              3000   7000
21000  10000              7000   3000
 1234   5678             20000  21000
14000  10000              3000   4000
                         14000  15000
                          6000   7000

Output format. Print to standard output the line segments that your program discovers, one per line. Print each line segment as the ordered sequence of its constituent points, separated by " -> ".

% java Brute < input6.txt
(14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (21000, 10000)
(14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (32000, 10000)
(14000, 10000) -> (18000, 10000) -> (21000, 10000) -> (32000, 10000)
(14000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000)
(18000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000)

% java Brute < input8.txt
(10000, 0) -> (7000, 3000) -> (3000, 7000) -> (0, 10000) 
(3000, 4000) -> (6000, 7000) -> (14000, 15000) -> (20000, 21000) 

% java Fast < input6.txt
(14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000) 

% java Fast < input8.txt
(10000, 0) -> (7000, 3000) -> (3000, 7000) -> (0, 10000)
(3000, 4000) -> (6000, 7000) -> (14000, 15000) -> (20000, 21000)

Also, plot the points to standard drawing using draw() and the line segments using drawTo(). Your programs should call draw() once for each point and drawTo() once for each line segment discovered. Before drawing, use StdDraw.setXscale(0, 32768) and StdDraw.setYscale(0, 32768) to rescale the coordinate system. Do not change the pen color with setPenColor() or the pen size with setPenRadius().

For full credit, do not print permutations of points on a line segment (e.g., if you output p→q→r→s, do not output s→r→q→p or p→r→q→s). Also, for full credit in Fast.java, do not print or plot subsegments of a line segment containing 5 or more points (e.g., if you output p→q→r→s→t, do not output p→q→s→t or q→r→s→t); you may print out such subsegments in Brute.java.

Analysis. Estimate (using tilde notation) the running time (in seconds) of your two programs as a function of the number of points N. Provide empirical and mathematical evidence to justify your two hypotheses.

Deliverables. Submit the files: Brute.java, Fast.java, and Point.java. Finally, submit a readme.txt file and answer the questions.