C# Welzl's Minimum Bounding Sphere

Hi,

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:
welzlcircle
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:
welzlsphere3pts
What I usually get:
welzlsphereFail

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)

2 Likes

James, I had a similar problem, I solved it with the help of geometry, iterating over the circles, given by all pairs and triples of points on the plane. This definition worked very slowly.

As a result, I began to master with с sharp))

Maybe these links will be useful to you

Have you tried this task through the grasshopper plugin? Moving the code to visual studio?

1 Like

Hi Alex,

Thanks for bringing this thread back from the brink of death and for your links.

If what you’ve done is brute force the min circle problem, you should download my definition and take a look at my working 2D welzl’s algorithm. It’s a lot faster than brute force trying all triplet combinations of points.

I have not tried it with Grasshopper since my purpose is to create a compiled C# component, and I don’t think this recursive algorithm would even be possible in plain GH anyways.

I do code it in Visual studio. The debugger hasn’t really helped me figure out whats going wrong. I just put the code into C# components in a GH definition so I could share it on the forum easily.

Maybe I’ll be able to get some ideas from your miniball link.
Thanks