Find the largest circle that fits in a planar curve: can this be faster and more precise?

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:


Largest Circle In Closed Curve.gh (49.2 KB)

Here are my questions:

  1. 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)
  2. 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?
2 Likes

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.

I was hoping for something that also works with degree N curves and polycurves.

…actually, could there be a Kangaroo method for this? Like just inflate a circle until it can’t go any further?

I was thinking (and trying) the same thing:


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…

This is the “roof generator” all over again…

1 Like

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.

Is there a kangaroo based way? Like, just inflate a circle until it can’t go any further? Not faster, but maybe more precise? And fun to watch?

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

1 Like

… maybe even single closed/periodic curves?

Make as you did, delanuay, extract 3 small curve fragments near biggest triangle vertexes, do tan-tan-tan circle.

Difficult to think of a fast method if degree >1 curves are involved XD.

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.

2 Likes

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!

…actually it looks like it won’t work for my original input, presumably due to multiple curves on different planes.

Advice on how I might fix that? It looks like it’s a planes issue, not just a tree issue.Largest Circle In Closed Curve2_re.gh (27.3 KB)

There was a tree issue, but also the planes at the end need to be oriented for each of the curves:
orientedcircs.gh (20.0 KB)

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.

1 Like

Just ran the solution above on a 60 face geodesic icosahedron and multipiped it. Handy.

1 Like

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

the bigger the offset gets, the more “offsets of original sides” get excluded by themselves because not part of the inside region anymore:

unless any 3 sides of the original curve are parallel, by increasing the offset we will get a triangle at a certain point… sometimes a very small one:

the bisectors of that triangle find a perfect center

time to sleep :slight_smile:

2 Likes

Seems like a non-convex polygon wouldn’t work.

ahhhh I understand what you mean, in cases like this where the circle is tangent to a “ghost edge”

I KNEW I had to go to sleep earlier :slight_smile: