在 3D 中的一组点中找到两个最远的点 space
Find two most distant points in a set of points in 3D space
我需要找到 3 维点云的直径（它们之间距离最大的两个点）space。作为一个临时解决方案，现在我只是遍历所有可能的对并比较它们之间的距离，这是一个非常慢的 O(n^2) 解决方案。
我相信 O(n log n) 可以完成。这在 2D 中是一个相当容易的任务（只需找到 convex hull 然后应用 rotating calipers 算法），但在 3D 中我无法想象如何使用旋转卡尺，因为无法对点进行排序。
是否有任何简单的方法可以做到这一点（或在 python 或 C/C++ 中的即用型实现）？
PS: Whosebug 上有类似的问题，但我找到的答案仅指旋转卡尺（或类似）算法，在 2D 中工作正常情况，但不太清楚如何在 3D（或更高维度）中实施。
虽然 3d 中存在 O(n log n) 预期时间算法，但它们似乎难以实现（同时与蛮力 O(n^2) 算法保持竞争力）。
Har-Peled 2001. The authors provide a source code 中描述了一种算法，可以选择将其用于优化计算。我无法下载最新版本，"old" 版本可能足以满足您的需求，或者您可能需要联系作者获取代码。
Malandain & Boissonnat 2002 and the authors provide code 中介绍了另一种方法。尽管此算法在更高维度上呈现为近似值，但它可能适合您的目的。请注意，他们的代码提供了 Har-Peled 的精确计算方法的实现，您也可以检查一下。
无论如何，在实际使用中，您应该始终检查您的算法相对于朴素的 O(n^2) 方法是否仍然具有竞争力。
我需要找到 3 维点云的直径（它们之间距离最大的两个点）space。作为一个临时解决方案，现在我只是遍历所有可能的对并比较它们之间的距离，这是一个非常慢的 O(n^2) 解决方案。
我相信 O(n log n) 可以完成。这在 2D 中是一个相当容易的任务（只需找到 convex hull 然后应用 rotating calipers 算法），但在 3D 中我无法想象如何使用旋转卡尺，因为无法对点进行排序。
是否有任何简单的方法可以做到这一点（或在 python 或 C/C++ 中的即用型实现）？
PS: Whosebug 上有类似的问题，但我找到的答案仅指旋转卡尺（或类似）算法，在 2D 中工作正常情况，但不太清楚如何在 3D（或更高维度）中实施。
虽然 3d 中存在 O(n log n) 预期时间算法，但它们似乎难以实现（同时与蛮力 O(n^2) 算法保持竞争力）。
Har-Peled 2001. The authors provide a source code 中描述了一种算法，可以选择将其用于优化计算。我无法下载最新版本，"old" 版本可能足以满足您的需求，或者您可能需要联系作者获取代码。
Malandain & Boissonnat 2002 and the authors provide code 中介绍了另一种方法。尽管此算法在更高维度上呈现为近似值，但它可能适合您的目的。请注意，他们的代码提供了 Har-Peled 的精确计算方法的实现，您也可以检查一下。
无论如何，在实际使用中，您应该始终检查您的算法相对于朴素的 O(n^2) 方法是否仍然具有竞争力。