Эффективный алгоритм для нахождения сфер дальше всего независимо в большом количестве
У меня есть набор 10000 - 100000 сфер, и я должен найти тех дальше всего независимо.
Один простой способ сделать это должно просто сравнить все сферы друг с другом и сохранить самое большое расстояние, но это чувствует себя подобно реальному пожирателю ресурсов алгоритма.
Сферы хранятся следующим образом:
Sphere (float x, float y, float z, float radius);
Сфера метода:: distanceTo (Сфера &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++, менее интересны.
4 ответа
Наибольшее расстояние между любыми двумя точками в наборе S точек называется диаметром . Определение диаметра набора точек - хорошо известная проблема вычислительной геометрии. В общем, здесь два шага:
Найдите трехмерную выпуклую оболочку, состоящую из центра каждой сферы - скажем, используя реализацию
quickhullв CGAL.Найдите точки на корпусе, которые находятся дальше всего друг от друга. (Две точки на внутренней стороне корпуса не могут быть частью диаметра, иначе они были бы на корпусе, что является противоречием.)
С быстрым корпусом вы можете сделать первый шаг за O (n log n) в среднем случае и время работы O (n 2 ) в худшем случае. (На практике quickhull значительно превосходит все другие известные алгоритмы.) Можно гарантировать лучшую оценку в худшем случае, если вы можете гарантировать определенные свойства порядка сфер, но это уже другая тема.
Второй шаг может быть выполнен в Ω (h log h), где h - количество точек на корпусе. В худшем случае h = n (каждая точка находится на корпусе), но это маловероятно, если у вас есть тысячи случайных сфер. В общем, h будет намного меньше, чем n . Вот обзор этого метода.
Пол заставил мой мозг думать, и вы можете немного оптимизировать, изменив
for (int j=0; j < nOfSpheres; j++)
на
for (int j=i+1; j < nOfSpheres; j++)
. Вам не нужно сравнивать сферу A с B И B с A. Это приведет к поиску О (п войти п).
--- Дополнение -------
Еще одна вещь, которая делает эти вычисления дорогостоящими, - это вычисления DistanceTo.
distance = sqrt((x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2)
Это много математики. Вы можете сократить это, проверив, удаляет ли
((x2 - x1)^2 + (y2 - y1)^2 + (z2 - z1)^2 > maxdist^2
sqrt до конца.
Не могли бы вы сохранить эти сферы в BSP-дереве ? Если это приемлемо, вы можете начать с поиска наиболее удаленных друг от друга узлов дерева, содержащих сферы. Затем вы можете продолжать спускаться по дереву, пока не дойдете до отдельных сфер.
Ваша проблема выглядит как нечто, что может быть решается с помощью графиков. Поскольку расстояние от Сферы A до Сферы B такое же, как расстояние от Сферы B до Сферы A, вы можете минимизировать количество сравнений, которые вам нужно сделать.
Я думаю, что то, что вы здесь видите, известно как Список смежности . Вы можете построить один, а затем пройти его, чтобы найти наибольшее расстояние.
Другой подход, который вы можете использовать, по-прежнему даст вам O (n ^ 2), но вы можете минимизировать количество сравнений, которые вам нужно сделать. Вы можете сохранить результат своих вычислений в хеш-таблице, где ключом является имя ребра (так, чтобы AB сохраняла длину от A до B). Прежде чем выполнять расчет расстояния, проверьте, существует ли AB или BA в хеш-таблице.
РЕДАКТИРОВАТЬ
Используя метод списка смежности (который в основном представляет собой поиск в ширину ), вы получите O (b ^ d) или в худшем случае O (| E | + | V | ) сложность.