Convex Hull Algorithms

In this lab, you will implement several convex hull algorithms:

• Incremental Algorithm
• Gift Wrapping (aka Jarvis March)
• Graham Scan

Starter code

Download and familiarize yourself with the starter code

The “Algorithms” tab contains the method signatures you need to implement.

Lecture on Convex Hull Algorithms

We will briefly review the 3 convex hull algorithms above at the start of class. Explanations for each are also in your book, where you can find English-language algorithm descriptions. You may also use pseudo-code from the wikipedia articles on the algorithms if you wish (though I would challenge you not to do this but rather to work from the English-language descriptions in your book, and using your own reason).

Turning-in

Implement at least 2 of the 3 algorithms. I suggest you start with the gift wrapping algorithm and then do either the incremental or graham scan. Turn in via Canvas. The due date will be next Monday.

Wednesday Feb. 8 Addition

Implement the divide-and-conquer convex hull algorithm by adding another function to the Algorithms file. You will also need to update the CHAlgorithmChoice enum in UserInput to add a choice for DIVIDEANDCONQUER, and add a case to the updateHull() method in Lab03ConvexHulls.