辅导R程序、辅导留学生R、R程序辅导讲解、辅导R报告

Part 2 (55 points)

For this question we will explore the world of video game graphics. To achieve the highest fidelity graphics possible it is important that the graphics are computed as efficiently as possible. In part, this means not wasting any time rendering models that cannot be seen from the player's current position and orientation. It helps to be able to quickly determine which models can be seen and which cannot so you don't use any processing power rendering the unseen models.

This general problem with 3d polygon-based models is very difficult, but we can work with a simplified version of this problem. For this homework we will make several simplifying assumption. First, instead of 3d models we will assume each model is represented as a single line on a 2d plane represented by y = mx + b. We will also assume the player is at a position such that y = ∞ and looking in the negative y direction (ie. The player is looking down from a very high vantage point). Your task is to determine which lines can be seen by the player and therefore should be rendered, at least in part.

More formally, you are given a set of n lines L where each li ∈ L is represented by it's slope and y-intercept as mi and bi respectively. Return all i such that ∃x ∀j≠i mix + bi > mjx + bj

You can assume that there are no points where 3 or more lines intersect, there are no vertical lines, and no 2 lines are parallel.

Give an O(nlog(n)) runtime algorithm that finds the set of visible lines, prove the correctness of your algorithm, and analyze its runtime.

Part 2 grading:

•[10 points] Algorithm: Your algorithm generally has a correct idea and has a runtime of O(nlog(n))

•[20 points] Correctness Proof: Your algorithm is correct on all inputs, has a runtime of O(nlog(n)), and your proof of correctness is logically sound and complete

•[5 points] Runtime Analysis: Your algorithm has a runtime of O(nlog(n)) and you correctly analyzed the runtime of your algorithm

•[20 points] Implementation: You correctly implemented your algorithm in code and the implementation is correct on all inputs with runtime O(nlog(n))

Submission (algorithm): Submit your algorithm, proof of correctness, and runtime analysis for part 2 as a pdf file to homework 4 part 2 - algorithm on AutoLab

________________________________________

Submission (implementation): Submit your coded implementation of your algorithm as a zip file to homework 4 part 2 - implementation on AutoLab. This zip file must contain the following:

•A Makefile. This makefile will be called exactly once during grading

•A bash script named "run.sh" that takes 2 command line parameters [inputFilename] and [outputFilename]. This script will be called with each of the testing inputs during grading. You can assume that make was called before any run.sh calls

Data Format:

•The input file will be a csv file with n lines where each line represents one graphical line in the format "id,m,b"

oSample lines.csv (you may have to right click and save-as)

•Your output file wile be a text/csv file where each line contains the id of a line that can be seen by the player. The ids can be listed in any order