org.apache.commons.math3.geometry.euclidean.twod.hull

Class AklToussaintHeuristic

java.lang.Object

org.apache.commons.math3.geometry.euclidean.twod.hull.AklToussaintHeuristic

public final class AklToussaintHeuristic
extends java.lang.Object

A simple heuristic to improve the performance of convex hull algorithms.

The heuristic is based on the idea of a convex quadrilateral, which is formed by four points with the lowest and highest x / y coordinates. Any point that lies inside this quadrilateral can not be part of the convex hull and can thus be safely discarded before generating the convex hull itself.

The complexity of the operation is O(n), and may greatly improve the time it takes to construct the convex hull afterwards, depending on the point distribution.

Since:

3.3

See Also:

Akl-Toussaint heuristic (Wikipedia)

Method Summary

Modifier and Type	Method and Description
static java.util.Collection<Vector2D>	reducePoints(java.util.Collection<Vector2D> points) Returns a point set that is reduced by all points for which it is safe to assume that they are not part of the convex hull.

Methods inherited from class java.lang.Object

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

Method Detail

reducePoints

public static java.util.Collection<Vector2D> reducePoints(java.util.Collection<Vector2D> points)

Returns a point set that is reduced by all points for which it is safe to assume that they are not part of the convex hull.

Parameters:

points - the original point set

Returns:

a reduced point set, useful as input for convex hull algorithms