## Monday, May 30, 2016

### Princeton Programming Assignment 3: Pattern Recognition

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. 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 pqr, 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.
```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 pqrs, then you should include either the line segment ps or sp (but not both) and you should not include subsegments such as pr or qr. 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.
Applying this method for each of the N points in turn yields an efficient algorithm to the problem. The algorithm solves the problem because points that have equal slopes with respect to p are collinear, and sorting brings such points together. The algorithm is fast because the bottleneck operation is sorting.
Write a program FastCollinearPoints.java that implements this algorithm.
```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 pqrst, then do not include the subsegments ps or qt.
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];
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>();
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>();
j++;
while(j<tmpPoints.size() && points.get(i).slopeTo(tmpPoints.get(j))==slote) {
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]);
Point[] points = new Point[pointsCount];
for (int i = 0; i < pointsCount; i++) {
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()) {
} else if (points[p].slopeTo(points[q - 1]) == points[p].slopeTo(points[q])) {
} else if (collinearPoints.size() > 2) {
// Draw collinear points.
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();
}
}
}
}

/***********************************************************************
*  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;
}

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]);
Point[] points = new Point[pointsCount];
for (int i = 0; i < pointsCount; i++) {
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);
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.
```double a = 1.0;
double x = (a - a) /  a;   // positive zero ( 0.0)
double y = (a - a) / -a;   // negative zero (-0.0)
```
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.
（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.

（4）其他一般情况。这种情况下，我们直接计算斜率即可，计算公式很简单，为：(y_1 - y_0) / (x_1 - x_0)。不过注意到点的坐标表示是int，斜率为double，因此我们还需要一个强制转换来保证计算的精度。

### SLOPE_ORDER

``` 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鼓励初学者开始编写快速算法时先不要担心5个或以上的点共线的情况，而实际上对基本功扎实的同学，从开始便考虑这个问题更为合适；
• checklist提到`compare()`和FastCollinearPoints类可以完全避免浮点数用整形运算实现，我想到的唯一符合要求（Point.java注释中规定不得依赖`toString()`）的方法是，对Point类的`compareTo()`方法返回值增加意义（不单纯返回正负1），以获取两点的坐标之差（因题目给定坐标取值范围0-32767，可在返回值低两位字节存储x坐标差， 高两位字节存储y坐标差），再利用坐标差判断斜率是否相等。虽依然完全符合题目要求，但已有一点奇技淫巧之嫌，并且不一定能够通过autograder（评分时会替换Point类去测试FastCollinearPoints），不多讨论。（更新：此方法已确定违反FastCollinearPoints的API。）