Class LineIntersector
- Direct Known Subclasses:
RobustLineIntersector
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 intersectPOINT_INTERSECTION
- the segments intersect in a single pointCOLLINEAR_INTERSECTION
- the segments are collinear and they intersect in a line segment
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 PrecisionModel
.
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
FieldsModifier and TypeFieldDescriptionstatic final int
static final int
Indicates that line segments intersect in a line segmentstatic final int
static final int
These are deprecated, due to ambiguous namingprotected Coordinate[][]
protected int[][]
The indexes of the endpoints of the intersection lines, in order along the corresponding lineprotected Coordinate[]
protected boolean
static final int
Indicates that line segments do not intersectprotected Coordinate
protected Coordinate
static final int
Indicates that line segments intersect in a single pointprotected PrecisionModel
If makePrecise is true, computed intersection coordinates will be made precise using Coordinate#makePreciseprotected int
-
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionstatic 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
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.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 segmentgetIntersection
(int intIndex) Returns the intIndex'th intersection pointgetIntersectionAlongSegment
(int segmentIndex, int intIndex) Computes the intIndex'th intersection point in the direction of a specified input line segmentint
Returns the number of intersection points found.private String
boolean
Tests whether the input geometries intersect.protected boolean
protected boolean
boolean
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
Test whether a point is a intersection point of two line segments.boolean
isProper()
Tests whether an intersection is proper.static double
This function is non-robust, since it may compute the square of large numbers.void
setMakePrecise
(PrecisionModel precisionModel) Deprecated.void
setPrecisionModel
(PrecisionModel precisionModel) Force computed intersection to be rounded to a given precision model.toString()
-
Field Details
-
DONT_INTERSECT
public static final int DONT_INTERSECTThese are deprecated, due to ambiguous naming- See Also:
-
DO_INTERSECT
public static final int DO_INTERSECT- See Also:
-
COLLINEAR
public static final int COLLINEAR- See Also:
-
NO_INTERSECTION
public static final int NO_INTERSECTIONIndicates that line segments do not intersect- See Also:
-
POINT_INTERSECTION
public static final int POINT_INTERSECTIONIndicates that line segments intersect in a single point- See Also:
-
COLLINEAR_INTERSECTION
public static final int COLLINEAR_INTERSECTIONIndicates that line segments intersect in a line segment- See Also:
-
result
protected int result -
inputLines
-
intPt
-
intLineIndex
protected int[][] intLineIndexThe indexes of the endpoints of the intersection lines, in order along the corresponding line -
isProper
protected boolean isProper -
pa
-
pb
-
precisionModel
If makePrecise is true, computed intersection coordinates will be made precise using Coordinate#makePrecise
-
-
Constructor Details
-
LineIntersector
public LineIntersector()
-
-
Method Details
-
computeEdgeDistance
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 distance 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
This function is non-robust, since it may compute the square of large numbers. Currently not sure how to improve this. -
setMakePrecise
Deprecated.usesetPrecisionModel
insteadForce computed intersection to be rounded to a given precision model- Parameters:
precisionModel
-
-
setPrecisionModel
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
-
-
getEndpoint
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
-
computeIntersection
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 ofp
. -
isCollinear
protected boolean isCollinear() -
computeIntersection
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
-
toString
-
getTopologySummary
-
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.- Returns:
- the number of intersection points found (0, 1, or 2)
-
getIntersection
Returns the intIndex'th intersection point- Parameters:
intIndex
- is 0 or 1- Returns:
- the intIndex'th intersection point
-
computeIntLineIndex
protected void computeIntLineIndex() -
isIntersection
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
Computes the intIndex'th intersection point in the direction of a specified input line segment- Parameters:
segmentIndex
- is 0 or 1intIndex
- 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 (order) of the intIndex'th intersection point in the direction of a specified input line segment- Parameters:
segmentIndex
- is 0 or 1intIndex
- is 0 or 1- Returns:
- the index of the intersection point along the input 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 1intIndex
- is 0 or 1- Returns:
- the edge distance of the intersection point
-
setPrecisionModel
instead