http://coursera.cs.princeton.edu/algs4/assignments/collinear.html
https://www.cs.princeton.edu/courses/archive/fall12/cos226/checklist/collinear.html
Computer vision involves analyzing patterns in visual images and reconstructing the real-world objects that produced them. The process is often broken up into two phases: feature detection and pattern recognition. Feature detection involves selecting important features of the image; pattern recognition involves discovering patterns in the features. We will investigate a particularly clean pattern recognition problem involving points and line segments. This kind of pattern recognition arises in many other applications such as statistical data analysis.
The problem. Given a set of N distinct points in the plane, find every (maximal) line segment that connects a subset of 4 or more of the points.
Brute Force
public static void main(String[] args) {
// Rescale the coordinate system.
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
// Read points from the input file.
In in = new In(args[0]);
int pointsCount = in.readInt();
Point[] points = new Point[pointsCount];
for (int i = 0; i < pointsCount; i++) {
int x = in.readInt();
int y = in.readInt();
points[i] = new Point(x, y);
points[i].draw();
}
// Go each 4 points and check whether they all lie on the same line segment.
for (int p = 0; p < pointsCount; p++) {
for (int q = p + 1; q < pointsCount; q++) {
double slopeToQ = points[p].slopeTo(points[q]);
for (int r = q + 1; r < pointsCount; r++) {
double slopeToR = points[p].slopeTo(points[r]);
if (slopeToQ == slopeToR) {
for (int s = r + 1; s < pointsCount; s++) {
double slopeToS = points[p].slopeTo(points[s]);
if (slopeToQ == slopeToS) {
// Create the list of collinear points and sort them.
List<Point> collinearPoints = new ArrayList<Point>(4);
collinearPoints.add(points[p]);
collinearPoints.add(points[q]);
collinearPoints.add(points[r]);
collinearPoints.add(points[s]);
Collections.sort(collinearPoints);
// Display collinear points.
for (int i = 0; i < 3; i++) {
StdOut.print(collinearPoints.get(i));
StdOut.print(" -> ");
}
StdOut.println(Collections.max(collinearPoints));
Collections.min(collinearPoints).drawTo(Collections.max(collinearPoints));
}
}
}
}
}
}
}
public class Point implements Comparable<Point> {
// compare points by slope
public final Comparator<Point> SLOPE_ORDER = new Comparator<Point>() {
public int compare(Point o1, Point o2) {
double slope1 = slopeTo(o1);
double slope2 = slopeTo(o2);
if (slope1 == slope2) {
return 0;
}
if (slope1 < slope2) {
return -1;
}
return 1;
}
};
private final int x; // x coordinate
private final int y; // y coordinate
// create the point (x, y)
public Point(int x, int y) {
/* DO NOT MODIFY */
this.x = x;
this.y = y;
}
// plot this point to standard drawing
public void draw() {
/* DO NOT MODIFY */
StdDraw.point(x, y);
}
// draw line between this point and that point to standard drawing
public void drawTo(Point that) {
/* DO NOT MODIFY */
StdDraw.line(this.x, this.y, that.x, that.y);
}
// slope between this point and that point
public double slopeTo(Point that) {
if (that == null) {
throw new NullPointerException();
}
if (that.x == x) {
if (that.y == y) {
return Double.NEGATIVE_INFINITY;
}
return Double.POSITIVE_INFINITY;
}
if (that.y == y) {
return 0.0;
}
return (double) (that.y - this.y) / (that.x - this.x);
}
// is this point lexicographically smaller than that one?
// comparing y-coordinates and breaking ties by x-coordinates
public int compareTo(Point that) {
if (y == that.y && x == that.x) {
return 0;
}
if (y < that.y || (y == that.y && x < that.x)) {
return -1;
}
return 1;
}
// return string representation of this point
public String toString() {
/* DO NOT MODIFY */
return "(" + x + ", " + y + ")";
}
}
http://blog.csdn.net/liuweiran900217/article/details/19285111
https://www.cs.princeton.edu/courses/archive/fall12/cos226/checklist/collinear.html
Computer vision involves analyzing patterns in visual images and reconstructing the real-world objects that produced them. The process is often broken up into two phases: feature detection and pattern recognition. Feature detection involves selecting important features of the image; pattern recognition involves discovering patterns in the features. We will investigate a particularly clean pattern recognition problem involving points and line segments. This kind of pattern recognition arises in many other applications such as statistical data analysis.
The problem. Given a set of N distinct points in the plane, find every (maximal) line segment that connects a subset of 4 or more of the points.
Brute force. Write a program BruteCollinearPoints.java that examines 4 points at a time and checks whether they all lie on the same line segment, returning all such line segments. To check whether the 4 points p, q, r, and s are collinear, check whether the three slopes between p and q, between p and r, and between p and s are all equal.
Corner cases. Throw a java.lang.NullPointerException either the argument to the constructor is null or if any point in the array is null. Throw a java.lang.IllegalArgumentException if the argument to the constructor contains a repeated point.
Performance requirement. The order of growth of the running time of your program should be N4 in the worst case and it should use space proportional to N plus the number of line segments returned.
A faster, sorting-based solution. Remarkably, it is possible to solve the problem much faster than the brute-force solution described above. Given a point p, the following method determines whether p participates in a set of 4 or more collinear points.
Write a program FastCollinearPoints.java that implements this algorithm.
Corner cases. Throw a java.lang.NullPointerException either the argument to the constructor is null or if any point in the array is null. Throw a java.lang.IllegalArgumentException if the argument to the constructor contains a repeated point.
Performance requirement. The order of growth of the running time of your program should be N2 log N in the worst case and it should use space proportional to N plus the number of line segments returned.FastCollinearPoints should work properly even if the input has 5 or more collinear points.
public class BruteCollinearPoints {
public BruteCollinearPoints(Point[] points) // finds all line segments containing 4 points
public int numberOfSegments() // the number of line segments
public LineSegment[] segments() // the line segments
}
The method segments() should include each line segment containing 4 points exactly once. If 4 points appear on a line segment in the order p→q→r→s, then you should include either the line segment p→s or s→p (but not both) and you should not include subsegments such as p→r or q→r. For simplicity, we will not supply any input to BruteCollinearPoints that has 5 or more collinear points.Corner cases. Throw a java.lang.NullPointerException either the argument to the constructor is null or if any point in the array is null. Throw a java.lang.IllegalArgumentException if the argument to the constructor contains a repeated point.
Performance requirement. The order of growth of the running time of your program should be N4 in the worst case and it should use space proportional to N plus the number of line segments returned.
A faster, sorting-based solution. Remarkably, it is possible to solve the problem much faster than the brute-force solution described above. Given a point p, the following method determines whether p participates in a set of 4 or more collinear points.
- Think of p as the origin.
- For each other point q, determine the slope it makes with p.
- Sort the points according to the slopes they makes with p.
- Check if any 3 (or more) adjacent points in the sorted order have equal slopes with respect to p. If so, these points, together with p, are collinear.
public class FastCollinearPoints {
public FastCollinearPoints(Point[] points) // finds all line segments containing 4 or more points
public int numberOfSegments() // the number of line segments
public LineSegment[] segments() // the line segments
}
The method segments() should include each maximal line segment containing 4 (or more) points exactly once. For example, if 5 points appear on a line segment in the order p→q→r→s→t, then do not include the subsegments p→s or q→t.Corner cases. Throw a java.lang.NullPointerException either the argument to the constructor is null or if any point in the array is null. Throw a java.lang.IllegalArgumentException if the argument to the constructor contains a repeated point.
Performance requirement. The order of growth of the running time of your program should be N2 log N in the worst case and it should use space proportional to N plus the number of line segments returned.FastCollinearPoints should work properly even if the input has 5 or more collinear points.
public static void main(String[] args) throws IOException {
String fileName = args[0];
List<Point> points = readList(fileName);
Collections.sort(points);
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
for(int i=0;i<points.size();i++) points.get(i).draw();
Map<String, Boolean> printedMap = new HashMap<String, Boolean>();
for(int i=0;i<points.size();i++) {
List<Point> tmpPoints = new ArrayList<Point>();
for(int j=i+1;j<points.size();j++) tmpPoints.add(points.get(j));
Collections.sort(tmpPoints, points.get(i).SLOPE_ORDER);
for(int j=0;j<tmpPoints.size();){
double slote = points.get(i).slopeTo(tmpPoints.get(j));
List<Point> nList = new ArrayList<Point>();
nList.add(points.get(i)); nList.add(tmpPoints.get(j));
j++;
while(j<tmpPoints.size() && points.get(i).slopeTo(tmpPoints.get(j))==slote) {
nList.add(tmpPoints.get(j));
j ++;
}
if(nList.size()>=4) {
boolean printedFlag = false;
for(int k=0;k<nList.size()-1;k++) {
String seg = nList.get(k).toString()+","+nList.get(k+1).toString();
if(!printedMap.containsKey(seg)) {
printedMap.put(seg, true);
printedFlag = true;
}
}
if(printedFlag){
Collections.sort(nList);
for(int k=0;k<nList.size()-1;k++) System.out.print(nList.get(k)+" -> ");
System.out.print(nList.get(nList.size()-1)+"\n");
points.get(i).drawTo(nList.get(nList.size()-1));
}
}
}
}
}
public static void main(String[] args) {
// Rescale the coordinate system.
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
// Read points from the input file.
In in = new In(args[0]);
int pointsCount = in.readInt();
Point[] points = new Point[pointsCount];
for (int i = 0; i < pointsCount; i++) {
int x = in.readInt();
int y = in.readInt();
points[i] = new Point(x, y);
points[i].draw();
}
// Go each point p.
for (int p = 0; p < pointsCount; p++) {
// Sort the points according to the slopes they makes with p.
sort(points, points[p].SLOPE_ORDER);
// Check if any 3 (or more) adjacent points in the sorted order have equal slopes with respect to p
ArrayList<Point> collinearPoints = new ArrayList<Point>(pointsCount);
for (int q = 0; q < pointsCount - 1; q++) {
if (p == q) {
continue;
}
if (collinearPoints.isEmpty()) {
collinearPoints.add(points[q]);
} else if (points[p].slopeTo(points[q - 1]) == points[p].slopeTo(points[q])) {
collinearPoints.add(points[q]);
} else if (collinearPoints.size() > 2) {
// Draw collinear points.
collinearPoints.add(points[p]);
Collections.sort(collinearPoints);
// Display collinear points.
for (int i = 0; i < 3; i++) {
StdOut.print(collinearPoints.get(i));
StdOut.print(" -> ");
}
StdOut.println(Collections.max(collinearPoints));
Collections.min(collinearPoints).drawTo(Collections.max(collinearPoints));
break;
} else {
collinearPoints.clear();
collinearPoints.add(points[q]);
}
}
}
}
/***********************************************************************
* Bottom-Up merge sorting functions
***********************************************************************/
// stably merge a[lo..m] with a[m+1..hi] using aux[lo..hi]
private static void merge(Point[] a, Point[] aux, int lo, int m, int hi, Comparator<Point> comparator) {
// copy to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = m+1;
for (int k = lo; k <= hi; k++) {
if (i > m) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(comparator, aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
// bottom-up mergesort
public static void sort(Point[] a, Comparator<Point> comparator) {
int N = a.length;
Point[] aux = new Point[N];
for (int n = 1; n < N; n = n+n) {
for (int i = 0; i < N-n; i += n+n) {
int lo = i;
int m = i+n-1;
int hi = Math.min(i+n+n-1, N-1);
merge(a, aux, lo, m, hi, comparator);
}
}
}
// is v < w ?
private static boolean less(Comparator<Point> comparator, Point v, Point w) {
return comparator.compare(v, w) < 0;
}
public static void main(String[] args) {
// Rescale the coordinate system.
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
// Read points from the input file.
In in = new In(args[0]);
int pointsCount = in.readInt();
Point[] points = new Point[pointsCount];
for (int i = 0; i < pointsCount; i++) {
int x = in.readInt();
int y = in.readInt();
points[i] = new Point(x, y);
points[i].draw();
}
// Go each 4 points and check whether they all lie on the same line segment.
for (int p = 0; p < pointsCount; p++) {
for (int q = p + 1; q < pointsCount; q++) {
double slopeToQ = points[p].slopeTo(points[q]);
for (int r = q + 1; r < pointsCount; r++) {
double slopeToR = points[p].slopeTo(points[r]);
if (slopeToQ == slopeToR) {
for (int s = r + 1; s < pointsCount; s++) {
double slopeToS = points[p].slopeTo(points[s]);
if (slopeToQ == slopeToS) {
// Create the list of collinear points and sort them.
List<Point> collinearPoints = new ArrayList<Point>(4);
collinearPoints.add(points[p]);
collinearPoints.add(points[q]);
collinearPoints.add(points[r]);
collinearPoints.add(points[s]);
Collections.sort(collinearPoints);
// Display collinear points.
for (int i = 0; i < 3; i++) {
StdOut.print(collinearPoints.get(i));
StdOut.print(" -> ");
}
StdOut.println(Collections.max(collinearPoints));
Collections.min(collinearPoints).drawTo(Collections.max(collinearPoints));
}
}
}
}
}
}
}
public class Point implements Comparable<Point> {
// compare points by slope
public final Comparator<Point> SLOPE_ORDER = new Comparator<Point>() {
public int compare(Point o1, Point o2) {
double slope1 = slopeTo(o1);
double slope2 = slopeTo(o2);
if (slope1 == slope2) {
return 0;
}
if (slope1 < slope2) {
return -1;
}
return 1;
}
};
private final int x; // x coordinate
private final int y; // y coordinate
// create the point (x, y)
public Point(int x, int y) {
/* DO NOT MODIFY */
this.x = x;
this.y = y;
}
// plot this point to standard drawing
public void draw() {
/* DO NOT MODIFY */
StdDraw.point(x, y);
}
// draw line between this point and that point to standard drawing
public void drawTo(Point that) {
/* DO NOT MODIFY */
StdDraw.line(this.x, this.y, that.x, that.y);
}
// slope between this point and that point
public double slopeTo(Point that) {
if (that == null) {
throw new NullPointerException();
}
if (that.x == x) {
if (that.y == y) {
return Double.NEGATIVE_INFINITY;
}
return Double.POSITIVE_INFINITY;
}
if (that.y == y) {
return 0.0;
}
return (double) (that.y - this.y) / (that.x - this.x);
}
// is this point lexicographically smaller than that one?
// comparing y-coordinates and breaking ties by x-coordinates
public int compareTo(Point that) {
if (y == that.y && x == that.x) {
return 0;
}
if (y < that.y || (y == that.y && x < that.x)) {
return -1;
}
return 1;
}
// return string representation of this point
public String toString() {
/* DO NOT MODIFY */
return "(" + x + ", " + y + ")";
}
}
http://blog.csdn.net/liuweiran900217/article/details/19285111
slopeTo类相当于来计算两点间连线的斜率了。初中数学我们就知道，有如下几种情况。
（1）两个点的y坐标相同，即连线与x轴平行。这种情况的斜率为0。但是我们要注意一个问题，在Java中实际上有两种0，即+0和-0，并且Java内置的比较函数认为+0>-0。这是怎么来的呢？在题目的CheckList中已经给出了相关的介绍，我们放在这里供大家参考：
What does it mean for slopeTo() to return positive zero?Java (and the IEEE 754 floating-point standard) define two representations of zero: negative zero and positive zero.
Note that while (x == y) is guaranteed to be true,Arrays.sort() treatsnegative zero as strictly less than positive zero.Thus, to make the specification precise, we require you to return positive zero for horizontal line segments.Unless your program casts to the wrapper type Double (either explicitly or via autoboxing),you probably will not notice any difference in behavior;but, if your program does cast to the wrapper type and fails only on (some) horizontal line segments, this may bethe cause.double a = 1.0; double x = (a - a) / a; // positive zero ( 0.0) double y = (a - a) / -a; // negative zero (-0.0)
（2）两个点的x坐标相同，即连线与y轴平行。根据题目要求，我们要把这种斜率定义为正无穷大。在Java中，Double类给出了双精度浮点数正无穷大的表示，为Double.POSITIVE_INFINITY，因此用这个值代表正无穷大即可。
（3）两个点相同。这是一个极为特殊的情况，在CheckList中也有过说明，内容如下：
Can the same point appear more than once as input to Brute or Fast?You may assume the input to Bruteand Fast are N distinct points.Nevertheless, the methods implemented as part of the Point data typemust correctly handle the case when the points are not distinct:for the slopeTo() method, this requirement is explicitly stated in the API;for the comparison methods, this requirement is implict in the contracts for Comparable andComparator.
对于这种情况，我的处理方法是将其结果设置为负无穷大，即Double.NEGATIVE_INFINITY。
（4）其他一般情况。这种情况下，我们直接计算斜率即可，计算公式很简单，为：(y_1 - y_0) / (x_1 - x_0)。不过注意到点的坐标表示是int，斜率为double，因此我们还需要一个强制转换来保证计算的精度。
compareTo()
这个类的实现也很容易，直接按照题目要求来实现即可。当y_0 < y_1或者当y_0 = y_1且x_0 < x_1时，返回-1。
SLOPE_ORDER
这个类的实现也很容易，分别计算两个点对于第三个点的斜率（调用slopeTo()），然后返回两个结果的比较值即可。因为在slopeTo()中我们已经处理过了3种特殊的情况，因此直接返回比较值就是正确的结果。
private static void FastMethod(Point[] pointArray){
int N = pointArray.length;
for (int i=0; i<N; i++){
Point origPoint = pointArray[i];
Point[] otherPoint = new Point[N-1];
for (int j=0; j<pointArray.length; j++){
if (j < i) otherPoint[j] = pointArray[j];
if (j > i) otherPoint[j-1] = pointArray[j];
}
Arrays.sort(otherPoint, origPoint.SLOPE_ORDER);
int count = 0;
int index = 0;
double tempSlope = origPoint.slopeTo(otherPoint[0]);
for (int j=0; j<otherPoint.length;j++){
if (Double.compare(origPoint.slopeTo(otherPoint[j]), tempSlope) == 0){
count++;
continue;
}else{
if (count >=3){
if (otherPoint[index].compareTo(origPoint) >=0){
StdOut.print(origPoint + " -> ");
for (int k=index; k<j-1; k++){
StdOut.print(otherPoint[k] + " -> ");
}
StdOut.println(otherPoint[j-1]);
origPoint.drawTo(otherPoint[j-1]);
}
}
count = 1;
index = j;
tempSlope = origPoint.slopeTo(otherPoint[j]);
}
}
if (count >= 3){
if (otherPoint[index].compareTo(origPoint) >= 0){
StdOut.print(origPoint + " -> ");
for (int k=index; k<otherPoint.length - 1; k++){
StdOut.print(otherPoint[k] + " -> ");
}
StdOut.println(otherPoint[otherPoint.length-1]);
origPoint.drawTo(otherPoint[otherPoint.length-1]);
}
}
}
StdDraw.show(0);
}
作业说明中对核心算法的描述非常清晰，应当特别小心的技术点（浮点误差、正负零等等）也都在checklist中予以强调，因而实现难度不算很大，其中使用了Java的Comparable与Comparator，排序过程调用
值得提到的点：
Arrays.sort()，详细思考问题理清关系后，实现非常自然，前提是编程基本功必须扎实。值得提到的点：
- checklist鼓励初学者开始编写快速算法时先不要担心5个或以上的点共线的情况，而实际上对基本功扎实的同学，从开始便考虑这个问题更为合适；
- checklist提到
compare()和FastCollinearPoints类可以完全避免浮点数用整形运算实现，我想到的唯一符合要求（Point.java注释中规定不得依赖toString()）的方法是，对Point类的compareTo()方法返回值增加意义（不单纯返回正负1），以获取两点的坐标之差（因题目给定坐标取值范围0-32767，可在返回值低两位字节存储x坐标差， 高两位字节存储y坐标差），再利用坐标差判断斜率是否相等。虽依然完全符合题目要求，但已有一点奇技淫巧之嫌，并且不一定能够通过autograder（评分时会替换Point类去测试FastCollinearPoints），不多讨论。（更新：此方法已确定违反FastCollinearPoints的API。）
