us.ihmc.utilities.math.geometry
Class ConvexHullCalculator2d

java.lang.Object
  us.ihmc.utilities.math.geometry.ConvexHullCalculator2d

public class ConvexHullCalculator2d
extends java.lang.Object

Title:

Description: calculates the convex hull from an ArrayList of Point2d Uses a marriage-before-conquer algorithm, as published by KirkPatrick and Seidel, 1983, potentially with worst case time complexity O(n log(H)), where n is the size of the input set and H is the size of the output set. For now, a random method is used instead of the median method. The linear time median methods must be implemented to make it O(n log(H)).

Copyright: Copyright (c) 2007

Company:

Version:

1.0

Author:

Twan Koolen

Constructor Summary

ConvexHullCalculator2d()

Method Summary

static java.util.ArrayList<javax.vecmath.Point2d>	getConvexHull(java.util.ArrayList<javax.vecmath.Point2d> pointList) getConvexHull Returns the convex hull of any unordered ArrayList of Point2d's.
static java.util.ArrayList<javax.vecmath.Point2d>	getConvexHullCopy(java.util.ArrayList<javax.vecmath.Point2d> pointList)
static java.util.ArrayList<javax.vecmath.Point2d>	getConvexHullCopy(double[][] pointListArray)
static java.util.ArrayList<javax.vecmath.Point2d>	getLowerHull(java.util.ArrayList<javax.vecmath.Point2d> pointList)
static java.util.ArrayList<javax.vecmath.Point2d>	getUpperHull(java.util.ArrayList<javax.vecmath.Point2d> pointList)
static boolean	isConvexAndClockwise(java.util.ArrayList<javax.vecmath.Point2d> pointList) isConvex Returns true iff clockwiseOrderedListOfVertices forms a convex polygon, based on the number of sign changes encountered when 'walking along' the polygon edges

Methods inherited from class java.lang.Object

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

Constructor Detail

ConvexHullCalculator2d

public ConvexHullCalculator2d()

Method Detail

getConvexHull

public static java.util.ArrayList<javax.vecmath.Point2d> getConvexHull(java.util.ArrayList<javax.vecmath.Point2d> pointList)

getConvexHull Returns the convex hull of any unordered ArrayList of Point2d's. The returned points will be ordered clockwise, starting from the point with the maximum y-coordinate value that is contained in the set of points with the minimum x-coordinate value ('upper rightmost' vertex). References are kept intact, so the output is mutable.

Parameters:

pointList - ArrayList

Returns:

ArrayList the convex hull

getConvexHullCopy

public static java.util.ArrayList<javax.vecmath.Point2d> getConvexHullCopy(java.util.ArrayList<javax.vecmath.Point2d> pointList)

getConvexHullCopy

public static java.util.ArrayList<javax.vecmath.Point2d> getConvexHullCopy(double[][] pointListArray)

getLowerHull

public static java.util.ArrayList<javax.vecmath.Point2d> getLowerHull(java.util.ArrayList<javax.vecmath.Point2d> pointList)

getUpperHull

public static java.util.ArrayList<javax.vecmath.Point2d> getUpperHull(java.util.ArrayList<javax.vecmath.Point2d> pointList)

isConvexAndClockwise

public static boolean isConvexAndClockwise(java.util.ArrayList<javax.vecmath.Point2d> pointList)

isConvex Returns true iff clockwiseOrderedListOfVertices forms a convex polygon, based on the number of sign changes encountered when 'walking along' the polygon edges

Parameters:

clockwiseOrderedListOfVertices - ArrayList

Returns:

boolean