edu.princeton.cs.algs4

## Class GrahamScan

• Object
• edu.princeton.cs.algs4.GrahamScan

• ```public class GrahamScan
extends Object```
The `GrahamScan` data type provides methods for computing the convex hull of a set of n points in the plane.

The implementation uses the Graham-Scan convex hull algorithm. It runs in O(n log n) time in the worst case and uses O(n) extra memory.

For additional documentation, see Section 9.9 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:
Robert Sedgewick, Kevin Wayne
• ### Constructor Summary

Constructors
Constructor and Description
`GrahamScan(Point2D[] points)`
Computes the convex hull of the specified array of points.
• ### Method Summary

Methods
Modifier and Type Method and Description
`Iterable<Point2D>` `hull()`
Returns the extreme points on the convex hull in counterclockwise order.
`static void` `main(String[] args)`
Unit tests the `GrahamScan` data type.
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### GrahamScan

`public GrahamScan(Point2D[] points)`
Computes the convex hull of the specified array of points.
Parameters:
`points` - the array of points
Throws:
`IllegalArgumentException` - if `points` is `null`
`IllegalArgumentException` - if any entry in `points[]` is `null`
`IllegalArgumentException` - if `points.length` is `0`
• ### Method Detail

• #### hull

`public Iterable<Point2D> hull()`
Returns the extreme points on the convex hull in counterclockwise order.
Returns:
the extreme points on the convex hull in counterclockwise order
• #### main

`public static void main(String[] args)`
Unit tests the `GrahamScan` data type. Reads in an integer `n` and `n` points (specified by their x- and y-coordinates) from standard input; computes their convex hull; and prints out the points on the convex hull to standard output.
Parameters:
`args` - the command-line arguments