Проверка расстояния при каждой 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

Рассмотрим разбиение объектов на ячейки размером thresholdИксthreshold (например, 100x100 в вашем примере). Вы можете выполнить этот раздел за один проход (т.е. O(n)), и представить его как что-то вроде Map<Cell, List<Point>> (где Point тип вашего оригинального объекта).

Теперь посмотрите на каждую ячейку по очереди, скажем, сверху вниз, справа налево, вдоль рядов. Для каждой ячейки вам нужно только проверить каждую точку на соответствие точкам в той же ячейке или в соседней ячейке (и вам не нужно сравнивать ячейки, которые вы сравнивали ранее, поэтому сравнивайте ячейку и ячейку, чтобы справа и клетки ниже). В худшем случае вы ничего не экономите (а разбиение стоит немного), но если точки распределены достаточно равномерно, это в среднем уменьшит количество сравнений.

Answer 2

Один простой способ оптимизировать это - ограничить значения j ты проверяешь. Нет необходимости проверять расстояние между точками A и B, если вы уже проверили расстояние между точками B и A. Это должно сократить количество проверок вдвое (и в качестве побочного эффекта вам больше не нужно проверять, 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

@edit Я неправильно понял вопрос. Вы не можете сделать это быстрее в пессимистическом случае, потому что у вас может быть O(n^2) пар, удовлетворяющих требованиям расстояния