|
|||||||||||
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 |