Как мне наиболее эффективно выполнять обнаружение столкновений в группе сфер

Предположим, у меня есть процессор с несколькими ядрами, на котором я хочу узнать, какие сферы касаются. Любой набор сфер, где каждая сфера связана (т. Е. Все они касаются хотя бы одной из сфер в наборе), называется «группой» и должен быть организован в вектор, называемый, в следующем примере, «group_members». ». Чтобы достичь этого, в настоящее время я использую довольно дорогую операцию, которая концептуально выглядит следующим образом:

vector<Sphere*> unallocated_spheres = all_spheres; // start with a copy of all spheres
vector<vector<Sphere*>> group_sequence; // groups will be collected here

while (unallocated_spheres.size() > 0U) // each iteration of this will represent the creation of a new group
{
std::vector<Sphere*> group_members; // this will store all members of the current group
group_members.push_back(unallocated_spheres.back()); // start with the last sphere (pop_back requires less resources than erase)
unallocated_spheres.pop_back(); // it has been allocated to a group so remove it from the unallocated list

// compare each sphere in the new group to every other sphere, and continue to do so until no more spheres are added to the current group
for (size_t i = 0U; i != group_members.size(); ++i) // iterators would be unsuitable in this case
{
Sphere const * const sphere = group_members[i]; // the sphere to which all others will be compared to to check if they should be added to the group
auto it = unallocated_spheres.begin();
while (it != unallocated_spheres.end())
{
// check if the iterator sphere belongs to the same group
if ((*it)->IsTouching(sphere))
{
// it does belong to the same group; add it and remove it from the unallocated_spheres vector and repair iterators
group_members.push_back(*it);
it = unallocated_spheres.erase(it); // repair the iterator
}
else ++it; // if no others were found, increment iterator manually
}
}

group_sequence.push_back(group_members);
}

У кого-нибудь есть какие-либо предложения по повышению эффективности этого кода с точки зрения настенного времени? Моя программа тратит значительную часть времени на прохождение этих циклов, и любые советы о том, как ее структурно изменить, чтобы сделать ее более эффективной, были бы оценены.

Обратите внимание, что, поскольку это сферы, «IsTouching ()» — это очень быстрая операция с плавающей запятой (сравнение положения и радиусов двух сфер). Это выглядит так (обратите внимание, что x, y и z — это положение сферы в этом евклидовом измерении):

// input whether this cell is touching the input cell (or if they are the same cell; both return true)
bool const Sphere::IsTouching(Sphere const * const that) const
{
// Apply pythagoras' theorem in 3 dimensions
double const dx = this->x - that->x;
double const dy = this->y - that->y;
double const dz = this->z - that->z;

// get the sum of the radii of the two cells
double const rad_sum = this->radius + that->radius;

// to avoid taking the square root to get actual distances, we instead compare
// the square of the pythagorean distance with the square of the radii sum
return dx*dx + dy*dy + dz*dz < rad_sum*rad_sum;
}