Package org.locationtech.jts.algorithm
Class RobustLineIntersector
- java.lang.Object
-
- org.locationtech.jts.algorithm.LineIntersector
-
- org.locationtech.jts.algorithm.RobustLineIntersector
-
public class RobustLineIntersector extends LineIntersector
A robust version ofLineIntersector
.- Version:
- 1.7
-
-
Field Summary
-
Fields inherited from class org.locationtech.jts.algorithm.LineIntersector
COLLINEAR, COLLINEAR_INTERSECTION, DO_INTERSECT, DONT_INTERSECT, inputLines, intLineIndex, intPt, isProper, NO_INTERSECTION, pa, pb, POINT_INTERSECTION, precisionModel, result
-
-
Constructor Summary
Constructors Constructor Description RobustLineIntersector()
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
checkDD(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2, Coordinate intPt)
private int
computeCollinearIntersection(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
protected int
computeIntersect(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
void
computeIntersection(Coordinate p, Coordinate p1, Coordinate p2)
Compute the intersection of a point p and the line p1-p2.private Coordinate
intersection(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
This method computes the actual value of the intersection point.private Coordinate
intersectionWithNormalization(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
private boolean
isInSegmentEnvelopes(Coordinate intPt)
Tests whether a point lies in the envelopes of both input segments.private static Coordinate
nearestEndpoint(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
Finds the endpoint of the segments P and Q which is closest to the other segment.private void
normalizeToEnvCentre(Coordinate n00, Coordinate n01, Coordinate n10, Coordinate n11, Coordinate normPt)
Normalize the supplied coordinates to so that the midpoint of their intersection envelope lies at the origin.private void
normalizeToMinimum(Coordinate n1, Coordinate n2, Coordinate n3, Coordinate n4, Coordinate normPt)
Normalize the supplied coordinates so that their minimum ordinate values lie at the origin.private Coordinate
safeHCoordinateIntersection(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
Computes a segment intersection using homogeneous coordinates.private double
smallestInAbsValue(double x1, double x2, double x3, double x4)
-
Methods inherited from class org.locationtech.jts.algorithm.LineIntersector
computeEdgeDistance, computeIntersection, computeIntLineIndex, computeIntLineIndex, getEdgeDistance, getEndpoint, getIndexAlongSegment, getIntersection, getIntersectionAlongSegment, getIntersectionNum, hasIntersection, isCollinear, isEndPoint, isInteriorIntersection, isInteriorIntersection, isIntersection, isProper, nonRobustComputeEdgeDistance, setMakePrecise, setPrecisionModel, toString
-
-
-
-
Method Detail
-
computeIntersection
public void computeIntersection(Coordinate p, Coordinate p1, Coordinate p2)
Description copied from class:LineIntersector
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
.- Specified by:
computeIntersection
in classLineIntersector
-
computeIntersect
protected int computeIntersect(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
- Specified by:
computeIntersect
in classLineIntersector
-
computeCollinearIntersection
private int computeCollinearIntersection(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
-
intersection
private Coordinate intersection(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
This method computes the actual value of the intersection point. To obtain the maximum precision from the intersection calculation, the coordinates are normalized by subtracting the minimum ordinate values (in absolute value). This has the effect of removing common significant digits from the calculation to maintain more bits of precision.
-
checkDD
private void checkDD(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2, Coordinate intPt)
-
intersectionWithNormalization
private Coordinate intersectionWithNormalization(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
-
safeHCoordinateIntersection
private Coordinate safeHCoordinateIntersection(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
Computes a segment intersection using homogeneous coordinates. Round-off error can cause the raw computation to fail, (usually due to the segments being approximately parallel). If this happens, a reasonable approximation is computed instead.- Parameters:
p1
- a segment endpointp2
- a segment endpointq1
- a segment endpointq2
- a segment endpoint- Returns:
- the computed intersection point
-
normalizeToMinimum
private void normalizeToMinimum(Coordinate n1, Coordinate n2, Coordinate n3, Coordinate n4, Coordinate normPt)
Normalize the supplied coordinates so that their minimum ordinate values lie at the origin. NOTE: this normalization technique appears to cause large errors in the position of the intersection point for some cases.- Parameters:
n1
-n2
-n3
-n4
-normPt
-
-
normalizeToEnvCentre
private void normalizeToEnvCentre(Coordinate n00, Coordinate n01, Coordinate n10, Coordinate n11, Coordinate normPt)
Normalize the supplied coordinates to so that the midpoint of their intersection envelope lies at the origin.- Parameters:
n00
-n01
-n10
-n11
-normPt
-
-
smallestInAbsValue
private double smallestInAbsValue(double x1, double x2, double x3, double x4)
-
isInSegmentEnvelopes
private boolean isInSegmentEnvelopes(Coordinate intPt)
Tests whether a point lies in the envelopes of both input segments. A correctly computed intersection point should returntrue
for this test. Since this test is for debugging purposes only, no attempt is made to optimize the envelope test.- Returns:
true
if the input point lies within both input segment envelopes
-
nearestEndpoint
private static Coordinate nearestEndpoint(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
Finds the endpoint of the segments P and Q which is closest to the other segment. This is a reasonable surrogate for the true intersection points in ill-conditioned cases (e.g. where two segments are nearly coincident, or where the endpoint of one segment lies almost on the other segment).This replaces the older CentralEndpoint heuristic, which chose the wrong endpoint in some cases where the segments had very distinct slopes and one endpoint lay almost on the other segment.
- Parameters:
p1
- an endpoint of segment Pp2
- an endpoint of segment Pq1
- an endpoint of segment Qq2
- an endpoint of segment Q- Returns:
- the nearest endpoint to the other segment
-
-