y.geom
Class Geom

java.lang.Object
  y.geom.Geom

public final class Geom
extends java.lang.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 mathematical calculations.

Method Summary

static YList	calcConvexHull(YList points) Calculates the convex hull for a set of points.
static YPoint	calcIntersection(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) Calculates the intersection point of two affine lines.
static java.awt.geom.Rectangle2D	calcIntersection(java.awt.geom.Rectangle2D r1, java.awt.geom.Rectangle2D r2, java.awt.geom.Rectangle2D dest) Intersects the pair of specified source Rectangle2D objects and puts the result into the specified destination Rectangle2D object.
static YPoint	calcIntersection(YPoint p1, YPoint p2, YPoint p3, YPoint p4) Calculates the intersection point of two affine lines.
static YPoint	calcIntersection(YPoint p1, YVector d1, YPoint p2, YVector d2) Calculates the intersection point of two affine lines.
static java.awt.geom.Rectangle2D	calcTransformedBounds(double x, double y, double width, double height, java.awt.geom.AffineTransform transform, java.awt.geom.Rectangle2D dest) Calculates the bounding box of the rectangle at location (x,y) with the specified width and height after the specified transformation has been applied.
static java.awt.geom.Rectangle2D	calcUnion(java.awt.geom.Rectangle2D r1, java.awt.geom.Rectangle2D r2, java.awt.geom.Rectangle2D dest) Unions the pair of source Rectangle2D objects and puts the result into the specified destination Rectangle2D object.
static boolean	collinear(YPoint p, YPoint q, YPoint r) Returns true iff the given points are collinear, that is, all three points lie on a common line.
static double	distanceToLineSegment(double pointX, double pointY, double lineX1, double lineY1, double lineX2, double lineY2) Determines the distance of the point p to the line segment [l1, l2].
static boolean	leftTurn(YPoint p, YPoint q, YPoint r) Same as orientation(p,q,r) > 0
static boolean	linesIntersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) Same as Line2D.linesIntersect(double, double, double, double, double, double, double, double).
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 YPoint	projection(double pointX, double pointY, double lineX1, double lineY1, double lineX2, double lineY2) Determines the projection of the point p onto the line segment [l1, l2].
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.
static double	toDegrees(double angrad) Same as Math.toDegrees(double).
static double	toRadians(double angdeg) Same as Math.toRadians(double).

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

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 collinear, that is, 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 counter clockwise 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.

toRadians

public static double toRadians(double angdeg)

Same as Math.toRadians(double).

toDegrees

public static double toDegrees(double angrad)

Same as Math.toDegrees(double).

calcIntersection

public static YPoint calcIntersection(YPoint p1,
                                      YVector d1,
                                      YPoint p2,
                                      YVector d2)

Calculates the intersection point of two affine lines. Each line is given by a point and a direction vector.

Parameters:

p1 - origin point of the first line.

d1 - direction vector of the first line.

p2 - origin point of the second line.

d2 - direction vector of the second line.

Returns:

the intersection point of the specified lines or null if there is no intersection.

calcIntersection

public static YPoint calcIntersection(YPoint p1,
                                      YPoint p2,
                                      YPoint p3,
                                      YPoint p4)

Calculates the intersection point of two affine lines. Each line is given by two points.

Parameters:

p1 - one point on the first line.

p2 - another point on the first line.

p3 - one point on the second line.

p4 - another point on the second line.

Returns:

the intersection point of the specified lines or null if there is no intersection.

calcIntersection

public static YPoint calcIntersection(double x1,
                                      double y1,
                                      double x2,
                                      double y2,
                                      double x3,
                                      double y3,
                                      double x4,
                                      double y4)

Calculates the intersection point of two affine lines. Each line is given by the coordinates of two points.

Parameters:

x1 - x-coordinate of one point on the first line.

y1 - y-coordinate of one point on the first line.

x2 - x-coordinate of another point on the first line.

y2 - y-coordinate of another point on the first line.

x3 - x-coordinate of one point on the second line.

y3 - y-coordinate of one point on the second line.

x4 - x-coordinate of another point on the second line.

y4 - y-coordinate of another point on the second line.

Returns:

the intersection point of the specified lines or null if there is no intersection.

linesIntersect

public static boolean linesIntersect(double x1,
                                     double y1,
                                     double x2,
                                     double y2,
                                     double x3,
                                     double y3,
                                     double x4,
                                     double y4)

Same as Line2D.linesIntersect(double, double, double, double, double, double, double, double).

projection

public static YPoint projection(double pointX,
                                double pointY,
                                double lineX1,
                                double lineY1,
                                double lineX2,
                                double lineY2)

Determines the projection of the point p onto the line segment [l1, l2]. The resulting point is

• the orthogonal projection of p onto the line through l1 and l2, iff the projection lies on the line segment [l1, l2]
• the end point of the line segment [l1, l2] that is closest to p
, otherwise

Parameters:

pointX - the x coordinate of p

pointY - the y coordinate of p

lineX1 - the x coordinate of l1

lineY1 - the y coordinate of l1

lineX2 - the x coordinate of l2

lineY2 - the y coordinate of l2

distanceToLineSegment

public static double distanceToLineSegment(double pointX,
                                           double pointY,
                                           double lineX1,
                                           double lineY1,
                                           double lineX2,
                                           double lineY2)

Determines the distance of the point p to the line segment [l1, l2].

Parameters:

pointX - the x coordinate of p

pointY - the y coordinate of p

lineX1 - the x coordinate of l1

lineY1 - the y coordinate of l1

lineX2 - the x coordinate of l2

lineY2 - the y coordinate of l2

calcUnion

public static java.awt.geom.Rectangle2D calcUnion(java.awt.geom.Rectangle2D r1,
                                                  java.awt.geom.Rectangle2D r2,
                                                  java.awt.geom.Rectangle2D dest)

Unions the pair of source Rectangle2D objects and puts the result into the specified destination Rectangle2D object. If one of the source rectangles has negative width or height, it is excluded from the union. If both source rectangles have negative width or height, the destination rectangle will become a copy of r1. One of the source rectangles can also be the destination to avoid creating a third Rectangle2D object, but in this case the original points of this source rectangle will be overwritten by this method. If the destination is null, a new Rectangle2D is created.

Parameters:

r1 - the first of a pair of Rectangle2D objects to be combined with each other

r2 - the second of a pair of Rectangle2D objects to be combined with each other

dest - the Rectangle2D that holds the results of the union of r1 and r2

calcIntersection

public static java.awt.geom.Rectangle2D calcIntersection(java.awt.geom.Rectangle2D r1,
                                                         java.awt.geom.Rectangle2D r2,
                                                         java.awt.geom.Rectangle2D dest)

Intersects the pair of specified source Rectangle2D objects and puts the result into the specified destination Rectangle2D object. If one or both of the source rectangles have negative width or height, the resulting rectangle will be located at (0,0) with a width and height of -1. One of the source rectangles can also be the destination to avoid creating a third Rectangle2D object, but in this case the original points of this source rectangle will be overwritten by this method.

Parameters:

r1 - the first of a pair of Rectangle2D objects to be intersected with each other

r2 - the second of a pair of Rectangle2D objects to be intersected with each other

dest - the Rectangle2D that holds the results of the intersection of r1 and r2

calcTransformedBounds

public static java.awt.geom.Rectangle2D calcTransformedBounds(double x,
                                                              double y,
                                                              double width,
                                                              double height,
                                                              java.awt.geom.AffineTransform transform,
                                                              java.awt.geom.Rectangle2D dest)

Calculates the bounding box of the rectangle at location (x,y) with the specified width and height after the specified transformation has been applied.

Parameters:

x - the x coordinate of the rectangle to be transformed

y - the y coordinate of the rectangle to be transformed

width - the width of the rectangle to be transformed

height - the height of the rectangle to be transformed

transform - the AffineTransform to be applied

dest - the Rectangle2D that holds the bounding box of the transformed input