A topographic map is a two-dimensional representation of a terrain, usually utilizing contour lines to represent changes in elevations. A digital representation of a topographic map samples elevations at regular intervals, essentially representing the continuous terrain as a two-dimensional grid of discrete elevations. The National Oceanic and Atmospheric Administration maintains a large database of topographic maps, and even provides a free tool for generating digitized topographic maps.

Suppose you are given a digitized topographic map (i.e., a 2-D grid of elevations) and wish to cross the terrain moving from west to east (i.e., left to right). As a hiker, you might prefer paths that avoid large changes in elevation, since steep climbs or descents can be difficult. For this assignment, you will implement a greedy algorithm for choosing a path across a map, always selecting the next step that represents the smallest change in elevation. For example, consider the following 5x4 map:

    1000    1200    1150    1175
    
     900    1000    1100    1300
     
    1000    1100    1050    1350
    
    1200    1325    1400    1250
    
    1150    1100    1000    1100

If the hiker begins in the third row of the first column, she has three choices for the next step: moving northeast (from 1000 meters to 1000 meters), east (from 1000 meters to 1100 meters), or southeast (from 1000 meters to 1325 meters). Since northeast results in no change in elevation, the greedy approach will choose this step. From there, there are three choices for the next step: northeast (1000 → 1150), east (1000 → 1100), or southeast (1000 → 1050). The southeast choice represents the smaller change in elevation, so it is selected. Similarly, the last step will be southeast. If there are ever ties in the elevation changes, preference should be given to moving directly east. If the northeast and southeast options tie for the lowest elevation change, the choice whose row is closer to the center should be selected. For example, starting in the first column of the fourth row, the northeast and southeast choices have identical elevations. In this case, northeast would be selected, since its row is closer to the map center.

As is the case with many greedy algorithms, this approach is not guaranteed to find the least-cost path in terms of elevation changes. In this example, the path 1000 → 1000 → 1150 → 1175 would be better than the greedy path. However, the greedy approach is reasonably effective at generating good paths across the terrain.

You are given three classes. The DrawingPanel class, written by Marty Stepp at the University of Washington, can be used to draw images in a Java window. The TopoMap class represents a 2-dimensional topographic map, and TopoDriver is a driver class for reading in a map from a file and drawing it in a DrawingPanel. For example, the screenshot below displays terrain from the Rocky Mountains in Colorado, with brighter shades corresponding to higher elevations.

1. Currently, the draw method of the TopoMap class assumes that the elevations will be between 0 and 10,000 meters. Any elevation below or above that range is treated as 0 or 10,000, respectively. When drawn, each elevation scaled to grayscale values in the range 0 to 255. For example, an elevation of 1000 meters would scale to 255*(1000/10000) = 25. Since most locations on earth are toward the bottom of 0-10,000 elevation range, the resulting image will tend to be very dark. You are to add methods to the class that identify the lowest and highest elevations in the current map. Then, modify your draw method to scale the elevations to that range in order to get the maximum contrast when displaying the map. For example, the lowest and highest elevations in the above map are 900 and 1400 meters, respectively. This defines an elevation range of only 500 meters from low to high. Since 900 is at the bottom of that range, it would scale to a grayscale value of 255*(0/500) = 0. An elevation of 1150 meters would scale to a grayscale value of 255*(250/500) = 127. An elevation of 1400 meters would scale to a grayscale value of 255*(500/500) = 255.

   Once you have modified the draw method to scale the elevations correctly, you can test it on a variety of actual maps: small.dat, medium.dat, large.dat and huge.dat.

   
   

2. Next, define a class named PathFinder whose structure is given below:

   public class PathFinder { /** * Constructs a PathFinder object with the given topographical map. * @param topo the map in which paths are to be found */ public PathFinder(TopoMap topo) { ... } /** * Draws a greedy path from the west edge to the east edge of the map. * @param g the graphics object in which the path will be drawn * @param row the starting row of the path (column is assumed to be 0) * @param pathColor the color in which the path is drawn (e.g., Color.GREEN) * @return the sum of all elevation changes along the path */ public int drawGreedyPath(Graphics g, int row, Color pathColor) { ...} /** * Draws all west->east greedy paths in green and highlights the minimal cost path in red. * @param g the graphics object in which the paths will be drawn */ public void drawAllPaths(Graphics g) { ... } }

   The drawGreedyPath method should draw a path on the map using the greedy approach outlined above. It should start in column 0 and the specified row, and draw the path in the specified color (e.g., Color.RED or Color.GREEN). To set the color and draw each pixel in the path, you will need to call the setColor and fillRect methods of the Graphics class. Example calls to these methods can be found in the TopoMap draw method.

   The drawAllGreedypaths method should repeatedly call the drawGreedypath method with each successive row as starting point. It should also highlight the optimal greedy path in red. That is, it should identify which of all the greedy paths has the lowest sum of all elevation changes and redraw that path in red.

   Once you have implemented this class, modify the TopoDriver to display all of the greedy paths on the map. For example: