src2/fr/orsay/lri/varna/models/geom/LinesIntersect.java

   1 /**
   2  * File written by Raphael Champeimont
   3  * UMR 7238 Genomique des Microorganismes
   4  */
   5 package fr.orsay.lri.varna.models.geom;
   6
   7 import java.awt.geom.Line2D;
   8 import java.awt.geom.Point2D;
   9
  10 /**
  11  * Like Line2D.Double.linesIntersect() of the standard library, but without the bug!
  12  * See this: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6457965
  13  * This result is incorrect with, for example:
  14  * System.out.println(Line2D.Double.linesIntersect(179.2690296114372, 1527.2309703885628, 150.9847583639753, 1498.946699141101, 94.4162158690515, 1442.378156646177, 66.1319446215896, 1414.0938853987152));
  15  * (real example observed on an RNA with no intersection at all)
  16  * This lines obviously don't intersect (both X and Y ranges are clearly disjoint!)
  17  * but linesIntersect() returns true.
  18  * Here we provide a bug-free function.
  19  */
  20 public class LinesIntersect {
  21         /**
  22          * Returns whether segment from (x1,y1) to (x2,y2)
  23          * intersect with segment from (x3,y3) to (x4,y4).
  24          */
  25         public static boolean linesIntersect(
  26                         double x1,
  27             double y1,
  28             double x2,
  29             double y2,
  30             double x3,
  31             double y3,
  32             double x4,
  33             double y4) {
  34
  35               double denom = (y4 - y3) * (x2 - x1) - (x4 - x3) * (y2 - y1);
  36               if (denom == 0.0) { // Lines are parallel.
  37                  return false;
  38               }
  39               double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denom;
  40               double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denom;
  41               return (ua >= 0.0 && ua <= 1.0 && ub >= 0.0 && ub <= 1.0);
  42         }
  43
  44         /**
  45          * Returns whether segment from p1 to p2 intersects segment from p3 to p4.
  46          */
  47         public static boolean linesIntersect(
  48                         Point2D.Double p1,
  49                         Point2D.Double p2,
  50                         Point2D.Double p3,
  51                         Point2D.Double p4) {
  52                 return linesIntersect(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, p4.x, p4.y);
  53         }
  54
  55         /**
  56          * Returns whether the two segment intersect.
  57          */
  58         public static boolean linesIntersect(Line2D.Double line1, Line2D.Double line2) {
  59                 return linesIntersect(
  60                                 line1.x1, line1.y1, line1.x2, line1.y2,
  61                                 line2.x1, line2.y1, line2.x2, line2.y2);
  62         }
  63
  64
  65         private static void test(
  66                         double x1,
  67             double y1,
  68             double x2,
  69             double y2,
  70             double x3,
  71             double y3,
  72             double x4,
  73             double y4,
  74             boolean expectedResult) {
  75                 boolean a = linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4);
  76                 boolean b = Line2D.Double.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4);
  77                 System.out.println("ours says " + a + " which is " + (a == expectedResult ? "correct" : "INCORRECT") +
  78                                 " / Line2D.Double says " + b + " which is " + (b == expectedResult ? "correct" : "INCORRECT"));
  79         }
  80
  81         public static void main(String[] args) {
  82                 test(179.2690296114372, 1527.2309703885628, 150.9847583639753, 1498.946699141101, 94.4162158690515, 1442.378156646177, 66.1319446215896, 1414.0938853987152, false);
  83                 test(0, 0, 0, 0, 1, 1, 1, 1, false);
  84                 test(0, 0, 0.5, 0.5, 1, 1, 2, 2, false);
  85                 test(0, 0, 2, 2, 0, 2, 2, 0, true);
  86                 test(0, 0, 2, 2, 4, 0, 3, 2, false);
  87         }
  88 }