在大集合中寻找相距最远的球体的高效算法 [英] Efficient algorithm for finding spheres farthest apart in large collection

问题描述

我收集了 10000 - 100000 个球体，我需要找到相距最远的球体.

I've got a collection of 10000 - 100000 spheres, and I need to find the ones farthest apart.

一种简单的方法是简单地将所有球体相互比较并存储最大距离，但这感觉就像算法的真正资源.

One simple way to do this is to simply compare all the spheres to each other and store the biggest distance, but this feels like a real resource hog of an algorithm.

球体的存储方式如下:

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

Sphere::distanceTo(Sphere &s) 方法返回球体的两个中心点之间的距离.

The method Sphere::distanceTo(Sphere &s) returns the distance between the two center points of the spheres.

示例:

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;
        }
    }
}

我正在寻找一种算法，它以某种方式以更智能的方式遍历所有可能的组合(如果有的话).

What I'm looking for is an algorithm that somehow loops through all the possible combinations in a smarter way, if there is any.

该项目是用 C++ 编写的(它必须是)，因此任何只在 C/C++ 以外的语言中工作的解决方案都不那么有趣.

The project is written in C++ (which it has to be), so any solutions that only work in languages other than C/C++ are of less interest.

推荐答案

一组 S 点中任意两点之间的最大距离称为 直径.求一组点的直径是计算几何中的一个众所周知的问题.一般来说，这里有两个步骤:

The largest distance between any two points in a set S of points is called the diameter. Finding the diameter of a set of points is a well-known problem in computational geometry. In general, there are two steps here:

1. 找到由每个球体的中心组成的三维凸包——比如说，使用 quickhull 在 CGAL 中的实现.

1. Find the three-dimensional convex hull composed of the center of each sphere -- say, using the quickhull implementation in CGAL.

找出船体上相距最远的点.(船体内部的两点不能是直径的一部分，否则它们会在船体上，这是矛盾的.)

Find the points on the hull that are farthest apart. (Two points on the interior of the hull cannot be part of the diameter, or otherwise they would be on the hull, which is a contradiction.)

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

With quickhull, you can do the first step in O(n log n) in the average case and O(n²) worst-case running time. (In practice, quickhull significantly outperforms all other known algorithms.) It is possible to guarantee a better worst-case bound if you can guarantee certain properties about the ordering of the spheres, but that is a different topic.

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

The second step can be done in Ω(h log h), where h is the number of points on the hull. In the worst case, h = n (every point is on the hull), but that's pretty unlikely if you have thousands of random spheres. In general, h will be much smaller than n. Here's an overview of this method.

这篇关于在大集合中寻找相距最远的球体的高效算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！