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 is 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/cpp 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 a ﬁle called “visualPoints.txt”. To get started, you may use the class Point.java/Point.h (starter code) as the data structure for a point and the client program PointPlotter.java (not graded, simply for visualization) which reads in a list of points from standard input, the output ﬁle “visualPoints.txt” and plots them along with the line segments. You will need to supply additional methods in Point.java/Point.h which will be used in Brute.java/cpp, including checking whether three or four 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 set of 4 or more collinear points.
Think of p as the origin. For each other point q, determine the angle it makes with p. Sort the points according to the angle they makes with p. Check if any 3 (or more) adjacent points in the sorted order have equal angles with p. If so, these points, together with p, are collinear. Applying this method for each of the _N _points in turn yields an efﬁcient algorithm to the problem. 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.