us.ihmc.utilities.math.geometry
Class ConvexHullCalculator2d

java.lang.Object
  extended by 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 void getConvexHull(java.util.ArrayList<javax.vecmath.Point2d> convexHullToPack, 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(double[][] pointListArray)
           
static java.util.List<javax.vecmath.Point2d> getConvexHullCopy(java.util.List<javax.vecmath.Point2d> pointList)
           
static void getLowerHull(java.util.ArrayList<javax.vecmath.Point2d> lowerHullToPack, java.util.ArrayList<javax.vecmath.Point2d> pointList)
           
static void getUpperHull(java.util.ArrayList<javax.vecmath.Point2d> upperHullToPack, java.util.ArrayList<javax.vecmath.Point2d> pointList)
           
static boolean isConvexAndClockwise(java.util.List<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 void getConvexHull(java.util.ArrayList<javax.vecmath.Point2d> convexHullToPack,
                                 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

getConvexHullCopy

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

getConvexHullCopy

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

getLowerHull

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

getUpperHull

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

isConvexAndClockwise

public static boolean isConvexAndClockwise(java.util.List<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