問(wèn)題描述：http://coursera.cs.princeton.edu/algs4/assignments/collinear.html
我的代碼:https://github.com/hym105289/Pattern-Recognition/
1.基本介紹
給定n個(gè)不同的點(diǎn)，識(shí)別出至少4個(gè)點(diǎn)在一條直線上的點(diǎn)集。
p——q——r——s休讳，如果這四個(gè)點(diǎn)在一條直線上难衰，那么斜率pq=斜率qr=斜率rs挨厚，我們可以從n個(gè)點(diǎn)中隨意地找4個(gè)點(diǎn)尸诽，然后判斷斜率是否相等鬼雀，識(shí)別出這四個(gè)點(diǎn)是否在一條直線上硝皂。
難點(diǎn)：
①p-q-r-s常挚，也可以以是p-q-s-r等，如何避免重復(fù)搜索稽物，這是一個(gè)要考慮的問(wèn)題奄毡。
②java實(shí)現(xiàn)中的Comparable和Comparator接口
③p-q-r-s線段，只能記錄成p-s贝或，任何子線短p-r等都不應(yīng)該保存吼过，如何保證線段只記錄一次，是一個(gè)非常難的問(wèn)題咪奖。
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的一個(gè)接口盗忱，并且是用來(lái)對(duì)自定義的class比較大小的。
Comparable：定義在類(lèi)的內(nèi)部羊赵，實(shí)現(xiàn)的函數(shù)是comparTo趟佃，當(dāng)我們調(diào)用Array,sort(points)時(shí)，覆蓋compareTo的比較大小的方式進(jìn)行排序。在Point類(lèi)中闲昭，根據(jù)y坐標(biāo)進(jìn)行排序罐寨，當(dāng)y相同時(shí)再根據(jù)x坐標(biāo)進(jìn)行排序。
Comparator：一般是定義在類(lèi)的外部序矩，但是在這個(gè)例子中我們定義在類(lèi)的內(nèi)部鸯绿，使用private class SlopeOrder implements Comparator<Point> {}進(jìn)行定義，假設(shè)給定了內(nèi)部點(diǎn)p簸淀，外部點(diǎn)q和r楞慈，將q和r按照斜率pq和斜率pr進(jìn)行排序。覆蓋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) { // 如果名字一樣,比較年齡, 返回比較年齡結(jié)果
return age - another.age;
} else {
return i; // 名字不一樣, 返回比較名字的結(jié)果.
}
}
}
使用Collections.sort( persons)就可以對(duì)persons進(jìn)行排序囊蓝。
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) { // 如果名字一樣,比較年齡,返回比較年齡結(jié)果
return one.age - another.age;
} else {
return i; // 名字不一樣, 返回比較名字的結(jié)果.
}
}
}
使用 Collections.sort( persons , new PersonComparator()) 可以對(duì)其排序。
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();
}
}
這里要注意的地方是在隨機(jī)選取之前令蛉，要先進(jìn)行排序聚霜，這樣能夠解決重復(fù)搜索的問(wèn)題。比如一共有6個(gè)點(diǎn)：排序后的結(jié)果1,2,3,4,5,6珠叔；這樣就能避免1234組合出現(xiàn)后再出現(xiàn)2134,4123等序列蝎宇，這樣能夠保證取了四個(gè)相同點(diǎn)的線段只能出現(xiàn)一次。
暴力的解法中祷安，如果四個(gè)點(diǎn)在一條直線中就把start姥芥，end插入到鏈表中即可。
比如input6.txt中有如下內(nèi)容
6
19000 10000
18000 10000
32000 10000
21000 10000
1234 5678
14000 10000
根據(jù)Comparatble接口排序后：1234,14000,18000,19000,21000;已知14000汇鞭，18000凉唐，19000，21000霍骄，32000這5點(diǎn)共線台囱；當(dāng)?shù)谝粋€(gè)點(diǎn)是1234時(shí)沒(méi)有任何線段加入，當(dāng)?shù)谝粋€(gè)點(diǎn)是14000读整，可以產(chǎn)生14000, 18000, 19000, 21000簿训；14000,18000,19000,32000;14000, 18000, 21000, 32000; 14000,19000,21000,32000四個(gè)線段，當(dāng)?shù)谝粋€(gè)點(diǎn)為18000時(shí)可以產(chǎn)生18000,19000,21000,32000一個(gè)線段米间；不可能產(chǎn)生相同的四個(gè)點(diǎn)强品；
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();
}
}
基本思想：加入給定點(diǎn)p，將剩余的所有點(diǎn)屈糊，根據(jù)和p的斜率進(jìn)行排序的榛，如果至少有pqr三個(gè)點(diǎn)到p點(diǎn)的斜率都相等，那就說(shuō)明pqrs四點(diǎn)共線另玖。
但是這樣可能會(huì)出現(xiàn)一個(gè)問(wèn)題：p到qrs的斜率都相同困曙，pqrs四點(diǎn)共線，還會(huì)出現(xiàn)p到qsr的斜率也相同的情況谦去，要求我們同一個(gè)線段只記錄最長(zhǎng)的那一段慷丽，p-q-r-s只添加線段p-s，同一個(gè)線段我們只記錄min和max即可鳄哭，不管遍歷四個(gè)點(diǎn)的順序如何我們都只記錄min和max要糊；
Example：
當(dāng)前點(diǎn)p=14000，其余點(diǎn)按斜率排序：1234妆丘，18000锄俄，19000，21000勺拣，3200奶赠；斜率分別是-0.338，+0.0药有，+0.0毅戈，+0.0；這里沒(méi)有區(qū)分+0和-0是因?yàn)轭}目本身要求當(dāng)y相同時(shí)k=+0.0愤惰；基本思路是掃描一遍斜率苇经，更新min和max，記錄連續(xù)相同k的個(gè)數(shù)宦言，當(dāng)k>=2時(shí)并且當(dāng)前點(diǎn)=min時(shí)添加min&max扇单；添加<14000,32000>(不要忘記處理最后兩個(gè)數(shù)據(jù)相等的情況)
當(dāng)前點(diǎn)p=18000，其余點(diǎn)：1234,14000,19000,21000,32000奠旺；斜率分別是：-0.257蜘澜，+0.0，+0.0响疚，+0.0兼都；出現(xiàn)了三個(gè)相同的斜率躯畴，說(shuō)明四點(diǎn)共線后控，但是18000！=min=14000堤瘤，則說(shuō)明該線段已經(jīng)保存過(guò)了杏糙，所以不能添加慎王，這樣我們就能多點(diǎn)共線只保留min和max了；上述的數(shù)據(jù)集保存的線段就是<14000,32000>
