Class ConvexHull2D

java.lang.Object
org.episteme.core.mathematics.geometry.ConvexHull2D
public final class ConvexHull2D extends Object
Robust 2D Convex Hull implementation using the Monotone Chain algorithm.

Time complexity: O(n log n)

The algorithm:

  1. Sort points lexicographically (by x, then by y)
  2. Build lower hull by processing points left-to-right
  3. Build upper hull by processing points right-to-left
  4. Concatenate hulls (removing duplicate endpoints)
Since:
1.0
Author:
Silvere Martin-Michiellot, Gemini AI (Google DeepMind)
See Also:

  • Method Details

    • compute

      public static List<Point2D> compute(List<Point2D> points)
      Computes the convex hull of a set of 2D points.
      Parameters:
      points - the input points
      Returns:
      the vertices of the convex hull in counter-clockwise order

    • compute

      public static List<Point2D> compute(Point2D... points)
      Computes the convex hull from an array.
      Parameters:
      points - the input points
      Returns:
      the hull vertices

    • computePolygon

      public static ConvexPolygon2D computePolygon(List<Point2D> points)
      Creates a ConvexPolygon2D from the hull.
      Parameters:
      points - the input points
      Returns:
      a convex polygon boundary

    • isConvex

      public static boolean isConvex(List<Point2D> points)
      Checks if a set of points is already convex (in convex position).
      Parameters:
      points - the points to check (assumed in order)
      Returns:
      true if convex

    • computeArea

      public static Real computeArea(List<Point2D> points)
      Computes the area of the convex hull.
      Parameters:
      points - the input points
      Returns:
      the area

    • computePerimeter

      public static Real computePerimeter(List<Point2D> points)
      Computes the perimeter of the convex hull.
      Parameters:
      points - the input points
      Returns:
      the perimeter

    • findFarthest

      public static Point2D findFarthest(List<Point2D> points, Point2D queryPoint)
      Finds the point on the hull farthest from a given point.
      Parameters:
      points - the input points
      queryPoint - the query point
      Returns:
      the farthest hull vertex

    • computeDiameter

      public static Real computeDiameter(List<Point2D> points)
      Computes the diameter of the convex hull (rotating calipers).
      Parameters:
      points - the input points
      Returns:
      the diameter (maximum distance between any two hull points)