A web application that provides a visualization of the Graham Scan algorithm. The user can manually add points or randomly generate a collection of points. Afterwards, the animation can be played automatically or step-by-step at the user's pace.
The live app can be found here.
The Graham Scan is an algorithm used to compute the convex hull of a point set. It is one of the faster convex hull algorithms, having a time complexity of O(n log n) in the worst case, and can reach as low as O(n) if the points are pre-sorted. Here is a high-level overview of how the algorithm works.
let points = [] of points
let convexHull = empty []
let startPoint = lowest, rightmost point in points
sort points by polar angle made with startPoint
for point in points
push point into convexHull
if convexHull has a right turn
pop the point at the vertex of the right turn
return convexHull
- React (Library for building UIs)
- Redux (State Management Tool)
- Enzyme (Tests React Components)
- Jest (Tests JavaScript)
- SASS (CSS Preprocessor)
Make sure you that you have Node.js installed. If you don't have it yet, head over to this link.
To get started, first clone the application, and move into the repository:
$ git clone https://github.com/sivakusayan/visual-graham-scan.git
$ cd visual-graham-scan
Afterwards, install all the dependencies and run the application. Enjoy!
$ npm install
$ npm run local
If you want to run the tests, you can do so with the following script:
$ npm run test
You can also only test a specific part of the application if you like:
$ npm run test-algorithm
$ npm run test-components
$ npm run test-containers
$ npm run test-state