用于在大型集合中找到距离最远的球体的高效算法

Question

我有10000到100000个球体的集合,我需要找到距离最远的球体.

一个简单的方法做,这是简单地比较所有的领域,彼此存储的最大距离,但这种感觉就像一个算法的实际资源猪.

Spheres以下列方式存储:

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. 找到由每个球体的中心组成的三维凸包 - 比如说,使用quickhullCGAL中的实现.

2. 找到最远的船体上的点.(船体内部的两个点不能是直径的一部分,否则它们会在船体上,这是一个矛盾.)

使用quickhull,您可以在平均情况下的O(n log n)和O(n ²)最坏情况运行时间中执行第一步.(在实践中,quickhull明显优于所有其他已知算法.)如果可以保证关于球体排序的某些属性,则可以保证更好的最坏情况界限,但这是一个不同的主题.

第二步可以用Ω(h log h)完成,其中h是船体上的点数.在最坏的情况下,h = n(每个点都在船体上),但如果你有数以千计的随机球体,这是不太可能的.一般来说,h会比小得多n.以下是此方法的概述.