Class CGAlgorithmsDD


  • public class CGAlgorithmsDD
    extends java.lang.Object
    Implements basic computational geometry algorithms using DD arithmetic.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private static double DP_SAFE_EPSILON
      A value which is safely greater than the relative round-off error in double-precision numbers
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private CGAlgorithmsDD()  
    • Field Detail

      • DP_SAFE_EPSILON

        private static final double DP_SAFE_EPSILON
        A value which is safely greater than the relative round-off error in double-precision numbers
        See Also:
        Constant Field Values
    • Constructor Detail

      • CGAlgorithmsDD

        private CGAlgorithmsDD()
    • Method Detail

      • orientationIndex

        public static int orientationIndex​(Coordinate p1,
                                           Coordinate p2,
                                           Coordinate q)
        Returns the index of the direction of the point q relative to a vector specified by p1-p2.
        Parameters:
        p1 - the origin point of the vector
        p2 - the final point of the vector
        q - the point to compute the direction to
        Returns:
        1 if q is counter-clockwise (left) from p1-p2
      • signOfDet2x2

        public static int signOfDet2x2​(DD x1,
                                       DD y1,
                                       DD x2,
                                       DD y2)
        Computes the sign of the determinant of the 2x2 matrix with the given entries.
        Returns:
        -1 if the determinant is negative,
      • signOfDet2x2

        public static int signOfDet2x2​(double dx1,
                                       double dy1,
                                       double dx2,
                                       double dy2)
        Computes the sign of the determinant of the 2x2 matrix with the given entries.
        Returns:
        -1 if the determinant is negative,
      • orientationIndexFilter

        private static int orientationIndexFilter​(Coordinate pa,
                                                  Coordinate pb,
                                                  Coordinate pc)
        A filter for computing the orientation index of three coordinates.

        If the orientation can be computed safely using standard DP arithmetic, this routine returns the orientation index. Otherwise, a value i > 1 is returned. In this case the orientation index must be computed using some other more robust method. The filter is fast to compute, so can be used to avoid the use of slower robust methods except when they are really needed, thus providing better average performance.

        Uses an approach due to Jonathan Shewchuk, which is in the public domain.

        Parameters:
        pa - a coordinate
        pb - a coordinate
        pc - a coordinate
        Returns:
        the orientation index if it can be computed safely
      • signum

        private static int signum​(double x)
      • intersection

        public static Coordinate intersection​(Coordinate p1,
                                              Coordinate p2,
                                              Coordinate q1,
                                              Coordinate q2)
        Computes an intersection point between two lines using DD arithmetic. Currently does not handle case of parallel lines.
        Parameters:
        p1 -
        p2 -
        q1 -
        q2 -
        Returns: