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, draw every line segment that connects 4 or more distinct points in the set.
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, printing out any such line segments to standard output and plotting them using StdDraw. 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. You will need to supply additional methods in 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.
Write a program Fast.java that implements this algorithm using Arrays.sort() and a user-defined Comparator for Point objects. 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 18666 16384 32000 16384 21761 10000 10000
Output format. Print to standard output the line segments that your program discovers. Ideally, you should print a minimal representation of each line segment: that is, only print the endpoints of the line segment and don't print subsegments. For example, your program should print out only the following for the 5-point example above.
We expect your program to print out a minimal representation for line segments consisting of 4 points; we will award a bonus if your program prints out a minimal representation for line segments consisting of 5 or more points.(16384, 32000) -> (16384, 18666)
Also, use StdDraw to plot all of the points and to draw all of the line segments that 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 it assumes the coordinate system is scaled so that coordinates between 0 and 32,768 fit in the graphics window.
Analysis. Estimate the running time of your two programs as a function of N. Provide empirical and mathematical evidence to justify your hypotheses.
Deliverables. Submit the files: readme.txt, Brute.java, Fast.java, Point.java. Also submit any other files, if any, that your program needs. Do not submit StdDraw.java or StdIn.java.