Four algorithms to implement the problem of finding the smallest convex polygon for a set of points which contains all the points in the plane. The four algorithms are:
- The divide and conquer approach
- The Graham Scan Algorithm.
- Jarvis March Algorithm.
- Quickhull Algorithm.
There are two options for executing the code. One is where the user gives the input and for this set of points, the convex polygon is found for these points using the divide and conquer approach.
The second approach is running for the predefined inputs which vary from input size 10 to 1000000. the range of the inputs
changes from (0,100), (0,1000) and (0,10000). This will run for 48 different test cases and will take time to plot all the graphs since the size of inputs increases to 1000000.
The user interface is written in python and the algorithms are written in cpp.
The implementation files that are called are:
- divide_and_conquer.cpp(To illustrate the output when the user gives the input).
- divide_and_conquer_analysis.cpp
- quickhull.cpp
- graham_scan.cpp
- jarvis_march.cpp
Make sure g++ is installed in your system.
Python modules required: subprocess, matplotlib
To run the code, run:
python ui.py
Then choose the option you want.
Github link: https://github.com/NinaadRao/Convex-Hull-algorithm