我收集了 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.
Spheres 的存储方式如下:
The Spheres are stored in the following way:
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:
找到由每个球体中心组成的三维凸包——比如说，使用 quickhull 在 CGAL 中的实现.
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(n2) 运行时间中完成第一步.(在实践中，quickhull 明显优于所有其他已知算法.)如果您可以保证球体排序的某些属性，则可以保证更好的最坏情况界限，但这是一个不同的主题.
With quickhull, you can do the first step in O(n log n) in the average case and O(n2) 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.
更多推荐
查找大型集合中相距最远的球体的高效算法
发布评论