Convex Hull

Project Requirements

Final research project for the graduate-level class, Algorithm Design and Analysis.

• The topic should be related to algorithm complexity and must involve implementing one or more algorithms or data structures.
• After completing their research, students are responsible for writing a 7-10 page paper which is to be submitted along with their source code.

Topic

Implement convex hull algorithms, which will include:

• Graham's scan
• Jarvis's march (gift-wrapping)

To implement in future work:

• Divide-and-conquer
• Prune-and-search
• Chan's algorithm

Compare the performance of each algorithm implemented, and create some visual representation (i.e. scatter plots) of the algorithms/performance.

Getting Started

These instructions will get you a copy of the project up and running on your local machine for development and testing purposes.

Prerequisites

What things were needed to set up the development environment and how to install them. Note: installation instructions based on macOS Mojave.

• Python 3.7.2
• pip
• matplotlib

Install pip:

curl https://bootstrap.pypa.io/gpython get-pip.pyet-pip.py -o get-pip.py

python get-pip.py

Install matplotlib:

pip install matplotlib

Run

After installing any prerequisites listed above, follow these steps to run the program:

1. Clone the project to your local machine.
   

   git clone https://github.com/carissaallen/convex-hull.git

2. From your terminal, enter the following command:
   

   python main.py

Hull Construction

To view the construction of the convex hull:

• Navigate to the main.py file. In the main method:

• If show_progress = False then the scatter plot will only display the final convex hull boundary.

• If show_progress = True then the scatter plot will show the hull's progress as the boundary is constructed.
  

  Note: keep the input size small, this is pretty slow. 🐢

Tree

├── LICENSE
├── README.md
├── datasets.py
├── graham_scan.py
├── jarvis_march.py
├── main.py
└── scatter_plot.py

Future Work

I am currently working on improving the input data set, and the timing mechanism used to analyze empirical performance of the algorithms. Once these areas are improved, I intend to implement additional algorithms for analysis.

Authors

• Carissa Allen - Initial work - Convex Hull

License

This project is licensed under the MIT License - see the LICENSE file for details

Acknowledgments

A thank you to the individuals who created material I was able to use for inspiration, understanding and implementing technical details, and credit to any other resources that contributed to the making of my project. 👏🏻

• Introduction to Algorithms 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
• Brian Faure for creating a tutorial for Graham's Scan, which was used to learn about matplotlib to create the visual representation of the convex hull, and for some implementation details.
• Determining if two consecutive line segments turn left or right
• Convex Hull Algorithms: Jarvis's March
• Computational Geometry Lecture by Jeff Erickson
• Computing Convex Hull in Python by John Washam
• Convex-Hull Algorithms by Neve Gamby and Jyrki Katajainen, primarily relied on to develop appropriate data sets as input to the algorithms implemented.
• To brush up on my geometry, Text Computational Geometry in C by Joseph O'Rourke.
• Convex Hull Applications
• Spatial Extent of an Outbreak in Animal Epidemics
• Hand Gesture Recognition Based on Convex Defect Detection
• The Convex Hull of a Finite Planar Set by R.L. Graham (1972)