CS25100: Data Structures and Algorithms, Spring 2011
Project 3, Pattern Recognition--------------------------------------------------------------------------------Description
Write a program to recognize line patterns in a given set of points. 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, for example statistical data analysis. The problem. Given a set of N points in the plane, draw every line segment that connects 4 or more distinct points in the set.
Brute force. Write a program Brute.java that examines 4 points at a time and checks if they all lie on the same line segment, printing out any such line segments to standard output and plotting them using standard draw. To get started, you may use the data type Point.java and the client program PointPlotter.java which reads in a list of points from standard input and plots them. You will need to supply additional methods in Point.java in order to support the brute-force client, including checking whether three or four points lie on the same line. Be sure to implement at least the following API: public class 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 static boolean areCollinear(Point p, Point q, Point r) // are the three points collinear?
public static boolean areCollinear(Point p, Point q, Point r, Point s) // are the four points collinear?
public String toString() // string representation
}You will also need to add a user-defined Comparator to the Point data type for the second part of the assignment.
A sorting solution. Reably, 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 angle it makes with p. Sort the points according to the angle they makes with p. Check if any 3 (or more) adjacent points in the sorted order have equal angles with 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 make the same angle with p are collinear, and sorting brings such points together. The algorithm is fast because the bottleneck operation is sorting.
Write a program Fast.java that implements this algorithm using Arrays.sort() and a user-defined Comparator for Point objects. Your program should use space proportional to N. Input format. The data file consists of an integer N, followed by N pairs of integers (x, y), each between 0 and 32,767. % more input6.txt % more input8.txt
6 8
19000 10000 10000 0
18000 10000 0 10000
32000 10000 3000 7000
21000 10000 7000 3000
1234 5678 20000 21000
14000 10000 3000 4000
14000 15000
6000 7000Output format. Print to standard output the line segments that your program discovers in the format below (number of collinear points in the line segment, followed by the points in the order in which they appear on the line segment). % java Brute < input8.txt
4: (10000, 0) -> (7000, 3000) -> (3000, 7000) -> (0, 10000)
4: (3000, 4000) -> (6000, 7000) -> (14000, 15000) -> (20000, 21000) % java Fast < input6.txt
5: (14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000) Also, plot the points and the line segments, using standard draw. (Do not change the pen color with setPenColor() or the pen size with setPenRadius().) Using the Point data type supplied, p.draw() draws the point p and p.drawTo(q) draws the line segment from p to q. Before drawing, use setXscale(0, 32768) and setYscale(0, 32768) to rescale the coordinate system.
For full credit, do not print permutations of points on a line segment (e.g., if you output p→q→r→s, do not also output s→r→q→p or p→r→q→s). Also, for full credit in Fast.java, do not print or plot subsegments of a line segment containing 5 or more points (e.g., if you output p→q→r→s→t, do not also output p→q→s→t or q→r→s→t); you may print out subsegments in Brute.java. You should have exactly one line of output and one call to drawTo() for each line segment discovered. Report
Submit a report (PDF file) answering the following questions:
Estimate (using tilde notation) the running time (in seconds) of your two programs as a function of the number of points N. Provide a formal analysis about why you consider the formula provided is correct; you can use a style similar to the proof sketch format used in several sections of the book.
Show, using empirical evidence, the execution time behavior of both versions (brute VS fast). Provide at least a plot and table where you compare the running time observed for different values of N (for example, 10, 20, 50, 100, 200, 400, 1000, 2000, 4000, 10000, etc). You are allowed to test different values of N as long as they don't exceed around 200 seconds of running time. The table should contain three columns: N, brute-force time and fast time. The plot should have the x-axis be the N value and the y-axis will represent running times, where you will show two lines (one for each version).
Estimate how long it would take to solve an instance of size N = 1,000,000 for each of the two algorithms using your computer.
Submission
Submit your solution before Feb 25 11:59pm. turnin will be used to submit assignments.
Create a folder where you will include all source code used and libraries in that folder. The report should be included in that folder too. Finally, provide a README file with your name, instructions to compile and run your code (Please do not use absolute paths, or at least tell how to modify it to compile without problems) and anything you would like us to know about your program (like errors, special conditions, etc). After logging into lore.cs.purdue.edu, please follow these steps to submit your assignment: Make a directory named yourName_yourSurname and copy all of your files there.
While in the upper level directory (if the files are in /homes/pangin/pelin_angin, goto /homes/pangin), execute the following command:
%turnin -c cs251 -p project3 your_folder_name(e.g. turnin -c cs251 -p project3 pelin_angin) Keep in mind that old submissions are overwritten with new ones whenever you execute this command. You can verify the contents of your submission by executing the following command:
%turnin -v -c cs251 -p project3Do not forget the -v flag here, as otherwise your submission would be replaced with an empty one. Based on an assignment developed by Bob Sedgewick and Kevin Wayne.
Copyright © 2008.
Project 3, Pattern Recognition--------------------------------------------------------------------------------Description
Write a program to recognize line patterns in a given set of points. 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, for example statistical data analysis. The problem. Given a set of N points in the plane, draw every line segment that connects 4 or more distinct points in the set.
Brute force. Write a program Brute.java that examines 4 points at a time and checks if they all lie on the same line segment, printing out any such line segments to standard output and plotting them using standard draw. To get started, you may use the data type Point.java and the client program PointPlotter.java which reads in a list of points from standard input and plots them. You will need to supply additional methods in Point.java in order to support the brute-force client, including checking whether three or four points lie on the same line. Be sure to implement at least the following API: public class 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 static boolean areCollinear(Point p, Point q, Point r) // are the three points collinear?
public static boolean areCollinear(Point p, Point q, Point r, Point s) // are the four points collinear?
public String toString() // string representation
}You will also need to add a user-defined Comparator to the Point data type for the second part of the assignment.
A sorting solution. Reably, 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 angle it makes with p. Sort the points according to the angle they makes with p. Check if any 3 (or more) adjacent points in the sorted order have equal angles with 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 make the same angle with p are collinear, and sorting brings such points together. The algorithm is fast because the bottleneck operation is sorting.
Write a program Fast.java that implements this algorithm using Arrays.sort() and a user-defined Comparator for Point objects. Your program should use space proportional to N. Input format. The data file consists of an integer N, followed by N pairs of integers (x, y), each between 0 and 32,767. % more input6.txt % more input8.txt
6 8
19000 10000 10000 0
18000 10000 0 10000
32000 10000 3000 7000
21000 10000 7000 3000
1234 5678 20000 21000
14000 10000 3000 4000
14000 15000
6000 7000Output format. Print to standard output the line segments that your program discovers in the format below (number of collinear points in the line segment, followed by the points in the order in which they appear on the line segment). % java Brute < input8.txt
4: (10000, 0) -> (7000, 3000) -> (3000, 7000) -> (0, 10000)
4: (3000, 4000) -> (6000, 7000) -> (14000, 15000) -> (20000, 21000) % java Fast < input6.txt
5: (14000, 10000) -> (18000, 10000) -> (19000, 10000) -> (21000, 10000) -> (32000, 10000) Also, plot the points and the line segments, using standard draw. (Do not change the pen color with setPenColor() or the pen size with setPenRadius().) Using the Point data type supplied, p.draw() draws the point p and p.drawTo(q) draws the line segment from p to q. Before drawing, use setXscale(0, 32768) and setYscale(0, 32768) to rescale the coordinate system.
For full credit, do not print permutations of points on a line segment (e.g., if you output p→q→r→s, do not also output s→r→q→p or p→r→q→s). Also, for full credit in Fast.java, do not print or plot subsegments of a line segment containing 5 or more points (e.g., if you output p→q→r→s→t, do not also output p→q→s→t or q→r→s→t); you may print out subsegments in Brute.java. You should have exactly one line of output and one call to drawTo() for each line segment discovered. Report
Submit a report (PDF file) answering the following questions:
Estimate (using tilde notation) the running time (in seconds) of your two programs as a function of the number of points N. Provide a formal analysis about why you consider the formula provided is correct; you can use a style similar to the proof sketch format used in several sections of the book.
Show, using empirical evidence, the execution time behavior of both versions (brute VS fast). Provide at least a plot and table where you compare the running time observed for different values of N (for example, 10, 20, 50, 100, 200, 400, 1000, 2000, 4000, 10000, etc). You are allowed to test different values of N as long as they don't exceed around 200 seconds of running time. The table should contain three columns: N, brute-force time and fast time. The plot should have the x-axis be the N value and the y-axis will represent running times, where you will show two lines (one for each version).
Estimate how long it would take to solve an instance of size N = 1,000,000 for each of the two algorithms using your computer.
Submission
Submit your solution before Feb 25 11:59pm. turnin will be used to submit assignments.
Create a folder where you will include all source code used and libraries in that folder. The report should be included in that folder too. Finally, provide a README file with your name, instructions to compile and run your code (Please do not use absolute paths, or at least tell how to modify it to compile without problems) and anything you would like us to know about your program (like errors, special conditions, etc). After logging into lore.cs.purdue.edu, please follow these steps to submit your assignment: Make a directory named yourName_yourSurname and copy all of your files there.
While in the upper level directory (if the files are in /homes/pangin/pelin_angin, goto /homes/pangin), execute the following command:
%turnin -c cs251 -p project3 your_folder_name(e.g. turnin -c cs251 -p project3 pelin_angin) Keep in mind that old submissions are overwritten with new ones whenever you execute this command. You can verify the contents of your submission by executing the following command:
%turnin -v -c cs251 -p project3Do not forget the -v flag here, as otherwise your submission would be replaced with an empty one. Based on an assignment developed by Bob Sedgewick and Kevin Wayne.
Copyright © 2008.
项目3，模式识别 -------------------------------------------------- ------------------------------ 说明
写一个程序来识别一组给定的点线图案。 计算机视觉包括视觉图像分析模式和改造现实世界的对象，产生的数据。这一过程通常分为两个阶段：特征检测和模式识别。特征检测包括选择图像的重要特征;涉及模式识别的特征发现模式。我们将探讨一个特别干净的模式识别问题，涉及点和线段。这种模式识别一种出现在许多其他应用，如统计数据分析。 这个问题。给定一个平面上的N点集，每画线段连接的设置4个或更多的不同点。
蛮力。写一个程序Brute.java，用于检查的时间和检查，如果他们都在同一线段位于4分，打印出任何线段到标准输出，使用标准的制定策划的。要开始使用，您可以使用数据类型Point.java和客户端程序PointPlotter.java这一个点，从标准输入读取和情节它们的列表。您需要提供在Point.java其他方法，以支持蛮力客户端，包括检查是否三，四点在同一行的谎言。一定要实现至少以下API： 公共类点{
公共点（智力的x，int y）将/ /构造的点（x，y）的
公共无效的draw（）/ /绘制了这一点
公共无效drawTo（点是）/ /绘制线段从该点到该点
公共静态布尔areCollinear（P点，Q点，点R）/ /是三点共线？
公共静态布尔areCollinear（P点，Q点，点R，S点）/ /是四点共线？
公共字符串的toString（）/ /字符串表示
} 您还需要添加一个用户定义的比较器来点数据的转让第二部分的类型。
一个排序的解决方案。值得注意的是，它有可能解决问题的速度远远超过了蛮力解决上文所述。给定一个点P，下列方法确定p是否在4个或更多参与共线点的集合。 想想为原点磷。 为对方点Q，使得它的角度确定与第 排序点，根据他们的角度，使与体育 检查是否有3个（或更多）在排序顺序相邻的点有平等的角度与体育如果是这样，这些点，再加上磷，共线。
运用这反过来又产生了N点为每个方法一个有效的算法来解决问题。该算法解决了问题，因为点P的提出具有相同的角度共线，并带来了这样的点排序在一起。因为该算法是快速排序操作的瓶颈。
写一个程序实现了该算法Fast.java使用Arrays.sort（）和一个点对象用户定义的比较。你的程序应该使用空间比例为N 输入格式。数据文件包含一个整数N的N对整数（的x，y），其次，在0至32,767元。 ％以上input6.txt％以上input8.txt
6 8
19000 10000 10000 0
0 10000 18000 10000
32000 10000 3000 7000
21000 10000 7000 3000
1234 5678 20000 21000
14000 10000 3000 4000
14000 15000
6000 7000 输出格式。打印到标准输出线段你的程序在下面的格式发现（共线点的线段在它们的顺序线段上的点出现之后，数字）。 ％纯Java的野蛮<input8.txt
4：（10000，0） - >“（7000，3000） - >”（3000，7000）“ - >（0，10000）
4：（3000，4000） - >“（6000，7000） - >”（14000，15000） - >“（20000，21000） ％的Java快速<input6.txt
5：（14000，10000） - >“（18000，10000） - >”（19000，10000） - >“（21000，10000） - >”（32000，10000） 另外，绘制点和线段，使用标准的制订。 （请勿更改与setPenColor（）或具有setPenRadius（笔笔的颜色大小）。）使用点数据类型提供，p.draw（）绘制和p.drawTo点P（Q）的绘制线段从P到Q在绘制之前，使用setXscale（0，32768）和setYscale（0，32768），以重新调整坐标系统。
对于满分，不打印线段上的点的排列（例如，如果你输出P→R的→→q秒，不也输出S→R的→q→p或P→R的→q→s）。此外，在Fast.java满分，不打印或绘制subsegments一行含5分以上（如段，如果你输出P→q→R的→s→吨，不也输出P→q→s →→R的吨或q→s→吨），你可以打印出Brute.java subsegments。 你应该有且只有一个行输出和一个调用drawTo（每个线段）发现。 报告
提交了一份报告（PDF文件）回答下列问题：
估计（使用波浪符号）的运行时间您的两个方案（单位：秒）作为数点全提供一份关于为何你认为该公式提供正式的分析功能是正确的，你可以使用一个风格类似的证明素描格式，用于在该书的几个部分。
显示，采用实证的证据，这两个版本（畜生比快）执行时间的行为。提供至少一个情节，你比较表，其中运行时间的N个不同的值（例如，10，20，50，100，200，400，1000，2000，4000，10000等）的观察。你被允许进行测试，只要他们不超过运行时间约200秒N个不同的值。该表应包含三个列：氮，蛮力时间和快速的时间。该地块应具有的X轴是N值和Y轴的运行时间将代表，在这里您将显示两行（每一个版本）。
估计将需要多长时间来解决这两个使用您的计算机算法每一个大小为N = 1,000,000实例。
提交
提交您的解决方案之前，2月25日晚上11:59。撇开将用于提交任务。
创建一个文件夹，您将包括所有源代码中使用，并在该文件夹库。该报告应包括在该文件夹了。最后，提供您的姓名README文件，指示来编译和运行代码（请不要使用绝对路径，或者至少告诉如何修改它来编译没有问题）和任何你希望我们了解你的程序（如错误，特殊条件等）。 项目建成后lore.cs.purdue.edu记录，请按照下列步骤提交您的作业： 建立一个目录名为yourName_yourSurname和复制你的文件都在那里。
而在上一级目录（如果该文件在/家庭/ pangin / pelin_angin，转到/家庭/ pangin中），执行以下命令：
％撇开- C的cs251 - P的project3 your_folder_name （如撇开- C的cs251 - P的project3 pelin_angin）请记住，每当老意见书与执行此命令的新的覆盖。您可以通过执行以下命令您提交的内容：
％撇开- V的- C的cs251 - P的project3 不要忘了- v标志在这里，否则您的提交将与一空一所取代。 根据由Bob塞奇威克和凯文韦恩开发的任务。
版权所有© 2008。
应该有的，微软好像有专门研究 Linux 的部门，还贡献 Linux 内核代码来着。