|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectedu.princeton.repeatedgames.rgsolve.polygon.RobustConvexHull
public class RobustConvexHull
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
|
monotoneChain(java.util.ArrayList<T> points,
java.lang.Class<T> cls)
Computes the convex hull non-robustly (but quickly) |
|
static
|
monotoneChain(T[] points,
java.lang.Class<T> cls)
Computes the convex hull non-robustly (but quickly) |
|
static
|
monotoneChainRobust(java.util.ArrayList<T> points,
java.lang.Class<T> cls)
Computes the convex hull robustly |
|
static
|
monotoneChainRobust(java.util.ArrayList<T> points,
java.lang.Class<T> cls,
boolean smoothHull,
double ccwTol,
double angleTol)
Computes the convex hull. |
|
static
|
monotoneChainRobust(T[] points,
java.lang.Class<T> cls)
Computes the convex hull robustly |
|
static
|
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 |
---|
public static final double u
public static final double u_
public static final double uN
public static final double ANG_TOL
public static final double CCW_TOL
public static final double FACTOR
static final RobustConvexHull.PointComparator ptComparator
Constructor Detail |
---|
public RobustConvexHull()
Method Detail |
---|
public static <T extends Point> java.util.ArrayList<T> monotoneChain(java.util.ArrayList<T> points, java.lang.Class<T> cls)
points
- an ArrayList of pointscls
- the class of the data
- Returns:
- the convex hull
public static <T extends Point> java.util.ArrayList<T> monotoneChainRobust(java.util.ArrayList<T> points, java.lang.Class<T> cls)
points
- an ArrayList of pointscls
- the class of the data
- Returns:
- the convex hull
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)
points
- an ArrayList of pointscls
- the class of the datasmoothHull
- should the routine do robustness checks?ccwTol
- signed area toleranceangleTol
- angle tolerance
- Returns:
- the convex hull
public static <T extends Point> T[] monotoneChain(T[] points, java.lang.Class<T> cls)
points
- an ArrayList of pointscls
- the class of the data
- Returns:
- the convex hull
public static <T extends Point> T[] monotoneChainRobust(T[] points, java.lang.Class<T> cls)
points
- an ArrayList of pointscls
- the class of the data
- Returns:
- the convex hull
public static <T extends Point> T[] monotoneChainRobust(T[] points, java.lang.Class<T> cls, boolean smoothHull, double ccwTol, double angleTol)
points
- an ArrayList of pointscls
- the class of the datasmoothHull
- should the routine do robustness checks?ccwTol
- signed area toleranceangleTol
- angle tolerance
- Returns:
- the convex hull
private static boolean TripleIsRobust(Point A, Point B, Point C, double ccwTol, double angleTol)
A
- pointB
- vertex pointC
- pointccwTol
- signed area toleranceangleTol
- angle tolerance
public static double AppOrient2D(Point A, Point B, Point C)
public static double Filter(Point A, Point B, Point C, int filterType)
public static double Verified1(Point A, Point B, Point C)
public static double[] TwoSum(double a, double b)
public static double[] TwoDiff(double a, double b)
public static double[] TwoProduct(double a, double b)
private static double[] Split(double a)
static double getDetRobust(Point A, Point B, Point C)
public static RobustConvexHull.ExtractSumObject ExtractSum(double[] P, double sigma)
public static double AccSum_false(double[] P)
private static double maxAbs(double[] P)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |