Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## edu.princeton.repeatedgames.rgsolve.polygon
Class RobustConvexHull

    java.lang.Object
      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.List<T>`
` | `monotoneChain(java.util.List<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.List<T>`
` | `monotoneChainRobust(java.util.List<T> points, java.lang.Class<T> cls)` Computes the convex hull robustly
`static
`<T extends Point> java.util.List<T>`
` | `monotoneChainRobust(java.util.List<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.List<T> monotoneChain(java.util.List<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.List<T> monotoneChainRobust(java.util.List<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.List<T> monotoneChainRobust(java.util.List<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)

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD