问题描述：http://coursera.cs.princeton.edu/algs4/assignments/collinear.html
我的代码:https://github.com/hym105289/Pattern-Recognition/
1.基本介绍
给定n个不同的点，识别出至少4个点在一条直线上的点集。
p——q——r——s，如果这四个点在一条直线上，那么斜率pq=斜率qr=斜率rs，我们可以从n个点中随意地找4个点，然后判断斜率是否相等，识别出这四个点是否在一条直线上。
难点：
①p-q-r-s，也可以以是p-q-s-r等，如何避免重复搜索，这是一个要考虑的问题。
②java实现中的Comparable和Comparator接口
③p-q-r-s线段，只能记录成p-s，任何子线短p-r等都不应该保存，如何保证线段只记录一次，是一个非常难的问题。
Point.java
import java.util.Arrays;
import java.util.Comparator;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;
public class Point implements Comparable<Point> {
private final int x;
private final int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public void draw() {
StdDraw.point(x, y);
}
public void drawTo(Point that) {
StdDraw.line(this.x, this.y, that.x, that.y);
}
/**
* Returns the slope between this point and the specified point. Formally,
* if the two points are (x0, y0) and (x1, y1), then the slope is (y1 - y0)
* / (x1 - x0). For completeness, the slope is defined to be +0.0 if the
* line segment connecting the two points is horizontal;
* Double.POSITIVE_INFINITY if the line segment is vertical; and
* Double.NEGATIVE_INFINITY if (x0, y0) and (x1, y1) are equal.
*
* @param that
* the other point
* @return the slope between this point and the specified point
*/
public double slopeTo(Point that) {
if (this.x == that.x && this.y == that.y) {
return Double.NEGATIVE_INFINITY;
} else if (this.x == that.x) {
return Double.POSITIVE_INFINITY;
} else if (this.y == that.y) {
return +0.0;
} else {
return (that.y - this.y) / (double) (that.x - this.x);
}
}
/**
* Compares two points by y-coordinate, breaking ties by x-coordinate.
* Formally, the invoking point (x0, y0) is less than the argument point
* (x1, y1) if and only if either y0 < y1 or if y0 = y1 and x0 < x1.
*
* @param that
* the other point
* @return the value <tt>0</tt> if this point is equal to the argument point
* (x0 = x1 and y0 = y1); a negative integer if this point is less
* than the argument point; and a positive integer if this point is
* greater than the argument point
*/
public int compareTo(Point that) {
if (this.x == that.x && this.y == that.y) {
return 0;
} else if (this.y < that.y || (this.y == that.y && this.x < that.x)) {
return -1;
} else {
return 1;
}
}
public Comparator<Point> slopeOrder() {
return new SlopeOrder();
}
private class SlopeOrder implements Comparator<Point> {
public int compare(Point p1, Point p2) {
double slope1 = slopeTo(p1);
double slope2 = slopeTo(p2);
if (slope1 < slope2) {
return -1;
} else if (slope1 > slope2) {
return 1;
} else {
return 0;
}
}
}
public String toString() {
return "(" + x + "," + y + ")";
}
public static void main(String[] args) {
String filename = args[0];
In in = new In(filename);
int N = in.readInt();
Point[] points = new Point[N];
for (int i = 0; i < N; i++) {
int x = in.readInt();
int y = in.readInt();
Point p = new Point(x, y);
points[i] = p;
}
Arrays.sort(points, points[0].slopeOrder());
for (Point p : points)
StdOut.println(p);
}
}
Comparable和Comparatoe都是java的一个接口，并且是用来对自定义的class比较大小的。
Comparable：定义在类的内部，实现的函数是comparTo，当我们调用Array,sort(points)时，覆盖compareTo的比较大小的方式进行排序。在Point类中，根据y坐标进行排序，当y相同时再根据x坐标进行排序。
Comparator：一般是定义在类的外部，但是在这个例子中我们定义在类的内部，使用private class SlopeOrder implements Comparator<Point> {}进行定义，假设给定了内部点p，外部点q和r，将q和r按照斜率pq和斜率pr进行排序。覆盖compare方法。
Comparable:
public class Person implements Comparable<Person> {
String name;
int age
public int compareTo(Person another) {
int i = 0;
i = name.compareTo(another.name); // 使用字符串的比较
if(i == 0) { // 如果名字一样,比较年龄, 返回比较年龄结果
return age - another.age;
} else {
return i; // 名字不一样, 返回比较名字的结果.
}
}
}
使用Collections.sort( persons)就可以对persons进行排序。
Comparator:
class PersonComparator implements Comparator <Person>{
public int compare(Person one, Person another) {
int i = 0;
i = one.name.compareTo(another.name); // 使用字符串的比较
if(i == 0) { // 如果名字一样,比较年龄,返回比较年龄结果
return one.age - another.age;
} else {
return i; // 名字不一样, 返回比较名字的结果.
}
}
}
使用 Collections.sort( persons , new PersonComparator()) 可以对其排序。
BruteCollinearPoints.java
import java.util.Arrays;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
public class BruteCollinearPoints {
private int lineNumber;
private ListNode last;
private class ListNode {
private LineSegment val;
private ListNode pre;
}
public BruteCollinearPoints(Point[] points) {
if (points == null) {
throw new IllegalArgumentException();
}
int num = points.length;
Point[] copy = new Point[num];
if (num < 4)
return;
for (int i = 0; i < num; i++) {
if (points[i] == null) {
throw new IllegalArgumentException();
}
for (int j = i + 1; j < num; j++) {
if (points[i].compareTo(points[j]) == 0) {
throw new IllegalArgumentException();
}
}
copy[i] = points[i];
}
Arrays.sort(copy, 0, num);// be careful
for (int i = 0; i < num; i++) {
for (int j = i + 1; j < num; j++) {
for (int k = j + 1; k < num; k++) {
for (int l = k + 1; l < num; l++) {
double slope1 = copy[i].slopeTo(copy[j]);
double slope2 = copy[j].slopeTo(copy[k]);
double slope3 = copy[k].slopeTo(copy[l]);
if (Double.compare(slope1, slope2) == 0 && Double.compare(slope2, slope3) == 0) {
addLine(copy[i], copy[l]);
lineNumber++;
}
}
}
}
}
}
private void addLine(Point a, Point b) {
if (last != null) {
ListNode node = new ListNode();
node.pre = last;
node.val = new LineSegment(a, b);
last = node;
} else {
last = new ListNode();
last.val = new LineSegment(a, b);
}
}
public int numberOfSegments() {
return lineNumber;
}
public LineSegment[] segments() {
LineSegment[] lines = new LineSegment[lineNumber];
ListNode pNode = last;
for (int i = 0; i < lineNumber; i++) {
lines[i] = pNode.val;
pNode = pNode.pre;
}
return lines;
}
public static void main(String[] args) {
StdDraw.enableDoubleBuffering();
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
StdDraw.setPenRadius(0.01);
String filename = args[0];
In in = new In(filename);
int n = in.readInt();
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
int x = in.readInt();
int y = in.readInt();
Point p = new Point(x, y);
points[i] = p;
p.draw();
}
StdDraw.show();
BruteCollinearPoints collinear = new BruteCollinearPoints(points);
System.out.println(collinear.lineNumber);
for (LineSegment segment : collinear.segments()) {
System.out.println(segment);
segment.draw();
}
StdDraw.show();
}
}
这里要注意的地方是在随机选取之前，要先进行排序，这样能够解决重复搜索的问题。比如一共有6个点：排序后的结果1,2,3,4,5,6；这样就能避免1234组合出现后再出现2134,4123等序列，这样能够保证取了四个相同点的线段只能出现一次。
暴力的解法中，如果四个点在一条直线中就把start，end插入到链表中即可。
比如input6.txt中有如下内容
6
19000 10000
18000 10000
32000 10000
21000 10000
1234 5678
14000 10000
根据Comparatble接口排序后：1234,14000,18000,19000,21000;已知14000，18000，19000，21000，32000这5点共线；当第一个点是1234时没有任何线段加入，当第一个点是14000，可以产生14000, 18000, 19000, 21000；14000,18000,19000,32000;14000, 18000, 21000, 32000; 14000,19000,21000,32000四个线段，当第一个点为18000时可以产生18000,19000,21000,32000一个线段；不可能产生相同的四个点；
FastCollinearPoints.java
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;
import java.util.Arrays;
public class FastCollinearPoints {
private int lineNumber;
private ListNode last;
private class ListNode {
private LineSegment val;
private ListNode pre;
}
public FastCollinearPoints(Point[] points) // finds all line segments
// containing 4 or more points
{
if (points == null) {
throw new IllegalArgumentException();
}
int num = points.length;
Point[] copy = new Point[num];
for (int i = 0; i < num; i++) {
if (points[i] == null) {
throw new IllegalArgumentException();
}
for (int j = i + 1; j < num; j++) {
if (points[i].compareTo(points[j]) == 0) {
throw new IllegalArgumentException();
}
}
copy[i] = points[i];
}
Arrays.sort(copy, 0, num);// be careful
if (num < 4) {
return;
}
for (int i = 0; i < num - 1; i++) {
Point origPoint = copy[i];
int otherPointsN = 0;
Point[] otherPoints = new Point[num - 1];
for (int j = 0; j < num; j++) {
if (i != j)
otherPoints[otherPointsN++] = copy[j];
}
Arrays.sort(otherPoints, copy[i].slopeOrder());
int count = 0;
Point min = null;
Point max = null;
for (int j = 0; j < otherPointsN - 1; j++) {
if (Double.compare(origPoint.slopeTo(otherPoints[j]), origPoint.slopeTo(otherPoints[j + 1])) == 0) {
count++;
if (min == null && max == null) {
if (origPoint.compareTo(otherPoints[j]) > 0) {
max = origPoint;
min = otherPoints[j];
} else {
max = otherPoints[j];
min = origPoint;
}
}
if (otherPoints[j + 1].compareTo(min) < 0) {
min = otherPoints[j + 1];
}
if (otherPoints[j + 1].compareTo(max) > 0) {
max = otherPoints[j + 1];
}
if (j == otherPointsN - 2 && count >= 2 && origPoint.compareTo(min) == 0) {
addLine(min, max);
lineNumber++;
}
} else {
if (count >= 2 && origPoint.compareTo(min) == 0) {
addLine(min, max);
lineNumber++;
}
count = 0;
max = null;
min = null;
}
}
}
}
private void addLine(Point a, Point b) {
if (last != null) {
ListNode node = new ListNode();
node.pre = last;
node.val = new LineSegment(a, b);
last = node;
} else {
last = new ListNode();
last.val = new LineSegment(a, b);
}
}
public int numberOfSegments() // the Nber of line segments
{
return lineNumber;
}
public LineSegment[] segments() // the line segments
{
LineSegment[] lines = new LineSegment[lineNumber];
ListNode current = last;
for (int i = 0; i < lineNumber; i++) {
lines[i] = current.val;
current = current.pre;
}
return lines;
}
public static void main(String[] args) {
// read the n points from a file
In in = new In(args[0]);
int n = in.readInt();
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
int x = in.readInt();
int y = in.readInt();
points[i] = new Point(x, y);
}
// draw the points
StdDraw.enableDoubleBuffering();
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
StdDraw.setPenRadius(0.01);
for (Point p : points) {
p.draw();
}
StdDraw.show();
// print and draw the line segments
FastCollinearPoints collinear = new FastCollinearPoints(points);
System.out.println(collinear.lineNumber);
for (LineSegment segment : collinear.segments()) {
StdOut.println(segment);
segment.draw();
}
StdDraw.show();
}
}
基本思想：加入给定点p，将剩余的所有点，根据和p的斜率进行排序，如果至少有pqr三个点到p点的斜率都相等，那就说明pqrs四点共线。
但是这样可能会出现一个问题：p到qrs的斜率都相同，pqrs四点共线，还会出现p到qsr的斜率也相同的情况，要求我们同一个线段只记录最长的那一段，p-q-r-s只添加线段p-s，同一个线段我们只记录min和max即可，不管遍历四个点的顺序如何我们都只记录min和max；
Example：
当前点p=14000，其余点按斜率排序：1234，18000，19000，21000，3200；斜率分别是-0.338，+0.0，+0.0，+0.0；这里没有区分+0和-0是因为题目本身要求当y相同时k=+0.0；基本思路是扫描一遍斜率，更新min和max，记录连续相同k的个数，当k>=2时并且当前点=min时添加min&max；添加<14000,32000>(不要忘记处理最后两个数据相等的情况)
当前点p=18000，其余点：1234,14000,19000,21000,32000；斜率分别是：-0.257，+0.0，+0.0，+0.0；出现了三个相同的斜率，说明四点共线，但是18000！=min=14000，则说明该线段已经保存过了，所以不能添加，这样我们就能多点共线只保留min和max了；上述的数据集保存的线段就是<14000,32000>
