每 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

@edit 我误解了这个问题。在悲观的情况下你不能做得更快，因为你可以有 O(n^2) 对满足距离要求

Answer 2

优化它的一个简单方法是限制您检查的 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.
        }
    }
}

Answer 3

考虑将对象划分为大小为 thresholdxthreshold 的单元格（例如，您的示例中为 100x100）。您可以一次性执行此分区（即 O(n)），并将其表示为 Map<Cell, List<Point>>（其中 Point 是原始对象的类型）。

现在依次查看每个单元格，从左上角到右下角，按行。对于每个单元格，您只需要针对同一单元格或紧邻单元格中的点测试每个点（并且您不需要比较之前比较过的单元格，因此在单元格内进行比较，并与单元格进行比较右侧，以及下方的单元格）。在最坏的情况下，您什么都不会节省（并且进行分区会花费一点点），但如果点合理均匀分布，这将平均减少比较次数。

每 n 次优化时的距离检查

Distance check at every nth optimization

python

java

optimization

distance