Using a method featured in many other scripts, relying on delaunay mesh and face circles, here’s a little definition (and cluster below) that finds the largest circle that can fit inside a closed planar curve. Unfortunately, it isn’t totally precise, and it can get pretty slow when dealing with a lot of curves.
This method also can create circles that go a little bit outside the input curve, so I added a few components at the end to ensure the result stayed inside. Definition below:
Is there a less processor intensive way to do this? (And I don’t mean by using fewer curve divisions to feed the Delaunay Mesh component)
Is there a way to make this more precise? Meaning, is there a way to make sure that if the largest circle that can fit is tangent to two or three segments of the input curve, that this will be the circle that gets created?
The largest circle will always be centred on one of the interior vertices of the medial axis of the curve.
Assuming we are dealing only with planar polygons, I think you could take all the bisectors between consecutive segments, then intersect each of these with the next one around, discard the intersection points which end up outside the polygon, and find the furthest from the curve of the remaining ones.
edit - scratch that - Thinking a little more - I believe it will be centred on a vertex of the medial axis, but this won’t necessarily be one of the points of it we can find simply as a bisector.
Circle and center (black dot) from Max original definition.
This would need the bisector of consecutive segments for simple quads, but also the bisector of i <> i+2 for more number of sides… and so on…
I believe the part about it lying on a vertex of the medial axis still holds, so as @maje90 says, it does look like the ‘roof generator’ problem all over again. Perhaps there’s another way that avoids doing the full medial axis calculation though.
Yes, I think it probably is solvable with Kangaroo, but I feel like there’s got to be a fast way to get an accurate solution here without resorting to an iterative method. (Of course I love iterative methods, but only for things where there’s no alternative, or it makes more sense).
That had occurred to me as a possibility but wouldn’t it fail if the curvature in the extracted segment is wrong and won’t work for tan-tan-tan? (For polylines, this would work well though)
For polylines this seems to work for an exact solution: Largest Circle In Closed Curve2.gh (20.7 KB)
It takes bisectors of all pairs of segments of the polyline, not just consecutive ones, then gets all the intersection points of these, and finds the one which is inside and farthest from the curve.
This works great and quick for polyhedra faces. And I couldn’t break it with complicated non-convex polycurves. It does slow down exponentially as the number of segments gets high - 26 segments took about a 1.5 seconds. But for applications like filling voronoi cells and polyhedra faces with circles this is a great solution!
Awesome. Thanks. Checking this as the “solution” because it solves the problem completely for many (most likely) applications, even if it’s not a holy grail that works for all curve types.
Now to go through it piece by piece to learn how all the components actually work. I get the concept, in terms of logic and geometry, but there are components here I’ve never used and am not fully familiar with.
It’s an interesting challenge. For sure this checking of all with all is rather brute force. Better ways of getting a fast exact medial axis would be nice.
I was thinking too, it could be interesting to try optimising not just to find the circle centers, but to actually adjust the faces so that each one has all its sides tangent to a circle. I think it should be doable with the EqualAngles goal.
I have this weird late-night thought: can’t we just offset inwards the curves until they form a triangle, and then just calculate the medial axis of that triangle?
theoretically, by just offsetting inwards the sides of the polygon, we will get a boundary that becomes smaller and smaller
