Package org.locationtech.jts.algorithm
Class RobustLineIntersector
java.lang.Object
org.locationtech.jts.algorithm.LineIntersector
org.locationtech.jts.algorithm.RobustLineIntersector
A robust version of
LineIntersector
.- 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 -
Method Summary
Modifier and TypeMethodDescriptionprivate 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
-
Constructor Details
-
RobustLineIntersector
public RobustLineIntersector()
-
-
Method Details
-
computeIntersection
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
- Specified by:
computeIntersect
in classLineIntersector
-
computeCollinearIntersection
private int computeCollinearIntersection(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2) -
intersection
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
-
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
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
-