Sphere that surely encompass given list of points [points are with x, y and z co-ordinate]

Question

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].

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.

Is there any standard way for finding encompassing sphere of given list of points?

Answer 1

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.

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.

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).