2004-11-30 Thomas Fitzsimmons <fitzsim@redhat.com>

[pf3gnuchains/gcc-fork.git] / libjava / java / awt / geom / Line2D.java

diff --git a/libjava/java/awt/geom/Line2D.java b/libjava/java/awt/geom/Line2D.java
index d2dd65c..05eedcd 100644 (file)
--- a/libjava/java/awt/geom/Line2D.java
+++ b/libjava/java/awt/geom/Line2D.java
@@ -48,6 +48,7 @@ import java.util.NoSuchElementException;
  *
  * @author Tom Tromey <tromey@cygnus.com>
  * @author Eric Blake <ebb9@email.byu.edu>
+ * @author David Gilbert
  * @since 1.2
  * @status updated to 1.4
  */
@@ -235,11 +236,57 @@ public abstract class Line2D implements Shape, Cloneable
   }
 
   /**
-   * Test if the line segment (x1,y1)-&gt;(x2,y2) intersects the line segment
+   * Computes twice the (signed) area of the triangle defined by the three
+   * points.  This method is used for intersection testing.
+   * 
+   * @param x1  the x-coordinate of the first point.
+   * @param y1  the y-coordinate of the first point.
+   * @param x2  the x-coordinate of the second point.
+   * @param y2  the y-coordinate of the second point.
+   * @param x3  the x-coordinate of the third point.
+   * @param y3  the y-coordinate of the third point.
+   * 
+   * @return Twice the area.
+   */
+  private static double area2(double x1, double y1,
+                             double x2, double y2,
+                             double x3, double y3) 
+  {
+    return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);    
+  }
+
+  /**
+   * Returns <code>true</code> if (x3, y3) lies between (x1, y1) and (x2, y2),
+   * and false otherwise,  This test assumes that the three points are 
+   * collinear, and is used for intersection testing.
+   * 
+   * @param x1  the x-coordinate of the first point.
+   * @param y1  the y-coordinate of the first point.
+   * @param x2  the x-coordinate of the second point.
+   * @param y2  the y-coordinate of the second point.
+   * @param x3  the x-coordinate of the third point.
+   * @param y3  the y-coordinate of the third point.
+   * 
+   * @return A boolean.
+   */
+  private static boolean between(double x1, double y1, 
+                                double x2, double y2, 
+                                double x3, double y3) 
+  {
+    if (x1 != x2) {
+      return (x1 <= x3 && x3 <= x2) || (x1 >= x3 && x3 >= x2);   
+    }
+    else {
+      return (y1 <= y3 && y3 <= y2) || (y1 >= y3 && y3 >= y2);   
+    }
+  }
+
+  /**
+   * Test if the line segment (x1,y1)-&gt;(x2,y2) intersects the line segment 
    * (x3,y3)-&gt;(x4,y4).
    *
    * @param x1 the first x coordinate of the first segment
-   * @param y1 the first y coordinate of the first segment
+   * @param y1 the first y coordinate of the first segment 
    * @param x2 the second x coordinate of the first segment
    * @param y2 the second y coordinate of the first segment
    * @param x3 the first x coordinate of the second segment
@@ -249,16 +296,64 @@ public abstract class Line2D implements Shape, Cloneable
    * @return true if the segments intersect
    */
   public static boolean linesIntersect(double x1, double y1,
-                                       double x2, double y2,
-                                       double x3, double y3,
-                                       double x4, double y4)
+                                      double x2, double y2,
+                                      double x3, double y3,
+                                      double x4, double y4)
   {
-    double beta = (((y1 - y3) * (x4 - x3) + (x1 - x3) * (y4 - y3))
-                   / ((y2 - y1) * (x4 - x3) + (x2 - x1) * (y4 - y3)));
-    if (beta < 0.0 || beta > 1.0)
-      return false;
-    double alpha = (x1 + beta * (x2 - x1) - x3) / (x4 - x3);
-    return alpha >= 0.0 && alpha <= 1.0;
+    double a1, a2, a3, a4;
+  
+    // deal with special cases
+    if ((a1 = area2(x1, y1, x2, y2, x3, y3)) == 0.0) 
+    {
+      // check if p3 is between p1 and p2 OR
+      // p4 is collinear also AND either between p1 and p2 OR at opposite ends
+      if (between(x1, y1, x2, y2, x3, y3)) 
+      {
+        return true;
+      }
+      else 
+      {
+        if (area2(x1, y1, x2, y2, x4, y4) == 0.0) 
+        {
+          return between(x3, y3, x4, y4, x1, y1) 
+                 || between (x3, y3, x4, y4, x2, y2);
+        }
+        else {
+          return false;
+        }
+      }
+    }
+    else if ((a2 = area2(x1, y1, x2, y2, x4, y4)) == 0.0) 
+    {
+      // check if p4 is between p1 and p2 (we already know p3 is not
+      // collinear)
+      return between(x1, y1, x2, y2, x4, y4);
+    }
+  
+    if ((a3 = area2(x3, y3, x4, y4, x1, y1)) == 0.0) {
+      // check if p1 is between p3 and p4 OR
+      // p2 is collinear also AND either between p1 and p2 OR at opposite ends
+      if (between(x3, y3, x4, y4, x1, y1)) {
+        return true;
+      }
+      else {
+        if (area2(x3, y3, x4, y4, x2, y2) == 0.0) {
+          return between(x1, y1, x2, y2, x3, y3) 
+                 || between (x1, y1, x2, y2, x4, y4);
+        }
+        else {
+          return false;
+        }
+      }
+    }
+    else if ((a4 = area2(x3, y3, x4, y4, x2, y2)) == 0.0) {
+      // check if p2 is between p3 and p4 (we already know p1 is not
+      // collinear)
+      return between(x3, y3, x4, y4, x2, y2);
+    }
+    else {  // test for regular intersection
+      return ((a1 > 0.0) ^ (a2 > 0.0)) && ((a3 > 0.0) ^ (a4 > 0.0));
+    } 
   }
 
   /**
@@ -668,7 +763,7 @@ public abstract class Line2D implements Shape, Cloneable
     return new PathIterator()
     {
       /** Current coordinate. */
-      private int current;
+      private int current = 0;
 
       public int getWindingRule()
       {
@@ -677,7 +772,7 @@ public abstract class Line2D implements Shape, Cloneable
 
       public boolean isDone()
       {
-        return current < 2;
+        return current >= 2;
       }
 
       public void next()