Smallest-circle problem to bound points?

[probiner]

I was expecting the input on the Sphere SOP to allow me to get the smallest bounding sphere of a mesh (in this case a polygon). But that's not what I'me getting the the picture below, even with Accurate Bounds turned on.




So is there any known solution for this sort of problem?
Here, since 2D, smallest circle problem:

 

Scene: PRB_Bound_Sphere.hipnc

Cheers
 

Edited September 25, 2017 by probiner

[Noobini]

hmm...if you chuck in a box/bound as a 'middleman', the circle/sphere tightens a bit to a better fit...but still not perfect...I'm surprised for such a powerful s/w....it can't even do a proper smallest circle containing points ? what's going on...there's no sim, just calculations, why doesn't it just works 'out of the box' ?

[galagast]

I also got something close, but I highly doubt that this approach is recommendable..  It involves scattering more points to the polygon.

PRB_Bound_Sphere_v2.zip

 

I'm also curious about this as well.
I would like to try and play around this a bit more later when I have time.

Edited September 26, 2017 by galagast

[Noobini]

what about find centroid of points, then r = max dist of a point to centroid, would that be correct ?

[probiner]

@Noobini
While I'm dealing with n-gons here, in the example of a triangle it's easy to see that the centroid and the circumcenter are different.
The Bound SOP does the same thing as the Sphere Input :/



@galagast
I tried to scatter points but the result was the same, did you turn off Accurate Bounds? Because when I did it looks likes your, but one of the tips comes out.
I think with Accurate Bounds off the center found is the Centroid.

 

I'm trying to use this for n-gons to find the center of the smallest circle that bounds all the points and rotate the n-gon about it.

But I guess it's a harder problem then I thought.
 

Edited September 26, 2017 by probiner

[animatrix]

I made this operator when I first started using Houdini. It's from Dave Eberly's library:

https://www.dropbox.com/s/ojzptmfpafqjw5n/MinimumCircle_SOP_Animatrix.otl?dl=1

Could be made faster by using least squares methods instead.

[probiner]

There's this cpp code here: https://www.nayuki.io/page/smallest-enclosing-circle but I don't have a clue how to turn that into a SOP, eheh


@pusat
That works pretty well! Thanks!
https://streamable.com/73xcm

Edited September 26, 2017 by probiner

[galagast]

@pusat
That is cool! Learned quite a few new tricks from that HDA. Thank you!

@probiner
Interestingly, this problem can really be tricky, the wiki entry proposed some solutions of varying accurateness. Most of which goes way over my head.
Anyways, thank you for the link. I used the python code from that website and added additional code to process and create the circle. Everything is now inside a single Python SOP. Here's the latest result:

PRB_Bound_Sphere_v3.zip

Although, it currently expects a flattened n-gon, I didn't include an automatic way to transform it flat on the XZ plane (Animatrix's MinimumCircle SOP seems to have one).

[probiner]

@galagast
Thanks, glad the link was of use. It seems indeed surprisingly tricky.

I know one day I'll wonder about bound sphere, but for now I'll just take the wins of the table and ride to the sunset, since it's what I need for my current problem 

Thanks guys

PRB_Bound_Sphere_v4.hipnc

Edited September 27, 2017 by probiner