Line Intersection??

Java 2D
#1

In a game that I’m currently writing which uses ray-casting, I quite often need to test for intersection between two lines. I am using the Line2D.intersectsLine() method to test for this. It doesn’t seem to be very efficient, however. Using a profiling tool, I’ve found out that this call takes up about 12% of all execution time in the game. Does anyone know of a better way to test for intersection between two line segments?
Thanks.

#2

I would be suprised if Suns implementation wasn’t the most efficient general purpose algorithm.
However, im sure you can improve performance by rolling your own float or int version (rather than the double provided by Suns implementation)
You should also be able to add a few additional early escape points, depending on other information your app. has about the world.

#3

Here is the Line2D.linesIntersect() code :


public static boolean linesIntersect(double X1, double Y1,
                               double X2, double Y2,
                               double X3, double Y3,
                               double X4, double Y4) {
      return ((relativeCCW(X1, Y1, X2, Y2, X3, Y3) *
             relativeCCW(X1, Y1, X2, Y2, X4, Y4) <= 0)
            && (relativeCCW(X3, Y3, X4, Y4, X1, Y1) *
                relativeCCW(X3, Y3, X4, Y4, X2, Y2) <= 0));
}

public static int relativeCCW(double X1, double Y1,
                          double X2, double Y2,
                          double PX, double PY) {
      X2 -= X1;
      Y2 -= Y1;
      PX -= X1;
      PY -= Y1;
      double ccw = PX * Y2 - PY * X2;
      if (ccw == 0.0) {
          // The point is colinear, classify based on which side of
          // the segment the point falls on.  We can calculate a
          // relative value using the projection of PX,PY onto the
          // segment - a negative value indicates the point projects
          // outside of the segment in the direction of the particular
          // endpoint used as the origin for the projection.
          ccw = PX * X2 + PY * Y2;
          if (ccw > 0.0) {
            // Reverse the projection to be relative to the original X2,Y2
            // X2 and Y2 are simply negated.
            // PX and PY need to have (X2 - X1) or (Y2 - Y1) subtracted
            //    from them (based on the original values)
            // Since we really want to get a positive answer when the
            //    point is "beyond (X2,Y2)", then we want to calculate
            //    the inverse anyway - thus we leave X2 & Y2 negated.
            PX -= X2;
            PY -= Y2;
            ccw = PX * X2 + PY * Y2;
            if (ccw < 0.0) {
                ccw = 0.0;
            }
          }
      }
      return (ccw < 0.0) ? -1 : ((ccw > 0.0) ? 1 : 0);
    }

I think it’s an interesting implementation ! Dunno if it can be optimized though…

#4

Yeah, I thought it was an interesting implementation as well. I was just wondering if there was a single equation that was able to determine intersection.
Although, the Line2D implementation really only does a few multiplications and few subtractions, which technically isn’t very bad at all.