org.moyoman.module.geometry
Interface Geometry

All Superinterfaces:
Cloneable, ModuleInterface, Serializable
All Known Implementing Classes:
GeometryImpl

public interface Geometry
extends ModuleInterface

A class that implements this interface will be computing geometrical information about the board. This includes information such as which empty points are closest to a given loose group, which stones and points make up the convex hull of a set of points, and which groups are adjacent to, or enclosed by a loose group.

There are two different methods for computing the convex hull, one that uses associated edge points, and one that does not. See the LooseGroups module documentation for an explanation of associated edge points. Consider a two space extension on the third line from a stone on the third line as an example. The getConvexHull() method would just return the two stones. The getConvexHullWithEdgePoints() method would return the two stones, as well as the two stones on the edge directly beneath the two stones, which would form a rectangle with four empty points inside.


Field Summary
static float CONFIDENCE
           
 
Method Summary
 boolean areLooseGroupsAdjacent(SingleLooseGroup slg1, SingleLooseGroup slg2)
          Determine if two loose groups are adjacent to each other.
 SingleLooseGroup[] getAdjacentGroups(SingleLooseGroup slg)
          Get all of the groups which are adjacent to the specified group.
 Point[] getBorderPointsBetweenGroups(SingleLooseGroup slg1, SingleLooseGroup slg2)
          Return the empty points midway between two adjacent loose groups.
 Point[] getClosestEmptyPoints(SingleLooseGroup slg)
          Get the empty points that are as close or closer to the specified group than to any other.
 HashMap getClosestStones(SingleLooseGroup slg1, SingleLooseGroup slg2)
          Get the closest stones between two loose groups.
 Point[] getClosestUniqueEmptyPoints(SingleLooseGroup slg)
          Get the empty points that are closer to the specified group than to any other.
 ConvexHull getConvexHull(Point[] points)
          Get the convex hull for the specified points.
 ConvexHull getConvexHull(SingleLooseGroup slg)
          Return the convex hull of the specified group.
 ConvexHull getConvexHullByColor(Stone stone)
          Get the convex hull for all of the adjacent stones of the same color as the specified stone.
 ConvexHull getConvexHullWithEdgePoints(SingleLooseGroup slg)
          Return the convex hull of the specified group.
 short getDistanceToClosestStone(Point pt)
          Determine the distance from the point to the nearest stone.
 SingleLooseGroup[] getEnclosedGroups(SingleLooseGroup slg)
          Return all of the groups which are enclosed by the specified group.
 Point[] getPointsBetweenGroups(SingleLooseGroup slg1, SingleLooseGroup slg2)
          Return the empty points between two adjacent loose groups.
 SingleLooseGroup[] getSingleLooseGroups(Point pt)
          Get all of the loose groups which are closest to the given point.
 int getTotalClosestEmptyPoints(SingleLooseGroup slg)
          Get the number of points which are closer to this group than any other.
 float getTotalUniqueClosestEmptyPoints(SingleLooseGroup slg)
          Get the number of points which are closer to this group than any other.
 boolean isAdjacentToCorner(SingleLooseGroup slg)
          Determine if the loose group is adjacent to any corner of the board.
 boolean isAdjacentToSide(SingleLooseGroup slg)
          Determine if the loose group is adjacent to any side of the board.
 
Methods inherited from interface org.moyoman.module.ModuleInterface
clone, getMoves, getScheduler
 

Field Detail

CONFIDENCE

public static final float CONFIDENCE
See Also:
Constant Field Values
Method Detail

getAdjacentGroups

public SingleLooseGroup[] getAdjacentGroups(SingleLooseGroup slg)
Get all of the groups which are adjacent to the specified group. The definition of adjacent is that for the given group, if any of its stones, or any of the empty points which are as close to it as to the stones of any other group are adjacent to the stones or empty points of another group, then the two groups are adjacent.

Parameters:
slg - The SingleLooseGroup in question.
Returns:
An array of SingleLooseGroup objects.

getEnclosedGroups

public SingleLooseGroup[] getEnclosedGroups(SingleLooseGroup slg)
Return all of the groups which are enclosed by the specified group. A group is considered to be enclosed by the specified group if two conditions are met. The first is that a call to getAdjacentGroups() on the enclosed group would return an array size of 1, which would be the enclosing group. The second condition is that the bounding box for the enclosed group must be completely contained by the bounding box for the enclosing group.

Parameters:
slg - The SingleLooseGroup in question.
Returns:
An array of SingleLooseGroup objects.

getConvexHull

public ConvexHull getConvexHull(SingleLooseGroup slg)
Return the convex hull of the specified group. The vertices of the convex hull are a subset of the stones in the loose group.

A convex hull is a standard geometrical concept. Basically, if a wooden board had pins placed in it that represented the stones, and a rubber band was stretched so that all of the pins were inside, the shape that the rubber band assumes is the convex hull. This method should return the maximal set of stones on the convex hull. See the book, Algorithms, by Robert Sedgewick for more details.

Parameters:
slg - The SingleLooseGroup in question.
Returns:
A ConvexHull for the loose group.

getConvexHull

public ConvexHull getConvexHull(Point[] points)
Get the convex hull for the specified points.

Returns:
A ConvexHull object.

getConvexHullByColor

public ConvexHull getConvexHullByColor(Stone stone)
                                throws NoSuchDataException
Get the convex hull for all of the adjacent stones of the same color as the specified stone.

Parameters:
stone - The specified stone.
Returns:
A ConvexHull object.
Throws:
NoSuchDataException - Thrown if the stone is not on the board.

getConvexHullWithEdgePoints

public ConvexHull getConvexHullWithEdgePoints(SingleLooseGroup slg)
Return the convex hull of the specified group. The vertices of the convex hull include a subset of the stones in the loose group as well as a subset of the associated edge points.

A convex hull is a standard geometrical concept. Basically, if a wooden board had pins placed in it that represented the stones, and a rubber band was stretched so that all of the pins were inside, the shape that the rubber band assumes is the convex hull. This method should return the maximal set of stones and points on the convex hull. See the book, Algorithms, by Robert Sedgewick for more details.

Parameters:
slg - The SingleLooseGroup in question.
Returns:
A ConvexHull for the loose group.

getClosestEmptyPoints

public Point[] getClosestEmptyPoints(SingleLooseGroup slg)
Get the empty points that are as close or closer to the specified group than to any other. The distance of an empty point from a group is the distance to the closest stone in that group. If the distance to a given group is less than or equal to that of any other group, then the point is considered to be closest to that group. Note that by this definition, an empty point may be part of the array returned by this method for more than one group.

Parameters:
slg - The SingleLooseGroup in question.
Returns:
An array of Point objects.

getClosestUniqueEmptyPoints

public Point[] getClosestUniqueEmptyPoints(SingleLooseGroup slg)
Get the empty points that are closer to the specified group than to any other. The distance of an empty point from a group is the distance to the closest stone in that group. If the distance to a given group is less than the distance of that to any other group, then the point is considered to be closest to that group. So, this method returns a subset of the points returned by getClosestEmptyPoints(), which will be the same if there are no empty points which are equally close between this group and another.

Parameters:
slg - The SingleLooseGroup in question.
Returns:
An array of Point objects.

getPointsBetweenGroups

public Point[] getPointsBetweenGroups(SingleLooseGroup slg1,
                                      SingleLooseGroup slg2)
                               throws IllegalArgumentException
Return the empty points between two adjacent loose groups. If two groups of stones are adjacent, then the points that would be returned by this method must meet the following conditions:
  1. The point is closer to at least one of these two groups than any other.
  2. The distance from the point to the closest stone in either group is less than the distance between the closest stones of these two groups.

Parameters:
slg1 - One of the loose groups.
slg2 - The other loose group.
Returns:
An array of Point objects, which may be of size 0 even if the groups are adjacent.
Throws:
IllegalArgumentException - Thrown if the two groups are not adjacent.

getBorderPointsBetweenGroups

public Point[] getBorderPointsBetweenGroups(SingleLooseGroup slg1,
                                            SingleLooseGroup slg2)
                                     throws IllegalArgumentException
Return the empty points midway between two adjacent loose groups. If two groups of stones are adjacent, the the points that would be returned by this method are a subset of the points that would be returned by the getPointsBetweenGroups method. The additional conditions are the following:
  1. The point is equally distant from the two groups.
  2. For the point and an adjacent one, one point is closest to each of the two groups.

IllegalArgumentException

getSingleLooseGroups

public SingleLooseGroup[] getSingleLooseGroups(Point pt)
Get all of the loose groups which are closest to the given point.

Parameters:
pt - The point in question.
Returns:
An array of SingleLooseGroup objects.

getTotalUniqueClosestEmptyPoints

public float getTotalUniqueClosestEmptyPoints(SingleLooseGroup slg)
Get the number of points which are closer to this group than any other. Since some points may be shared by more than one group, the return value is a float. If a point is shared by two groups, then it counts as a half, if by three groups, then a third, and so on.

Parameters:
slg - The SingleLooseGroup in question.
Returns:
A float which is the total closest empty points.

getTotalClosestEmptyPoints

public int getTotalClosestEmptyPoints(SingleLooseGroup slg)
Get the number of points which are closer to this group than any other. This value is just the size of the array returned by getClosestEmptyPoints(). Each point is counted once, even if it is shared with other groups.

Parameters:
slg - The SingleLooseGroup in question.
Returns:
An int which is the total number of empty points closest to this group.

getClosestStones

public HashMap getClosestStones(SingleLooseGroup slg1,
                                SingleLooseGroup slg2)
Get the closest stones between two loose groups. For any two loose groups on the board there is a pair of stones, one from each loose group, such that there is no other pair of stones which are closer together. It may well be the case that there is more than one pair of stones which are equally close, so a HashMap is returned, where the keys are the stones from loose group 1, and the values are the corresponding stone from loose group 2.

This distance is measured without taking into account whether there are any stones of other loose groups in between, so it is not an error to call this method on two loose groups which are not adjacent to each other.

Parameters:
slg1 - The first loose group
Returns:
A HashMap object, where the keys are Stone objects in slg1, and the values are Stone objects in slg2.

isAdjacentToSide

public boolean isAdjacentToSide(SingleLooseGroup slg)
Determine if the loose group is adjacent to any side of the board. A loose group is considered to be adjacent to the side of the board if any of the points on any of the edges are as close or closer to this loose group than to any other loose group.

Parameters:
slg - The loose group.
Returns:
true if the loose group is adjacent to the side, or false.

isAdjacentToCorner

public boolean isAdjacentToCorner(SingleLooseGroup slg)
Determine if the loose group is adjacent to any corner of the board. A loose group is considered to be adjacent to the corner of the board if any of the four corner points are as close or closer to this loose group than to any other loose group.

Parameters:
slg - The loose group.
Returns:
true if the loose group is adjacent to the corner, or false.

areLooseGroupsAdjacent

public boolean areLooseGroupsAdjacent(SingleLooseGroup slg1,
                                      SingleLooseGroup slg2)
Determine if two loose groups are adjacent to each other. In determining whether the loose groups are adjacent, the set of points for each group which are either a stone of that group, or an empty point returned by getClosestEmptyPoints() are used. If one of the points from the set for the first loose group is adjacent to one of the points from the set for the second loose group, then then ae considered to be adjacent. Note that the same empty point could be in both sets in which case this method would also return true.

So as an example, in a cross cut there are four groups. Each black stone is adjacent to the two loose groups containing a white stone, but not to the loose group containing the other black stone.

Parameters:
slg1 - The first loose group
Returns:
true if the two loose groups are adjacent, or false.

getDistanceToClosestStone

public short getDistanceToClosestStone(Point pt)
Determine the distance from the point to the nearest stone. The distance is the square of the geometric distance, so if the point is 7,3 and the nearest stone is at 11, 5, then the value 40 would be returned. The square of the distance is used because it is simpler comparing equality of distances using short than float. If the actual distance is needed, use the org.moyoman.util.Sqrt class for conversion.

Parameters:
pt - The point in question.
Returns:
The geometric distance between the point and the closest stone.