edu.princeton.cs.algs4

Class GrahamScan

java.lang.Object

edu.princeton.cs.algs4.GrahamScan

public class GrahamScan
extends java.lang.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.

Constructor Summary

Constructors

Constructor and Description
GrahamScan(Point2D[] points) Computes the convex hull of the specified array of points.

Method Summary

Modifier and Type	Method and Description
java.lang.Iterable<Point2D>	hull() Returns the extreme points on the convex hull in counterclockwise order.
static void	main(java.lang.String[] args) Unit tests the GrahamScan data type.

Methods inherited from class java.lang.Object

equals, 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:

java.lang.IllegalArgumentException - if points is null

java.lang.IllegalArgumentException - if any entry in points[] is null

java.lang.IllegalArgumentException - if points.length is 0

Method Detail

hull

public java.lang.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(java.lang.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