public class GrahamScan extends Object
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.
Constructor and Description |
---|
GrahamScan(Point2D[] points)
Computes the convex hull of the specified array of points.
|
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. |
public GrahamScan(Point2D[] points)
points
- the array of pointsIllegalArgumentException
- if points
is null
IllegalArgumentException
- if any entry in points[]
is null
IllegalArgumentException
- if points.length
is 0
public Iterable<Point2D> hull()
public static void main(String[] args)
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.args
- the command-line arguments