public static boolean linesIntersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4){
      // Return false if either of the lines have zero length
      if (x1 == x2 && y1 == y2 ||
            x3 == x4 && y3 == y4){
         return false;
      }
      // Fastest method, based on Franklin Antonio's "Faster Line Segment Intersection" topic "in Graphics Gems III" book (http://www.graphicsgems.org/)
      double ax = x2-x1;
      double ay = y2-y1;
      double bx = x3-x4;
      double by = y3-y4;
      double cx = x1-x3;
      double cy = y1-y3;

      double alphaNumerator = by*cx - bx*cy;
      double commonDenominator = ay*bx - ax*by;
      if (commonDenominator > 0){
         if (alphaNumerator < 0 || alphaNumerator > commonDenominator){
            return false;
         }
      }else if (commonDenominator < 0){
         if (alphaNumerator > 0 || alphaNumerator < commonDenominator){
            return false;
         }
      }
      double betaNumerator = ax*cy - ay*cx;
      if (commonDenominator > 0){
         if (betaNumerator < 0 || betaNumerator > commonDenominator){
            return false;
         }
      }else if (commonDenominator < 0){
         if (betaNumerator > 0 || betaNumerator < commonDenominator){
            return false;
         }
      }
      if (commonDenominator == 0){
         // This code wasn't in Franklin Antonio's method. It was added by Keith Woodward.
         // The lines are parallel.
         // Check if they're collinear.
         double y3LessY1 = y3-y1;
         double collinearityTestForP3 = x1*(y2-y3) + x2*(y3LessY1) + x3*(y1-y2);   // see http://mathworld.wolfram.com/Collinear.html
         // If p3 is collinear with p1 and p2 then p4 will also be collinear, since p1-p2 is parallel with p3-p4
         if (collinearityTestForP3 == 0){
            // The lines are collinear. Now check if they overlap.
            if (x1 >= x3 && x1 <= x4 || x1 <= x3 && x1 >= x4 ||
                  x2 >= x3 && x2 <= x4 || x2 <= x3 && x2 >= x4 ||
                  x3 >= x1 && x3 <= x2 || x3 <= x1 && x3 >= x2){
               if (y1 >= y3 && y1 <= y4 || y1 <= y3 && y1 >= y4 ||
                     y2 >= y3 && y2 <= y4 || y2 <= y3 && y2 >= y4 ||
                     y3 >= y1 && y3 <= y2 || y3 <= y1 && y3 >= y2){
                  return true;
               }
            }
         }
         return false;
      }
      return true;
   }

   public static KPoint getLineLineIntersection(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {
      double det1And2 = det(x1, y1, x2, y2);
      double det3And4 = det(x3, y3, x4, y4);
      double x1LessX2 = x1 - x2;
      double y1LessY2 = y1 - y2;
      double x3LessX4 = x3 - x4;
      double y3LessY4 = y3 - y4;
      double det1Less2And3Less4 = det(x1LessX2, y1LessY2, x3LessX4, y3LessY4);
      if (det1Less2And3Less4 == 0){
         // the denominator is zero so the lines are parallel and there's either no solution (or multiple solutions if the lines overlap) so return null.
         return null;
      }
      double x = (det(det1And2, x1LessX2,
            det3And4, x3LessX4) /
            det1Less2And3Less4);
      double y = (det(det1And2, y1LessY2,
            det3And4, y3LessY4) /
            det1Less2And3Less4);
      return new KPoint(x, y);
   }
   protected static double det(double a, double b, double c, double d) {
      return a * d - b * c;
   }

   public static boolean doesIntersect(LineSegment line, double x1, double y1, double x2, double y2) {
      return doesIntersect(line.getStart().x, line.getStart().y, line.getEnd().x, line.getEnd().y, x1, y1, x2, y2);
   }

   public static boolean doesIntersect(double l1x1, double l1y1, double l1x2, double l1y2, double l2x1, double l2y1, double l2x2,
         double l2y2) {
      double denom = ((l2y2 - l2y1) * (l1x2 - l1x1)) - ((l2x2 - l2x1) * (l1y2 - l1y1));

      if (denom == 0.0f) {
         return false;
      }

      double ua = (((l2x2 - l2x1) * (l1y1 - l2y1)) - ((l2y2 - l2y1) * (l1x1 - l2x1))) / denom;
      double ub = (((l1x2 - l1x1) * (l1y1 - l2y1)) - ((l1y2 - l1y1) * (l1x1 - l2x1))) / denom;

      return ((ua >= 0.0d) && (ua <= 1.0d) && (ub >= 0.0d) && (ub <= 1.0d));
   }

   public static boolean doesIntersect(LineSegment ln1, LineSegment ln2) {
      float denom = ((ln2.getEnd().y - ln2.getStart().y) * (ln1.getEnd().x - ln1.getStart().x))
            - ((ln2.getEnd().x - ln2.getStart().x) * (ln1.getEnd().y - ln1.getStart().y));

      if (denom == 0.0f) {
         return false;
      }

      double ua = ((ln2.getEnd().x - ln2.getStart().x) * (ln1.getStart().y - ln2.getStart().y))
            - ((ln2.getEnd().y - ln2.getStart().y) * (ln1.getStart().x - ln2.getStart().x)) / denom;
      double ub = ((ln1.getEnd().x - ln1.getStart().x) * (ln1.getStart().y - ln2.getStart().y))
            - ((ln1.getEnd().y - ln1.getStart().y) * (ln1.getStart().x - ln2.getStart().x)) / denom;

      return ((ua >= 0.0d) && (ua <= 1.0d) && (ub >= 0.0d) && (ub <= 1.0d));
   }

   public static Point getIntersection(LineSegment line, double x1, double y1, double x2, double y2) {
      double denom = ((line.getEnd().y - line.getStart().y) * (x2 - x1))
            - ((line.getEnd().x - line.getStart().x) * (y2 - y1));
      double nume_a = ((line.getEnd().x - line.getStart().x) * (y1 - line.getStart().y))
            - ((line.getEnd().y - line.getStart().y) * (x1 - line.getStart().x));
      double nume_b = ((x2 - x1) * (y1 - line.getStart().y)) - ((y2 - y1) * (x1 - line.getStart().x));

      if (denom == 0.0f) {
         return null;
      }

      double ua = nume_a / denom;
      double ub = nume_b / denom;

      if ((ua >= 0.0f) && (ua <= 1.0f) && (ub >= 0.0f) && (ub <= 1.0f)) {

         // Get the intersection point.
         int intersectX = (int) (line.getStart().x + ua * (line.getEnd().x - line.getStart().x));
         int intersectY = (int) (line.getStart().y + ua * (line.getEnd().y - line.getStart().y));

         return new Point(intersectX, intersectY);
      }

      return null;
   }

   public static Point lineIntersect(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4) {
      double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
      if (denom == 0.0) { // Lines are parallel.
         return null;
      }
      double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denom;
      double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denom;
      if (ua >= 0.0f && ua <= 1.0f && ub >= 0.0f && ub <= 1.0f) {
         // Get the intersection point.
         return new Point((int) (x1 + ua * (x2 - x1)), (int) (y1 + ua * (y2 - y1)));
      }

      return null;
   }