c++ - 给定 3D 空间中的 N 个点，如何找到包含这 N 个点的最小球体？

给定 3D 空间中的 N 个点，如何找到包含这 N 个点的最小球体？

最佳答案

这个问题称为最小封闭球问题。 (谷歌这个词可以找到关于它的教程和论文)。

这是一种实现:C++ 中的 http://www.inf.ethz.ch/personal/gaertner/miniball.html。

它的 2d 情况(找到一个圆来包围平面中的所有点)是计算几何类(class)中教授的经典示例。 3D 只是 2D 情况的简单扩展。

此问题的一种算法是增量式。你从 4 个点开始，它们固定一个球体，当你添加第 5 个点时，有两种情况:

点在球体中。无需更新。

点外。在这种情况下，您需要更新您的球体。然后一个重要的属性是这个新点必须在你的新球体上!

根据上述观察，您的问题会变小。阅读 this book 的第 4.7 节。它也可以在谷歌书上找到。

关于c++ - 给定 3D 空间中的 N 个点，如何找到包含这 N 个点的最小球体？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/2395178/