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-2023 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

Method Summary

Modifier and Type	Method	Description
static Polygon2d	convexHull(Collection<Drawable2d> drawableCollection)	Construct a Bounds2d for a Collection of Drawable2d objects.
static Polygon2d	convexHull(Iterator<Point2d> iterator)	Compute the convex hull of a collection of Point2d objects.
static Polygon2d	convexHull(List<Point2d> list)	Compute the convex hull of a list of Point2d objects.
static Polygon2d	convexHull(Drawable2d... drawable2d)	Compute the convex hull of one or more Drawable2d objects.
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.
static Polygon2d	convexHullMonotone(List<Point2d> list)	Implementation of Andrew's Monotone Chain convex hull algorithm.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

convexHull

public static Polygon2d convexHull(Iterator<Point2d> iterator)

Compute the convex hull of a collection of Point2d objects.

Parameters:

iterator - Iterator<Point2d>; iterator that shall return all the points for which the convex hull is to be computed

Returns:

Polygon2d; the convex hull of the points

convexHull

public static Polygon2d convexHull(Drawable2d... drawable2d)
                            throws NullPointerException,
                                   IllegalArgumentException

Compute the convex hull of one or more Drawable2d objects.

Parameters:

drawable2d - Drawable2d...; the Drawable2d objects

Returns:

Polygon2d; 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)
                            throws NullPointerException,
                                   IllegalArgumentException

Construct a Bounds2d for a Collection of Drawable2d objects.

Parameters:

drawableCollection - Collection<Drawable2d>; the collection

Returns:

Polygon2d; the convex hull of the Drawable2d objects

Throws:

NullPointerException - when the collection is null, or contains null values

IllegalArgumentException - when the collection 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 - List<Point2d>; the list of Point2d objects

Returns:

Polygon2d; the convex hull of the points

convexHullAlshamrani

public static Polygon2d convexHullAlshamrani(List<Point2d> list)
                                      throws NullPointerException,
                                             DrawRuntimeException

Implementation of the convex hull algorithm by Reham Alshamrani c.s.; see A Preprocessing Technique for Fast Convex Hull Computation.

Parameters:

list - List<Point2d>; list of the points (will not be modified)

Returns:

Polygon2d; the convex hull of the points

Throws:

NullPointerException - when the list is null

DrawRuntimeException - when the list contains too few points

convexHullMonotone

public static Polygon2d convexHullMonotone(List<Point2d> list)
                                    throws NullPointerException,
                                           DrawRuntimeException

Implementation of Andrew's Monotone Chain convex hull algorithm. This implementation (sorts) modifies the provided list of points!

Parameters:

list - List<Point2d>; list of the points (will be modified)

Returns:

Polygon2d; the convex hull of the points

Throws:

NullPointerException - when the list is null

DrawRuntimeException - when the list contains too few points