Package org.djutils.draw.line

Class ConvexHull

java.lang.Object
org.djutils.draw.line.ConvexHull
public final class ConvexHull extends Object
ConvexHull.java. Compute the convex hull of a collection of Point2d or Drawable2d. All implementations here return a Polygon2d object. If the convex hull of the input would be a single point, the implementations will throw a DrawRuntimeException because a single point does not make a valid Polygon2d.

Copyright (c) 2020-2025 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
BSD-style license. See DJUTILS License.

Author:
Alexander Verbraeck, Peter Knoppers, Wouter Schakel

  • Method Details

    • convexHull

      public static Polygon2d convexHull(Iterator<Point2d> iterator)
      Compute the convex hull of a collection of Point2d objects.
      Parameters:
      iterator - iterator that shall return all the points for which the convex hull is to be computed
      Returns:
      the convex hull of the points

    • convexHull

      public static Polygon2d convexHull(Drawable2d... drawable2d)
      Compute the convex hull of one or more Drawable2d objects.
      Parameters:
      drawable2d - the Drawable2d objects
      Returns:
      the convex hull of the Drawable2d objects
      Throws:
      NullPointerException - when any of the drawable2d object is null
      IllegalArgumentException - when zero arguments are provided

    • convexHull

      public static Polygon2d convexHull(Collection<Drawable2d> drawableCollection)
      Construct a Bounds2d for a Collection of Drawable2d objects.
      Parameters:
      drawableCollection - the collection
      Returns:
      the convex hull of the Drawable2d objects
      Throws:
      NullPointerException - when the drawableCollection is null, or contains a null value
      IllegalArgumentException - when the drawableCollection is empty

    • convexHull

      public static Polygon2d convexHull(List<Point2d> list)
      Compute the convex hull of a list of Point2d objects. The input list will not be modified.
      Parameters:
      list - the list of Point2d objects
      Returns:
      the convex hull of the points

    • convexHullAlshamrani

      public static Polygon2d convexHullAlshamrani(List<Point2d> list)
      Implementation of the convex hull algorithm by Reham Alshamrani c.s.; see A Preprocessing Technique for Fast Convex Hull Computation.
      Parameters:
      list - list of the points (will not be modified)
      Returns:
      the convex hull of the points
      Throws:
      NullPointerException - when the list is null
      IllegalArgumentException - when the list contains too few points

    • convexHullMonotone

      public static Polygon2d convexHullMonotone(List<Point2d> list)
      Implementation of Andrew's Monotone Chain convex hull algorithm. This implementation (sorts) modifies the provided list of points!
      Parameters:
      list - list of the points (will be modified)
      Returns:
      the convex hull of the points
      Throws:
      NullPointerException - when the list is null
      IllegalArgumentException - when the list contains too few points