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. Implement the following immutable
`Point` API:

public class Point implements Comparable<Point> { public final Comparator<Point> BY_SLOPE_ORDER; // compare points by slope 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 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 int compareTo(Point that) // is this point lexicographically smaller than that one? public String toString() // string representation }

- The constuctor,
`draw()`,`drawTo()`, and`toString()`methods are provided. Do not modify. - The
`areCollinear()`methods should take three or four points and return true if they are collinear, false otherwise. These methods should work even if two or more argument points are equal. - The
`compareTo()`method should compare points by their*y*-coordinates, breaking ties by their*x*-coordinates. - The
`BY_SLOPE_ORDER`comparator should compare points by the slopes they make with this point. If two points make the same slope, break ties by their natural order. Consider vertical line segments as having slope positive infinity. Consider the line segment between a point and itself as having slope negative infinity.

**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 slope it makes with`p`. - Sort the points according to the slopes
they makes with
`p`. - Check if any 3 (or more) adjacent points in the sorted order have equal
slopes with respect to
`p`. If so, these points, together with`p`, are collinear.

Write a program `Fast.java` that implements this algorithm.
Your program should use space proportional to *N*.

**Input format.**
Read the points from standard input.
The input consists of an integer *N*, followed by *N*
pairs of integers (*x*, *y*), each between 0 and 32,767.

%more input6.txt%more input8.txt6 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. Using the%java Brute < input8.txt4: (10000, 0) -> (7000, 3000) -> (3000, 7000) -> (0, 10000) 4: (3000, 4000) -> (6000, 7000) -> (14000, 15000) -> (20000, 21000) %java Brute < input6.txt4: (14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (21000, 10000) 4: (14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (32000, 10000) 4: (14000, 10000) -> (18000, 10000) -> (21000, 10000) -> (32000, 10000) 4: (14000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000) 4: (18000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000) java Fast226 < input8.txt 4: (10000, 0) -> (7000, 3000) -> (3000, 7000) -> (0, 10000) 4: (3000, 4000) -> (6000, 7000) -> (14000, 15000) -> (20000, 21000) %java Fast < input6.txt5: (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`.

**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`, and `Point.java`.
Finally, submit a
readme.txt file and answer the questions.

Copyright © 2005.