 ## Collinear Points

1824 0 2020年3月16日

0 0 投票数

Princeton Algotithms Collinear Points

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.

Points array passsed to the constructor can be changed by some other parts of the code while construction is still in progress.

Stores a reference to an externally mutable object in the instance variable ‘points’, exposing the internal representation of the class.

Instead, create a defensive copy of the object referenced by the parameter variable ‘points’ and store that copy in the instance variable ‘points’.

check that data type is immutable by testing whether each method returns the same value, regardless of any intervening operations

Let’s say you have 5 points in their natural order a, b, c, d, e. When you have b as the anchor and sort the remaining points by slopeOrder, you want points with the same slope to appear in their natural order (i.e. … a, c, d, e, …).

To avoid adding the subsegment (b, c, d, e), whenever you start seeing a new slope (i.e. at a), you just need to check if b is less than a in terms of natural order – if it is not, it means b is not the first point in that segment, then you know you don’t need to add it.

import java.util.ArrayList;
import java.util.Arrays;

public class BruteCollinearPoints {
private final Point[] points;
private final LineSegment[] cached;

public BruteCollinearPoints(Point[] points) {
if (points == null) {
throw new IllegalArgumentException();
}
// Points array passsed to the constructor can be changed by some other parts of the code while construction is still in progress.
this.points = Arrays.copyOf(points, points.length);
for (Point point : this.points) {
if (point == null) {
throw new IllegalArgumentException();
}
}
Arrays.sort(this.points);
for (int i = 0; i < this.points.length; i++) {
if (i > 0 && Double.compare(this.points[i].slopeTo(this.points[i - 1]), Double.NEGATIVE_INFINITY) == 0) {
throw new IllegalArgumentException();
}
}
// Stores a reference to an externally mutable object in the instance variable 'points', exposing the internal representation of the class.
// Instead, create a defensive copy of the object referenced by the parameter variable 'points' and store that copy in the instance variable 'points'.
cached = cache();
}

private LineSegment[] cache() {
ArrayList<LineSegment> list = new ArrayList<>();
int n = points.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
for (int m = k + 1; m < n; m++) {
Point p = points[i];
Point q = points[j];
Point r = points[k];
Point s = points[m];
double slope1 = p.slopeTo(q);
double slope2 = p.slopeTo(r);
double slope3 = p.slopeTo(s);
if (Double.compare(slope1, slope2) == 0 && Double.compare(slope2, slope3) == 0) {
}
}
}
}
}
LineSegment[] segments = new LineSegment[list.size()];
return list.toArray(segments);
}

public int numberOfSegments() {
return cached.length;
}

public LineSegment[] segments() {
// check that data type is immutable by testing whether each method
// returns the same value, regardless of any intervening operations
return Arrays.copyOf(cached, cached.length);
}
}
/*************************************************************************
*  Compilation:  javac LineSegment.java
*  Execution:    none
*  Dependencies: Point.java
*
*  An immutable data type for Line segments in the plane.
*  For use on Coursera, Algorithms Part I programming assignment.
*
*  DO NOT MODIFY THIS CODE.
*
*************************************************************************/

public class LineSegment {
private final Point p;   // one endpoint of this line segment
private final Point q;   // the other endpoint of this line segment

/**
* Initializes a new line segment.
*
* @param  p one endpoint
* @param  q the other endpoint
* @throws NullPointerException if either <tt>p</tt> or <tt>q</tt>
*         is <tt>null</tt>
*/
public LineSegment(Point p, Point q) {
if (p == null || q == null) {
throw new NullPointerException("argument is null");
}
this.p = p;
this.q = q;
}

/**
* Draws this line segment to standard draw.
*/
public void draw() {
p.drawTo(q);
}

/**
* Returns a string representation of this line segment
* This method is provide for debugging;
* your program should not rely on the format of the string representation.
*
* @return a string representation of this line segment
*/
public String toString() {
return p + " -> " + q;
}

/**
* Throws an exception if called. The hashCode() method is not supported because
* hashing has not yet been introduced in this course. Moreover, hashing does not
* typically lead to good *worst-case* performance guarantees, as required on this
* assignment.
*
* @throws UnsupportedOperationException if called
*/
public int hashCode() {
throw new UnsupportedOperationException();
}

}
import java.util.ArrayList;
import java.util.Arrays;

public class FastCollinearPoints {
private final Point[] points;
private final LineSegment[] cached;

public FastCollinearPoints(Point[] points) {
if (points == null) {
throw new IllegalArgumentException();
}
// Points array passsed to the constructor can be changed by some other parts of the code while construction is still in progress.
this.points = Arrays.copyOf(points, points.length);
for (Point point : this.points) {
if (point == null) {
throw new IllegalArgumentException();
}
}
Arrays.sort(this.points);
for (int i = 0; i < this.points.length; i++) {
if (i > 0 && Double.compare(this.points[i].slopeTo(this.points[i - 1]), Double.NEGATIVE_INFINITY) == 0) {
throw new IllegalArgumentException();
}
}
// Stores a reference to an externally mutable object in the instance variable 'points', exposing the internal representation of the class.
// Instead, create a defensive copy of the object referenced by the parameter variable 'points' and store that copy in the instance variable 'points'.
cached = cache();
}

public int numberOfSegments() {
return cached.length;
}

public LineSegment[] segments() {
// check that data type is immutable by testing whether each method
// returns the same value, regardless of any intervening operations
return Arrays.copyOf(cached, cached.length);
}

private LineSegment[] cache() {
ArrayList<LineSegment> list = new ArrayList<>();
Arrays.sort(points);
for (Point p: points) {
Point[] pp = Arrays.copyOf(points, points.length);
if (pp.length < 4) {
continue;
}
Arrays.sort(pp, p.slopeOrder());
int begin = 1;
int end = 1;
double last = p.slopeTo(pp[end]);
for (int j = 2; j < pp.length; j++) {
double slope = p.slopeTo(pp[j]);
if (Double.compare(last, slope) != 0) {
if (end - begin >= 2) {
// end - begin + 1 有 3 个以上了，加上 p（即pp） 就至少有 4 个了
if (p.compareTo(pp[begin]) < 0) {
// 去掉子线段
/*
Let's say you have 5 points in their natural order a, b, c, d, e.
When you have b as the anchor and sort the remaining points by slopeOrder, you want points with the same slope to appear in their natural order (i.e. ... a, c, d, e, ...).
To avoid adding the subsegment (b, c, d, e), whenever you start seeing a new slope (i.e. at a), you just need to check if b is less than a in terms of natural order
- if it is not, it means b is not the first point in that segment, then you know you don't need to add it.
*/
}
}
last = slope;
begin = j;
}
end = j;
}
if (end - begin >= 2) {
if (p.compareTo(pp[begin]) < 0) {
}
}
}
LineSegment[] segments = new LineSegment[list.size()];
return list.toArray(segments);
}
}
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;

public class Client {
public static void main(String[] args) {

// read the n points from a file
In in = new In(args);
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
points[i] = new Point(x, y);
}

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

// print and draw the line segments
FastCollinearPoints collinear = new FastCollinearPoints(points);
for (LineSegment segment : collinear.segments()) {
StdOut.println(segment);
segment.draw();
}
points = new Point(0, 0);
for (LineSegment segment : collinear.segments()) {
StdOut.println(segment);
segment.draw();
}
StdDraw.show();
}
}
/******************************************************************************
*  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 java.util.Arrays;
import java.util.Comparator;

import edu.princeton.cs.algs4.StdDraw;

public class Point implements Comparable<Point> {

private final int x;     // x-coordinate of this point
private 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 (x == that.x && y == that.y) {
return Double.NEGATIVE_INFINITY;
} else if (x == that.x) {
return Double.POSITIVE_INFINITY;
} else if (y == that.y) {
return 0;
// 注意这里必须返回正 0，否则 0 带有正负号，会使得平行于 x 轴的排序出错
// 例如 (0, 5), (1, 5), (2, 5), (3, 5), (4, 5), (5, 5) 以 (1, 5) 为排序时结果是
// (1, 5), (2, 5), (3, 5), (4, 5), (5, 5), (0, 5)
// (0, 5) 到最后了
} else {
return (double) (y - that.y) / (x - that.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
*/
@Override
public int compareTo(Point that) {
if (y != that.y) {
return Integer.compare(y, that.y);
} else {
return Integer.compare(x, that.x);
}
}

/**
* 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() {
return new Comparator<Point>() {
@Override
public int compare(Point o1, Point o2) {
return Double.compare(slopeTo(o1), slopeTo(o2));
}
};
}

/**
* 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
*/
@Override
public String toString() {
/* DO NOT MODIFY */
return "(" + x + ", " + y + ")";
}

/**
* Unit tests the Point data type.
*/
public static void main(String[] args) {
Point p1 = new Point(0, 0);
Point p2 = new Point(1, 1);
System.out.println(p1.compareTo(p2));
System.out.println(p1.slopeTo(p2));
Point[] pp = new Point;
pp = new Point(2, 1);
pp = new Point(0, 0);
pp = new Point(1, 1);
Arrays.sort(pp, pp.slopeOrder());
System.out.println(Arrays.toString(pp));
}
}

0 0 投票数 （可选）如果您也有个人网站，不妨分享一下

0 评论

Warning: error_log(/home/wwwroot/www.jxtxzzw.com/wp-content/plugins/spider-analyser/#log/log-1012.txt): failed to open stream: No such file or directory in /home/wwwroot/www.jxtxzzw.com/wp-content/plugins/spider-analyser/spider.class.php on line 2900