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

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:

circle.gh (23.7 KB)

For a convex polygon K there is a classic solution the Chebyshev center.
The solution is a linear optimization problem with linear inequality constraints.
Let the m-gon K be represented by the m inequalities a_i \cdot x<=b_i, where a_i is the 2d unit vector that is the outward normal of an edge of K. The variables of the optimization problem are the coordinates of the circle (x1, x2) and the radius r. The objective is to maximize r subject to a_i \cdot x +r <= b_i

3 Likes

Some time ago I also implemented this one by translating C++ to C# for OpenNest, works nice even if it is not fully touching all the sides:



For me this was needed to find a good placement of a label, since it was rarely a medial center of points.

2 Likes
1 Like