I have been working on Welzl’s algorithm for smallest enclosing circles and spheres. I have been able to write a working C# script for the 2D case (circle), but have been having a lot of trouble extending that into 3D for the sphere.
I am not looking for approximations for the minimum bounding sphere, I already have that, I am looking for the exact minimum bounding sphere using Welzl’s algorithm, since that should be able to compute in linear time.
Here’s a result for the 2D case using the code I have for that:
Note that it is tangent to 3 points, uniquely defining a circle.
What I get from my current best code for spheres, when it works:
What I usually get:
It seems the biggest issue I have is that it fails when the sphere must be defined by 4 points. It appears to work when it is defined by 1 point (a 0 radius sphere centered on the point), 2 points (a sphere where the center is the midpoint between the points), and 3 points (a sphere with the same center and radius as the circumcircle of the points), but fails when it is to be defined by 4 points.
My latest attempt has been based on this webpage: https://www.gamedev.net/tutorials/programming/graphics/welzl-r2484/ but hasn’t worked out yet.
I find this hard to debug due to the recursiveness of the code, hopefully someone here can help me out! I am attaching all of my code for the 2D and 3D attempts I have made so far.
WelzlforForum.gh (16.5 KB)