Project 2: Hull2d with Graham scan

• Assigned: Tuesday, February 7
• Due: Sunday, February 19, 11:59pm
• Group policy: Partner-optional
• Collaboration policy: Level 1

In this assignment you will write code to find the convex hull of a set of points in the plane using Graham’s scan and come up with a couple of testing cases. The goal is to figure out the details of the algorithm discussed in class and specifically to figure out how to handle degeneracies in the input. You will receive starter code on Github. The starter code provides the graphical interface and should compile as is.

Overview

What you need to do:

• Fill in the graham_scan function, and anything else that may be necessary to make it all work.

• Come up with at least two interesting configuration of points on which to compute the hull, and write the corresponding initializer functions. The sets of points can be easy but should not be trivial. At least one of them should contain some collinear points.

• Post your special initialier functions to the whole class on Slack on the channel called #projects (to keeep things seasy to find, please post your initializer on #projects and not on #general).

• Include at least 8 of your classmates test cases in your code.

What and how to turn in

You will receive the assignment on GitHub. Fill in the necessary functions. You do not need to create any new files (but you can if you want to). Update the Readme file with a brief description of the project and how to run it. If it is a team project, please include the names. Remember not to turn in any object or executable files.

Evaluation

Your code will be evaluated on the correctness of your algorithm, whether it can produce correct output without crashing on all the initializers, on the initializers you created, and on the quality of your code.