Linear Least Squares Fit of Sphere to Points

Question

I'm looking for an algorithm to find the best fit between a cloud of points and a sphere.

That is, I want to minimise

where C is the centre of the sphere, r its radius, and each P a point in my set of n points. The variables are obviously Cx, Cy, Cz, and r. In my case, I can obtain a known r beforehand, leaving only the components of C as variables.

I really don't want to have to use any kind of iterative minimisation (e.g. Newton's method, Levenberg-Marquardt, etc) - I'd prefer a set of linear equations or a solution explicitly using SVD.

Answer 1

There are no matrix equations forthcoming. Your choice of E is badly behaved; its partial derivatives are not even continuous, let alone linear. Even with a different objective, this optimization problem seems fundamentally non-convex; with one point P and a nonzero radius r, the set of optimal solutions is the sphere about P.

You should probably reask on an exchange with more optimization knowledge.

Answer 2

You might find the following reference interesting but I would warn you that you will need to have some familiarity with geometric algebra - particularly conformal geometric algebra to understand the mathematics. However, the algorithm is straight forward to implement with standard linear algebra techniques and is not iterative.

One caveat, the algorithm, at least as presented fits both center and radius, you may be able to work out a way to constrain the fit so the radius is constrained.

Total Least Squares Fitting of k-Spheres in n-D Euclidean Space Using an (n+ 2)-D Isometric Representation. L Dorst, Journal of Mathematical Imaging and Vision, 2014 p1-21

Your can pull in a copy from Leo Dorst's researchgate page

One last thing, I have no connection to the author.