肯定包含给定点列表的球体[点具有x，y和z坐标] [英] Sphere that surely encompass given list of points [points are with x, y and z co-ordinate]

问题描述

我正在尝试找到一定包含给定点列表的球体.点将具有x，y和z坐标[点在3D中].

I am trying to find sphere that surly encompasses given list of points. Points will have x, y and z co-ordinate[Points are in 3D].

实际上，我试图通过给定的点列表通过诸如MinX，MaxX，MinY，MaxY和MinZ和MaxZ之类的计算来找到新的三个点，并进行一些操作以找到新的三个点

Actually I am trying to find new three points based on given list of points by some calculations like find MinX,MaxX ,MinY,MaxY,and MinZ and MaxZ and do some operation and find new three points

我将从这三个点画出球体.

And I will draw sphere from these three points.

我还将在球体直径上获取所有这些三个点，所以我有一个唯一的球体.

And I will also taking all these three points on the diameter of sphere so I have a unique sphere.

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

推荐答案

是的，标准算法是 Welzl的算法(假设您希望在点周围使用最小球体).特别是 Gaertner 的改进版本非常有用，稳定且在数值上稳定！它也可以很好地处理所有退化的情况.

Yes, the standard algorithm is Welzl's algorithm (assuming you want the minimal sphere around your points). Particularly the improved version of Gaertner is very useful, robust and numerically stable! It handles all the degenerate cases well too.

该算法的核心是随机地对这些点进行置换，以找到位于球体边界上的1-4个点.从本质上讲，这是一个聪明的反复试验算法.从这些点中，您可以找到与所有这些点都具有相同距离的点来找到中心.盖尔特纳(Gärtner)的版本使用了改进的数字设备来查找中心.而且，它采用了额外的枢轴调整步骤，大概使该算法在大量输入点上工作得更好.

At its core, the algorithm permutes the points (randomly) to find the 1-4 points that lie on the boundary of the sphere. It's basically a clever trial-and-error algorithm. From these points, you can find the center by finding a point that has the same distance to all those points. Gärtner's version uses an improved numerical device to find the center. Also, it employs an extra pivoting step that presumably makes the algorithm work better for a large number of input points.

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

If all you want is a sphere around three points, I suggest you still use Gärtners "device" to compute the circumsphere of the triangle. Otherwise, the method will probably degenerate easily (i.e. when the triangle is very flat).

这篇关于肯定包含给定点列表的球体[点具有x，y和z坐标]的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！