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

Question

У меня есть коллекция из 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 ++ (что и должно быть), поэтому любые решения, которые только работают на языках, отличных от C / C ++, представляют меньший интерес.

Answer 1

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

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

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

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

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

Answer 2

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

Answer 3

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

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 до конца.

Answer 4

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

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

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

EDIT

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