高效的算法发现球相距最远的大集合 [英] 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.

的球被存储在以下方式：

The Spheres are stored in the following way:

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

的方法，球体:: distanceTo（球面＆安培;多个）返回球的两个中间点之间的距离

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.

推荐答案

在一组任意两点之间的最大距离取值点叫做 < A HREF =htt​​p://en.wikipedia.org/wiki/Diameter#Generalizations>直径 。找到一组点的直径是在计算几何一个众所周知的问题。在一般情况下，有两个步骤这里：

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. 查找三维凸包每个球体的中心组成的 - 比如，使用 <一个href="http://www.cgal.org/Manual/last/doc_html/cgal_manual/Convex_hull_3_ref/Function_convex_hull_3.html#Cross_link_anchor_911"><$c$c>quickhull实施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，你可以在澳第一步（N日志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）中，其中ħ是在船体的点的数量。在最坏的情况下， ^ h = N （每一个点在船体），但是这是pretty的可能性不大，如果你有成千上万的随机领域。在一般情况下， ^ h 会比小得多ñ。这里的 这种方法的概述。

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