Programming Assignment 3 : Pattern Recognition

这周的这个问题是在给定一系列的点中寻找多点共线的模式。

计算机视觉重要的两个部分：特征检测(Feature Dectection)和模式识别(Pattern Recognition)。特征检测提取出图片的重要特征，模式识别发掘出这些特征中的模式。这里探究的点共线的问题在现实生活中也有很多应用，比如统计数据分析。

Problem. 从二维平面上的N个互不相同的点中，绘制出每个(最多)连接的4个或4个以上点集合的线段。

Point data type. 给定的Point类型的API

public class Point implements Comparable<Point> {
       public final Comparator<Point> SLOPE_ORDER;        // compare points by slope to this point

       public Point(int x, int y)                         // construct the point (x, y)

       public   void draw()                               // draw this point
       public   void drawTo(Point that)                   // draw the line segment from this point to that point
       public String toString()                           // string representation

       public    int compareTo(Point that)                // is this point lexicographically smaller than that point?
       public double slopeTo(Point that)                  // the slope between this point and that point
}

draw(), drawTo(), toString()方法已经实现好了，需要实现compareTo(),slopeTo(),SLOPE_ORDER comparator.

compareTo(): 是比较按照y轴坐标排序。如果点(x0,y0)<(x1,y1),那么y0<y1，或者y0=y1,x0<x1.

slopeTo: 返回两个点的斜率。(y1-y0)/(x1-x0), 水平线段的斜率为Positive Zero, 垂直线段的斜率为Positive Infinity, 退化成一个点的线段斜率为Negative Infinity

SLOPE_ORDER comparator: 用来进行斜率的比较排序。使用一个调用点(x0, y0)，如果(x1,y1)小于(x2,y2),当且仅当(y1-y0)/(x1-x0)小于(y2-y0)/(x2-x0)。这里直接调用slopeTo(), 水平，垂直，退化情况也已经考虑在里面了。

Brute force. 暴力的方法来寻找p,q,r,s这样的4个点在一条直线上共线。先对所有的点进行排序，枚举p,q,r,s，判断p-q, p-r, p-s是否斜率相同，如果找到了，那么我们就直接从p到s连接一条直线。时间复杂度最差为N^4,使用的空间比例为N。

int N = points.length;
Arrays.sort(points);
//BruteForce Implementation
for (int ip = 0; ip < N; ip++) {
    Point p = points[ip];
    for (int iq = ip + 1; iq < N; iq++) {
        Point q = points[iq];
        for (int ir = iq + 1; ir < N; ir++) {
            Point r = points[ir];
            for (int is = ir + 1; is < N; is++) {
                Point s = points[is];
                if (p.slopeTo(q) == p.slopeTo(r) 
                        && p.slopeTo(q) == p.slopeTo(s)) {
                    p.drawTo(s);
                    StdOut.println(p.toString() + " -> " 
                                       + q.toString() + " -> " 
                                       + r.toString() + " -> " 
                                       + s.toString());
                }
            }
        }
    }
}

A faster, sorting-based solution. 给一个点p, 对于其他的所有点，按照它们与p的斜率进行排序，那么如果存在相邻的3个点或以上的斜率相等，那么它们就共线。

这样算法只需要枚举所有的origin点(p点)，然后把剩余点按照origin点的斜率排序，然后去在排序后的点中寻找是否有共线，复杂度为N(枚举)+NlogN(排序)+N(遍历查找)，要求使用的空间比例为N。

注意统计时候不要出现共线的子线段和同一共线线段输出多次，这里使用compareTo()比较点的位置关系来避免。

Sample data files 里面有很多输入的例子可以拿来做测试。

总的来说这三次的Assignment都不是特别难，但是做的时候一定要认真认真认真啊，解决问题的第一步就是要认真阅读题目说明和checklist，弄明白未知是什么？条件是什么？已知是什么？思考怎么来实现？是否有可以使用的例子？每次的不认真造成怒交n次才能换回个100分，真是惨不忍睹。记下来，鞭策自己，不断总结提高。