Package science.aist.imaging.core.pointprocessing.convexhull

Class GrahamConvexHull

java.lang.Object

science.aist.imaging.core.pointprocessing.convexhull.GrahamConvexHull

All Implemented Interfaces:

Function<List<JavaPoint2D>,List<JavaPoint2D>>, UnaryOperator<List<JavaPoint2D>>

public class GrahamConvexHull
extends Object
implements UnaryOperator<List<JavaPoint2D>>

Implementation of the GrahamScan Algorithms for finding a ConvexHull

Based on: https://github.com/bkiers/GrahamScan

Since:

1.0

Author:

Christoph Praschl, Bart Kiers

Constructor Summary

Constructors

Constructor	Description
GrahamConvexHull()

Method Summary

Modifier and Type	Method	Description
List<JavaPoint2D>	apply(int[] xs, int[] ys)	Returns the convex hull of the points created from xs and ys.
List<JavaPoint2D>	apply(List<JavaPoint2D> points)	Returns the convex hull of the points created from the list points.
boolean	areAllCollinear(List<JavaPoint2D> points)	Returns true iff all points in points are collinear.
JavaPoint2D	getLowestPoint(List<JavaPoint2D> points)	Returns the points with the lowest y coordinate.
Set<JavaPoint2D>	getSortedPointSet(List<JavaPoint2D> points)	Returns a sorted set of points from the list points.
Turn	getTurn(JavaPoint2D a, JavaPoint2D b, JavaPoint2D c)	Returns the GrahamScan#Turn formed by traversing through the ordered points a, b and c.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.function.Function

andThen, compose

Constructor Detail

GrahamConvexHull

public GrahamConvexHull()

Method Detail

apply

public List<JavaPoint2D> apply(int[] xs,
                               int[] ys)

Returns the convex hull of the points created from xs and ys. Note that the first and last point in the returned List<JavaPoint> are the same point.

Parameters:

xs - the x coordinates.

ys - the y coordinates.

Returns:

the convex hull of the points created from xs and ys.

apply

public List<JavaPoint2D> apply(List<JavaPoint2D> points)

Returns the convex hull of the points created from the list points. Note that the first and last point in the returned List<JavaPoint> are the same point.

Specified by:

apply in interface Function<List<JavaPoint2D>,List<JavaPoint2D>>

Parameters:

points - the list of points.

Returns:

the convex hull of the points created from the list points.

areAllCollinear

public boolean areAllCollinear(List<JavaPoint2D> points)

Returns true iff all points in points are collinear.

Parameters:

points - the list of points.

Returns:

true iff all points in points are collinear.

getLowestPoint

public JavaPoint2D getLowestPoint(List<JavaPoint2D> points)

Returns the points with the lowest y coordinate. In case more than 1 such point exists, the one with the lowest x coordinate is returned.

Parameters:

points - the list of points to return the lowest point from.

Returns:

the points with the lowest y coordinate. In case more than 1 such point exists, the one with the lowest x coordinate is returned.

getSortedPointSet

public Set<JavaPoint2D> getSortedPointSet(List<JavaPoint2D> points)

Returns a sorted set of points from the list points. The set of points are sorted in increasing order of the angle they and the lowest point P make with the x-axis. If tow (or more) points form the same angle towards P, the one closest to P comes first.

Parameters:

points - the list of points to sort.

Returns:

a sorted set of points from the list points.

See Also:

getLowestPoint(java.util.List)

getTurn

public Turn getTurn(JavaPoint2D a,
                    JavaPoint2D b,
                    JavaPoint2D c)

Returns the GrahamScan#Turn formed by traversing through the ordered points a, b and c. More specifically, the cross product C between the 3 points (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 points are COLLINEAR.

Parameters:

a - the starting point.

b - the second point.

c - the end point.

Returns:

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