math - 肯定包含给定点列表的球体 [点具有 x、y 和 z 坐标]

Question

我试图找到 的球体粗暴地包含 给定的点列表。
点将具有 x、y 和 z 坐标[点在 3D 中]。

实际上，我试图根据给定的点列表通过一些计算找到新的三个点，例如 find MinX,MaxX ,MinY,MaxY,and MinZ 和 MaxZ 并进行一些操作并找到新的三个点

我将从这三个点绘制球体。

我也会带走所有这些 三 球体直径上的点，所以我有一个独特的球体。

是否有任何标准方法可以找到给定点列表的包含范围？

Answer 1

是的，标准算法是 Welzl's algorithm (假设您想要 最小 球体围绕您的点)。特别是Gaertner的改进版非常有用，稳健且数值稳定!它也可以很好地处理所有退化的情况。

该算法的核心是(随机)排列点以找到位于球体边界上的 1-4 个点。它基本上是一个聪明的试错算法。从这些点中，您可以通过找到与所有这些点距离相同的点来找到中心。 Gärtner 的版本使用改进的数字设备来找到中心。此外，它采用了一个额外的旋转步骤，大概可以使算法对大量输入点更好地工作。

如果您只想要一个围绕三个点的球体，我建议您仍然使用 Gärtners“设备”来计算三角形的外 catch 面。否则，该方法可能很容易退化(即当三角形非常平坦时)。