Try this:
Divide your rectangle up into N*M squares, such that the squares are slightly wider than the radius of a ball. It might be a good idea to have the squares overlap the edges of your rectangle, rather than fit neatly within it.
Make an array of BitSet. Don't use an Bitset[M][N], just new Bitset[M*N] - a little multiplication isn't going to hurt you.
Identify each ball with a number. When you position a ball at a location, set the bit in the bitset for that square and the 8 squares around it (to make this easier, extend your array of squares so that they extend one beyond the edge of the rectangle - that way you don't have to clip.)
Run through the squares. For each pair of balls in each square mark that pair as being a potential collision. To do this, create a bitset and - given that you have H balls and balls A and B occupy the same square - set the bits A+B*H and A*H+B.
Looing through the potential collisions is now easy, because BitSet includes a method that says "find me the next bit after this one that is set". Remember that each bit is double counted, so when bit Q is detected as being set, be sure to unset bit (Q%H)*H + (Q/H) - which is the other bit of the pair.
Alternatively: you can collapse that array of collisions pretty easily. A collision between A and B - given that A > B can be marked by setting bit A * (A-1) / 2 + B. This has the advantage that you don't need to care about the total number of balls.
Actually: forget it. just use this class which I wrote as an exercise:
import java.util.BitSet;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class PairSet extends BitSet implements
Iterable<PairSet.Pair> {
public static class Pair implements Comparable<Pair> {
public final int a;
public final int b;
private Pair(int a, int b) {
if (a < 0 || b < 0 || a == b) { throw new IllegalArgumentException(
"Pair(" + a + "," + b + ")"); }
if (a > b) {
this.a = a;
this.b = b;
} else {
this.a = b;
this.b = a;
}
}
public String toString() {
return "Pair(" + a + "," + b + ")";
}
public int hashCode() {
return a * (a - 1) / 2 + b;
}
public boolean equals(Object o) {
return o instanceof Pair
&& hashCode() == ((Pair) o).hashCode();
}
public int compareTo(Pair o) {
return hashCode() - o.hashCode();
}
}
PairSet() {}
PairSet(BitSet z) {
or(z);
}
PairSet(Iterable<Pair> z) {
for (Pair p : z)
set(p);
}
public void set(Pair p) {
set(p.a, p.b);
}
public void clear(Pair p) {
clear(p.a, p.b);
}
public void set(int a, int b) {
if (a < 0 || b < 0 || a == b) { throw new IllegalArgumentException(
"add(" + a + "," + b + ")"); }
if (a > b) {
set(a * (a - 1) / 2 + b);
} else {
set(b * (b - 1) / 2 + a);
}
}
public void clear(int a, int b) {
if (a < 0 || b < 0 || a == b) { throw new IllegalArgumentException(
"add(" + a + "," + b + ")"); }
if (a > b) {
clear(a * (a - 1) / 2 + b);
} else {
clear(b * (b - 1) / 2 + a);
}
}
public Iterator<Pair> iterator() {
return new Iterator<Pair>() {
int at = -1;
int triangle = 0;
int a = 0;
public boolean hasNext() {
return nextSetBit(at + 1) != -1;
}
public Pair next() {
int nextat = nextSetBit(at + 1);
if (nextat == -1) { throw new NoSuchElementException(); }
at = nextat;
while (triangle <= at) {
triangle += a++;
}
return new Pair(a - 1, at - (triangle - a) - 1);
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
And that will nicely keep track of your potential collisions. The psudeocode is then
SW = width of rectangle
SH = height of rectangle
R = radius of balls + 1 // +1 is a fudge factor.
XS = number of squares across = SW/R + 4; // the +4 adds some slop
YS = number of squares hight = SH/R + 4; // the +4 adds some slop
int sx(Point2D.Float p) // the square into which you put a ball at x
// never returns a number < 1
:= (int)((p.x-R/2)/R) + 2;
int sy(Point2D.Float p) // the square into which you put a ball at y
// never returns a number < 1
:= (int)((p.y-R/2)/R) + 2;
Bitset[] buckets = new BitSet[XS*YS];
{for(int i: 0; i<buckets.length; i++) bukets[i] = new BitSet();}
BitSet bucket(int x, int y) {return bucket[y*XS + x]}
BitSet bucket(Point2D.Float p) {return bucket(sy(p),sx(p));}
void move(int ball, Point2D.Float from, Point2D.Float to) {
if bucket(from) == bucket(to) return;
int x,y;
x = sx(from); y=sy(from);
for(int xx==-1;xx<=1; xx++)
for(int yy==-1;yy<=1; yy++)
bucket(sx+xx, sy+yy).clear(ball);
x = sx(to); y=sy(to);
for(int xx==-1;xx<=1; xx++)
for(int yy==-1;yy<=1; yy++)
bucket(sx+xx, sy+yy).set(ball);
}
PointSet findCollisions() {
PointSet pp = new PointSet();
for(BitSet bb: buckets) {
int a;
int prev_a;
for(prev_a = -1; (a = bb.nextSetBit(prev_a+1))!=-1; prev_a=a) {
int b;
int prev_b;
for(prev_b = a; (b = bb.nextSetBit(prev_b+1))!=-1; prev_b=b) {
pp.add(a,b);
}
}
return pp;
}