

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object  +org.moyoman.module.geometry.geometryimpl.ConvexHullImpl
This class computes the convex hull of a set of points. The algorithms used in here are taken from the book, Algorithms, by Robert Sedgewick. Note that the definition of a convex hull differs slightly from his, because he defines the convex hull as a minimum set of points, and in this class, all points that are on the convex hull are returned.
Field Summary  
private static HashMap 
convexHulls
The key is a Long from Zobrist, the value is the ConvexHullImpl object. 
private Point[] 
pich
These are the points which are inside of the convex hull. 
private Point[] 
points
These are the vertices of the convex hull. 
Constructor Summary  
private 
ConvexHullImpl(Point[] pts)
Create a ConvexHull object for the set of points. 
Method Summary  
private boolean 
checkEdge(Point pt,
Point[] points)
Check if the point in question is on an edge of the polygon. 
Object 
clone()
Override the Object.clone() method. 
private static Point 
findClosestColinearPoint(Point anchor,
Point next,
Set potential)
Find the closest point to the anchor on the same line as the next point. 
protected static int 
findGCD(int i1,
int i2)
Find the greatest common divisor of the two points. 
private static Point 
findMinimumVertical(Point[] points)
Find the point with the smallest y value. 
private static Point 
findNext(Point anchor,
Set potential,
double minangle)
Find the next point on the convex hull. 
static ConvexHullImpl 
get(Point[] pts)

Point[] 
getPointsInConvexHull()
Get the points inside of the convex hull. 
Point[] 
getPointsOnConvexHull()
Get all of the points on the convex hull, including the vertices. 
int 
getTotalPointsInConvexHull()
Get the number of points inside of the convex hull. 
Point[] 
getVertices()
Get the vertices of the convex hull. 
protected boolean 
isColinear()
Determine if all of the points of the convex hull are colinear. 
private static boolean 
isColinear(Point pt,
Point[] arr)
Determine if the given point is on the polygon formed by the array of points. 
protected static boolean 
isOnConvexHull(Point pt,
Point[] ch)
Determine if the given point falls on the convex hull. 
static void 
main(String[] args)
This is a test method for this class. 
private boolean 
testInside(float x,
float y)
This method tests a single point for being inside a polygon. 
private boolean 
testInside(Point pt)
Determine whether a point is inside a polygon. 
private static double 
theta(Point pt1,
Point pt2)
Compute the theta value for the two points. 
Methods inherited from class java.lang.Object 
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Field Detail 
private static HashMap convexHulls
private Point[] points
private Point[] pich
Constructor Detail 
private ConvexHullImpl(Point[] pts)
Method Detail 
public static void main(String[] args)
args
 The command line arguments.public static ConvexHullImpl get(Point[] pts)
public Point[] getVertices()
getVertices
in interface ConvexHull
private static Point findNext(Point anchor, Set potential, double minangle)
anchor
 The previous point found on the convex hull.potential
 The potential points on the convex hull.minangle
 The minimum angle to be used.
private static Point findClosestColinearPoint(Point anchor, Point next, Set potential)
anchor
 The first point in the line.next
 The second point in the line.potential
 The set of potential points being examined.
protected static boolean isOnConvexHull(Point pt, Point[] ch)
pt
 The point in question.ch
 The convex hull of points.
private static boolean isColinear(Point pt, Point[] arr)
pt
 The point in question.arr
 The points which make up the polygon.
protected boolean isColinear()
public Point[] getPointsOnConvexHull()
getPointsOnConvexHull
in interface ConvexHull
protected static int findGCD(int i1, int i2)
i1
 The first integer.i2
 The second integer.
private static Point findMinimumVertical(Point[] points)
points
 An array of Point objects.
private static double theta(Point pt1, Point pt2)
pt1
 The first point.pt2
 The second point.
public Point[] getPointsInConvexHull()
getPointsInConvexHull
in interface ConvexHull
public int getTotalPointsInConvexHull()
getTotalPointsInConvexHull
in interface ConvexHull
private boolean checkEdge(Point pt, Point[] points) throws IllegalArgumentException
pt
 The point in question.points
 The vertices of the polygon.
IllegalArgumentException
 Thrown if the point is not on an edge.private boolean testInside(Point pt)
pt
 The Point object to be tested.
private boolean testInside(float x, float y)
x
 The x coordinate of the point.y
 The y coordinate of the point.
public Object clone()
clone
in class Object


PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 