y.geom
Class Geom

java.lang.Object
  |
  +--y.geom.Geom

public final class Geom

extends Object

This class provides useful geometric primitives and advanced geometric algorithms.

This class is intended to provide static methods for geometric calculations. It can be compared to the class java.lang.Math which provides methods for general mathematic calculations.

Method Summary

static YList	calcConvexHull(YList points) Calculates the convex hull for a set of points.
static boolean	collinear(YPoint p, YPoint q, YPoint r) Returns true iff the given points are colinear, i.e. all three points lie on a common line.
static boolean	leftTurn(YPoint p, YPoint q, YPoint r) Same as orientation(p,q,r) > 0
static int	orientation(double px, double py, double qx, double qy, double rx, double ry) Same as #orientation(YPoint, YPoint, YPoint) with double values as arguments.
static int	orientation(YPoint p, YPoint q, YPoint r) Returns the orientation of point r relative to the directed line from point p to point q.
static boolean	rightTurn(YPoint p, YPoint q, YPoint r) Same as orientation(p,q,r) < 0
static int	sideOfCircle(YPoint a, YPoint b, YPoint c, YPoint d) Returns +1 if point d lies left of the directed circle through points a, b, and c, 0 if a,b,c and d are cocircular, and -1 otherwise.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

orientation

public static int orientation(YPoint p,
                              YPoint q,
                              YPoint r)

Returns the orientation of point r relative to the directed line from point p to point q.

The given tuple of points is said to have positive orientation if p and q are distinct and r lies to the left of the oriented line passing through p and q and oriented from p to q.

The tuple is said to have negative orientation if p and q are distinct and r lies to the right of the line, and the tuple is said to have orientation zero if the three points are colinear.

Returns:

+1 in the case of positive orientation, -1 in the case of negative orientation and 0 in the case of zero orientation.

orientation

public static int orientation(double px,
                              double py,
                              double qx,
                              double qy,
                              double rx,
                              double ry)

Same as #orientation(YPoint, YPoint, YPoint) with double values as arguments.

leftTurn

public static boolean leftTurn(YPoint p,
                               YPoint q,
                               YPoint r)

Same as orientation(p,q,r) > 0

rightTurn

public static boolean rightTurn(YPoint p,
                                YPoint q,
                                YPoint r)

Same as orientation(p,q,r) < 0

collinear

public static boolean collinear(YPoint p,
                                YPoint q,
                                YPoint r)

Returns true iff the given points are colinear, i.e. all three points lie on a common line.

Same as orientation(p,q,r) == 0

sideOfCircle

public static int sideOfCircle(YPoint a,
                               YPoint b,
                               YPoint c,
                               YPoint d)

Returns +1 if point d lies left of the directed circle through points a, b, and c, 0 if a,b,c and d are cocircular, and -1 otherwise.

calcConvexHull

public static YList calcConvexHull(YList points)

Calculates the convex hull for a set of points.

Complexity: O(n)*log(n), n := points.size()

Parameters:

points - a list of YPoint objects

Returns:

a list of YPoint objects that constitute the convex hull of the given points. The list contains points in anticlockwise order around the hull. the first point is the one with the smallest x coordinate. If two such points exist then of these points the one with the smallest y coordinate is chosen as the first one.