Questions: *C programing question*

1. [30 marks] This question asks you to implement Jarviss march to compute the convex hull of a given point set. Note that if your solution does not implement Jarvis march at all, then up to only a very small number of marks can possibly be awarded for handling error cases, no matter whether your program can compute convex hull correctly or not.

General Requirements: Use a6q1.c as the name of your C source code file. We will use the following command on bluenose to compile your program:

 gcc -std=c99 -o hull a6q1.c 

As many numbers have to be read from stdin to test your program, you are expected to use input redirection to read the input from a file. More precisely, you can run your program using the following command:

 ./hull < a6q1.in.0 

In the above command, the file a6q1.in.0 is a plain text file. The first line of this file is an integer that is the number of points in the point set. Starting from the second line, each line contains two integers. The first integer is the x-coordinate of a point, and the second integer is its y-coordinate. Hence, in this question, you can assume that coordinates are int values.

To simplify your work, you can assume that the x-coordinates of points are distinct, and the y-coordinates of points are also distinct. You can also assume that no three points in the point set lie on a single line.

For example, the following file a6q1.in.0 contains a set of points: 4

12 5 19 33 2 -5 88 54 5 12 13 18 39 15 42 17 -5 -3 23 9 29 -8 17 -1 25 

Your program should then find the convex hull of these points. It first prints the number of vertices of the convex hull. It then report the coordinates of these vertices in clockwise order starting from the topmost vertex. To report a vertex, print its x- coordinate and y-coordinate in a single line, use exactly one space between these two values (this is the only space character in this line), and terminate this line with a newline character. For example, the output of the above example is expected to be

4 -5 88 54 5 17 -5 -8 17 

Error Handling: Your program should print an appropriate error message and terminate in each of the following cases:

(a) The number of points is less than 3 (obviously you need at least 3 points to define a polygon).

(b) When you try to read an integer from the input file, you encounter an illegal character. For example, your scanf function encounters a100 in the input file and cannot read it as a decimal number.

If there is more than one problem with user input, your program just has to detect one of them. You can assume that everything else regarding the input file is correct.

Testing: To help you make sure that the output format of your program is exactly what this question asks for, several files are provided in the following folder on bluenose to show how exactly your program will be automatically tested:

*please use a6q1.in.0 above for testing*

/users/faculty/prof2132/public/a6test/ 

In this folder, open the file a6q1test to see the commands used to test the program with three test cases. The output files, generated using output redirection, are also given.

To check whether the output of your program on any test case is correct, redirect your output into a file, and use the UNIX utility diff (learned in Lab 3) to compare your output file with the output file in the above folder, to see whether they are identical.

Since these output files are given, we will apply a penalty to any program that does not strictly meet the requirement on output format. This includes the case in which your output has extra spaces, or has a missing newline at the end. Note that it is extremely important to use diff here, as the number of values in the output file is large.

We will use different test cases to test your program thoroughly. Therefore, construct a number of test cases to test your program thoroughly before submitting it.

Hints:

(a) If you use gdb to debug your program, the following command can run your program with input redirection (say, the input file is named a6q1.in.0):

 run < a6q1.in.0 

(b) If you use variable length arrays to store point coordinates, then, to print the content of the array, you have to use the command given in 4(d) of Lab 6.

(c) To make it easier to test your program, you could make use of some free online programs for graph plotting. There are many online, and I found the following one: http://itools.subhashbose.com/grapher/index.php

These programs will not draw convex hulls, but they will make it easier for you to see which points are on the convex hull. Alternatively, you could buy engineering pads and draw points on them.

2. [5 marks extra credit only] VERY IMPORTANT: Before you work on this question, make a backup copy of a6q1.c. This is because this question asks you to modify this program. Make a backup copy so that you will not lose your work for Question 1 should you somehow introduce a bug that you are unable to fix before the deadline.

In this bonus question, you are asked to improve the implementation of your program by modifying it. Instead of creating a new source file, modify the program you wrote for Question 1.

Since during this process, you might introduce more bugs which you may or may not have sufficient time to eliminate, you are strongly recommended to fully test your program for Question 1 first and use the submit command to submit one version. If you use git to manage your source code (see Lab 7, though you are not required to use it), also commit one version. If you do not use git, at least make a copy of your program and store it in a different folder before modifying it. When you finish, simply submit a6q1.c again.

In this question, You are asked to modify your program so that it will still compute the convex hull correctly even if x and y-coordinates of points are not necessarily distinct (2.5 marks), and there might be groups of three or more points in the point set that lie on a single line (the other 2.5 marks). You can assume that there are no duplicate points in the given point set.

Recall that you are required to report vertices of the convex hull. Thus, if a point from the point set is on the boundary of the convex hull, but it is not a vertex, then do not report it.

Note that for this assignment, the header file math.h is not required. Be sure to fully test your program before you submit. Also use the sample input/output given for Question 1 to make sure that your output format is correct.

Make sure to provide sufficient documentation, as documentation marks for Question 1 will be awarded according to the entire program you submit (see the marking scheme). That is, the 5 bonus marks for this assignment are for correctness only.