尝试这个：
将你的矩形分成 N*M 个正方形，使正方形比球的半径稍宽。让正方形与矩形的边缘重叠可能是个好主意，而不是整齐地放在其中。
制作一个 BitSet 数组。不要使用 Bitset[M][N]，只需使用 new Bitset[M*N] - 一点乘法不会对您造成伤害。
用数字识别每个球。当您将球定位在某个位置时，为该正方形及其周围的 8 个正方形设置 bitset 中的位（为了使这更容易，扩展您的正方形数组，使它们延伸到矩形边缘之外 - 这样您不必剪辑。）
穿过广场。对于每个方形标记中的每对球，这对球都是潜在的碰撞。为此，请创建一个位组 - 假设您有 H 个球并且球 A 和 B 占据同一个方格 - 设置位 A+B H 和 A H+B。
现在很容易找出潜在的冲突，因为 BitSet 包含一个方法，该方法说“在设置的那个之后找到我的下一个位”。请记住，每个位都是双重计数的，因此当检测到位 Q 被设置时，请务必取消设置位(Q%H)*H + (Q/H)- 这是该对的另一位。
或者：您可以很容易地折叠该冲突数组。A 和 B 之间的冲突 -假设 A > B可以通过设置 bit 来标记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}