PA1: Line of Sight

Objectives

The objective of PA1 is to implement three different algorithms to solve a line of sight problem. As discussed in lecture, given:

• image - A 2D N×N array of floating point numbers (in meters) representing a terrain.
• h - The horizontal distance between adjacent points
• angle - The Sun's angle of elevation

The algorithms must return a 2D N×N boolean array where:

• An entry [i,j] is True if the point [i,j] in the terrain is in the shade
• An entry [i,j] is False if the point [i,j] in the terrain is in the sunlight

Starter Code

Download the starter code:

• PA1.txt

Change PA1.txt into PA1.py. (We call these file x.txt instead of x.py because many browsers refuse to read .py files)

As discussed in lecture, provide the implementation for the three methods: naive, early, and fast with the following signatures:

def naive(image, h, angle, N, shade):

def earlyexit(image, h, angle, N, shade):

def fast(image, h, angle, N, shade):

Here, the "shade" parameter represents a 2D N×N boolean array where all values are initialized to False. Your code has to update this boolean array and return it. In your implementation, do not use any relations (<,>,<=, or >=) or the functions min()/max(). Anytime a comparison is needed, you are required to use the "compare" method that is provided in the code.

 def compare(x,y):

This boolean function expects two floats x and y. It returns a value of True if x is less than y. It returns False otherwise.

Running your code

The program requires 4 command-line arguments to run.

python3 PA1.py [file_name] [h] [theta] [algorithm]  

• file_name - name of input file containing a square terrain (2D array)
• h - horizontal distance between adjacent points
• theta - Sun's angle of elevation
• algorithm - a string containing the name of the method to run (naive|early|fast)

When provided with an input file (in the same folder as PA1.py) named "elev15x15.txt" containing a 2D array, an example usage would be:

python3 PA1.py elev15x15.txt 1 45 naive

That will run your code on the terrain contained in "elev15x15.txt" using the naive method with h=1 and theta=45.

Here is some example output, unrelated to the previous command:

0    0    *    *    *    *    *    *    *    0    *    *    *    *    *    

0    0    *    0    0    *    *    *    *    *    *    *    *    *    *    

0    *    *    0    0    *    *    *    *    *    0    *    *    *    *    

0    0    *    *    *    *    0    *    *    *    0    *    *    *    *    

0    *    *    0    *    *    *    *    *    *    0    *    0    *    *    

0    *    0    *    *    *    0    *    0    *    *    *    *    *    *    

0    *    *    *    0    *    *    0    *    *    *    *    0    *    0    

0    0    0    *    *    0    0    *    0    0    *    *    *    *    *    

0    *    *    *    *    *    *    *    0    *    *    *    *    *    0    

0    0    *    *    *    *    *    *    *    *    *    *    *    0    *    

0    *    *    *    *    0    *    *    *    *    *    *    *    *    0    

0    0    *    *    *    *    *    0    0    *    *    *    *    *    *    

0    *    *    0    *    0    *    *    0    *    *    0    0    *    *    

0    0    *    *    *    *    *    *    *    *    0    *    *    0    *    

0    0    0    0    0    *    *    0    0    *    *    0    *    *    *    

Number of comparisons: 1575

Sample Input Terrains

Five sample input files containg terrains are given below:

• elev5x5.txt
• elev10x10.txt
• elev15x15.txt
• elev20x20.txt
• elev25x25.txt

Using the naive method with h= 1 and theta= 45, the expected outputs for these samples are:

• 5x5output.txt
• 10x10output.txt
• 15x15output.txt
• 20x20output.txt
• 25x25output.txt

Here is sample input file containing a terrain of higher dimensions. The expected output for this sample is not given.

• elev150x150.txt

Checkin and grading rubric

The Checkin tab on the course website (to be enabled soon) will perform preliminary testing of your code. These tests do not indicate your final grade. The preliminary test are intended to merely make sure that your program compiles and runs, and works correctly on the simple examples given. They are provided only to help you catch basic mistakes in your submission. As a junior, the onus is now on you to thoroughly check and test your code yourself. Moreover, merely getting the correct answers is not sufficient, your algorithmic complexity must match expectations.

Grading Rubric

We will test the three functions on multiple inputs. We will evaluate some for correct answers and some for execution time. Here is the tentative weightage

• Naive: 40 points (20 correctness, 20 complexity)
• Earlyexit: 20 points (10 correctness, 10 complexity)
• Fast: 40 points (10 correctness, 30 complexity)