Coursera Algorithms Programming Assignment 3: Pattern Recognition （100分）
2024-09-02 05:24:38
题目原文详见http://coursera.cs.princeton.edu/algs4/assignments/collinear.html
程序的主要目的是寻找n个points中的line segment，line segment的要求就是包含不少于4个点。
作业包含三部分程序实现：
一、Point
compareTo()用来比较本节点this与其他节点that的大小：假如this节点坐标(x0, y0)，that节点坐标(x1, y1)，只有y0 < y1或(y0==y1 && x0<x1)的时候this < that
slopeTo()用来计算that节点到本节点this的斜率，计算方法为(y1 − y0) / (x1 − x0)，特别注意的是，x0 != x1 && y0==y1时，slople为0，x0==x1 && y0!=y1时，slople应为positive infinity，x0==x1 && y0==y1时，slope应为negative infinity，
slopeOrder()用来返回比较器，这个比较器的参照点是本节点p0(x0, y0)，如果两个待比较节点分别是p1(x1, y1)和p2(x2, y2)，此比较器的设计要求是当p1相对于p0的斜率大于p2相对于p0的斜率时，p1>p2。比较器主要在排序方法中使用
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) {
/* YOUR CODE HERE */
int x0 = this.x;
int y0 = this.y;
int x1 = that.x;
int y1 = that.y;
if (x0 == x1 && y0 == y1)
return Double.NEGATIVE_INFINITY;
else if (x0 == x1)
return Double.POSITIVE_INFINITY;
else if (y0 == y1)
return +0.0;
else
return (y1 - y0) / (double)(x1 - x0);
} /**
* 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
*/
public int compareTo(Point that) {
/* YOUR CODE HERE */
int x0 = this.x;
int y0 = this.y;
int x1 = that.x;
int y1 = that.y;
if (y0 == y1) {
if (x0 == x1)
return 0;
else if (x0 > x1)
return 1;
else
return -1;
} else if (y0 > y1)
return 1;
else
return -1;
} /**
* 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() {
/* YOUR CODE HERE */
return new SlopeOrder(this);
}
/**
* 此comparator提供两个点关于参照点的比较方法，主要供排序方法使用
* invokePoint就是参照点，两个待比较的Point的大小，这就是排序方法中要用的排序依据
* @author evasean www.cnblogs.com/evasean/
*
*/
private class SlopeOrder implements Comparator<Point>{
private final Point p0;
public SlopeOrder(Point invokePoint){
this.p0 = invokePoint;
}
@Override
public int compare(Point o1, Point o2) {
// TODO Auto-generated method stub
double slope1 = p0.slopeTo(o1);
double slope2 = p0.slopeTo(o2);
return Double.compare(slope1, slope2); //double不推荐用==直接比大小，采用这种方式比较好
}
} /**
* 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
*/
public String toString() {
/* DO NOT MODIFY */
return "(" + x + ", " + y + ")";
} /**
* Unit tests the Point data type.
*/
public static void main(String[] args) {
/* YOUR CODE HERE */
Point p1 = new Point(0, 0);
Point p2 = new Point(1, 1);
System.out.println("p1.compareTo(p2)=" + p1.compareTo(p2));
System.out.println("p1.slopeTo(p2)=" + p1.slopeTo(p2));
Point p3 = new Point(0, 4);
System.out.println("p1.slopeTo(p3)=" + p1.slopeTo(p3));
Point p4 = new Point(4, 4);
System.out.println("p3.compareTo(p4)=" + p3.compareTo(p4));
System.out.println("p3.slopeTo(p4)=" + p3.slopeTo(p4));
Point p5 = new Point(0, 0);
System.out.println("p1.slopeTo(p5)=" + p1.slopeTo(p5));
}
}
二、Brute force
这个类很简单，直接看代码
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;
/**
* @author evasean www.cnblogs.com/evasean/
*/
public class BruteCollinearPoints {
private int segNum;
private Point[] points; //提交作业时提示输入的给构造函数的数组内容不能发生改变，故类中加个数组将输入参数存起来
private ArrayList<LineSegment> segmentList= new ArrayList<LineSegment>(); public BruteCollinearPoints(Point[] inpoints) {
if (inpoints == null)
throw new IllegalArgumentException("Constructor argument Point[] is null!");
// finds all line segments containing 4 points
for (int i=0;i<inpoints.length;i++) {
if (inpoints[i] == null)
throw new IllegalArgumentException("there is null in constructor argument");
}
points = new Point[inpoints.length];
for (int i=0;i<inpoints.length;i++) {
points[i] = inpoints[i];
}
Arrays.sort(points); //对本对象的私有数组进行排序
for (int i=0;i<points.length-1;i++) {
if (points[i].compareTo(points[i+1]) == 0) // 与前一个元素相等
throw new IllegalArgumentException("there exists repeated points!");
}
//作业提交时提示随机穿插顺序调用numberOfSegments()和segment()方法返回结果要求稳定
//那么构造函数中就要把LineSegment找好
findLineSegment(points);
} /**
* 按照作业要求用四层循环来做
* @param points
*/
private void findLineSegment(Point[] points) {
int pNum = points.length;
for (int i = 0; i < pNum - 3; i++) { // i不需要遍历最后三个节点，因为至少四个节点才能组成LineSegment
// 每个comparator需要占据额外空间，总共需要n-4个Comparator<Point>的额外空间
Comparator<Point> comparator = points[i].slopeOrder();
for (int j = i + 1; j < pNum - 2; j++) {
if (points[j].compareTo(points[i]) == 0)
continue; // 相同point直接跳过
for (int l = j + 1; l < pNum - 1; l++) {
if (points[l].compareTo(points[i]) == 0)
continue;
if (points[l].compareTo(points[j]) == 0)
continue;
if (comparator.compare(points[j], points[l]) == 0) { // point[j]和point[l]相对于point[i]的斜率相等
for (int m = l + 1; m < pNum; m++) {
if (points[m].compareTo(points[i]) == 0)
continue;
if (points[m].compareTo(points[j]) == 0)
continue;
if (points[m].compareTo(points[l]) == 0)
continue;
if (comparator.compare(points[l], points[m]) == 0) {
// point[l]和point[m]相对于point[i]的斜率相等时，i、j、l、m 四点可以组成一个linesegment
// 每个LineSegment需要占据一份额外空间
LineSegment seg = new LineSegment(points[i], points[m]);
segmentList.add(seg);
}
}
}
}
}
}
segNum = segmentList.size(); } public int numberOfSegments() {
// the number of line segments
return segNum;
} public LineSegment[] segments() {
// the line segments
//作业提交时，提示要求多次调用segments()方法返回的应该是不同的对象
LineSegment[] segments = new LineSegment[segNum];
int i = 0;
for(LineSegment seg : segmentList){
segments[i++] = seg;
}
return segments;
} public static void main(String[] args) {
// read the n points from a file
In in = new In(args[0]);
//In in = new In("collinear/input8.txt"); //本地测试使用
int n = in.readInt();
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
int x = in.readInt();
int y = in.readInt();
points[i] = new Point(x, y);
} // draw the points
StdDraw.enableDoubleBuffering();
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
StdDraw.setPenColor(StdDraw.RED);
StdDraw.setPenRadius(0.01);
for (Point p : points) {
p.draw();
}
StdDraw.show(); // print and draw the line segments
BruteCollinearPoints collinear = new BruteCollinearPoints(points);
for (LineSegment segment : collinear.segments()) {
StdOut.println(segment);
segment.draw();
}
StdDraw.show();
}
}
三、A faster, sorting-based solution
这个类的设计思想题目中已经描述的很详细了，主要就是以下四点：
- 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.
这个算法的性能瓶颈就在于第三点的排序，更详细的设计思路我直接写在代码注释里。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map; import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdOut;
/**
* @author evasean www.cnblogs.com/evasean/
*/
public class FastCollinearPoints { private Point[] points; //提交作业时提示输入的给构造函数的数组内容不能发生改变，故类中加个数组将输入参数存起来
private final LineSegment[] segments;
private int segNum; private List<PointPair> pointPairList; //存储构成LineSegment的起点和终点Point对
/**
* LineSegment类不允许变动，但是可使用灵活度受限，自己新加个内部类使用
* 本类用来存储可构成LineSegment的起点和终点point对
* 由于在遍历过程中会存在包含关系的起点和终点point对，仅仅靠LineSegment类识别包含关系的效率会很低
* 此类中加了slope来记录就可以很大的提高效率了，因为一个点和一个斜率就确定了一条直线
* 不需要再进行额外比较和计算
* 因为由于PointPair是对points从前到后遍历产生的，所以如果两个PointPair存在包含关系，那么
* 这两个PointPair中largePoint和slope一定相等
* 但smallPoint不相等，smallPoint更小的那个PointPair包含了另一个PointPair
* 这是LineSegment去重的关键
* @author evasean www.cnblogs.com/evasean/
*/
private class PointPair{
private final Point smallPoint;
private final Point largePoint;
private final double slope;
public PointPair(Point smallPoint, Point largePoint){
this.smallPoint = smallPoint;
this.largePoint = largePoint;
this.slope = largePoint.slopeTo(smallPoint);
}
public Point getLargePoint(){
return this.largePoint;
}
public Point getSmallPoint(){
return this.smallPoint;
}
public double getSlope(){
return this.slope;
}
public int compareTo(PointPair that) {
Point l1 = this.getLargePoint();
Point l2 = that.getLargePoint();
double s1 = this.getSlope();
double s2 = that.getSlope();
if(l1.compareTo(l2) > 0) return 1;
else if(l1.compareTo(l2) < 0) return -1;
else{
if(s1>s2) return 1;
else if(s1<s2) return -1;
else return 0;
}
}
/**
* 判断PointPair中的包含关系时需要用到比较器
* 此比较器是以largePoint为比较的主要元素，slope为次要元素
* smallPoint不参比较大小的考核，仅仅在两个PointPair相等时用作判断包含关系之用
* 两个PointPair pp1 和 pp2中
* if pp1.largePoint > pp2.largePoint --> pp1 > pp2
* else if pp1.largePoint < pp2.largePoint --> pp1 < pp2
* if pp1.largePoint == pp2.largePoint && pp1.slope > pp2.slope --> pp1 > pp2
* if pp1.largePoint == pp2.largePoint && pp1.slope < pp2.slope --> pp1 < pp2
* if pp1.largePoint == pp2.largePoint && pp1.slope == pp2.slope --> pp1 == pp2
* @return
*/
public Comparator<PointPair> pointPairComparator() {
return new PointPairComparator();
}
private class PointPairComparator implements Comparator<PointPair>{
@Override
public int compare(PointPair pp1, PointPair pp2) {
// TODO Auto-generated method stub
Point l1 = pp1.getLargePoint();
Point l2 = pp2.getLargePoint();
double s1 = pp1.getSlope();
double s2 = pp2.getSlope();
if(l1.compareTo(l2) > 0) return 1;
else if(l1.compareTo(l2) < 0) return -1;
else{
return Double.compare(s1, s2); //double元素用Double.compare进行比较更精确
}
}
}
} public FastCollinearPoints(Point[] inpoints) {
// finds all line segments containing 4 or more points
if (inpoints == null)
throw new IllegalArgumentException("Constructor argument Point[] is null!");
// finds all line segments containing 4 points
for (int i=0;i<inpoints.length;i++) {
if (inpoints[i] == null)
throw new IllegalArgumentException("there is null in constructor argument");
}
points = new Point[inpoints.length];
for (int i=0;i<inpoints.length;i++) {
points[i] = inpoints[i];
}
Arrays.sort(points); //对本对象的私有数组进行排序
for (int i=0;i<points.length-1;i++) {
if (points[i].compareTo(points[i+1]) == 0) // 与前一个元素相等
throw new IllegalArgumentException("there exists repeated points!");
}
//作业提交时提示随机穿插顺序调用numberOfSegments()和segment()方法返回结果要求稳定
//那么构造函数中就要把LineSegment找好
findPointPairForLineSegment(points);
segments = generateLineSegment();
} /**
* 寻找满足LineSegment的PointPair
* @param points
*/
private void findPointPairForLineSegment(Point[] points){
int pNum = points.length;
pointPairList = new ArrayList<PointPair>();
for (int i = 0; i < pNum - 3; i++) { //i不需要遍历最后三个节点，因为至少四个节点才能组成LineSegment
if(points[i]==null)
throw new IllegalArgumentException("there is null in constructor argument");
Point origin = points[i]; //i处节点作为相对原点
Point[] tPoints = new Point[pNum-i-1]; //需要用到额外空间来存储本轮i之后的节点根据它们各自与节点i的相对斜率来排序的结果
int tpNum = 0;
for (int j = i + 1; j < pNum; j++) {
tPoints[tpNum++] = points[j];
}
//origin.slopeOrder()这个比较器就是告诉Arrays.sort待排序的那些节点tPoints排序的依据是各自与节点i的斜率
Arrays.sort(tPoints,origin.slopeOrder()); int startPostion = 0; //startPosition用来记录slope相同的point位置区间的起始位置
double slope = origin.slopeTo(tPoints[0]);
Map<Integer,Integer> intervalMap = new HashMap<Integer,Integer>(); //记录slope相同的point位置区间
int curPostion = 1;
for(; curPostion<tpNum; curPostion++){
if(Double.compare(origin.slopeTo(tPoints[curPostion]), slope)==0)
continue;
else{ //遍历至slope不与之前相同的位置
if(curPostion-startPostion >= 3) { //如果大于3，就表示满足了组成LineSegment的条件，记录point位置区间
intervalMap.put(startPostion, curPostion-1);//curPostion-1就是区间终止节点位置
}
slope = origin.slopeTo(tPoints[curPostion]);
startPostion = curPostion; //重置起始节点
}
}
if(curPostion-startPostion >= 3) { //tPoints最后一个节点也可能与前一节点有相同的slope
intervalMap.put(startPostion, curPostion-1);
}
//根据满足条件的区间位置，创建PointPair
for(int key : intervalMap.keySet()){
int value = intervalMap.get(key);
Point[] linearPoints = new Point[value-key+2];
linearPoints[0] = origin;
int l = 1;
while(key<=value){
linearPoints[l++] = tPoints[key++];
}
Arrays.sort(linearPoints);
PointPair pointPair = new PointPair(linearPoints[0], linearPoints[l-1]);
pointPairList.add(pointPair);
}
//清空临时数据，便于垃圾回收
intervalMap.clear();
intervalMap = null;
for(int t=0;t<tPoints.length;t++){
tPoints[t] = null;
}
tPoints = null;
}
}
/**
* 生成LineSegment
* @return
*/
private LineSegment[] generateLineSegment(){
int ppsize = pointPairList.size();
if(ppsize==0) return new LineSegment[0];;
PointPair[] pointPairs = new PointPair[ppsize];
int i = 0;
for(PointPair pp : pointPairList){
pointPairs[i++] = pp;
}
pointPairList.clear();
//根据pointPairComparator比较器所定制的排序依据进行排序，使得存在包含关系的PointPair变成相邻关系
Arrays.sort(pointPairs,pointPairs[0].pointPairComparator());
List<LineSegment> lineSegmentList = new ArrayList<LineSegment>(); PointPair ppls = pointPairs[0];
for(i=1;i<ppsize;i++){
if(ppls.compareTo(pointPairs[i])==0){ //相邻的PointPair相等时，具有更小smallPoint的PointPair区间更大
Point s = pointPairs[i].getSmallPoint();
if(ppls.getSmallPoint().compareTo(s) > 0)
ppls = pointPairs[i];
}else{
LineSegment seg = new LineSegment(ppls.getSmallPoint(),ppls.getLargePoint());
lineSegmentList.add(seg);
ppls = pointPairs[i];
}
}
LineSegment seg = new LineSegment(ppls.getSmallPoint(),ppls.getLargePoint());
lineSegmentList.add(seg); LineSegment[] segments = new LineSegment[lineSegmentList.size()];
segNum = 0;
for (LineSegment ls : lineSegmentList) {
segments[segNum++] = ls;
}
return segments;
} public int numberOfSegments() {
// the number of line segments
return segNum;
} public LineSegment[] segments() {
// the line segments
//作业提交时，提示要求多次调用segments()方法返回的应该是不同的对象
LineSegment[] retseg = new LineSegment[segNum];
for(int i =0 ;i<segNum;i++){
retseg[i] = segments[i];
}
return retseg;
} public static void main(String[] args) {
// read the n points from a file
//In in = new In(args[0]);
In in = new In("collinear/rs1423.txt"); //本地测试使用
int n = in.readInt();
Point[] points = new Point[n];
for (int i = 0; i < n; i++) {
int x = in.readInt();
int y = in.readInt();
points[i] = new Point(x, y);
} // draw the points
StdDraw.enableDoubleBuffering();
StdDraw.setXscale(0, 32768);
StdDraw.setYscale(0, 32768);
// StdDraw.setPenColor(StdDraw.RED);
// StdDraw.setPenRadius(0.01);
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();
}
StdDraw.show();
}
}
最新文章
- 2016huasacm暑假集训训练五 G - 湫湫系列故事——减肥记I
- linux下命令运行目录上程序前面要加./
- springMVC验证码程序
- ubuntu1404_server搭建lamp
- 分享10款功能强大的HTML5/CSS3应用插件
- python生成简单的验证码
- 享元模式（咖啡屋）【java与模式】
- C++ 读取XML文件（tinyXML库的应用）
- C++ new和delete实现原理——new和delete最终调用malloc和free
- GitHub Student Developer Pack创建个人网站
- 教你如何安装配置Windows7系统 IIS IIS7.5本地浏览测试网站 完整版介绍
- 力扣算法题—093复原IP地址
- 【Zabbix】CentOS6.9系统下部署Zabbix-agent
- Window 无法完成请求的更改，找不到引用的汇编，错误代码 0X80073701
- EasyWeChat使用(laravel框架下)
- print2flash文档在线预览应用（java,.net）
- Makefile introduction (very old presentation)
- NOIP2018考前抱佛脚——搜索复习
- 如何在集群中获得处理本次请求的web容器的端口号？
- ubuntu-server-18.04 设置开机启动脚本