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 feature points in the plane, determine every line segment that contains 4 or more of the points, and plot all such line segments.
Brute force. Write a program Brute.java that examines 4 points at a time and checks if they all lie on the same line segment, plotting any such line segments in turtle graphics. To get started, you may use the data type Point.java and the client program PointPlotter.java which reads in a list of points from standard input and plots them using Turtle graphics. You will need to supply additional interface functions to Point.java in order to support the brute force client, e.g., checking whether three points lie on the same line.
A sorting 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 group of 4 or more collinear points. Applying this method for each of the N points in turn yields an efficient algorithm to the problem.
Write a program Fast.java that implements this algorithm. The algorithm solves the problem because points that make the same angle with p are collinear, and sorting brings such points together. The algorithm is fast because the bottleneck operation is sorting.
Input format. The data file consists of an integer N, followed by N pairs of integers (x, y) between 0 and 32,768.
5 16384 19200 16384 21120 16384 32000 16384 21761 10000 10000
Output format. Your program should use Turtle graphics to draw all of the points and the line segments your program discovers. Using the point data type supplied, the command p.draw() draws the point p and the command p.drawTo(q) draws the line segment from p to q. Note that the points are scaled down by a factor of 64.0 so that they fit snugly inside a 512-by-512 turtle graphics window.
Analysis. Estimate the running time of your two programs as a function of N. Provide analytical and empirical evidence to support your answer.
Deliverables. Submit the files: readme.txt, Brute.java, Fast.java, Point.java. Also submit any other file that your program needs, except for Turtle.java and StdIn.java, which we will supply.