public final class AklToussaintHeuristic
extends java.lang.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 | Constructor and Description |
---|---|
private |
AklToussaintHeuristic()
Hide utility constructor.
|
Modifier and Type | Method and Description |
---|---|
private static java.util.List<Vector2D> |
buildQuadrilateral(Vector2D... points)
Build the convex quadrilateral with the found corner points (with min/max x/y coordinates).
|
private static boolean |
insideQuadrilateral(Vector2D point,
java.util.List<Vector2D> quadrilateralPoints)
Checks if the given point is located within the convex quadrilateral.
|
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.
|
public static java.util.Collection<Vector2D> reducePoints(java.util.Collection<Vector2D> points)
points
- the original point setprivate static java.util.List<Vector2D> buildQuadrilateral(Vector2D... points)
points
- the respective points with min/max x/y coordinateprivate static boolean insideQuadrilateral(Vector2D point, java.util.List<Vector2D> quadrilateralPoints)
point
- the point to checkquadrilateralPoints
- the convex quadrilateral, represented by 4 pointstrue
if the point is inside the quadrilateral, false
otherwiseCopyright (c) 2003-2014 Apache Software Foundation