java - 每第 n 次优化时进行距离检查

Question

尽管代码是用 Java 编写的，但这更像是一个一般性的编程问题。请随时以任何语言回答!

我有一个要迭代的对象列表，我想检查是否有任何对象在距离阈值内。为了做到这一点，我必须重新遍历整个列表以检查每个对象的距离。我大致是这样做的(伪代码):

for (int i = 0; i < objects.size(); i++) {
    for (int j = 0; j < objects.size(); j++) {
        if (i == j) {
            continue;
        }

        if (dist(objs[i], objs[j]) < 100) {
            // Do something.
        }
    }
}

有什么办法可以优化这个吗？我知道我可以使用距离平方来避免平方根，但我发现它没有多大帮助。这是我当前的距离函数:

Math.sqrt(((vector.x-this.x)*(vector.x-this.x)) + ((vector.y-this.y)*(vector.y-this.y)));

如果屏幕底部有一个物体，顶部有一个物体，那么它们显然彼此不靠近，那么它们如何能够忽略彼此呢？

谢谢!

Answer 1

优化此功能的一种简单方法是限制您检查的 j 值。如果您已经检查了 B 点和 A 点之间的距离，则无需检查 A 点和 B 点之间的距离。这应该会将检查次数减少一半(并且作为副作用，您不再需要检查是否 i==j)。

for (int i = 0; i < objects.size(); i++) {
    for (int j = i+1; j < objects.size(); j++) {

        if (dist(objs[i], objs[j]) < 100) {
            // Do something.
        }
    }
}