org.openimaj.math.geometry.shape.util

Class GrahamScan

java.lang.Object

org.openimaj.math.geometry.shape.util.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

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.

See Also:

getLowestPoint2d(java.util.List)

getTurn

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. 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.

Parameters:

a - the starting Point2d.

b - the second Point2d.

c - the end Point2d.

Returns:

the GrahamScan#Turn formed by traversing through the ordered Point2ds a, b and c.