Class RobustLineIntersector

    • Constructor Detail

      • RobustLineIntersector

        public RobustLineIntersector()
    • 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 of p.
        Specified by:
        computeIntersection in class LineIntersector
      • 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.
      • 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 endpoint
        p2 - a segment endpoint
        q1 - a segment endpoint
        q2 - 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 return true 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 P
        p2 - an endpoint of segment P
        q1 - an endpoint of segment Q
        q2 - an endpoint of segment Q
        Returns:
        the nearest endpoint to the other segment