A bug of org.apache.harmony.awt.geom.GeometryUtil

[rubypdf]

here is a Graphics2D example, https://gist.github.com/4230687 but it will stop at "leaf1.intersect(leaf2);" after some debug, I found it should a bug in the cubicNewton method of org.apache.harmony.awt.geom.GeometryUtil

first, if d==0 it will be infinity loop, second, if Math.sqrt((t - t1) * (t - t1) + (s - s1) * (s - s1)) > EPSILON, it will be always true, also a infinity loop, because it do the same job every time.

private static void cubicNewton(double xCoefs1[], double yCoefs1[], double xCoefs2[], 
                                double yCoefs2[], double[] params) {
    double t = 0.0, s = 0.0;
    double t1 = params[0];
    double s1 = params[1];
    double d, dt, ds;

    while (Math.sqrt((t - t1) * (t - t1) + (s - s1) * (s - s1)) > EPSILON) {

        d = -(3 * t * t * xCoefs1[0] + 2 * t * xCoefs1[1] + xCoefs1[2]) * 
            (3 * s * s * yCoefs2[0] + 2 * s * yCoefs2[1] + yCoefs2[2]) +
            (3 * t * t * yCoefs1[0] + 2 * t * yCoefs1[1] + yCoefs1[2]) *
            (3 * s * s * xCoefs2[0] + 2 * s * xCoefs2[1] + xCoefs2[2]);

        dt = (t * t * t * xCoefs1[0] + t * t * xCoefs1[1] + t * xCoefs1[2] +
              xCoefs1[3] - s * s * s * xCoefs2[0] - s * s * xCoefs2[1] - 
              s * xCoefs2[2] - xCoefs2[3]) * (- 3 * s * s * yCoefs2[0] - 
              2 * s * yCoefs2[1] - yCoefs2[2]) + (t * t * t * yCoefs1[0] + 
              t * t * yCoefs1[1] + t * yCoefs1[2] + yCoefs1[3] - s * s *s * yCoefs2[0] - 
              s * s * yCoefs2[1] - s * yCoefs2[2] - yCoefs2[3]) * 
             (3 * s * s * xCoefs2[0] + 2 * s * xCoefs2[1] + xCoefs2[2]);

        ds = (3 * t * t * xCoefs1[0] + 2 * t * xCoefs1[1] + xCoefs1[2]) *
             (t * t * t * yCoefs1[0] + t * t * yCoefs1[1] + t * yCoefs1[2] + 
              yCoefs1[3] - s * s * s * yCoefs2[0] - s * s * yCoefs2[1] - 
              s * yCoefs2[2] - yCoefs2[3]) - (3 * t * t * yCoefs1[0] + 
              2 * t * yCoefs1[1] + yCoefs1[2]) * (t * t * t * xCoefs1[0] + 
              t * t * xCoefs1[1] + t * xCoefs1[2] + xCoefs1[3] - 
              s * s * s * xCoefs2[0] - s * s * xCoefs2[1] - s * xCoefs2[2] - xCoefs2[3]);

        t1 = t - dt / d;
        s1 = s - ds / d;
    }
    params[0] = t1;
    params[1] = s1;
}

[akbertram]

Thanks for the bug report, can you propose a fix for the method? I'm afraid I'm not familiar with this algorithm at all.

[rubypdf]

I have no idea either, I tried to fix it in this way, but got the following error,

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException at java.lang.System.arraycopy(Native Method) at com.google.code.appengine.awt.geom.Area.includeCoordsAndRules(Area.java:1175) at com.google.code.appengine.awt.geom.Area.intersectCurvePolygon(Area.java:614) at com.google.code.appengine.awt.geom.Area.intersect(Area.java:282) at com.witwall.Graphics2DEx.main(Graphics2DEx.java:100)

private static void cubicNewton(double xCoefs1[], double yCoefs1[], double xCoefs2[], double yCoefs2[], double[] params) { double t = 0.0, s = 0.0; double t1 = params[0]; double s1 = params[1]; double d, dt, ds; while (Math.sqrt((t - t1) * (t - t1) + (s - s1) * (s - s1)) > EPSILON) {

    t=t1;
    s=s1;
    d = -(3 * t * t * xCoefs1[0] + 2 * t * xCoefs1[1] + xCoefs1[2]) * 
        (3 * s * s * yCoefs2[0] + 2 * s * yCoefs2[1] + yCoefs2[2]) +
        (3 * t * t * yCoefs1[0] + 2 * t * yCoefs1[1] + yCoefs1[2]) *
        (3 * s * s * xCoefs2[0] + 2 * s * xCoefs2[1] + xCoefs2[2]);
   if(d==0)
       break;  

    dt = (t * t * t * xCoefs1[0] + t * t * xCoefs1[1] + t * xCoefs1[2] +
          xCoefs1[3] - s * s * s * xCoefs2[0] - s * s * xCoefs2[1] - 
          s * xCoefs2[2] - xCoefs2[3]) * (- 3 * s * s * yCoefs2[0] - 
          2 * s * yCoefs2[1] - yCoefs2[2]) + (t * t * t * yCoefs1[0] + 
          t * t * yCoefs1[1] + t * yCoefs1[2] + yCoefs1[3] - s * s *s * yCoefs2[0] - 
          s * s * yCoefs2[1] - s * yCoefs2[2] - yCoefs2[3]) * 
         (3 * s * s * xCoefs2[0] + 2 * s * xCoefs2[1] + xCoefs2[2]);

    ds = (3 * t * t * xCoefs1[0] + 2 * t * xCoefs1[1] + xCoefs1[2]) *
         (t * t * t * yCoefs1[0] + t * t * yCoefs1[1] + t * yCoefs1[2] + 
          yCoefs1[3] - s * s * s * yCoefs2[0] - s * s * yCoefs2[1] - 
          s * yCoefs2[2] - yCoefs2[3]) - (3 * t * t * yCoefs1[0] + 
          2 * t * yCoefs1[1] + yCoefs1[2]) * (t * t * t * xCoefs1[0] + 
          t * t * xCoefs1[1] + t * xCoefs1[2] + xCoefs1[3] - 
          s * s * s * xCoefs2[0] - s * s * xCoefs2[1] - s * xCoefs2[2] - xCoefs2[3]);

    t1 = t - dt / d;
    s1 = s - ds / d;
}
params[0] = t1;
params[1] = s1;

}