普林斯顿大学算法 Week3:CollinearPoints 共线模式识别(95分)

admin 管理员组

文章数量: 1086929

普林斯顿大学算法 Week3:CollinearPoints 共线模式识别(95分)

FastCollinearPoints的实现中，个人认为最关键的一步是使用Merge Sort对以每个点为出发点的线段进行排序而不能用QuickSort，其原因在与排序的Stability稳定性。MergeSort不会打乱之前因为对Points排序后形成的有序线段组，才能保证后面循环检查线段斜率操作的有效性。

关于排序算法Stability的说明，见《算法（第四版）》第217页的2.5.1.8稳定性一节的讲述

Points.java

/*******************************************************************************  Compilation:  javac Point.java*  Execution:    java Point*  Dependencies: none**  An immutable data type for points in the plane.*  For use on Coursera, Algorithms Part I programming assignment.*******************************************************************************/import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;import java.util.Comparator;public class Point implements Comparable<Point> {private final int x;     // x-coordinate of this pointprivate final int y;     // y-coordinate of this point/*** Initializes a new point.** @param x the <em>x</em>-coordinate of the point* @param y the <em>y</em>-coordinate of the point*/public Point(int x, int y) {/* DO NOT MODIFY */this.x = x;this.y = y;}/*** Draws this point to standard draw.*/public void draw() {/* DO NOT MODIFY */StdDraw.point(x, y);}/*** Draws the line segment between this point and the specified point* to standard draw.** @param that the other point*/public void drawTo(Point that) {/* DO NOT MODIFY */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.equal(that))return Double.NEGATIVE_INFINITY;if (this.x == that.x)return Double.POSITIVE_INFINITY;if (this.y == that.y)return +0.0;return (double) (that.y - this.y) / (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) {/* YOUR CODE HERE */int result = 1;if ((this.y < that.y) || ((this.y == that.y) && (this.x < that.x)))result = -1;if (this.equal(that))result = 0;return result;}/*** Compares two points by the slope they make with this point.* The slope is defined as in the slopeTo() method.** @return the Comparator that defines this ordering on points*/public Comparator<Point> slopeOrder() {/* YOUR CODE HERE */return new slopeComparator();}private class slopeComparator implements Comparator<Point> {public int compare(Point p, Point q) {return Doublepare(slopeTo(p), slopeTo(q));}}private boolean equal(Point that) {return (this.x == that.x) && (this.y == that.y);}/*** Returns a string representation of this point.* This method is provide for debugging;* your program should not rely on the format of the string representation.** @return a string representation of this point*/public String toString() {/* DO NOT MODIFY */return "(" + x + ", " + y + ")";}/*** Unit tests the Point data type.*/public static void main(String[] args) {/* YOUR CODE HERE */Point p = new Point(1, 1);Point p2 = new Point(2, 2);Point p3 = new Point(2, 3);StdOut.println(p.slopeTo(p2));StdOut.println(p.slopeTo(p3));}
}

BruteCollinearPoints.java

import java.util.ArrayList;
import java.util.Arrays;public class BruteCollinearPoints {private final ArrayList<LineSegment> lineSegments;private int count_line;public BruteCollinearPoints(Point[] pointsIn) {//three exceptionsif (pointsIn == null)throw new IllegalArgumentException();int n = pointsIn.length;for (Point point : pointsIn)if (point == null)throw new IllegalArgumentException();Point[] points = new Point[n];//copy points in pointsIn into private array pointsSystem.arraycopy(pointsIn, 0, points, 0, n);Arrays.sort(points);for (int i = 1; i < n; i++)if (points[i - 1]pareTo(points[i]) == 0)throw new IllegalArgumentException();lineSegments = new ArrayList<LineSegment>();for (int a = 0; a < n - 3; a++) {for (int b = a + 1; b < n - 2; b++) {double Kab = points[a].slopeTo(points[b]);for (int c = b + 1; c < n - 1; c++) {double Kac = points[a].slopeTo(points[c]);if (Kac != Kab) continue;assert Kac == Kab;for (int d = c + 1; d < n; d++) {double Kad = points[a].slopeTo(points[d]);if (Kad != Kab) continue;assert Kad == Kab && Kac == Kab;LineSegment addLine = new LineSegment(points[a], points[d]);lineSegments.add(addLine);}}}}count_line = lineSegments.size();}// the number of line segmentspublic int numberOfSegments() {return count_line;}// the line segmentspublic LineSegment[] segments() {LineSegment[] segments = new LineSegment[count_line];int i = 0;for (LineSegment Line : lineSegments) {segments[i++] = Line;}return segments;}//mainpublic static void main(String[] args) {}}

FastCollinearPoints.java

import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Merge;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;import java.util.ArrayList;
import java.util.Arrays;public class FastCollinearPoints {private ArrayList<LineSegment> lineSegments;private ArrayList<line> linesArraylist;private int count_line;public FastCollinearPoints(Point[] pointsIn) {linesArraylist = new ArrayList<line>();//three exceptionsif (pointsIn == null)throw new IllegalArgumentException();int n = pointsIn.length;for (Point point : pointsIn)if (point == null)throw new IllegalArgumentException();Point[] points = new Point[n];//copy points in pointsIn into private array pointsSystem.arraycopy(pointsIn, 0, points, 0, n);Arrays.sort(points);for (int i = 1; i < n; i++) {if (points[i - 1]pareTo(points[i]) == 0) {throw new IllegalArgumentException();}}for (int i = 0; i < n - 1; i++) {line[] lines = new line[n - 1 - i];int sz = 0;for (int j = i + 1; j < n; j++) {line tempLine = new line(points[i], points[j]);lines[sz++] = tempLine;}if (lines.length < 3)continue;Merge.sort(lines);
//            StdOut.println("以点" + points[i] + "为起点的线总共有" + lines.length + "条");
//            for (line temp : lines) {
//                StdOut.println(temp + "，其斜率为：" + temp.slope);
//            }
//
//            StdOut.println();
//            StdOut.println();int pa = 0, pb = 1;while (pa < sz && pb < sz) {if (lines[pa].slope == lines[pb].slope) {pb++;if (pb == sz && pb - pa >= 3) {line temp_Line = new line(lines[pa].startPoint, lines[pb - 1].endPoint);if (!isExisted(lines[pb - 1].endPoint, temp_Line.slope)) {linesArraylist.add(temp_Line);//StdOut.println("添加了线段" + temp_Line);}}continue;}if ((pb - pa) < 3) {pa = pb;pb++;} else {line temp_Line = new line(lines[pa].startPoint, lines[pb - 1].endPoint);if (!isExisted(lines[pb - 1].endPoint, temp_Line.slope)) {linesArraylist.add(temp_Line);//StdOut.println("添加了线段" + temp_Line);}pa = pb;pb++;}}//
//            StdOut.println();
//            StdOut.println();
//            StdOut.println();}lineSegments = new ArrayList<LineSegment>();for (line l : linesArraylist) {LineSegment lineSegment = new LineSegment(l.startPoint, l.endPoint);lineSegments.add(lineSegment);}count_line = lineSegments.size();
//               int lineNum = (N * (N - 1)) / 2;
//        int index = 0;
//        //把所有的两点线段全都加到lines中，lines用于存储所有的线段
//        for (int i = 0; i < N - 1; i++) {
//            for (int j = i + 1; j < N; j++) {
//                line tempLine = new line(points[i], points[j]);
//                lines[index++] = tempLine;
//            }
//        }
//        assert index == lineNum - 1;//        //将所有线段按照斜率进行快排(不需要考虑稳定性)
//        assert lines != null;
//        Quick.sort(lines);
//        //将所有线段按照名称进行归并排序}private boolean isExisted(Point end, double slope) {boolean result = false;for (line l : linesArraylist) {if ((endpareTo(l.endPoint) == 0) && (Doublepare(slope, l.slope) == 0)) {result = true;break;}}return result;}//由两个点组成的线段，提供按照斜率和按照起始点两种排序方式private static class line implements Comparable<line> {public final Point startPoint;public final Point endPoint;public double slope;public line(Point s, Point e) {startPoint = s;endPoint = e;slope = s.slopeTo(e);}@Overridepublic int compareTo(line o) {return Doublepare(this.slope, o.slope);}@Overridepublic String toString() {return startPoint + " -> " + endPoint;}}public int numberOfSegments() {return count_line;}public LineSegment[] segments() {LineSegment[] segments = new LineSegment[count_line];int i = 0;for (LineSegment Line : lineSegments) {segments[i++] = Line;}return segments;}//mainpublic static void main(String[] args) {In in = new In("src/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 pointsStdDraw.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 segmentsFastCollinearPoints collinear = new FastCollinearPoints(points);StdOut.println(collinear.numberOfSegments());for (LineSegment segment : collinear.segments()) {StdOut.println(segment);segment.draw();}StdDraw.show();//        Point test1 = new Point(1000, 21);
//        Point test2 = new Point(1000, 2000);
//        Point test3 = new Point(1000, 3000);
//        StdOut.println(test1.slopeTo(test2) == test1.slopeTo(test3));//上面几行的输出是true}
}

本文标签： 普林斯顿大学算法 Week3CollinearPoints 共线模式识别(95分)