Programming Assignment 3: Pattern Recognition Assignment

Programming Assignment 3: 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 such as statistical data analysis.

The problem. Given a set of N distinct points in the plane, draw every (maximal) line segment that connects a subset of M 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 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?
   public double slopeTo(Point that)                  // the slope between this point and 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 compareTo() method should compare points by their y-coordinates, breaking ties by their x-coordinates. Formally, 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 slopeTo() method should return the slope between the invoking point (x₀, y₀) and the argument point (x₁, y₁), which is given by the formula (y₁ − y₀) / (x₁ − x₀). Treat the slope of a horizontal line segment as positive zero; 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.
The SLOPE_ORDER comparator should compare points by the slopes they make with the invoking point (x₀, y₀). Formally, 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 horizontal, vertical, and degenerate line segments as in the slopeTo() method.

Brute force. Write a program BruteCollinearPoints.java that examines 4 points at a time and checks whether they all lie on the same line segment. Your program should implement the following API:


public class BruteCollinearPoints {
    public BruteCollinearPoints(Point [] points)    //makes a defensive copy of the array of points
    public int numberOfPoints()                     //returns the number of total points in the array
    public int numberOfSegments()                   //returns the number of segments of length 4
    public Iterable<PointSequence> segments()       //returns an iterable of segments of length 4
    public static void main(String[] args)          //draws all 4 point segments in file
}

To check whether the 4 points p, q, r, and s are collinear, check whether the slopes between p and q, between p and r, and between p and s are all equal.

The PointSequence class is a simple container class that is primarily intended to simplify syntax. Given Point[] pointArray, you can create a PointSequence with new PointSequence(pointArray). The order of the elements in the array matters. You should give the points in either strictly ascending order or strictly descending order. This means that for a given segment, there are exactly two allowable orders. The PointSequence class also contains public methods that may be helpful for debugging.

The order of growth of the running time of your methods should be no worse than N⁴ in the worst case and your methods should use space proportional to the number of segments of length 4.

Suggested Programming Challenge. Before proceeding to the final part of this assignment, we recommend that you complete this suggested programming challenge in which you will identify runs of consecutive identical values in an array. Though the identifyRuns() method will not be usable by FastCollinearPoints, the optimal structure for solving both problems is extremely similar.

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 M 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 M-1 (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 FastCollinearPoints.java that implements this algorithm for an arbitrary number of points M > 2. The order of growth of the running time of your methods should be N² log N in the worst case and it should use space proportional to the number of collinear segments of length minLength.


public class FastCollinearPoints {
    public FastCollinearPoints(Point [] points)        //makes a defensive copy of the array of points
    public int numberOfPoints()                        //returns the number of total points in the array
    public int numberOfSegments(int minLength)         //returns the number of segments of length minLength or more
    public Iterable<PointSequence> segments(int minLength) 
    public static void main(String[] args)             //draws all maximal length segments of length 4 or more
}

The segments(int minLength) method returns an iterable of all maximal length segments of length minLength or more. A maximal length segment is any segment that is not a subsegment of another segment, e.g. if minLength is 5, and p→q→r→s→t, then p→q→s→t and q→r→s→t are subsegments and therefore are not maximal length segments.

Input format. Your main method should read the points from an input file (with filename given as a command line argument) in the following format: An integer N, followed by N pairs of integers (x, y), each between 0 and 32,767. Below are two examples.

% 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. Your segments() methods should return an Iterable <PointSequence>. The type of Iterable is unimportant, and we also don't care about the order in which the PointSequences appear. However, the order of the points within a PointSequence does matter. They should appear in either ascending or descending order (with respect to the natural order defined by you in Point.java).

In main(), draw points and line sequences using the respective draw() methods. Your programs should call the appropriate draw() method once for each point and once for each line segment discovered. Before drawing, use StdDraw.setXscale(0, 32768) and StdDraw.setYscale(0, 32768) to rescale the coordinate system.

For full credit, do not include permutations of points on a line segment (e.g., if you output the PointSequence p→q→r→s, do not also output either s→r→q→p or p→r→q→s). Also, for full credit in FastCollinearPoints.java, do not include subsegments of a line segment containing minLength or more points (e.g., if you output p→q→r→s→t, do not also output either p→q→s→t or q→r→s→t); you may include such subsegments in BruteCollinearPoints.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 only BruteCollinearPoints.java, FastCollinearPoints.java, and Point.java. We will supply stdlib.jar and algs4.jar. Your may not call any library functions other than those in PointSequence.java, java.lang, java.util, stdlib.jar, and algs4.jar. Finally, submit a readme.txt file and answer the questions.