Name: mc57594 Date: 03/13/97


Hi,

I just discovered a problem, in the geometrical methods of the
java.awt.Rectangle class, concerning the intersection stuff.


problem: some methods (at least intersects, intersection, union, add) are
using int-based operations like 'x+width' and 'y+height'. since all the
Rectangle fields (x, y, width, height) are coded by ints, this leads to
overflowed results. I don't feel this important for methods like 'union' or
'add', because we all know that such operations can lead to mathematical
overflow. But for methods like 'intersects' and 'intersection', nothing in
their logical specification indicates that an overflow can occur.
However, an overflow DOES occur in Sun's JDK-1.1-Final.

As a result, see what happens with the two following rectangles:

r1 = java.awt.Rectangle[x=10,y=10,width=10,height=10]
r3 = java.awt.Rectangle[x=1,y=1,width=2147483647,height=2147483647]

r1.intersects(r3) returns 'false' instead of 'true'.

To avoid this bug with the current implementation, you must be sure that you do
not build a Rectangle with either (x + width > Integer.MAX_VALUE) or
(y + height > Integer.MAX_VALUE).

Included below are my test results and the source code for this test, and also
methods 'fixed' to not encouter the overflow problem.

jm.
--
###@###.### - GIE Dyade - http://www.inria.fr/koala/jml


clip results :
============


koala$ java11 clip
r1 = java.awt.Rectangle[x=10,y=10,width=10,height=10]
r2 = java.awt.Rectangle[x=1,y=1,width=32767,height=32767]
r3 = java.awt.Rectangle[x=1,y=1,width=2147483647,height=2147483647]
r1 ^ r2 : -> true
r1 ^ r2 : true
r1 ^ r3 : -> false
r1 ^ r3 : true
r1 ^ r2 : -> java.awt.Rectangle[x=10,y=10,width=10,height=10]
r1 ^ r2 : java.awt.Rectangle[x=10,y=10,width=10,height=10]
r1 ^ r3 : -> java.awt.Rectangle[x=10,y=10,width=2147483638,height=2147483638]
r1 ^ r3 : java.awt.Rectangle[x=10,y=10,width=10,height=10]



   ------------------------- 8< clip.java 8< ---------------------------

import java.awt.Rectangle;

public class clip {
    static public void main(String args[]) {
Rectangle r1, r2, r3;
r1 = new Rectangle(10, 10, 10, 10);
r2 = new Rectangle(1, 1, Short.MAX_VALUE, Short.MAX_VALUE);
r3 = new Rectangle(1, 1, Integer.MAX_VALUE, Integer.MAX_VALUE);

System.out.println("r1 = " + r1);
System.out.println("r2 = " + r2);
System.out.println("r3 = " + r3);

System.out.println("r1 ^ r2 : -> " + r1.intersects(r2));
System.out.println("r1 ^ r2 : " + intersects(r1, r2));

System.out.println("r1 ^ r3 : -> " + r1.intersects(r3));
System.out.println("r1 ^ r3 : " + intersects(r1, r3));

System.out.println("r1 ^ r2 : -> " + r1.intersection(r2));
System.out.println("r1 ^ r2 : " + intersection(r1, r2));

System.out.println("r1 ^ r3 : -> " + r1.intersection(r3));
System.out.println("r1 ^ r3 : " + intersection(r1, r3));
    }


    static public boolean intersects(Rectangle r1, Rectangle r2) {
return !(((long)r1.x + r1.width <= (long)r2.x) ||
((long)r1.y + r1.height <= (long)r2.y) ||
((long)r1.x >= (long)r2.x + r2.width) ||
((long)r1.y >= (long)r2.y + r2.height));
    }

    
    static public Rectangle intersection(Rectangle r1, Rectangle r2) {
int x1 = Math.max(r1.x, r2.x);
long x2 = Math.min((long)r1.x + r1.width, (long)r2.x + r2.width);
int y1 = Math.max(r1.y, r2.y);
long y2 = Math.min((long)r1.y + r1.height, (long)r2.y + r2.height);
return new Rectangle(x1, y1, (int)(x2 - x1), (int)(y2 - y1));
    }
}

   ------------------------- 8< clip.java 8< ---------------------------

company - Dyade , email - ###@###.###
======================================================================