public final class AklToussaintHeuristic extends Object
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.
Modifier and Type | Method and Description |
---|---|
static Collection<Vector2D> |
reducePoints(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.
|
public static Collection<Vector2D> reducePoints(Collection<Vector2D> points)
points
- the original point setCopyright © 2003–2016 The Apache Software Foundation. All rights reserved.