Class CGAlgorithmsDD


  • public class CGAlgorithmsDD
    extends java.lang.Object
    Implements basic computational geometry algorithms using DD arithmetic.
    Author:
    Martin Davis
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static Coordinate intersection​(Coordinate p1, Coordinate p2, Coordinate q1, Coordinate q2)
      Computes an intersection point between two lines using DD arithmetic.
      static int orientationIndex​(double p1x, double p1y, double p2x, double p2y, double qx, double qy)
      Returns the index of the direction of the point q relative to a vector specified by p1-p2.
      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.
      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.
      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.
      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • 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 -1 if q is clockwise (right) from p1-p2 0 if q is collinear with p1-p2
      • orientationIndex

        public static int orientationIndex​(double p1x,
                                           double p1y,
                                           double p2x,
                                           double p2y,
                                           double qx,
                                           double qy)
        Returns the index of the direction of the point q relative to a vector specified by p1-p2.
        Parameters:
        p1x - the x ordinate of the vector origin point
        p1y - the y ordinate of the vector origin point
        p2x - the x ordinate of the vector final point
        p2y - the y ordinate of the vector final point
        qx - the x ordinate of the query point
        qy - the y ordinate of the query point
        Returns:
        1 if q is counter-clockwise (left) from p1-p2 -1 if q is clockwise (right) from p1-p2 0 if q is collinear with 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, 1 if the determinant is positive, 0 if the determinant is 0.
      • 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, 1 if the determinant is positive, 0 if the determinant is 0.
      • intersection

        public static Coordinate intersection​(Coordinate p1,
                                              Coordinate p2,
                                              Coordinate q1,
                                              Coordinate q2)
        Computes an intersection point between two lines using DD arithmetic. If the lines are parallel (either identical or separate) a null value is returned.
        Parameters:
        p1 - an endpoint of line segment 1
        p2 - an endpoint of line segment 1
        q1 - an endpoint of line segment 2
        q2 - an endpoint of line segment 2
        Returns:
        an intersection point if one exists, or null if the lines are parallel