com.revolsys.jts.algorithm

Class LineIntersector

java.lang.Object

com.revolsys.jts.algorithm.LineIntersector

Direct Known Subclasses:

NonRobustLineIntersector, RobustLineIntersector

public abstract class LineIntersector
extends Object

A LineIntersector is an algorithm that can both test whether two line segments intersect and compute the intersection point(s) if they do.

There are three possible outcomes when determining whether two line segments intersect:

• NO_INTERSECTION - the segments do not intersect
• #POINT_INTERSECTION - the segments intersect in a single point
• {@link #COLLINEAR_INTERSECTION - the segments are collinear and they intersect in a line segment

For segments which intersect in a single point, the point may be either an endpoint or in the interior of each segment. If the point lies in the interior of both segments, this is termed a proper intersection. The method {@link #isProper()} test for this situation.

The intersection point(s) may be computed in a precise or non-precise manner. Computing an intersection point precisely involves rounding it via a supplied scale.

LineIntersectors do not perform an initial envelope intersection test to determine if the segments are disjoint. This is because this class is likely to be used in a context where envelope overlap is already known to occur (or be likely).

Version:

1.7

Field Summary

Fields

Modifier and Type	Field and Description
static int	COLLINEAR
static int	COLLINEAR_INTERSECTION Indicates that line segments intersect in a line segment
static int	DO_INTERSECT
static int	DONT_INTERSECT These are deprecated, due to ambiguous naming
protected Point[][]	inputLines
protected int[][]	intLineIndex The indexes of the endpoints of the intersection lines, in order along the corresponding line
protected Point[]	intPt
protected boolean	isProper
static int	NO_INTERSECTION Indicates that line segments do not intersect
protected Point	pa
protected Point	pb
static int	POINT_INTERSECTION Indicates that line segments intersect in a single point
protected int	result

Constructor Summary

Constructors

Constructor and Description
LineIntersector()
LineIntersector(double scale)

Method Summary

Methods

Modifier and Type	Method and Description
static double	computeEdgeDistance(Point p, Point p0, Point p1) Computes the "edge distance" of an intersection point p along a segment.
protected abstract int	computeIntersect(Point p1, Point p2, Point q1, Point q2)
abstract void	computeIntersection(Point p, Point p1, Point p2) Compute the intersection of a point p and the line p1-p2.
void	computeIntersection(Point p1, Point p2, Point p3, Point p4) Computes the intersection of the lines p1-p2 and p3-p4.
protected void	computeIntLineIndex()
protected void	computeIntLineIndex(int segmentIndex)
double	getEdgeDistance(int segmentIndex, int intIndex) Computes the "edge distance" of an intersection point along the specified input line segment.
Point	getEndpoint(int segmentIndex, int ptIndex) Gets an endpoint of an input segment.
int	getIndexAlongSegment(int segmentIndex, int intIndex) Computes the index (order) of the intIndex'th intersection point in the direction of a specified input line segment
Point	getIntersection(int intIndex) Returns the intIndex'th intersection point
Point	getIntersectionAlongSegment(int segmentIndex, int intIndex) Computes the intIndex'th intersection point in the direction of a specified input line segment
int	getIntersectionNum() Returns the number of intersection points found.
double	getScale()
boolean	hasIntersection() Tests whether the input geometries intersect.
protected boolean	isCollinear()
protected boolean	isEndPoint()
boolean	isInteriorIntersection() Tests whether either intersection point is an interior point of one of the input segments.
boolean	isInteriorIntersection(int inputLineIndex) Tests whether either intersection point is an interior point of the specified input segment.
boolean	isIntersection(Point pt) Test whether a point is a intersection point of two line segments.
boolean	isProper() Tests whether an intersection is proper.
static double	nonRobustComputeEdgeDistance(Point p, Point p1, Point p2) This function is non-robust, since it may compute the square of large numbers.
void	setScale(double scale)
String	toString()

Methods inherited from class java.lang.Object

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

Field Detail

DONT_INTERSECT

public static final int DONT_INTERSECT

These are deprecated, due to ambiguous naming

See Also:

Constant Field Values

DO_INTERSECT

public static final int DO_INTERSECT

See Also:

Constant Field Values

COLLINEAR

public static final int COLLINEAR

See Also:

Constant Field Values

NO_INTERSECTION

public static final int NO_INTERSECTION

Indicates that line segments do not intersect

See Also:

Constant Field Values

POINT_INTERSECTION

public static final int POINT_INTERSECTION

Indicates that line segments intersect in a single point

See Also:

Constant Field Values

COLLINEAR_INTERSECTION

public static final int COLLINEAR_INTERSECTION

Indicates that line segments intersect in a line segment

See Also:

Constant Field Values

result

protected int result

inputLines

protected Point[][] inputLines

intPt

protected Point[] intPt

intLineIndex

protected int[][] intLineIndex

The indexes of the endpoints of the intersection lines, in order along the corresponding line

isProper

protected boolean isProper

pa

protected Point pa

pb

protected Point pb

Constructor Detail

LineIntersector

public LineIntersector()

LineIntersector

public LineIntersector(double scale)

Method Detail

computeEdgeDistance

public static double computeEdgeDistance(Point p,
                         Point p0,
                         Point p1)

Computes the "edge distance" of an intersection point p along a segment. The edge distance is a metric of the point along the edge. The metric used is a robust and easy to compute metric function. It is not equivalent to the usual Euclidean metric. It relies on the fact that either the x or the y ordinates of the points in the edge are unique, depending on whether the edge is longer in the horizontal or vertical direction.

NOTE: This function may produce incorrect distances for inputs where p is not precisely on p1-p2 (E.g. p = (139,9) p1 = (139,10), p2 = (280,1) produces distanct 0.0, which is incorrect.

My hypothesis is that the function is safe to use for points which are the result of rounding points which lie on the line, but not safe to use for truncated points.

nonRobustComputeEdgeDistance

public static double nonRobustComputeEdgeDistance(Point p,
                                  Point p1,
                                  Point p2)

This function is non-robust, since it may compute the square of large numbers. Currently not sure how to improve this.

computeIntersect

protected abstract int computeIntersect(Point p1,
                   Point p2,
                   Point q1,
                   Point q2)

computeIntersection

public abstract void computeIntersection(Point p,
                       Point p1,
                       Point p2)

Compute the intersection of a point p and the line p1-p2. This function computes the boolean value of the hasIntersection test. The actual value of the intersection (if there is one) is equal to the value of p.

computeIntersection

public void computeIntersection(Point p1,
                       Point p2,
                       Point p3,
                       Point p4)

Computes the intersection of the lines p1-p2 and p3-p4. This function computes both the boolean value of the hasIntersection test and the (approximate) value of the intersection point itself (if there is one).

computeIntLineIndex

protected void computeIntLineIndex()

computeIntLineIndex

protected void computeIntLineIndex(int segmentIndex)

getEdgeDistance

public double getEdgeDistance(int segmentIndex,
                     int intIndex)

Computes the "edge distance" of an intersection point along the specified input line segment.

Parameters:

segmentIndex - is 0 or 1

intIndex - is 0 or 1

Returns:

the edge distance of the intersection point

getEndpoint

public Point getEndpoint(int segmentIndex,
                int ptIndex)

Gets an endpoint of an input segment.

Parameters:

segmentIndex - the index of the input segment (0 or 1)

ptIndex - the index of the endpoint (0 or 1)

Returns:

the specified endpoint

getIndexAlongSegment

public int getIndexAlongSegment(int segmentIndex,
                       int intIndex)

Computes the index (order) of the intIndex'th intersection point in the direction of a specified input line segment

Parameters:

segmentIndex - is 0 or 1

intIndex - is 0 or 1

Returns:

the index of the intersection point along the input segment (0 or 1)

getIntersection

public Point getIntersection(int intIndex)

Returns the intIndex'th intersection point

Parameters:

intIndex - is 0 or 1

Returns:

the intIndex'th intersection point

getIntersectionAlongSegment

public Point getIntersectionAlongSegment(int segmentIndex,
                                int intIndex)

Computes the intIndex'th intersection point in the direction of a specified input line segment

Parameters:

segmentIndex - is 0 or 1

intIndex - is 0 or 1

Returns:

the intIndex'th intersection point in the direction of the specified input line segment

getIntersectionNum

public int getIntersectionNum()

Returns the number of intersection points found. This will be either 0, 1 or 2.

Returns:

the number of intersection points found (0, 1, or 2)

getScale

public double getScale()

hasIntersection

public boolean hasIntersection()

Tests whether the input geometries intersect.

Returns:

true if the input geometries intersect

isCollinear

protected boolean isCollinear()

isEndPoint

protected boolean isEndPoint()

isInteriorIntersection

public boolean isInteriorIntersection()

Tests whether either intersection point is an interior point of one of the input segments.

Returns:

true if either intersection point is in the interior of one of the input segments

isInteriorIntersection

public boolean isInteriorIntersection(int inputLineIndex)

Tests whether either intersection point is an interior point of the specified input segment.

Returns:

true if either intersection point is in the interior of the input segment

isIntersection

public boolean isIntersection(Point pt)

Test whether a point is a intersection point of two line segments. Note that if the intersection is a line segment, this method only tests for equality with the endpoints of the intersection segment. It does not return true if the input point is internal to the intersection segment.

Returns:

true if the input point is one of the intersection points.

isProper

public boolean isProper()

Tests whether an intersection is proper.
The intersection between two line segments is considered proper if they intersect in a single point in the interior of both segments (e.g. the intersection is a single point and is not equal to any of the endpoints).

The intersection between a point and a line segment is considered proper if the point lies in the interior of the segment (e.g. is not equal to either of the endpoints).

Returns:

true if the intersection is proper

setScale

public void setScale(double scale)

toString

public String toString()

Overrides:

toString in class Object