Hello All,
I've recently started exploring Classpath to see where I can help out.
In general, I am interested in Java2D, since the project I work on
(JFreeChart) depends on this quite a lot. My FSF copyright assignment
is already completed.
To begin with, I've written some test cases for the Line2D class, and
sent these (just now) to the Mauve patches mailing list. Another
developer (Sven de Marothy) previously posted a test case that
highlights a problem with the Line2D.linesIntersect() method. I didn't
find any additional problems.
I modified the Line2D class to correct the linesIntersect() method - a
patch is attached. The fix is based on an algorithm described in
"Computational Geometry in C" (2nd edition) by Joseph O'Rourke. I have
no background in computational geometry, by the way, just a mild
interest - so my code may be rubbish (but it passes the test cases,
which the existing code doesn't).
Re-reading Sven's earlier post, it sounds as though he has a fix for the
problem also, which I'll try to find out more about (I couldn't find it
posted anywhere). Of course, if I had read his post properly the first
time, I would have found out about his fix before writing one myself...
Regards,
Dave Gilbert
Index: java/awt/geom/Line2D.java
===================================================================
RCS file: /cvsroot/classpath/classpath/java/awt/geom/Line2D.java,v
retrieving revision 1.6
diff -u -r1.6 Line2D.java
--- java/awt/geom/Line2D.java 18 Jul 2003 19:35:02 -0000 1.6
+++ java/awt/geom/Line2D.java 2 Aug 2004 12:33:11 -0000
@@ -235,11 +235,57 @@
}
/**
- * Test if the line segment (x1,y1)->(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)->(x2,y2) intersects the line segment
* (x3,y3)->(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 +295,64 @@
* @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 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 x2, double y2,
+ double x3, double y3,
+ double x4, double y4)
+ {
+ 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));
+ }
}
/**
_______________________________________________
Classpath mailing list
[EMAIL PROTECTED]
http://lists.gnu.org/mailman/listinfo/classpath
