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

Question

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

Answer 1

这个问题称为最小包围球问题。 (谷歌这个术语可以找到关于它的教程和论文)。

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

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

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

1. 该点在球体中。无需更新。

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

根据以上观察，你的问题变小了。阅读 this book 的第 4.7 节.也可以在 google book 上找到。