Class 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)
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private AklToussaintHeuristic()
      Hide utility constructor.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method 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.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • AklToussaintHeuristic

        private AklToussaintHeuristic()
        Hide utility constructor.
    • 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
      • buildQuadrilateral

        private static java.util.List<Vector2D> buildQuadrilateral​(Vector2D... points)
        Build the convex quadrilateral with the found corner points (with min/max x/y coordinates).
        Parameters:
        points - the respective points with min/max x/y coordinate
        Returns:
        the quadrilateral
      • insideQuadrilateral

        private static boolean insideQuadrilateral​(Vector2D point,
                                                   java.util.List<Vector2D> quadrilateralPoints)
        Checks if the given point is located within the convex quadrilateral.
        Parameters:
        point - the point to check
        quadrilateralPoints - the convex quadrilateral, represented by 4 points
        Returns:
        true if the point is inside the quadrilateral, false otherwise