edu.princeton.repeatedgames.rgsolve.polygon
Class RobustConvexHull

java.lang.Object
  extended by edu.princeton.repeatedgames.rgsolve.polygon.RobustConvexHull

public class RobustConvexHull
extends java.lang.Object

Computes convex hull robustly using Andrew's Monotone Chain algorithm (based on C++ code found here: http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull.cpp), with robustness checks from the literature.


Nested Class Summary
static class RobustConvexHull.ExtractSumObject
           
static class RobustConvexHull.PointComparator
          This object compares Point objects lexicographically, using the rule: p1 < p2 iff p1.x > p2.x || (p1.x == p2.x && p1.y < p2.y) This is the usual Lexicographic ordering except we have flipped the comparison on the x-coordinate; we want points ordered right-to-left.
static interface RobustConvexHull.SignedAreaFunc
          Interface for signed area calculator
 
Field Summary
static double ANG_TOL
          Default angle tolerance: 1.0E-14
static double CCW_TOL
          Default signed area tolerance: 1.0E-15
static double FACTOR
           
(package private) static RobustConvexHull.PointComparator ptComparator
          Lexicographic orderer on points
static double u
          2^-53
static double u_
          2^-1075
static double uN
          minimum normalized double
 
Constructor Summary
RobustConvexHull()
           
 
Method Summary
static double AccSum_false(double[] P)
           
static double AppOrient2D(Point A, Point B, Point C)
          Non-robust signed area calculation
static RobustConvexHull.ExtractSumObject ExtractSum(double[] P, double sigma)
           
static double Filter(Point A, Point B, Point C, int filterType)
          Robust signed area calucation
(package private) static double getDetRobust(Point A, Point B, Point C)
           
private static double maxAbs(double[] P)
           
static
<T extends Point>
java.util.ArrayList<T>
monotoneChain(java.util.ArrayList<T> points, java.lang.Class<T> cls)
          Computes the convex hull non-robustly (but quickly)
static
<T extends Point>
T[]
monotoneChain(T[] points, java.lang.Class<T> cls)
          Computes the convex hull non-robustly (but quickly)
static
<T extends Point>
java.util.ArrayList<T>
monotoneChainRobust(java.util.ArrayList<T> points, java.lang.Class<T> cls)
          Computes the convex hull robustly
static
<T extends Point>
java.util.ArrayList<T>
monotoneChainRobust(java.util.ArrayList<T> points, java.lang.Class<T> cls, boolean smoothHull, double ccwTol, double angleTol)
          Computes the convex hull.
static
<T extends Point>
T[]
monotoneChainRobust(T[] points, java.lang.Class<T> cls)
          Computes the convex hull robustly
static
<T extends Point>
T[]
monotoneChainRobust(T[] points, java.lang.Class<T> cls, boolean smoothHull, double ccwTol, double angleTol)
          Computes the convex hull
private static double[] Split(double a)
           
private static boolean TripleIsRobust(Point A, Point B, Point C, double ccwTol, double angleTol)
          Robustness check on the adjacent triple (A,B,C) on the hull
static double[] TwoDiff(double a, double b)
           
static double[] TwoProduct(double a, double b)
           
static double[] TwoSum(double a, double b)
           
static double Verified1(Point A, Point B, Point C)
           
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

u

public static final double u
2^-53


u_

public static final double u_
2^-1075


uN

public static final double uN
minimum normalized double

See Also:
Constant Field Values

ANG_TOL

public static final double ANG_TOL
Default angle tolerance: 1.0E-14

See Also:
Constant Field Values

CCW_TOL

public static final double CCW_TOL
Default signed area tolerance: 1.0E-15

See Also:
Constant Field Values

FACTOR

public static final double FACTOR

ptComparator

static final RobustConvexHull.PointComparator ptComparator
Lexicographic orderer on points

Constructor Detail

RobustConvexHull

public RobustConvexHull()
Method Detail

monotoneChain

public static <T extends Point> java.util.ArrayList<T> monotoneChain(java.util.ArrayList<T> points,
                                                                     java.lang.Class<T> cls)
Computes the convex hull non-robustly (but quickly)

Parameters:
points - an ArrayList of points
cls - the class of the data
Returns:
the convex hull

monotoneChainRobust

public static <T extends Point> java.util.ArrayList<T> monotoneChainRobust(java.util.ArrayList<T> points,
                                                                           java.lang.Class<T> cls)
Computes the convex hull robustly

Parameters:
points - an ArrayList of points
cls - the class of the data
Returns:
the convex hull

monotoneChainRobust

public static <T extends Point> java.util.ArrayList<T> monotoneChainRobust(java.util.ArrayList<T> points,
                                                                           java.lang.Class<T> cls,
                                                                           boolean smoothHull,
                                                                           double ccwTol,
                                                                           double angleTol)
Computes the convex hull.

Parameters:
points - an ArrayList of points
cls - the class of the data
smoothHull - should the routine do robustness checks?
ccwTol - signed area tolerance
angleTol - angle tolerance
Returns:
the convex hull

monotoneChain

public static <T extends Point> T[] monotoneChain(T[] points,
                                                  java.lang.Class<T> cls)
Computes the convex hull non-robustly (but quickly)

Parameters:
points - an ArrayList of points
cls - the class of the data
Returns:
the convex hull

monotoneChainRobust

public static <T extends Point> T[] monotoneChainRobust(T[] points,
                                                        java.lang.Class<T> cls)
Computes the convex hull robustly

Parameters:
points - an ArrayList of points
cls - the class of the data
Returns:
the convex hull

monotoneChainRobust

public static <T extends Point> T[] monotoneChainRobust(T[] points,
                                                        java.lang.Class<T> cls,
                                                        boolean smoothHull,
                                                        double ccwTol,
                                                        double angleTol)
Computes the convex hull

Parameters:
points - an ArrayList of points
cls - the class of the data
smoothHull - should the routine do robustness checks?
ccwTol - signed area tolerance
angleTol - angle tolerance
Returns:
the convex hull

TripleIsRobust

private static boolean TripleIsRobust(Point A,
                                      Point B,
                                      Point C,
                                      double ccwTol,
                                      double angleTol)
Robustness check on the adjacent triple (A,B,C) on the hull

Parameters:
A - point
B - vertex point
C - point
ccwTol - signed area tolerance
angleTol - angle tolerance
Returns:
whether the adjacent triple (A,B,C) on the hull is robust

AppOrient2D

public static double AppOrient2D(Point A,
                                 Point B,
                                 Point C)
Non-robust signed area calculation


Filter

public static double Filter(Point A,
                            Point B,
                            Point C,
                            int filterType)
Robust signed area calucation


Verified1

public static double Verified1(Point A,
                               Point B,
                               Point C)

TwoSum

public static double[] TwoSum(double a,
                              double b)

TwoDiff

public static double[] TwoDiff(double a,
                               double b)

TwoProduct

public static double[] TwoProduct(double a,
                                  double b)

Split

private static double[] Split(double a)

getDetRobust

static double getDetRobust(Point A,
                           Point B,
                           Point C)

ExtractSum

public static RobustConvexHull.ExtractSumObject ExtractSum(double[] P,
                                                           double sigma)

AccSum_false

public static double AccSum_false(double[] P)

maxAbs

private static double maxAbs(double[] P)