com.vividsolutions.jts.algorithm
Class CGAlgorithms

java.lang.Object
  com.vividsolutions.jts.algorithm.CGAlgorithms

Direct Known Subclasses:

NonRobustCGAlgorithms, RobustCGAlgorithms

public class CGAlgorithms
extends java.lang.Object

Specifies and implements various fundamental Computational Geometric algorithms. The algorithms supplied in this class are robust for double-precision floating point.

Version:

1.7

Field Summary

static int	CLOCKWISE A value that indicates an orientation of clockwise, or a right turn.
static int	COLLINEAR A value that indicates an orientation of collinear, or no turn (straight).
static int	COUNTERCLOCKWISE A value that indicates an orientation of counterclockwise, or a left turn.
static int	LEFT
static int	RIGHT
static int	STRAIGHT

Constructor Summary

CGAlgorithms()

Method Summary

static int	computeOrientation(Coordinate p1, Coordinate p2, Coordinate q) Computes the orientation of a point q to the directed line segment p1-p2.
static double	distanceLineLine(Coordinate A, Coordinate B, Coordinate C, Coordinate D) Computes the distance from a line segment AB to a line segment CD Note: NON-ROBUST!
static double	distancePointLine(Coordinate p, Coordinate[] line) Computes the distance from a point to a sequence of line segments.
static double	distancePointLine(Coordinate p, Coordinate A, Coordinate B) Computes the distance from a point p to a line segment AB Note: NON-ROBUST!
static double	distancePointLinePerpendicular(Coordinate p, Coordinate A, Coordinate B) Computes the perpendicular distance from a point p to the (infinite) line containing the points AB
static boolean	isCCW(Coordinate[] ring) Computes whether a ring defined by an array of Coordinates is oriented counter-clockwise.
static boolean	isOnLine(Coordinate p, Coordinate[] pt) Tests whether a point lies on the line segments defined by a list of coordinates.
static boolean	isPointInRing(Coordinate p, Coordinate[] ring) Tests whether a point lies inside or on a ring.
static double	length(CoordinateSequence pts) Computes the length of a linestring specified by a sequence of points.
static int	locatePointInRing(Coordinate p, Coordinate[] ring) Determines whether a point lies in the interior, on the boundary, or in the exterior of a ring.
static int	orientationIndex(Coordinate p1, Coordinate p2, Coordinate q) Returns the index of the direction of the point q relative to a vector specified by p1-p2.
static double	signedArea(Coordinate[] ring) Computes the signed area for a ring.
static double	signedArea(CoordinateSequence ring) Computes the signed area for a ring.

Methods inherited from class java.lang.Object

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

Field Detail

CLOCKWISE

public static final int CLOCKWISE

A value that indicates an orientation of clockwise, or a right turn.

See Also:

Constant Field Values

RIGHT

public static final int RIGHT

See Also:

Constant Field Values

COUNTERCLOCKWISE

public static final int COUNTERCLOCKWISE

A value that indicates an orientation of counterclockwise, or a left turn.

See Also:

Constant Field Values

LEFT

public static final int LEFT

See Also:

Constant Field Values

COLLINEAR

public static final int COLLINEAR

A value that indicates an orientation of collinear, or no turn (straight).

See Also:

Constant Field Values

STRAIGHT

public static final int STRAIGHT

See Also:

Constant Field Values

Constructor Detail

CGAlgorithms

public CGAlgorithms()

Method Detail

orientationIndex

public static int orientationIndex(Coordinate p1,
                                   Coordinate p2,
                                   Coordinate q)

Returns the index of the direction of the point q relative to a vector specified by p1-p2.

Parameters:

p1 - the origin point of the vector

p2 - the final point of the vector

q - the point to compute the direction to

Returns:

1 if q is counter-clockwise (left) from p1-p2

isPointInRing

public static boolean isPointInRing(Coordinate p,
                                    Coordinate[] ring)

Tests whether a point lies inside or on a ring. The ring may be oriented in either direction. A point lying exactly on the ring boundary is considered to be inside the ring.

This method does not first check the point against the envelope of the ring.

Parameters:

p - point to check for ring inclusion

ring - an array of coordinates representing the ring (which must have first point identical to last point)

Returns:

true if p is inside ring

See Also:

locatePointInRing

locatePointInRing

public static int locatePointInRing(Coordinate p,
                                    Coordinate[] ring)

Determines whether a point lies in the interior, on the boundary, or in the exterior of a ring. The ring may be oriented in either direction.

This method does not first check the point against the envelope of the ring.

Parameters:

p - point to check for ring inclusion

ring - an array of coordinates representing the ring (which must have first point identical to last point)

Returns:

the Location of p relative to the ring

isOnLine

public static boolean isOnLine(Coordinate p,
                               Coordinate[] pt)

Tests whether a point lies on the line segments defined by a list of coordinates.

Returns:

true if the point is a vertex of the line or lies in the interior of a line segment in the linestring

isCCW

public static boolean isCCW(Coordinate[] ring)

Computes whether a ring defined by an array of Coordinates is oriented counter-clockwise.

• The list of points is assumed to have the first and last points equal.
• This will handle coordinate lists which contain repeated points.

This algorithm is only guaranteed to work with valid rings. If the ring is invalid (e.g. self-crosses or touches), the computed result may not be correct.

Parameters:

ring - an array of Coordinates forming a ring

Returns:

true if the ring is oriented counter-clockwise.

Throws:

java.lang.IllegalArgumentException - if there are too few points to determine orientation (< 3)

computeOrientation

public static int computeOrientation(Coordinate p1,
                                     Coordinate p2,
                                     Coordinate q)

Computes the orientation of a point q to the directed line segment p1-p2. The orientation of a point relative to a directed line segment indicates which way you turn to get to q after travelling from p1 to p2.

Returns:

1 if q is counter-clockwise from p1-p2

distancePointLine

public static double distancePointLine(Coordinate p,
                                       Coordinate A,
                                       Coordinate B)

Computes the distance from a point p to a line segment AB Note: NON-ROBUST!

Parameters:

p - the point to compute the distance for

A - one point of the line

B - another point of the line (must be different to A)

Returns:

the distance from p to line segment AB

distancePointLinePerpendicular

public static double distancePointLinePerpendicular(Coordinate p,
                                                    Coordinate A,
                                                    Coordinate B)

Computes the perpendicular distance from a point p to the (infinite) line containing the points AB

Parameters:

p - the point to compute the distance for

A - one point of the line

B - another point of the line (must be different to A)

Returns:

the distance from p to line AB

distancePointLine

public static double distancePointLine(Coordinate p,
                                       Coordinate[] line)

Computes the distance from a point to a sequence of line segments.

Parameters:

p - a point

line - a sequence of contiguous line segments defined by their vertices

Returns:

the minimum distance between the point and the line segments

distanceLineLine

public static double distanceLineLine(Coordinate A,
                                      Coordinate B,
                                      Coordinate C,
                                      Coordinate D)

Computes the distance from a line segment AB to a line segment CD Note: NON-ROBUST!

Parameters:

A - a point of one line

B - the second point of (must be different to A)

C - one point of the line

D - another point of the line (must be different to A)

signedArea

public static double signedArea(Coordinate[] ring)

Computes the signed area for a ring. The signed area is positive if the ring is oriented CW, negative if the ring is oriented CCW, and zero if the ring is degenerate or flat.

Parameters:

ring - the coordinates forming the ring

Returns:

the signed area of the ring

signedArea

public static double signedArea(CoordinateSequence ring)

Computes the signed area for a ring. The signed area is:

• positive if the ring is oriented CW
• negative if the ring is oriented CCW
• zero if the ring is degenerate or flat

Parameters:

ring - the coordinates forming the ring

Returns:

the signed area of the ring

length

public static double length(CoordinateSequence pts)

Computes the length of a linestring specified by a sequence of points.

Parameters:

pts - the points specifying the linestring

Returns:

the length of the linestring