org.moyoman.module.geometry.geometryimpl
Class ConvexHullImpl

java.lang.Object
  |
  +--org.moyoman.module.geometry.geometryimpl.ConvexHullImpl

All Implemented Interfaces:

Cloneable, ConvexHull, Serializable

class ConvexHullImpl

extends Object

implements ConvexHull

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

convexHulls

private static HashMap convexHulls

The key is a Long from Zobrist, the value is the ConvexHullImpl object.

points

private Point[] points

These are the vertices of the convex hull.

pich

private Point[] pich

These are the points which are inside of the convex hull.

Constructor Detail

ConvexHullImpl

private ConvexHullImpl(Point[] pts)

Create a ConvexHull object for the set of points.

Method Detail

main

public static void main(String[] args)

This is a test method for this class. Eventually, code like this should be moved into a common testing framework.

Parameters:

args - The command line arguments.

get

public static ConvexHullImpl get(Point[] pts)

getVertices

public Point[] getVertices()

Get the vertices of the convex hull.

Specified by:

getVertices in interface ConvexHull

Returns:

An array of Point objects which are the vertices of the convex hull.

findNext

private static Point findNext(Point anchor,
                              Set potential,
                              double minangle)

Find the next point on the convex hull.

Parameters:

anchor - The previous point found on the convex hull.

potential - The potential points on the convex hull.

minangle - The minimum angle to be used.

Returns:

The point which is the next one on the convex hull.

findClosestColinearPoint

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.

Parameters:

anchor - The first point in the line.

next - The second point in the line.

potential - The set of potential points being examined.

Returns:

A Point on the same line as anchor and next, which may or may not be next.

isOnConvexHull

protected static boolean isOnConvexHull(Point pt,
                                        Point[] ch)

Determine if the given point falls on the convex hull.

Parameters:

pt - The point in question.

ch - The convex hull of points.

Returns:

true if the point is on the convex hull, or false.

isColinear

private static boolean isColinear(Point pt,
                                  Point[] arr)

Determine if the given point is on the polygon formed by the array of points.

Parameters:

pt - The point in question.

arr - The points which make up the polygon.

Returns:

true if the point is on any of the edges of the polygon, or false.

isColinear

protected boolean isColinear()

Determine if all of the points of the convex hull are colinear.

Returns:

true if they are all colinear, or false.

getPointsOnConvexHull

public Point[] getPointsOnConvexHull()

Get all of the points on the convex hull, including the vertices.

Specified by:

getPointsOnConvexHull in interface ConvexHull

Returns:

An array of Point objects which are the points on the convex hull.

findGCD

protected static int findGCD(int i1,
                             int i2)

Find the greatest common divisor of the two points. Since this is a special case, only need to try dividing by 2, 3, 5, and 7.

Parameters:

i1 - The first integer.

i2 - The second integer.

Returns:

The greatest common divisor, which is an integer.

findMinimumVertical

private static Point findMinimumVertical(Point[] points)

Find the point with the smallest y value. If two or more points have the same smallest y value, then return the one with the smallest x value as well.

Parameters:

points - An array of Point objects.

Returns:

The Point from the array with the smallest y value.

theta

private static double theta(Point pt1,
                            Point pt2)

Compute the theta value for the two points. For an explanation of this, see the book Algorithms, by RobertSedgewick.

Parameters:

pt1 - The first point.

pt2 - The second point.

Returns:

A double which is the theta value.

getPointsInConvexHull

public Point[] getPointsInConvexHull()

Get the points inside of the convex hull. All points are returned, which may be empty, or contain stones of either color. The points are not necessarily closest to this group than to any other.

Specified by:

getPointsInConvexHull in interface ConvexHull

Returns:

An array of Point objects.

getTotalPointsInConvexHull

public int getTotalPointsInConvexHull()

Get the number of points inside of the convex hull.

Specified by:

getTotalPointsInConvexHull in interface ConvexHull

Returns:

The number of points inside the convex hull.

checkEdge

private boolean checkEdge(Point pt,
                          Point[] points)
                   throws IllegalArgumentException

Check if the point in question is on an edge of the polygon.

Parameters:

pt - The point in question.

points - The vertices of the polygon.

Returns:

true if the point is on an edge of the polygon, or false.

Throws:

IllegalArgumentException - Thrown if the point is not on an edge.

testInside

private boolean testInside(Point pt)

Determine whether a point is inside a polygon. See the book, Algorithms, by Robert Sedgewick for more details. For the purposes of this module, a point on one of the edges of the polygons is considered to be outside the polygon.

Parameters:

pt - The Point object to be tested.

Returns:

A boolean value indicating whether the point is inside the polygon.

testInside

private boolean testInside(float x,
                           float y)

This method tests a single point for being inside a polygon. The caller of this method must ensure that the x, y coordinates are not on any of the edges of the polygon. It must also check that the polygon has at least three vertices, and that they are not colinear.

Parameters:

x - The x coordinate of the point.

y - The y coordinate of the point.

Returns:

true if the point is inside the convex hull, or false.

clone

public Object clone()

Override the Object.clone() method.

Overrides:

clone in class Object

Returns:

A ConvexHullImpl object which is a clone of this one.