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 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 standard draw. 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, including checking whether three or four points lie on the same line. Be sure to implement at least the following API:
You will also need to add a user-defined Comparator to the Point data type for the second part of the assignment.public class 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 static boolean areCollinear(Point p, Point q, Point r) // are the three points collinear? public static boolean areCollinear(Point p, Point q, Point r, Point s) // are the four points collinear? public String toString() // string representation }
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 set 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. Your program should use space proportional to N.
Input format. The data file 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 in the format below (number of collinear points in the line segment, followed by the points in the order in which they appear on the line segment).
Also, plot the points and the line segments, using standard draw. (Do not change the pen color with setPenColor() or the pen size with setPenRadius().) Using the Point data type supplied, p.draw() draws the point p and p.drawTo(q) draws the line segment from p to q. Before drawing, use setXscale(0, 32768) and setYscale(0, 32768) to rescale the coordinate system.% java Brute < input8.txt 4: (10000, 0) -> (7000, 3000) -> (3000, 7000) -> (0, 10000) 4: (3000, 4000) -> (6000, 7000) -> (14000, 15000) -> (20000, 21000) % java Fast < input6.txt 5: (14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000)
For full credit, do not print permutations of points on a line segment (e.g., if you output p→q→r→s, do not also 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 also output p→q→s→t or q→r→s→t); you may print out subsegments in Brute.java.
You should have exactly one line of output and one call to drawTo() for each line segment discovered.
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, Point.java. Also submit any other auxiliary files (if any) that your program needs (excluding our standard libraries). Finally, submit a readme.txt file and answer the questions.