Package edu.princeton.cs.algs4
Class GrahamScan
 Object

 edu.princeton.cs.algs4.GrahamScan

public class GrahamScan extends Object
TheGrahamScan
data type provides methods for computing the convex hull of a set of n points in the plane.The implementation uses the GrahamScan 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 Description GrahamScan(Point2D[] points)
Computes the convex hull of the specified array of points.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description Iterable<Point2D>
hull()
Returns the extreme points on the convex hull in counterclockwise order.static void
main(String[] args)
Unit tests theGrahamScan
data type.



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
 ifpoints
isnull
IllegalArgumentException
 if any entry inpoints[]
isnull
IllegalArgumentException
 ifpoints.length
is0


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 theGrahamScan
data type. Reads in an integern
andn
points (specified by their x and ycoordinates) from standard input; computes their convex hull; and prints out the points on the convex hull to standard output. Parameters:
args
 the commandline arguments

