普林斯顿大学算法Week3:CollinearPoints共线模式识别(99分)--总结及代码

总结

(代码有详细注释)

  1. 本课讲了归并排序,作业应用是排序进行共线的模式识别,java1.8中的排序用的是tim排序,结合了归并排序与插入排序,属于稳定排序:排序之后相同元素的相对位置会不会改变
  2. Point.java中有个非常重要的方法,compareTo(),它定义:纵坐标越小则点越小,如果纵坐标相同,那么横坐标越小则点越小.(如果作业中要求横坐标也是按顺序排列,那么排序后的点集映射到二维坐标系中是非递减的折线, 这样找共线只用一层循环即可,可惜作业没加上对x的限制)
  3. 比较大小,一开始我用的是points[i-1] == point[i],尽管坐标相同但是points[i-1]不等于points[i]
    因为points[i-1]和points[i]表示引用,在堆中指向两个不同的地址,比较大小得用points[i-1].compareTo(points[i])
  4. 在FastCollinearPoints.java中,一定要注意什么时候对共线点数变量count进行判断,有两种情况,一个是,相邻元素与参考点的斜率不同;另一个是循环到最后一个元素.这两种情况在代码注释中有解释
  5. 唯一一处FAILED,扣了1分,没系统学过java,先跳过了

    1
    2
    3
    4
    5
    6
    7
    8
    Test 7: check for dependence on either compareTo() or compare()
    returning { -1, +1, 0 } instead of { negative integer,
    positive integer, zero }
    * filename = equidistant.txt
    - number of entries in student solution: 0
    - number of entries in reference solution: 4
    - 4 missing entries in student solution, including: '(30000, 0) -> (20000, 10000) -> (10000, 20000) -> (0, 30000)'
    ==> FAILED
  6. week3课件中,递归调用的图示:
    这是包含两个递归调用的递归 (图示只画了一半)
    Merge.jpg

代码

(如需提交,请删除中文注释)

一:Point.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.Comparator;
import edu.princeton.cs.algs4.StdDraw;
public class Point implements Comparable<Point> {
// x-coordinate of this point
private final int x;
// y-coordinate of this point
private final int y;
// constructs the point (x, y)
public Point(int x, int y) {
this.x = x;
this.y = y;
}
// draws this point
public void draw() {
StdDraw.point(x,y);
}
// draws the line segment from this point to that point
public void drawTo(Point that) {
StdDraw.line(this.x, this.y, that.x, that.y);
}
// string representation
public String toString() {
return "(" + x + ", " + y + ")";
}
// compare two points by y-coordinates, breaking ties by x-coordinates
public int compareTo(Point that) {
if(y<that.y || (y==that.y && x<that.x)) return -1;
else if(y==that.y && x==that.x) return 0;
else return +1;
}
// the slope between this point and that point
public double slopeTo(Point that) {
if(x==that.x && y==that.y) return Double.NEGATIVE_INFINITY;
if(x==that.x && y!=that.y) return Double.POSITIVE_INFINITY;
if(y==that.y) return +0.0;
return (double)(y-that.y)/(x-that.x);
}
// compare two points by slopes they make with this point
public Comparator<Point> slopeOrder(){
return new SlopeOrder();
}
//nested class
//sort rule
private class SlopeOrder implements Comparator<Point>{
public int compare(Point p,Point q) {
//p点斜率大
if(slopeTo(p)<slopeTo(q)) return -1;
//p点斜率小
else if(slopeTo(p)>slopeTo(q)) return 1;
//p,q斜率相等
else return 0;
}
}

public static void main(String[] args) {
Point p1 = new Point(0,0);
Point p2 = new Point(1,1);
Point p3 = new Point(2,2);
Point p4 = new Point(2,1);
Point p5 = new Point(4,1);
System.out.println("p1.compareTo(p1) is "+p1.compareTo(p2));
System.out.println("p2.compareTo(p1) is "+p2.compareTo(p1));
System.out.println("p1.compareTo(p1) is "+p1.compareTo(p1)+"\n");

System.out.println("p1.slopeTo(p2) is " +p1.slopeTo(p2));
System.out.println("p1.slopeTo(p4) is "+p1.slopeTo(p4));
System.out.println("p1.slopeTo(p1) is "+p1.slopeTo(p1));
System.out.println("p3.slopeTo(p4) is "+p3.slopeTo(p4));
System.out.println("p2.slopeTo(p5) is "+p2.slopeTo(p5));
}
}

二:BruteCollinearPoints.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
import java.util.ArrayList;
import java.util.Arrays;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Insertion;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdDraw;

public class BruteCollinearPoints {
//to store line segments
private ArrayList<LineSegment> LineSegmentList;
//to store the given points
private Point[] points;

//在构造函数中找出由4点构成的线段(作业说了:没有5点及更多点共线的情况)
// finds all line segments containing 4 point
public BruteCollinearPoints(Point[] pointsIn) {
//三种异常
//一:if the argument to the constructor is null
System.out.println(" a ");
if(pointsIn == null) throw new IllegalArgumentException("there is no point");
//二:if any point in the array is null
int N = pointsIn.length;
for(int i=0;i<N;i++) if(pointsIn[i]==null) throw new IllegalArgumentException("exist null point");
//三:if the argument to the constructor contains a repeated point
//检查是否有重复的点,先排序,再查重会方便,作业允许这样: For example, you may use Arrays.sort()
points = new Point[N];
for(int i=0;i<N;i++) points[i] = pointsIn[i];
Arrays.sort(points);
for(int i=1;i<N;i++) if(points[i-1].compareTo(points[i])==0) throw new IllegalArgumentException("exist repeated point");

//to save every required line segment
LineSegmentList = new ArrayList<LineSegment>();

//find line segment
for(int dot1=0;dot1<=N-4;dot1++) {
for(int dot2=dot1+1;dot2<=N-3;dot2++) {
//k12:the slope between point[dot2] and point[dot1]
double k12 = points[dot2].slopeTo(points[dot1]);
for(int dot3=dot2+1;dot3<=N-2;dot3++) {
//k13:the slope between point[dot3] and point[dot1]
double k13 = points[dot3].slopeTo(points[dot1]);
if(k13 != k12) continue;
for(int dot4=dot3+1;dot4<=N-1;dot4++) {
//k14:the slope between point[dot4] and point[dot1]
double k14 = points[dot4].slopeTo(points[dot1]);
if(k14 != k12) continue;
//find a line segment
LineSegment linesegment = new LineSegment(points[dot1],points[dot4]);
LineSegmentList.add(linesegment);
}
}
}
}
}
// the number of line segments
public int numberOfSegments() {
return LineSegmentList.size();
}
// the line segments
public LineSegment[] segments() {
LineSegment[] segments = new LineSegment[LineSegmentList.size()];
int index=0;
for(LineSegment Line : LineSegmentList) {
segments[index++] = Line;
}
return segments;
}
//main
public static void main(String[] args) {
In in = new In("src/week3/input8.txt");
int n = in.readInt();
StdOut.println("total "+n+" points");
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
int x = in.readInt();
int y = in.readInt();
StdOut.println("("+x+","+y+")");
points[i] = new Point(x,y);
}
//draw the points
StdDraw.enableDoubleBuffering();
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
StdDraw.setPenColor(StdDraw.RED);
StdDraw.setPenRadius(0.01);
for (Point p : points) {
p.draw();
}
StdDraw.show();
// print and draw the line segments
BruteCollinearPoints collinear = new BruteCollinearPoints(points);
StdOut.println(collinear.numberOfSegments());
for (LineSegment segment : collinear.segments()) {
StdOut.println(segment);
segment.draw();
}
StdDraw.show();
}
}

三:FastCollinearPoints.java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
import java.util.ArrayList;
import java.util.Arrays;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;

//much faster than the brute-force solution
public class FastCollinearPoints {
//to store line segments
private ArrayList<LineSegment> LineSegmentList;
//to store the given points
private Point[] points;

// finds all line segments containing 4 or more points
public FastCollinearPoints(Point[] pointsIn) {
//三种异常
//一:if the argument to the constructor is null
if(pointsIn == null) throw new IllegalArgumentException("there is no point");
//number of points
int N=pointsIn.length;
//二:if any point in the array is null
for(int i=0;i<N;i++) if(pointsIn[i]==null) throw new IllegalArgumentException("exist null point");
//三:if the argument to the constructor contains a repeated point
//检查是否有重复的点,先排序,再查重会方便,作业允许这样: For example, you may use Arrays.sort()
//同时有利于后面排除重复线段
points = new Point[N];
for(int i=0;i<N;i++) points[i] = pointsIn[i];
//用的是结合了归并和插入的tim排序,稳定排序
Arrays.sort(points);
for(int i=1;i<N;i++) if(points[i-1].compareTo(points[i])==0) throw new IllegalArgumentException("exist repeated point");

//to save every required line segment
LineSegmentList = new ArrayList<LineSegment>();


//当前的参考点
Point currentCheck;
//对照点重新存储,不包括参考点,共N-1个
Point[] otherPoints = new Point[N-1];
//开始比较斜率,一个一个来
for (int i=0;i<N;i++) {
currentCheck = points[i];
// copy points without Point currentCheck to otherPoints
for(int j=0;j<N;j++) {
if(j<i) otherPoints[j] = points[j];
if(j>i) otherPoints[j-1] = points[j];
}

//根据斜率对点排序
//用的是结合了归并和插入的tim排序,稳定排序
Arrays.sort(otherPoints,currentCheck.slopeOrder());
//遍历已经排序的otherPoints找线段
//注意,归并和插入排序都是稳定的,所以tim排序是稳定的,这非常重要
//配合Point的compareTo方法,可以直接过滤掉重复线段
//一开始没太注意compareTo方法,后来发现这个方法能固定住点之间的相对位置,所以可以过滤重复线段
//两点共线
int count=2;
for(int k=1;k<N-1;k++) {
double k1 = otherPoints[k-1].slopeTo(currentCheck);
double k2 = otherPoints[k].slopeTo(currentCheck);
if(k1==k2) {
count++;
//当循环到最后一个点,同时这个点和前面的点共线
if(k==N-2) {
//如果4点及以上共线,并且otherPoints中与参考点共线且排在最左边的点比参考点大的话,注意此处是遍历到头,所以索引是k-count+2
if(count>=4 && currentCheck.compareTo(otherPoints[k-count+2])==-1) {
//线段起点
Point start = currentCheck;
//线段终点
Point end = otherPoints[k];
LineSegment linesegment = new LineSegment(start,end);
LineSegmentList.add(linesegment);
}
}
}
else{
//如果4点及以上共线,并且otherPoints中与参考点共线且排在最左边的点比参考点大的话,索引是k-count+1
if(count>=4 && currentCheck.compareTo(otherPoints[k-count+1])==-1) {
Point start = currentCheck;
Point end = otherPoints[k-1];
LineSegment linesegment = new LineSegment(start,end);
LineSegmentList.add(linesegment);
}
count=2;
}
}
}
}

// the number of line segments
public int numberOfSegments() {
return LineSegmentList.size();
}
// the line segments
public LineSegment[] segments() {
LineSegment[] segments = new LineSegment[LineSegmentList.size()];
int index=0;
for(LineSegment Line : LineSegmentList) {
segments[index++] = Line;
}
return segments;
}

//main
public static void main(String[] args) {
In in = new In("src/week3/input9.txt");
int n = in.readInt();
StdOut.println("total "+n+" points");
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
int x = in.readInt();
int y = in.readInt();
StdOut.println("("+x+","+y+")");
points[i] = new Point(x,y);
}

//draw the points
StdDraw.enableDoubleBuffering();
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
StdDraw.setPenColor(StdDraw.RED);
StdDraw.setPenRadius(0.01);
for (Point p : points) {
p.draw();
}
StdDraw.show();

//print and draw the line segments
FastCollinearPoints collinear = new FastCollinearPoints(points);
StdOut.println(collinear.numberOfSegments());
for (LineSegment segment : collinear.segments()) {
StdOut.println(segment);
segment.draw();
}
StdDraw.show();
}
}
0%