首页 > 代码库 > Programming Assignment 3 : Pattern Recognition
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 Implementationfor (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 里面有很多输入的例子可以拿来做测试。