用于发现大集合中最远的球体的有效算法 [英] Efficient algorithm for finding spheres farthest apart in large collection

问题描述

我有一个10000 - 100000个球体的集合，我需要找到最远的球体。

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

球体以以下方式存储：

  x，float y，float z，float radius）; 
  

方法Sphere :: distanceTo（Sphere& s）返回两个中心点之间的距离

示例：

 球体* 
 float largestDistance; 
 
 for（int i = 0; i  for（int j = 0; j< nOfSpheres; j ++）{
 if i] .distanceTo（spheres [j]）> largestDistance）{
 largestDistance = spheres [i] .distanceTo（spheres [j]）>最大距离
} 
} 
} 
  

这个项目是用C ++编写的（它必须是），它是以一种更聪明的方式循环遍历所有可能的组合的算法。因此只有工作在非C / C ++语言的解决方案才感兴趣。

解决方案

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

1. 找到由每个球体的中心组成的三维凸包 - 例如，使用




2. 在船体上找到距离最远的点。 （船体内部的两个点不能是直径的一部分，否则它们将在船体上，这是一个矛盾。）

对于quickhull，可以在平均情况下执行O（n log n）中的第一步，并在最坏情况下运行时间执行O（n 2 ）。 （在实践中，quickhull明显优于所有其他已知的算法。）如果您能保证关于球体的排序的某些属性，那么可以保证更好的最坏情况约束。但是这是一个不同的主题。





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

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.

The Spheres are stored in the following way:

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

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

Example:

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.

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.

解决方案

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. Find the three-dimensional convex hull composed of the center of each sphere -- say, using the quickhull implementation in CGAL.

2. 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.)

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.

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屋！