This program creates the convex hull from given set of points using Graham Scan algorithm. The algorithm works as on gif below:
By Shiyu Ji - Own work, CC BY-SA 4.0, https://commons.wikimedia.org/w/index.php?curid=54390512
The custom Point
struct which is used to store points, is implemented using templetes. The convex_hull::convexHull
function which uses Points
(vector of Point
) as an argument was also made generic usig templates. So all the code is in include directory in header files.
The algorithm was implemented by mostly using iterators and functions from <algorithm>
std library.
To build the project use CMake:
mkdir build
cd build
cmake ..
make
The application takes one optional argument, the filepath to the data file. If the path is not given the program will ask for filepath. One data file is included in data.txt.
# in build folder
./convex_hull [path_to_data]
# Filepath not given as argument
./convex_hull
Filepath not given, please enter filepath: ../data/data.txt
Convex hull points: [(4, -1), (5, 3), (2, 3), (-1, 2), (1, 0)]
# Filepath given as argument
./convex_hull ../data/data.txt
Convex hull points: [(4, -1), (5, 3), (2, 3), (-1, 2), (1, 0)]