これを試して：
正方形がボールの半径よりもわずかに広くなるように、長方形を N*M の正方形に分割します。四角形が四角形の中にきちんと収まるのではなく、四角形の端に重なるようにすることをお勧めします。
BitSet の配列を作成します。Bitset[M][N] を使用しないでください。新しい Bitset[M*N] だけを使用してください。多少の乗算は問題ありません。
各ボールを番号で識別します。ある場所にボールを配置するときは、その正方形とその周囲の 8 つの正方形のビットセットにビットを設定します (これを簡単にするために、正方形の配列を拡張して、長方形の端を 1 つ超えて拡張します。クリップする必要はありません。）
正方形を実行します。各正方形のボールのペアごとに、そのペアが衝突の可能性があるものとしてマークします。これを行うには、ビットセットを作成し、H 個のボールがあり、ボール A と B が同じ正方形を占めていると仮定して、ビット A+B H と A H+B を設定します。
BitSet には「設定されているビットの次のビットを見つけてください」というメソッドが含まれているため、衝突の可能性を簡単に回避できます。各ビットは二重にカウントされるため、ビット Q がセットされていることが検出されたら(Q%H)*H + (Q/H)、ペアのもう一方のビットであるビットを必ずアンセットしてください。
あるいは、その衝突の配列を非常に簡単に折りたたむことができます。A と B の間の衝突 -ビットを設定することで A > Bをマークできる場合A * (A-1) / 2 + B。これには、ボールの総数を気にする必要がないという利点があります。
実際：忘れてください。演習として書いたこのクラスを使用してください。
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();
}
};
}
}
そして、それはあなたの潜在的な衝突をうまく追跡します. 疑似コードは次のとおりです。
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;
}
![[拡大版へのリンク]](http://i43.tinypic.com/j0k67o.png){kind=link}
![[拡大版へのリンク]](http://i39.tinypic.com/2jes2fb.png){kind=link}