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

Replies to This Discussion

Permalink Reply by Ali Nayeri on June 10, 2012 at 10:07am

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.

Permalink Reply by Ali Nayeri on June 10, 2012 at 3:43pm

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:

Permalink Reply by Yoann Mescam (Systemiq) on June 10, 2012 at 3:54pm

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:

MaxInscrCircGalapagos.gh, 10 KB

Permalink Reply by Ali Nayeri on June 10, 2012 at 4:25pm

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:

curve_test.3dm, 23 KB
gen_max_circle_curve_test.gh, 8 KB

Permalink Reply by Yoann Mescam (Systemiq) on June 11, 2012 at 9:19am

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).

Permalink Reply by Ali Nayeri on June 10, 2012 at 4:05pm

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:

max_circle.3dm, 35 KB
gen_max_circle_2.gh, 11 KB

Permalink Reply by Jissi Choi on June 10, 2012 at 11:25pm

Here is a trick(?) using polyline..

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

Attachments:

gen_max_circle_2_polyline.gh, 13 KB

Permalink Reply by Jissi Choi on June 11, 2012 at 1:14am

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

Permalink Reply by Mateusz Zwierzycki on June 11, 2012 at 9:18am

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.

Permalink Reply by Mateusz Zwierzycki on June 11, 2012 at 9:32am

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.

Permalink Reply by Ali Nayeri on June 11, 2012 at 11:03am

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

Permalink Reply by Mateusz Zwierzycki on June 11, 2012 at 11:08am

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.