Эффективный алгоритм поиска сфер, наиболее удаленных друг от друга в большой коллекции

У меня есть коллекция из 10000 - 100000 сфер, и мне нужно найти самых дальних.

Один простой способ сделать это - просто сравнить все сферы друг с другом и сохранить самое большое расстояние, но это похоже на реальный ресурс свиньи алгоритма.

Сферы хранятся следующим образом:

Sphere (float x, float y, float z, float radius);

Метод Sphere:: distanceTo (Sphere & s) возвращает расстояние между двумя центральными точками сфер.

Пример:

Sphere *spheres;
float biggestDistance;

for (int i = 0; i < nOfSpheres; i++) {
    for (int j = 0; j < nOfSpheres; j++) {
        if (spheres[i].distanceTo(spheres[j]) > biggestDistance) {
            biggestDistance = spheres[i].distanceTo(spheres[j]) > biggestDistance;
        }
    }
}

То, что я ищу, - это алгоритм, который каким-то образом перебирает все возможные комбинации умным способом, если таковой существует.

Проект написан на С++ (который он должен быть), поэтому любые решения, которые работают только на языках, отличных от C/С++, представляют меньший интерес.

Ответ 1

Наибольшее расстояние между любыми двумя точками в наборе S точек называется diameter, Обнаружение диаметра набора точек является известной проблемой в вычислительной геометрии. В общем, здесь есть два шага:

Найдите трехмерную выпуклую оболочку, состоящую из центра каждой сферы - скажем, используя quickhull в CGAL.
Найдите точки на корпусе, которые находятся на расстоянии друг от друга. (Две точки на внутренней части корпуса не могут быть частью диаметра, иначе они были бы на корпусе, что является противоречием.)

С помощью quickhull вы можете сделать первый шаг в O (n log n) в среднем случае и O (n ²) в худшем случае. (На практике quickhull значительно превосходит все другие известные алгоритмы.) Можно гарантировать лучшую худшую случайность, если вы можете гарантировать определенные свойства о упорядочении сфер, но это другая тема.

Второй шаг можно сделать в & Omega; (h log h), где h - количество точек на корпусе. В худшем случае h = n (каждая точка находится на корпусе), но это маловероятно, если у вас есть тысячи случайных сфер. В общем случае h будет намного меньше n. Здесь обзор этого метода.

Ответ 2

Возможно, вы сохранили эти сферы в BSP Tree? Если это приемлемо, то вы можете начать с поиска узлов дерева, содержащих сферы, которые наиболее удалены друг от друга. Затем вы можете продолжать движение по дереву, пока не попадете в отдельные сферы.

Ответ 3

Ваша проблема выглядит как нечто, что можно решить с помощью графиков. Поскольку расстояние от Сферы А до Сферы В совпадает с расстоянием от Сферы В до Сферы А, вы можете свести к минимуму количество сравнений, которые вы должны сделать.

Я думаю, что вы смотрите здесь, называется Adjacency List. Вы можете построить один, а затем пересечь его, чтобы найти самое длинное расстояние.

Другой подход, который вы можете использовать, по-прежнему даст вам O (n ^ 2), но вы можете свести к минимуму количество сравнений, которое вы должны выполнить. Вы можете сохранить результат вычисления в хеш-таблицу, где ключ - это имя края (так что AB будет содержать длину от A до B). Прежде чем выполнять расчет расстояний, проверьте, существует ли AB или BA в хеш-таблице.

ИЗМЕНИТЬ

Используя метод списка смежности (который в основном представляет собой Поиск по ширине и ширине), вы получаете O (b ^ d) или худшее, сложность O (| E | + | V |).

Ответ 4

Пол задумал мой мозг, и вы можете немного оптимизировать, изменив

for (int j=0; j < nOfSpheres; j++)

for (int j=i+1;  j < nOfSpheres; j++)

Вам не нужно сравнивать сферу A с B И от B до A. Это сделает поиск O (n log n).

--- Дополнение -------

Еще одна вещь, которая делает этот расчет дорогим, - это дистанции.

distance = sqrt((x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2)

Это много математики. Вы можете обрезать это, проверив, есть ли

((x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2 > maxdist^2

Удаляет sqrt до конца.