X-Git-Url: http://source.jalview.org/gitweb/?p=jalview.git;a=blobdiff_plain;f=srcjar%2Ffr%2Forsay%2Flri%2Fvarna%2Fmodels%2Fgeom%2FLinesIntersect.java;fp=srcjar%2Ffr%2Forsay%2Flri%2Fvarna%2Fmodels%2Fgeom%2FLinesIntersect.java;h=fa238feef5d5f46f3b6914f1c87421805cf092af;hp=0000000000000000000000000000000000000000;hb=2d6292c0377bc6b773c6844a45d3f2c5fac352c7;hpb=954af328a2a6a0055572cd1a09ee035301222574

diff --git a/srcjar/fr/orsay/lri/varna/models/geom/LinesIntersect.java b/srcjar/fr/orsay/lri/varna/models/geom/LinesIntersect.java
new file mode 100644
index 0000000..fa238fe
--- /dev/null
+++ b/srcjar/fr/orsay/lri/varna/models/geom/LinesIntersect.java
@@ -0,0 +1,88 @@
+/**
+ * File written by Raphael Champeimont
+ * UMR 7238 Genomique des Microorganismes
+ */
+package fr.orsay.lri.varna.models.geom;
+
+import java.awt.geom.Line2D;
+import java.awt.geom.Point2D;
+
+/**
+ * Like Line2D.Double.linesIntersect() of the standard library, but without the bug!
+ * See this: http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6457965
+ * This result is incorrect with, for example:
+ * System.out.println(Line2D.Double.linesIntersect(179.2690296114372, 1527.2309703885628, 150.9847583639753, 1498.946699141101, 94.4162158690515, 1442.378156646177, 66.1319446215896, 1414.0938853987152));
+ * (real example observed on an RNA with no intersection at all)
+ * This lines obviously don't intersect (both X and Y ranges are clearly disjoint!)
+ * but linesIntersect() returns true.
+ * Here we provide a bug-free function.
+ */
+public class LinesIntersect {
+	/**
+	 * Returns whether segment from (x1,y1) to (x2,y2)
+	 * intersect with segment from (x3,y3) to (x4,y4).
+	 */
+	public static boolean linesIntersect(
+			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 false;
+	      }
+	      double ua = ((x4 - x3) * (y1 - y3) - (y4 - y3) * (x1 - x3)) / denom;
+	      double ub = ((x2 - x1) * (y1 - y3) - (y2 - y1) * (x1 - x3)) / denom;
+	      return (ua >= 0.0 && ua <= 1.0 && ub >= 0.0 && ub <= 1.0);
+	}
+	
+	/**
+	 * Returns whether segment from p1 to p2 intersects segment from p3 to p4.
+	 */
+	public static boolean linesIntersect(
+			Point2D.Double p1,
+			Point2D.Double p2,
+			Point2D.Double p3,
+			Point2D.Double p4) {
+		return linesIntersect(p1.x, p1.y, p2.x, p2.y, p3.x, p3.y, p4.x, p4.y);
+	}
+	
+	/**
+	 * Returns whether the two segment intersect.
+	 */
+	public static boolean linesIntersect(Line2D.Double line1, Line2D.Double line2) {
+		return linesIntersect(
+				line1.x1, line1.y1, line1.x2, line1.y2,
+				line2.x1, line2.y1, line2.x2, line2.y2);
+	}
+	
+	
+	private static void test(
+			double x1,
+            double y1,
+            double x2,
+            double y2,
+            double x3,
+            double y3,
+            double x4,
+            double y4,
+            boolean expectedResult) {
+		boolean a = linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4);
+		boolean b = Line2D.Double.linesIntersect(x1, y1, x2, y2, x3, y3, x4, y4);
+		System.out.println("ours says " + a + " which is " + (a == expectedResult ? "correct" : "INCORRECT") +
+				" / Line2D.Double says " + b + " which is " + (b == expectedResult ? "correct" : "INCORRECT"));
+	}
+	
+	public static void main(String[] args) {
+		test(179.2690296114372, 1527.2309703885628, 150.9847583639753, 1498.946699141101, 94.4162158690515, 1442.378156646177, 66.1319446215896, 1414.0938853987152, false);
+		test(0, 0, 0, 0, 1, 1, 1, 1, false);
+		test(0, 0, 0.5, 0.5, 1, 1, 2, 2, false);
+		test(0, 0, 2, 2, 0, 2, 2, 0, true);
+		test(0, 0, 2, 2, 4, 0, 3, 2, false);
+	}
+}