———————————————————————————————————–

Topography (Part 1)

In this homework, you will read a set of topographic (landelevation) data into a 2D vector and manipulate the data so that itcan be visualized.

You will write code to read elevation data and produce a filerepresenting an image that, when visualized, displays each positionon the map with a color that represents the position elevation. Thevisualization will produce a picture like the one below:

Program Flow

1. Read the data into a 2D array
2. Find min and max elevation to correspond to darkest andbrightest color, respectively
3. Compute the shade of gray for each cell in the map
4. Produce the output file in the specified format (BMP)

Step 1 – Read the data into a 2D array

Your first goal is to read the values into a 2D array (i.e., amatrix) of ints from the data file. Note: You shoulduse a vector to benefit from the additional runtimechecks.

This data file contains, in plain text, data representing theaverage elevations of patches of land (roughly 700×700 meters) inthe US, stretching from California to Colorado.

Optionally, other input files can be obtained from the NationalOceanic and Atmospheric Administration (Links to an externalsite.)Links to an external site. if you are interested in makingyour own outside of this project. Select an area and download thedata in “ArcGIS ASCII Grid” format.

You can change the extension of the file to .txt to read it astext, or you can open it in Notepad++. You will see that the filecontains a header that contains information about the file: numberof columns (width), number of rows(height), the GPS coordinates of the lower leftcorner of the map, and the size of the cell in degrees. You willwant to extract the width and the height from this header. You canignore the rest of it.

After the header comes a large, space-separated list ofintegers. There are height x width integersrepresenting a height-row bywidth-col grid. Each integer is the averageelevation in meters of each cell in the grid. The data is listed inrow-major order, i.e., the first width numbers forrow 0, then width numbers for row 1, etc.

Step 2 – Find the min and max values

In order to draw the map with a gray scale that indicates theelevation, you will need to determine which scale to use, i.e.,which will be shown as a dark area (with low elevation) and whichones will be shown as bright areas (high elevation.) This means youneed to find the min and maxvalues in the map first, so that you know which values to associatewith the brightest and darkest colors.

You should write two functions for this that scan the entire mapand keep track of the smallest and largest values found so far.

Test this functionality to make sure you’re getting the correctvalues for min and max, beforeyou proceed to implement the rest of the program. You may want tocheck with a friend or colleagues to see if other students aregetting the same min and maxvalues for the provided input file.

Step 3 – Compute the color for each part of themap

The input data file contains the elevation value for each cellin the map. Now you need to compute the color (in a gray scalebetween white and black) to use to represent these evaluationvalues. The shade of gray should be scaled to the elevation of themap.

Traditionally, images are represented and displayed inelectronic systems (such as TVs and computers) through the RGBcolor model, an additive color model in which red, green, and bluelight are added together in various ways to reproduce a broad arrayof colors. In this model, colors are represented through threeintegers (R, G, and B) values between 0 and 255. For example, (0,0, 255) represents blue and (255, 255, 0) represents yellow. In RGBcolor, if each of the three RGB values are the same, we get a shadeof gray. Thus, there are 256 possible shades of gray from black(0,0,0) to middle gray (128,128,128), to white (255,255,255).

To make the shade of gray, you should use themin and max values in the 2Darray to scale each integer (elevation data) to a value between 0and 255 inclusive. For example, if your minimum elevation was 1000and your maximum was 2000, an elevation of 1500 would map to agrayscale value of 127.

int mapRange(int n, int fromLow, int fromHigh, int toLow, int toHigh)

You can come up with a formula for this by finding the distancebetween fromLow and fromHigh, then finding out what percent n is ofthat distance, then multiplying that percentage by the distancebetween toLow and toHigh.

Step 4 – Create the Image

Create a 2D array of rgb pixel values, where r, g, and b are agrayscale value. Create a Bmp object from the provided sourcefiles, assign each grayscale pixel value to correspond to eachelevation value, and then write the Bmp object to a file as shownin lecture. You should then see a beautiful image of the SierraNevada Mountains!

Object-Oriented Design

Use a class called Topograph to organize thedata. The header file is attached below and also written here:

class Topograph{public: ///Constructor. Open a ArcGIS ASCII Grid file ///read the header to assign height and width ///resize v and read elevation data Topograph(string fileName); int getHeight(){return height;} int getWidth(){return width;} ///find min and max elevation values ///call mapRange to convert each elevation to grayscale ///set each bmp(i,j) to its grayscale value void drawMap(Bmp& bmp);private: void findMin(); void findMax(); ///scale n from [fromLow:fromHigh] to [toLow:toHigh] int mapRange(int n, int fromLow, int fromHigh, int toLow, int toHigh); vector<vector<int>> v; int height; int width; int min; int max;};

• From main, construct a Topograph object withthe file name “map_input.txt”.
• Construct a Bmp object with the same heightand width as your Topograph object.
• Call drawMap on your Topograph object and passin the Bmp object as an argument
• Call write on your Bmp objectwith the file name “map.bmp”
• To easily view the image in Windows, type the following to open“map.bmp” with the default image viewer:

system(outputFileName.c_str());

Elevation Data File

map_input.txt

Provided Source Files

• Bmp.h and Bmp.cpp fromlecture.
• They are posted in the M05 Source Files page.
• You do not have to change them.
• Topograph.h

Source Files to Implement

• Topograph.cpp
• main.cpp

Scoring

• Associate all of your source files with a Codeblocks project(.cbp), zip the project folder, including the data files, andupload your .zip file here.
• If you do not have Codeblocks on your machine you will have todo this in the lab
• Don’t worry about Linux for this assignment. We won’t be ableto view the image from the terminal.
• (2 pts) Output the height (rows) and width(columns) of the elevation data file and load the elevations intov
• (2 pts) Output the correctmin and max values
• (6 pts) Write and displaymap.bmp so it matches the file posted above.
• Code that does not build will not receivecredit.

Greedy Walk (Part 2)

There are many contexts in which you want to know the mostefficient way to travel over land. When traveling through mountains(let’s say you’re walking) perhaps you want to take the route thatrequires the least total change in elevation with each step youtake – call it the path of least resistance. Given some topographicdata it should be possible to calculate a “greedylowest-elevation-change walk” from one side of a map to theother.

A “greedy” algorithm is one in which, in the face of too manypossible choices, you make a choice that seems best at thatmoment.

Since our map is in a 2D grid, we can envision a “walk” asstarting in some in some cell at the left-most edge of the map(column 0) and proceeding forward by taking a “step” into one ofthe 3 adjacent cells in the next column over (column 1). Our”greedy walk” will assume that you will choose the cell whoseelevation is closest to the elevation of the cell you’re standingin. (NOTE: this might mean walking uphill or downhill).

The diagrams below show a few scenarios for choosing where totake the next step. In the case of a tie with the forward position,you should always choose to go straight forward. In the case of atie between the two non-forward locations, you should always chooseto go down.

• Case 1: smallest change is 5, go fwd-down
• Case 2: smallest change is 3, go fwd
• Case 3: smallest change is a tie (3), fwd is an option, so gofwd
• Case 4: smallest change is a tie (4), choose fwd-down

Object-Oriented Design

Notice that the header file provided above in part 1 has somefunction prototypes for part 2:

///Draw one greedy path///call moveForward to advance (i,j)///set each bmp(i,j) to color///returns the total sum of the elevation changeint drawGreedyPath(Bmp& bmp, int startingRow, rgb color);///call drawGreedyPath for each startingRow, color red///store the index of the path with lowest elevation change///call drawGreedyPath for the lowest index, color bluevoid drawBestPath(Bmp& bmp);///Advance (i,j) along its greedy path///Choose the right side adjacent index with the lowest elevation change///For a tie, mid has highest priority, then down, then up///i + 1 is down, i – 1 is up///j + 1 is forward///Be careful if i is on the upper or lower edgevoid moveForward(int& i, int& j);

Step 1 – Draw a lowest-elevation-change path from somerow

Implement the drawGreedyPath method. Note thatthis method does two things: 1) it draws the path, 2) it calculatesand returns the total elevation change on that path.

The method should draw a line by drawing pixels in a differentcolor on top of the existing drawing. The path should be drawngoing West-to-East, starting from the given row using the greedylowest-elevation-change technique described earlier.

You will need to do the following things in some order.

1. Starting from the given row, and column 0, color it red (orwhatever color you want to draw your path).
2. Write a loop that generates every possible column across themap (you start at column 0, but column 1 is the first column youneed to make choice about where to step). For each column you willdecide which row to take your next “step” to – fwd, fwd-and-up, orfwd-and-down – using the greedy choice strategy described.
3. Color the chosen location to step to red (or whatever color youchoose).
4. Use a variable that keeps track of the ‘current row’ you’re on,and update it each time you take a step forward – the row may staythe same, or go up or down by 1 depending how you walk.
5. Use fabs to get the absolute value of thedifference between two elevations.
6. Continue finding the lowest neighboring cell and coloring itred as you go.
7. Keep a running total of the total elevation change that wouldbe ‘experienced’ by a person walking this path. Since we consideran elevation change the absolute value (i.e. going ‘uphill’ 10meters is the same amount of change as going ‘downhill’ 10 meters)this running total will be non-decreasing and will end up being apretty large positive number

Use the moveForward to choose and advance therow and column to the next cell.

When you’re done you should see a line tracing the lowestelevation-change path from west to east.

Step 2 – find the lowest elevation path for the wholemap

Implement the drawBestPath method which callsdrawGreedyPath for each row, then finds theoverall lowest-elevation-change path and draw it.

You will find the lowest-elevation-change route by noting thatdrawGreedyPath returns the total elevation changefor a path starting at a given row.   If you write a loopthat generates every possible starting row and calldrawGreedyPath for each, you should find thelowest route for the whole map. Since that method also draws all ofthe routes it’s good feedback that the method is running properly.You should end up with something that looks like the imageabove.

From main, call drawBestPathfrom your Topograph object and pass in theBmp object as an argument. Write to“map2.bmp” with your Bmp object,and use the system call to display it.

We were unable to transcribe this imageWe were unable to transcribe this imageWe were unable to transcribe this imageWe were unable to transcribe this image30I1 2900 2852 280B 279 2818 2972 29372886 286028302748 2937 2959 2913 286A 2791 2742 299928BB2986 2910 2821l 2754 29092BI6 28932997 2962 2798 das dange dang dhng dang 09 9 100 1077 105 5 109 9 100 97 3 105 5 97 3 100 97 3 105 5 964 00 1055 104 4 Show transcribed image text

30I1 2900 2852 280B 279 2818 2972 29372886 286028302748 2937 2959 2913 286A 2791 2742 299928BB2986 2910 2821l 2754 29092BI6 28932997 2962 2798
das dange dang dhng dang 09 9 100 1077 105 5 109 9 100 97 3 105 5 97 3 100 97 3 105 5 964 00 1055 104 4