Grasshopper

generative modeling for Rhino

# Maximum inscribed circle

Hi all,

I have a grasshopper/math question. Is there an algorithm or method for finding the maximum circle that can be inscribed inside a curve? I've found a way of finding the minimum enclosing circle, now I'm trying to find the maximum circle that can be put inside a circular curve with one or more points on the curve being coincident and none of the points being contained. I was trying to figure this out with the containment component and galapagos, but couldn't get it to work. Any ideas?

Thanks,

Ali

Views: 711

### Replies to This Discussion

I'm an idiot. I've been searching for this problem for a whole day and until I posted my message here didn't come up with the right description for the problem: maximum inscribed circle. I found a post about this just now: http://stackoverflow.com/questions/3953623/is-there-an-simple-algor... . Apparently the problem is not trivial :( So I guess I have my work cut out for me.

Okay this is my first attempt. I must admit I haven't yet read any of the papers on the subject. But just looking at the Voronoi diagram, I thought that the maximum inscribed circle will be centered at one of the vertices of the Voronoi curves. Is this right?

My test seems to work, but it would be great if someone else confirms if this is in fact the correct approach.

Also, I was trying to extend my first file so that I can feed more than one set of points and get the max inscribed circle for each set. However, I am having problem again with working with the data tree. When I want to find the distance between each of the vertices of the Voronoi diagram and my points, I need to repeat the points. It works fine for a single set of points but breaks down in the second file (gen_max_circle_02). Any ideas how I can do this?

Regards,

Ali

Attachments:

I didn't check your voronoi method but here is a galapagos method which seems to work reasonably well.

It can probably be greatly optimized.

Attachments:

Hi there,

Thank you for the reply. I've tried to use the file. However, when I try and run Galapagos solver, it gives me an "Overflow Error" without even running the solution process. Do I need to have something special to use this file? I'm sorry if this is a stupid question but I'm new to Grasshopper.

But from the saved solution in your file, it seems that we get the same results using either method. I was just trying to see which is the faster method.

Attachments:

Perhaps Galapagos lost the links to the sliders and fitness function, Genome sliders are the one at beginning of definition, fitness is the result of the last component.

Your solution seems faster but less accurate (unless you increase the number of division points, and it can get very slow).

Well here is the corrected version of the file for multiple set. I don't think What I've done is very elegant but it seems to work.

Attachments:

Here is a trick(?) using polyline..

and Shift Path makes it work for either one or multiple set..

Attachments:

Or you can use Group / Ungroup rather than polyline / explode..

Here is my def :

Top one makes exact circles for your points :

Bottom one makes approximated circle for any curve :

Sad to say, but nothing comes to my mind about how to make exact circle for any curve...

EDIT : We discussed here some time ago about medial axis (this is directly related topic), but no one made an exact representation of it - I searched for some papers, but nothing found.

To make it more accurate for polylines - add polyline points to delaunay triangulation... There are some intersections at corners (concave polylines), this will eliminate them.

Hey Mateusz,

Do you mind posting your solution file? I'm not sure what is the expression you've used in your definition.

Thanks,

Ali

Expression is  If(x=1,1,0)  because containment component outputs 1 if something is in curve, 0 if is coincidend and 2 if its outside.

• View All