Java代写: CS251 Data Structures and Algorithms代写

这个Java作业要求在一堆二维点中寻找共线(co-linear)的点。一共提供了两种算法:Brute 和 Fast。


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 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 file called “visualPoints.txt”. To get started, you may use the class (starter code) as the data structure for a point and the client program (not graded, simply for visualization) which reads in a list of points from standard input, the output file “visualPoints.txt” and plots them along with the line segments. You will need to supply additional methods in which will be used in, 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 efficient 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.


kamisama wechat