public final class GrahamScan extends Object
Modifier and Type  Class and Description 

protected static class 
GrahamScan.Turn
An enum denoting a directionalturn between 3 Point2ds (vectors).

Constructor and Description 

GrahamScan() 
Modifier and Type  Method and Description 

protected static boolean 
areAllCollinear(List<Point2d> Point2ds)
Returns true iff all Point2ds in
Point2ds are collinear. 
static Polygon 
getConvexHull(List<Point2d> Point2ds)
Returns the convex hull of the Point2ds created from the list
Point2ds . 
protected static Point2d 
getLowestPoint2d(List<Point2d> Point2ds)
Returns the Point2ds with the lowest y coordinate.

protected static Set<Point2d> 
getSortedPoint2dSet(List<Point2d> Point2ds)
Returns a sorted set of Point2ds from the list
Point2ds . 
protected static GrahamScan.Turn 
getTurn(Point2d a,
Point2d b,
Point2d c)
Returns the GrahamScan#Turn formed by traversing through the ordered Point2ds
a , b and c . 
public GrahamScan()
protected static boolean areAllCollinear(List<Point2d> Point2ds)
Point2ds
are collinear.Point2ds
 the list of Point2ds.Point2ds
are collinear.public static Polygon getConvexHull(List<Point2d> Point2ds)
Point2ds
. Note that the first and last Point2d in the returned
List<java.awt.Point2d>
are the same Point2d.Point2ds
 the list of Point2ds.Point2ds
.protected static Point2d getLowestPoint2d(List<Point2d> Point2ds)
Point2ds
 the list of Point2ds to return the lowest Point2d from.protected static Set<Point2d> getSortedPoint2dSet(List<Point2d> Point2ds)
Point2ds
. The set
of Point2ds are sorted in increasing order of the angle they and the lowest
Point2d P make with the xaxis. If two (or more) Point2ds form the
same angle towards P, the one closest to P comes first.Point2ds
 the list of Point2ds to sort.Point2ds
.getLowestPoint2d(java.util.List)
protected static GrahamScan.Turn getTurn(Point2d a, Point2d b, Point2d c)
a
, b
and c
. More specifically, the
cross product C between the 3 Point2ds (vectors) is calculated:
(b.getX()a.getX() * c.getY()a.getY())  (b.getY()a.getY() * c.getX()a.getX())
and if C is less than 0, the turn is CLOCKWISE, if C is
more than 0, the turn is COUNTER_CLOCKWISE, else the three Point2ds are
COLLINEAR.a
 the starting Point2d.b
 the second Point2d.c
 the end Point2d.a
, b
and c
.