com.vividsolutions.jts.algorithm
Class LineIntersector

java.lang.Object
  extended bycom.vividsolutions.jts.algorithm.LineIntersector
Direct Known Subclasses:
NonRobustLineIntersector, RobustLineIntersector

public abstract class LineIntersector
extends java.lang.Object

A LineIntersector is an algorithm that can both test whether two line segments intersect and compute the intersection point if they do. The intersection point may be computed in a precise or non-precise manner. Computing it precisely involves rounding it to an integer. (This assumes that the input coordinates have been made precise by scaling them to an integer grid.)

Version:
1.7

Field Summary
static int COLLINEAR
           
static int DO_INTERSECT
           
static int DONT_INTERSECT
           
protected  Coordinate[][] inputLines
           
protected  int[][] intLineIndex
          The indexes of the endpoints of the intersection lines, in order along the corresponding line
protected  Coordinate[] intPt
           
protected  boolean isProper
           
protected  Coordinate pa
           
protected  Coordinate pb
           
protected  PrecisionModel precisionModel
          If makePrecise is true, computed intersection coordinates will be made precise using Coordinate#makePrecise
protected  int result
           
 
Constructor Summary
LineIntersector()
           
 
Method Summary
static double computeEdgeDistance(Coordinate p, Coordinate p0, Coordinate p1)
          Computes the "edge distance" of an intersection point p along a segment.
protected abstract  int computeIntersect(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
           
abstract  void computeIntersection(Coordinate p, Coordinate p1, Coordinate p2)
          Compute the intersection of a point p and the line p1-p2.
 void computeIntersection(Coordinate p1, Coordinate p2, Coordinate p3, Coordinate 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.
 int getIndexAlongSegment(int segmentIndex, int intIndex)
          Computes the index of the intIndex'th intersection point in the direction of a specified input line segment
 Coordinate getIntersection(int intIndex)
          Returns the intIndex'th intersection point
 Coordinate 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.
 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(Coordinate pt)
          Test whether a point is a intersection point of two line segments.
 boolean isProper()
          Tests whether an intersection is proper.
static double nonRobustComputeEdgeDistance(Coordinate p, Coordinate p1, Coordinate p2)
          This function is non-robust, since it may compute the square of large numbers.
 void setMakePrecise(PrecisionModel precisionModel)
          Deprecated. use setPrecisionModel instead
 void setPrecisionModel(PrecisionModel precisionModel)
          Force computed intersection to be rounded to a given precision model.
 java.lang.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
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

result

protected int result

inputLines

protected Coordinate[][] inputLines

intPt

protected Coordinate[] 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 Coordinate pa

pb

protected Coordinate pb

precisionModel

protected PrecisionModel precisionModel
If makePrecise is true, computed intersection coordinates will be made precise using Coordinate#makePrecise

Constructor Detail

LineIntersector

public LineIntersector()
Method Detail

computeEdgeDistance

public static double computeEdgeDistance(Coordinate p,
                                         Coordinate p0,
                                         Coordinate 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(Coordinate p,
                                                  Coordinate p1,
                                                  Coordinate p2)
This function is non-robust, since it may compute the square of large numbers. Currently not sure how to improve this.


setMakePrecise

public void setMakePrecise(PrecisionModel precisionModel)
Deprecated. use setPrecisionModel instead

Force computed intersection to be rounded to a given precision model

Parameters:
precisionModel -

setPrecisionModel

public void setPrecisionModel(PrecisionModel precisionModel)
Force computed intersection to be rounded to a given precision model. No getter is provided, because the precision model is not required to be specified.

Parameters:
precisionModel -

computeIntersection

public abstract void computeIntersection(Coordinate p,
                                         Coordinate p1,
                                         Coordinate 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.


isCollinear

protected boolean isCollinear()

computeIntersection

public void computeIntersection(Coordinate p1,
                                Coordinate p2,
                                Coordinate p3,
                                Coordinate 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).


computeIntersect

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

toString

public java.lang.String toString()

isEndPoint

protected boolean isEndPoint()

hasIntersection

public boolean hasIntersection()
Tests whether the input geometries intersect.

Returns:
true if the input geometries intersect

getIntersectionNum

public int getIntersectionNum()
Returns the number of intersection points found. This will be either 0, 1 or 2.


getIntersection

public Coordinate getIntersection(int intIndex)
Returns the intIndex'th intersection point

Parameters:
intIndex - is 0 or 1
Returns:
the intIndex'th intersection point

computeIntLineIndex

protected void computeIntLineIndex()

isIntersection

public boolean isIntersection(Coordinate 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.

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

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

getIntersectionAlongSegment

public Coordinate 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

getIndexAlongSegment

public int getIndexAlongSegment(int segmentIndex,
                                int intIndex)
Computes the index 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 segment (0 or 1)

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