在3D空间中找出一组点中距离最远的两个点。

Question

4

我需要找到三维空间中点云的直径（两个距离最远的点）。目前的临时解决方案是，我只是遍历所有可能的点对并比较它们之间的距离，这是一个非常慢的O(n^2)解决方案。

我相信可以用O(n log n)的时间复杂度完成。在二维平面上，这是一个相当简单的任务（只需找到凸包，然后应用旋转卡尺算法），但在三维空间中，我无法想象如何使用旋转卡尺算法，因为没有办法对点进行排序。

是否有任何简单的方法来实现它（或在python或C/C++中使用现成的实现）？

PS：StackOverflow上有类似的问题，但我发现的答案只涉及旋转卡尺（或类似的）算法，在二维情况下运行良好，但不清楚如何在三维（或更高维）中实现。

- Chan Kha Vu

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Maxim · Accepted Answer

虽然在三维中存在 O(n log n) 的预期时间算法，但它们似乎很难实现（而且要与暴力的 O(n^2) 算法竞争）。

Har-Peled 2001 中描述了一种算法。作者提供了一个源代码，可选择用于最优计算。我无法下载最新版本，旧版本可能已足够您的目的，或者您可能想联系作者获取代码。

Malandain & Boissonnat 2002 中介绍了另一种方法，作者提供了代码。尽管这种算法在更高维度上被认为是近似的，但它可能适合您的目的。请注意，他们的代码提供了 Har-Peled 方法的精确计算实现，您也可以检查一下。

无论如何，在实际使用中，您应始终检查您的算法是否与天真的O(n^2)方法相比具有竞争力。