A JavaScript implementation of the Graham scan algorithm for finding the convex hull of a set of points.
npm i @lucio/graham-scan
const grahamScan = new GrahamScan();
grahamScan.setPoints([[1,0], [0,1], [2,1], [1,0.5]]);
const hull = grahamScan.getHull(); // [1,0], [2,1], [0,1]Creates a new instance of the algorithm, meant to be reusable.
const grahamScan = new GrahamScan();Adds a point to the set. The point must be an array of two numbers: the x and y coordinates.
const grahamScan = new GrahamScan();
grahamScan.addPoint([10, 20]);Clear the underlying array of points.
const grahamScan = new GrahamScan();
grahamScan.addPoint([10, 20]);
grahamScan.clear();Computes the convex hull. Returns a new array containing all the hull vertices, starting from the one with the lowest y value (in case there are multiple ones, it will be the one with the lowest x as well) and going in counter-clockwise direction.
const grahamScan = new GrahamScan();
grahamScan.setPoints([[1,0], [0,1], [2,1], [1,0.5]]);
const hull = grahamScan.getHull(); // [1,0], [2,1], [0,1]Returns a reference to the underlying array containing all the points.
const grahamScan = new GrahamScan();
grahamScan.addPoint([10, 20]);
grahamScan.addPoint([30, 40]);
grahamScan.getPoints(); // [10, 20], [30, 40]Replace the underlying array with the given one.
const grahamScan = new GrahamScan();
grahamScan.setPoints([[10, 20], [30, 40]]);git clone git@github.com:luciopaiva/graham-scan.git
cd graham-scan
nvm install
npm install
npm test
No. Graham scan runs in O(n log n), where n is the total number of points in the set. Chan's algorithm does a bit better, O(n log h), where h is the number of vertices composing the final hull.
It is still much better than Jarvis march, though, which runs in O(nh).
Node.js projects that use this library by directly copying the script file instead of installing it via npm would need to add type: module to package.json, which may be undesired.