Grading

Your inal [MP] Mountain Paths score is                          +                      = max 100 pts

— If you do not submit anything by the initial checkpoint deadline, the most you can get on this assignment is 90%.

Checkpoint I (10 pts)

You must submit by Tuesday, July 12, 2022 23:59 central time and score at least 10% to earn full 10 points. If you do not score at least 10% before this deadline, you will receive 0 points.

You will submit to Mountain Paths - Checkpoint for this 10 points.

Due Date (90 pts)

You must pass ALL test cases correctly to earn full 90 pts.

If your code does not pass all of our test cases, these 90 pts will be prorated → 90 pts * (% what you earned / 100%).

Extra credit deadline

You must submit by 23:59 Champaign local time on Wednesday, July 13, 2022, and score 100% on the entire assignment to earn 5% extra credit for a total of 105%. You are not eligible for this if you missed the checkpoint.

Please review the syllabus for more information about this opportunity.

Learning Objectives and Outcomes

1. Writing classes in the C++ programming language from speciication.

2. Read from and write to iles using ifstream and ofstream respectively; ensure stream integrity is maintained throughout these processes; able to distinguish between diferent stream states.

3. Understand the diferences between argument passing modes (value, reference) in the C++ language and communicate their appropriate usage.

Background

Elevation Dataset

The NOAA provides samples of their elevation dataset in plain text, as a space-separated list of integers values. Each integer              represents the average elevation in meters of a cell in the grid of topological data. This data maps directly onto a square grid in row- major order. For instance, a ile representing a 2 row by 5 column grid would present 10 integer values in some fashion:

This toy example suggests that there is some region in the United States that has been mapped onto a 2 row by 5 column grid. The  sample iles that we provide you with describe the average elevations in 700 meter by 700 meter square patches of land within the United States; each datum describes the average elevation of one of those grid cells in meters. You can acquire additional datasets  from the National Oceanic and Atmospheric Administration (http://maps.ngdc.noaa.gov/viewers/wcs-client/). However, we strongly suggest you formulate some ictional samples by hand for testing purposes.

Your irst goal in this assignment is to translate the ile representation of a data sample into an ElevationDataset object. The data in the ile will be given as a continuous stream of numbers -- there may be or may not be any line breaks in the ile. Notice that the   constructor of this object takes the path to the plain-text ile to be read, as well as the composition of the dataset (i.e., width and    height) that it describes (the width and height are not provided in the ile of data). During the construction of an ElevationDataset object, you must initialize the width_ and height_ members with the values stored in their corresponding parameters, and will         write the elevation data to ElevationDataset object’s data_ member in row-major form. During this process, you should be              recording the minimum and maximum elevation datum values observed in the dataset in min_ele_ and max_ele_ respectively.

While translating the ile to matrix form, you should validate the input from the user. The number of elevation points in the ile should be exactly width * height. If there are too many data points or too few in the ile, you must throw an exception.            Furthermore, if an error results from a formatted-read failure, you must throw an exception. An std::runtime_error with an    adequate description of the exceptional case is sumcient.

Grayscale topological image map formulation

The next step is to construct a grayscale topological image from the elevation data. We do this by scaling our elevation data to        construct an image where high brightness areas represent high elevations and dark regions low elevations. In translating to this      representation, we will encode an elevation datum as a grayscale color using the RGB color model. This model blends together red, green, and blue components to construct colors. When this model is used to present a grayscale color, the red, green, and blue        components take on the same integer value between 0-255 (i.e., the valid color component range, inclusive).

Therefore, in order to calculate the shade of gray for an elevation datum, we must scale that elevation point between 0 and 255. This scaling requires us to leverage the maximum value elevation datum observed in the dataset as well as the lowest. With this information, the shade of gray of any elevation point is calculated as

You should use std::round deined in header to perform the rounding. Pay special attention to the types you are dividing, otherwise information will be lost in the computation.

If the denominator in this equation evaluates to 0 (i.e., max_ele == min_ele), the shade_of_gray should take on 0. The grayscale RGB value for the elevation value’s grid will take on shade_of_gray for the R, G, and B components of the RGB color model. To     represent a color in our program, we create a Color object. For the grayscale image, we construct a GrayscaleImage object that encodes the topological map by housing a std::vector>. For example, given the following data_ from an  ElevationDataset object,

which represents the following colors for each grid position:

Grayscale topological image map overlaid with colored paths

Imagine you are hiking in the Colorado Rockies and would like to know the path of least elevation change (i.e., the path of least         resistance) from one side of the mountain to the other. Given the topological data for the region that you are in, one can calculate    the path of least resistance from one side of the topological image map to the other. In this assignment, a PathImage object will be  initialized with the topological image map, elevation data, and the width and height of the dataset. Starting from each data cell in    the irst (0th) column, a greedy least-elevation-change walk will be calculated from the irst column to the last. The path found from each row will be encoded as a Path object and stored in the PathImage object’s paths_ collection. This will result in a height number of paths stored in the PathImage object. During construction, the PathImage object’s path_image_ is initialized with a copy of the      argument passed to the parameter image. Before construction of the PathImage object has inished, each path will be painted           across path_image_ in red [RGB(252,25,63)], with the path of least overall resistance colored in green [RGB(31,253,13)]. If there are

paths of equal least overall resistance, color green the path begins from the lowest“row”number.

For instance, given a GrayscaleImage object’s image_ encoding the following topological image map:

Notice that there is exactly one path starting from each row in the zeroth column spanning the topological image map. While paths can merge together, each is considered independent from another and will have its own observed elevation change stored in its      representation (Path object). To emphasize, the path with the least overall total change in elevation is colored in green.

Calculating paths: a greedy walk across the image (read carefully!)

We will calculate height_ number of paths through our elevation dataset, ultimately drawing each path upon the topological image map to create a path_image_. To calculate a path, we will“walk”across the elevation data, starting at the cell on the left-most edge (column 0) and proceeding forward by taking a "step" into one of the 3 adjacent cells (if valid -- current_row, current_row + 1,        current_row -1) in the next column over (column 1). As we traverse the image, each step will always be into the next column;           however, the row that we end up in maybe diferent from the one we started our“step”from.

Let's brieHy consider directionality. The top-left corner of our image is at (0, 0) in the vector and bottom-right at (height-1, width-1). North is towards row 0, south towards row height-1. West is towards column 0, east is towards column width-1. Therefore, a              southeast move is towards the bottom-right corner of the image.

Now, let's talk speciics about the greedy walk through the image. We will always choose the cell of least change in elevation. In the case of a tie with the straight-forward position (east direction), choose to go straight forward. If there is a tie between the two non- forward locations, always choose the southeast movement. The following diagrams illustrate a few of these rules:

How do we deine least change in elevation? During our walk, the total elevation change“experienced”by a person walking this  path needs to be maintained and is considered the absolute value of the change in each step summed across the total path. This value will be stored in the Path object’s ele_change_ data member and will be compared against other Path objects values when determining the best path amongst all the paths. How do we encode the path? Using a Path object of course. Given the following image,

we would construct a Path object encoding this traversal as:

Explanation: path_.at(0) says our path starts at row 2 of col 0 in the image; path_.at(1) tells us our row location for col 1 =>  row 1; path_.at(2) => row 2; path_.at(3) => row 3; path_.at(4) => row 4; path_.at(5) => row 4.                                                  Recall that there will be a height_ number of Path objects contained in the PathImage object’s paths_ collection (one for each row  of the dataset). Again, we will use these objects to“paint”paths across the PathImage object’s path_image_. Don’t skip creating the

path objects: we test that you have satisfactorily computed them.                                                                                                                        Notice that our approach in formulating a path constitutes a greedy approach. Each step taken during our walk simply is chosen as  the one that seems best at that instance. This can take us to regions of topography that are rather expensive to traverse, with large changes in elevation. This could have been avoided by considering every path through our dataset from a given row. Such an

approach becomes expensive rather quickly: if we must step into width_ columns to traverse the region, the number of possible paths is close to 3width_. Searching for a solution in this manner does not scale very well, especially considering that we must