python - 在 3D 空间中的一组点中找到两个最远的点

Question

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

我相信它可以在 O(n log n) 中完成。这在 2D 中是一个相当容易的任务(只需找到凸包然后应用旋转卡尺算法)，但在 3D 中我无法想象如何使用旋转卡尺，因为没有办法订购积分。

是否有任何简单的方法(或在 python 或 C/C++ 中现成可用的实现)？

PS:StackOverflow 上有类似的问题，但我找到的答案仅涉及旋转卡尺(或类似)算法，它在 2D 情况下工作正常但不太清楚如何在3D(或更高维度)。

Answer 1

虽然 O(n log n) 预期时间算法存在于 3d 中，但它们似乎难以实现(同时保持与蛮力 O(n^2) 算法的竞争力)。

Har-Peled 2001 中描述了一种算法.作者提供了一个 source code than 可以选择性地用于优化计算。我无法下载最新版本，“旧”版本可能足以满足您的需求，或者您可能需要联系作者以获取代码。

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

无论如何，在实际使用中，您应该始终检查您的算法相对于朴素的 O(n^2) 方法是否仍然具有竞争力。