org.openimaj.math.geometry.shape.util

## Class GrahamScan

• ```public final class GrahamScan
extends Object```
Graham Scan convex hull algorithm, based on the implementation by Bart Kiers.
Author:
Jonathon Hare (jsh2@ecs.soton.ac.uk), Bart Kiers
• ### Nested Class Summary

Nested Classes
Modifier and Type Class and Description
`protected static class ` `GrahamScan.Turn`
An enum denoting a directional-turn between 3 Point2ds (vectors).
• ### Constructor Summary

Constructors
Constructor and Description
`GrahamScan()`
• ### Method Summary

All Methods
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`.
• ### Methods inherited from class java.lang.Object

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

• #### GrahamScan

`public GrahamScan()`
• ### Method Detail

• #### areAllCollinear

`protected static boolean areAllCollinear(List<Point2d> Point2ds)`
Returns true iff all Point2ds in `Point2ds` are collinear.
Parameters:
`Point2ds` - the list of Point2ds.
Returns:
true iff all Point2ds in `Point2ds` are collinear.
• #### getConvexHull

`public static Polygon getConvexHull(List<Point2d> Point2ds)`
Returns the convex hull of the Point2ds created from the list `Point2ds`. Note that the first and last Point2d in the returned `List<java.awt.Point2d>` are the same Point2d.
Parameters:
`Point2ds` - the list of Point2ds.
Returns:
the convex hull of the Point2ds created from the list `Point2ds`.
• #### getLowestPoint2d

`protected static Point2d getLowestPoint2d(List<Point2d> Point2ds)`
Returns the Point2ds with the lowest y coordinate. In case more than 1 such Point2d exists, the one with the lowest x coordinate is returned.
Parameters:
`Point2ds` - the list of Point2ds to return the lowest Point2d from.
Returns:
the Point2ds with the lowest y coordinate. In case more than 1 such Point2d exists, the one with the lowest x coordinate is returned.
• #### getSortedPoint2dSet

`protected static Set<Point2d> getSortedPoint2dSet(List<Point2d> Point2ds)`
Returns a sorted set of Point2ds from the list `Point2ds`. The set of Point2ds are sorted in increasing order of the angle they and the lowest Point2d P make with the x-axis. If two (or more) Point2ds form the same angle towards P, the one closest to P comes first.
Parameters:
`Point2ds` - the list of Point2ds to sort.
Returns:
a sorted set of Point2ds from the list `Point2ds`.
`getLowestPoint2d(java.util.List)`
```protected static GrahamScan.Turn getTurn(Point2d a,
Returns the GrahamScan#Turn formed by traversing through the ordered Point2ds `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.
the GrahamScan#Turn formed by traversing through the ordered Point2ds `a`, `b` and `c`.